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.
The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by ...codesigning full-stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, a sampling of a few use case studies, and significant challenges for the development of quantum computers for science over the next 2–10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21–22, 2019 in Alexandria, VA.
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.
Given a single copy of an unknown quantum state, the no-cloning theorem limits the amount of information that can be extracted from it. Given a gapped Hamiltonian, in most situations it is ...impractical to compute properties of its ground state, even though in principle all the information about the ground state is encoded in the Hamiltonian. We show in this Letter that if you know the Hamiltonian of a system and have a single copy of its ground state, you can use a quantum computer to efficiently compute its local properties. Specifically, in this scenario, we give efficient algorithms that copy small subsystems of the state and estimate the full statistics of any local measurement.
PDF
