TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Sat, 03 Dec 2022 19:37:20 GMT2022-12-03T19:37:20Z5031Training variational quantum algorithms Is NP-hardhttp://hdl.handle.net/11420/13620Title: Training variational quantum algorithms Is NP-hard
Authors: Bittel, Lennart; Kliesch, Martin
Abstract: Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.
Fri, 17 Sep 2021 00:00:00 GMThttp://hdl.handle.net/11420/136202021-09-17T00:00:00ZFast gradient estimation for variational quantum algorithmshttp://hdl.handle.net/11420/14133Title: Fast gradient estimation for variational quantum algorithms
Authors: Bittel, Lennart; Watty, Jens; Kliesch, Martin
Abstract: Many optimization methods for training variational quantum algorithms are based on estimating gradients of the cost function. Due to the statistical nature of quantum measurements, this estimation requires many circuit evaluations, which is a crucial bottleneck of the whole approach. We propose a new gradient estimation method to mitigate this measurement challenge and reduce the required measurement rounds. Within a Bayesian framework and based on the generalized parameter shift rule, we use prior information about the circuit to find an estimation strategy that minimizes expected statistical and systematic errors simultaneously. We demonstrate that this approach can significantly outperform traditional gradient estimation methods, reducing the required measurement rounds by up to an order of magnitude for a common QAOA setup. Our analysis also shows that an estimation via finite differences can outperform the parameter shift rule in terms of gradient accuracy for small and moderate measurement budgets.
Wed, 12 Oct 2022 00:00:00 GMThttp://hdl.handle.net/11420/141332022-10-12T00:00:00ZScalable approach to many-body localization via quantum datahttp://hdl.handle.net/11420/14162Title: Scalable approach to many-body localization via quantum data
Authors: Gresch, Alexander; Bittel, Lennart; Kliesch, Martin
Abstract: We are interested in how quantum data can allow for practical solutions to otherwise difficult computational problems. A notoriously difficult phenomenon from quantum many-body physics is the emergence of many-body localization (MBL). So far, is has evaded a comprehensive analysis. In particular, numerical studies are challenged by the exponential growth of the Hilbert space dimension. As many of these studies rely on exact diagonalization of the system's Hamiltonian, only small system sizes are accessible. In this work, we propose a highly flexible neural network based learning approach that, once given training data, circumvents any computationally expensive step. In this way, we can efficiently estimate common indicators of MBL such as the adjacent gap ratio or entropic quantities. Our estimator can be trained on data from various system sizes at once which grants the ability to extrapolate from smaller to larger ones. Moreover, using transfer learning we show that already a two-dimensional feature vector is sufficient to obtain several different indicators at various energy densities at once. We hope that our approach can be applied to large-scale quantum experiments to provide new insights into quantum many-body physics.
Thu, 17 Feb 2022 00:00:00 GMThttp://hdl.handle.net/11420/141622022-02-17T00:00:00Z