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.
 Award ID(s):
 1818914
 NSFPAR ID:
 10339345
 Date Published:
 Journal Name:
 ArXivorg
 ISSN:
 23318422
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from \cite{DMRF22}; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form e ι H ( p ) ⋯ e ι H ( 1 )  ψ 0 ⟩ for any n qubit product state  ψ 0 ⟩ , where each H ( i ) can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits. Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates.An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at superconstant level p = o ( log log n ) , assuming a strengthened version of the socalled overlap gap property. This gives the first limitations on the QAOA on dense instances at superconstant level, improving upon the recent result [BGMZ22].more » « less

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with stateoftheart classical solvers Gurobi and MQLib to solve the MaxCut problem on 3regular graphs. We identify the minimum noiseless sampling frequency and depthmore » « less
p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing highquality approximate solutions in linear time complexity. In order to match this quality for large graph sizesN , a quantum device must support depthp > 11. Additionally, multishot QAOA is not efficient on large graphs, indicating that QAOAp ≤ 11 does not scale withN . These results limit achieving quantum advantage for QAOA MaxCut on 3regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3SAT, may be better suited for achieving quantum advantage on nearterm quantum devices. 
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 present O(log logn)round algorithms in the Massively Parallel Computation (MPC) model, with ˜O(n) memory per machine, that compute a maximal independent set, a 1 + ε approximation of maximum matching, and a 2 + ε approximation of minimum vertex cover, for any nvertex graph and any constant ε > 0. These improve the state of the art as follows: • Our MIS algorithm leads to a simple O(log log Δ)round MIS algorithm in the CONGESTEDCLIQUE model of distributed computing, which improves on the ˜O (plog Δ)round algorithm of Ghaffari [PODC’17]. • OurO(log logn)round (1+ε)approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2 logn)round (1 + ε)approximation algorithm of Czumaj et al. [STOC’18] and O(log logn)round (1 + ε) approximation algorithm of Assadi et al. [arXiv’17]. • Our O(log logn)round (2+ε)approximate minimum vertex cover algorithm improves on an O(log logn)round O(1) approximation of Assadi et al. [arXiv’17].more » « less