The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers
p
. While ...QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of
n
spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within
(
1
−
ϵ
)
times the ground state energy. We hope to match its performance with the QAOA.Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the
2
p
QAOA parameters, in the infinite size limit that can be evaluated on a computer with
O
(
16
p
)
complexity. We evaluate the formula up to
p
=
12
, and find that the QAOA at
p
=
11
outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as
n
→
∞
, measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of ...algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
Spatial search by quantum walk Childs, Andrew M.; Goldstone, Jeffrey
Physical review. A, Atomic, molecular, and optical physics,
08/2004, Letnik:
70, Številka:
2
Journal Article
Odprti dostop
Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a ...database of N items laid out in d spatial dimensions can be searched in time of order {radical}(N) for d>2, and in time of order {radical}(N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that {radical}(N) speedup can also be achieved on the hypercube. We show that full {radical}(N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order {radical}(N) poly(log N), and in d<4, the algorithm does not provide substantial speedup.
A Quantum Monte Carlo method at fixed energy Farhi, Edward; Goldstone, Jeffrey; Gosset, David ...
Computer physics communications,
08/2011, Letnik:
182, Številka:
8
Journal Article
Recenzirano
Odprti dostop
In this paper we explore ways to study the zero temperature limit of quantum statistical mechanics using Quantum Monte Carlo simulations. We develop a Quantum Monte Carlo method in which one fixes ...the ground state energy as a parameter. The Hamiltonians we consider are of the form H=H0+λV with ground state energy E. For fixed H0 and V, one can view E as a function of λ whereas we view λ as a function of E. We fix E and define a path integral Quantum Monte Carlo method in which a path makes no reference to the times (discrete or continuous) at which transitions occur between states. For fixed E we can determine λ(E) and other ground state properties of H.
► A Quantum Monte Carlo method where the ground state energy is an input parameter. ► Properties of the ground state are computed at fixed energy. ► Method is numerically tested on a small transverse field spin system.
The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers \(p\). While ...QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of \(n\) spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within \((1-\epsilon)\) times the ground state energy. We hope to match its performance with the QAOA. Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the \(2p\) QAOA parameters, in the infinite size limit that can be evaluated on a computer with \(O(16^p)\) complexity. We evaluate the formula up to \(p=12\), and find that the QAOA at \(p=11\) outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as \(n\to\infty\), measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.
Spatial search and the Dirac equation Childs, Andrew M.; Goldstone, Jeffrey
Physical review. A, Atomic, molecular, and optical physics,
10/2004, Letnik:
70, Številka:
4
Journal Article
Odprti dostop
We consider the problem of searching a d-dimensional lattice of N sites for a single marked location. We present a Hamiltonian that solves this problem in time of order {radical}(N) for d>2 and of ...order {radical}(N) log N in the critical dimension d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.
PDF
