Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with nearterm quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that boundederror quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SATUNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.
 Publication Date:
 NSFPAR ID:
 10381676
 Journal Name:
 npj Quantum Information
 Volume:
 8
 Issue:
 1
 ISSN:
 20566387
 Publisher:
 Nature Publishing Group
 Sponsoring Org:
 National Science Foundation
More Like this

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum manybody systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a lowdepth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the groundstate energy of the Transverse Field Ising Model with longrange interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with highfidelity, singleshot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closedloop optimization of the variational parameters, approximating the groundstate energy with up to 40 trappedion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ( P H ) does not collapse, a stronger version of the statement that P ≠ N P , which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing finegrained versions of the noncollapse conjecture. Our first two conjectures poly3NSETH( a ) and perintNSETH( b ) take specific classical counting problems related to the number of zeros of a degree3 polynomial in n variables over F 2 or the permanent of an n × n integervalued matrix, and assert that any nondeterministic algorithm that solves them requires 2 c nmore »

Abstract Realizing the potential of nearterm quantum computers to solve industryrelevant constrainedoptimization problems is a promising path to quantum advantage. In this work, we consider the extractive summarization constrainedoptimization problem and demonstrate the largesttodate execution of a quantum optimization algorithm that natively preserves constraints on quantum hardware. We report results with the Quantum Alternating Operator Ansatz algorithm with a Hammingweightpreserving XY mixer (XYQAOA) on trappedion quantum computer. We successfully execute XYQAOA circuits that restrict the quantum evolution to the inconstraint subspace, using up to 20 qubits and a twoqubit gate depth of up to 159. We demonstrate the necessity of directly encoding the constraints into the quantum circuit by showing the tradeoff between the inconstraint probability and the quality of the solution that is implicit if unconstrained quantum optimization methods are used. We show that this tradeoff makes choosing good parameters difficult in general. We compare XYQAOA to the Layer Variational Quantum Eigensolver algorithm, which has a highly expressive constantdepth circuit, and the Quantum Approximate Optimization Algorithm. We discuss the respective tradeoffs of the algorithms and implications for their execution on nearterm quantum hardware.

We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph{quantum} algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019] we then show limitations of generic local algorithms including QAOA on random instances of constraint satisfaction problems (CSPs). Specifically, we show that any generic local algorithm whose assignment to a vertex depends only on a local neighborhood with o(n) other vertices (such as the QAOA at depth less than ϵlog(n)) cannot arbitrarilywell approximate boolean CSPs if the problem satisfies a geometric property from statistical physics called the coupled overlapgap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random MAXkXOR problem has this property when k≥4 is even by extending the corresponding result for diluted kspin glasses. Our concentration lemmas confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth  in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. One of these concentration lemmas ismore »

The quantum approximate optimization algorithm (QAOA) is a nearterm hybrid algorithm intended to solve combinatorial optimization problems, such as MaxCut. QAOA can be made to mimic an adiabatic schedule, and in the p → ∞ limit the final state is an exact maximal eigenstate in accordance with the adiabatic theorem. In this work, the connection between QAOA and adiabaticity is made explicit by inspecting the regime of p large but finite. By connecting QAOA to counterdiabatic (CD) evolution, we construct CDQAOA angles which mimic a counterdiabatic schedule by matching Trotter "error" terms to approximate adiabatic gauge potentials which suppress diabatic excitations arising from finite ramp speed. In our construction, these "error" terms are helpful, not detrimental, to QAOA. Using this matching to link QAOA with quantum adiabatic algorithms (QAA), we show that the approximation ratio converges to one at least as 1 − C ( p ) ∼ 1 / p μ . We show that transfer of parameters between graphs, and interpolating angles for p + 1 given p are both natural byproducts of CDQAOA matching. Optimization of CDQAOA angles is equivalent to optimizing a continuous adiabatic schedule. Finally, we show that, using a property of variational adiabatic gaugemore »