Source-linked AI summary
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
Edward Farhi, Aram W Harrow
TL;DR
The paper asks whether shallow quantum optimization circuits can be classically simulated despite their potential computational value. It analyzes QAOA and QADI using complexity-theoretic arguments, concluding that efficient sampling from p = 1 QAOA would collapse the Polynomial Hierarchy, whereas stoquastic gapped QADI is more classically simulable under its stated conditions.
Problem
The paper examines whether the output distribution of shallow QAOA can be efficiently reproduced classically, a question relevant to assessing quantum computational usefulness.
Method
The paper applies complexity-theoretic reductions to QAOA sampling and contrasts them with classical simulation of gapped stoquastic QADI.
Results
Efficient classical sampling from the p = 1 QAOA output would collapse the Polynomial Hierarchy.
Takeaways & Limitations
QAOA is presented as a near-term quantum-computing candidate because it combines shallow depth, optimization goals, and potential nonsimulatability.
Takeaways & Limitations
The sampling-hardness conclusion depends on reasonable or plausible complexity-theoretic assumptions, while the paper leaves additive-error hardness for p = 1 QAOA to future work.
Abstract
from arXiv · showhide
The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on a gate model quantum computer and has shallow depth. It takes as input a combinatorial optimization problem and outputs a string that satisfies a high fraction of the maximum number of clauses that can be satisfied. For certain problems the lowest depth version of the QAOA has provable performance guarantees although there exist classical algorithms that have better guarantees. Here we argue that beyond its possible computational value the QAOA can exhibit a form of Quantum Supremacy in that, based on reasonable complexity theoretic assumptions, the output distribution of even the lowest depth version cannot be efficiently simulated on any classical device. We contrast this with the case of sampling from the output of a quantum computer running the Quantum Adiabatic Algorithm (QADI) with the restriction that the Hamiltonian that governs the evolution is gapped and stoquastic. Here we show that there is an oracle that would allow sampling from the QADI but even with this oracle, if one could efficiently classically sample from the output of the QAOA, the Polynomial Hierarchy would collapse. This suggests that the QAOA is an excellent candidate to run on near term quantum computers not only because it may be of use for optimization but also because of its potential as a route to establishing quantum supremacy.
1 Introduction
The paper motivates quantum supremacy through the difficulty of classically simulating quantum amplitudes and measurement distributions, focusing on shallow QAOA circuits and contrasting them with QADI.
- Motivation: Generic n-qubit states require 2^n complex amplitudes, making direct classical representation infeasible for sufficiently large n.The paper frames amplitude computation and sampling as possible forms of quantum simulation.
- Motivation: No methods are known that compute amplitudes or sample efficiently for all quantum systems.Problem-specific techniques can make simulation efficient in selected cases.
- QAOA: QAOA is a family of shallow quantum circuits intended to find good solutions to optimization problems.The paper investigates whether even its shallowest version is classically hard to sample from.
- QAOA: The paper argues that sampling the lowest-depth QAOA output is difficult for complexity-theoretic reasons and may support quantum supremacy.QAOA may also provide approximate combinatorial solutions, although the paper presents nonsimulatability as a separate value.
- QADI contrast: For QADI, the stoquastic Hamiltonian assumption rules out applying the same quantum-supremacy arguments used for QAOA.The paper therefore contrasts the classical simulation prospects of QADI and QAOA.
2 Background
The paper introduces CSPs and QAOA as optimization frameworks, then reviews the Polynomial Hierarchy as the complexity-theoretic setting for its hardness arguments.
- Constraint satisfaction problems: A CSP consists of n bits and m constraints, with the goal of maximizing or approximately maximizing satisfied constraints.MAX-CUT is presented as an example in which edge constraints are satisfied when endpoint bits disagree.
- Constraint satisfaction problems: CSP objectives can be represented by a cost operator C acting diagonally on computational-basis strings in a 2^n-dimensional Hilbert space.The two quantum algorithms considered use this operator framework.
- QAOA: QAOA constructs a state using angles γ and β, measures a computational-basis string, and uses a classical search to optimize the angles.For p = 1, the circuit is shallow and consists of commuting two-qubit and one-qubit components when the cost function has local terms.
- QAOA: For p = 1, the expected cost can be efficiently calculated classically for fixed γ and β, while the quantum computer can provide strings achieving the target cost.The p = 1 algorithm has provable worst-case approximation guarantees for some problems, though certain classical algorithms perform better.
- QAOA: Increasing p cannot worsen the optimized performance, and the QAOA can achieve Cmax as p approaches infinity.The p > 1 formulation uses 2p angles and increases circuit depth proportionally with p.
- Polynomial Hierarchy: The Polynomial Hierarchy is a tower beginning with P and NP whose higher levels use alternating existential and universal quantifiers over efficiently checkable predicates.The paper describes each higher level as seemingly requiring more resources than the preceding one.
- Polynomial Hierarchy: The paper treats P ≠ NP and the apparent increasing difficulty of higher hierarchy levels as complexity-theoretic assumptions underlying its arguments.A brute-force search over 2^n strings is given as the generic approach to the NP decision problem.
3 Efficient Classical Computation of Matrix Elements of Quantum Circuits Implies that P = NP
The paper connects quantum-circuit matrix elements to counting CSP solutions and then extends the argument to the lowest-depth QAOA and its output-sampling problem.
- Hardness of matrix elements: Matrix elements of CSP-based quantum circuits encode the Fourier transform of the distribution over numbers of satisfied clauses.The distribution can be reconstructed from m + 1 matrix elements using an inverse Fourier transform.
- Hardness of matrix elements: Efficiently computing these matrix elements would reveal the number of assignments satisfying all clauses, a #P-hard quantity.The paper concludes that such classical computation would contradict the assumption that P ≠ NP.
- Hardness for QAOA: A p = 1 QAOA instance with β = 0 contains the relevant matrix element, so efficiently computing it classically would imply P = NP.This specializes the general quantum-circuit argument to the lowest-depth QAOA.
- Sampling problem: The paper distinguishes computing amplitudes from sampling, since measured quantum outputs follow probabilities given by squared amplitudes.It later argues that even p = 1 QAOA output distributions cannot be faithfully reproduced classically under reasonable assumptions.
4 Post-Selected Quantum Computing
Post-selected quantum computing augments polynomial-size quantum circuits by conditioning on selected measurement outcomes, enabling powerful counting and decision procedures.
- Post-selected quantum computing: Post-selection solves the Grover search problem with one oracle call and therefore solves NP-complete problems such as 3SAT.
- State discrimination: Unambiguous state discrimination distinguishes distinct quantum states without error, sometimes returning “don’t know”; post-selection retains only definitive outcomes.For states corresponding to M=N/2 and M=N/2+1, the retained answer is correct with probability 1.
- Quantum advantage from post-selection: A Hadamard-based amplification step doubles the distance between M and N/2, while classical post-selection amplifies distances only from 0 or N.This difference supports exact counting for post-selected quantum computers but apparently not for post-selected classical computers.
- Exact counting: Post-selected quantum computing can determine the exact number M of satisfying assignments for combinatorial search problems such as 3SAT.The procedure repeatedly amplifies the difference between M and a chosen threshold.
- Post-selected quantum computing: PostBQP extends conventional quantum computing with the ability to post-select measured qubits onto chosen outcomes.It uses polynomially many qubits and gates, plus post-selection on a subset of measured qubits.
5 Efficient Classical Sampling of the Output of an Arbitrary Quantum Circuit Implies the Collapse of the Polynomial Hierarchy
The paper relates efficient classical sampling of arbitrary quantum-circuit outputs to post-selected classical simulation, which would imply equality of post-selected complexity classes and collapse the Polynomial Hierarchy.
- Sampling assumptions: For a quantum circuit U producing output distribution q(z), efficient classical sampling produces a distribution p(z) that is assumed close to q(z).The comparison applies across polynomial-size circuits and inputs.
- Post-selection: Post-selecting the same measured register in the classical sampler yields a classical post-selected distribution that can simulate the quantum post-selected distribution.
- Decision consequences: The resulting post-selected probabilities remain separated: at least 0.54 for YES instances and at most 0.41 for NO instances.
- Decision consequences: Efficient classical sampling would imply PostBQP ⊆ PostBPP, and hence PostBPP = PostBQP.
- Complexity consequence: Because PostBPP is contained in the third level of the Polynomial Hierarchy, this equality would collapse the Polynomial Hierarchy at the third level.
6 PostQAOA = PostBQP
The paper shows that post-selected QAOA at p=1 has the full power of PostBQP by replacing arbitrary circuit structure with shallow diagonal-gate constructions and post-selected gadgets.
- Relation to IQP: At p=1, QAOA has a structure related to IQP circuits, with diagonal cost unitaries and commuting one- or two-qubit terms measured in the computational basis.
- Class inclusion: QAOA is a special case of BQP, so PostQAOA is contained in PostBQP.
- Circuit reduction: A general BQP circuit can be rewritten as a post-selected QAOA circuit by replacing internal Hadamards with auxiliary-qubit gadgets.The gadget uses diagonal gates followed by measurement and post-selection.
- Circuit reduction: The construction enforces the QAOA circuit form by arranging initial Hadamards, consecutive diagonal gates, and final ˜H operations on each qubit.
- Equality of classes: The reduction preserves post-selected outputs exactly and establishes PostBQP = PostQAOA.
7 Efficient Classical Sampling of the Output of the p = 1 QAOA Implies the Collapse of the Polynomial Hierarchy
The paper applies the post-selection argument to p=1 QAOA: an efficient classical sampler with sufficiently small multiplicative error would imply a Polynomial Hierarchy collapse, while additive-error hardness remains open.
- Hardness proof: Assuming a polynomial-time randomized sampler whose output probabilities satisfy the required multiplicative-error bound, the paper derives a post-selected classical simulation of PostBQP.
- Hardness proof: The simulated post-selected probabilities are at least 0.54 for YES instances and at most 0.41 for NO instances.
- Complexity consequence: Such an efficient classical sampler would collapse the Polynomial Hierarchy through the containment of PostBPP in its third level.
- Hardness claim: The p=1 QAOA output distribution is claimed, in the worst case, to be inefficiently classically samplable.
- Sampling versus estimation: The expected QAOA cost can be calculated classically, but the output distribution used to produce strings with that cost cannot be efficiently reproduced classically.For fixed p, estimating the expected value uses resources polynomial in n and m but doubly exponential in p.
- Scope and limitation: The result rules out efficient classical sampling with low multiplicative error, whereas additive-error hardness requires additional conjectures and is left for future work.
8 Quantum Adiabatic Algorithm
The section examines classical simulation of QADI under stoquasticity and a polynomial spectral gap, showing that QADI-SG can be simulated in PostBPP while practical sampling may still take exponentially long.
- Algorithm: QADI seeks a cost-function optimum by evolving from the ground state of a driving Hamiltonian toward the ground state of −C.In the infinite-time limit, the adiabatic theorem gives the ground state of −C.
- Conditions: Stoquastic Hamiltonians have real non-positive off-diagonal elements, a restriction that supports classical simulation of ground-state properties.The Perron-Frobenius theorem guarantees a non-vanishing gap for the chosen driving Hamiltonian.
- Conditions: QADI-SG imposes stoquasticity, an inverse-polynomial gap throughout the evolution, and polynomial runtime sufficient for the adiabatic condition.The gap and runtime conditions support efficient quantum optimization, while stoquasticity is needed for classical simulation.
- Classical simulation: Quantum Monte Carlo can sample the ground-state measurement distribution by sampling a nonnegative path-integral distribution using locally computable probability ratios.The construction uses weights w(z, x) and post-selection to obtain the desired distribution.
- Limitations: This sampling approach may require exponential equilibration time, including instances where efficient sampling would solve NP-complete problems.Nevertheless, QMC simulations of QADI-SG have reached hundreds of qubits in practice.
- Complexity comparison: QADI-SG can be simulated in PostBPP, whereas efficient QAOA sampling would collapse the Polynomial Hierarchy under the paper’s complexity assumptions.A PostBPP oracle could therefore efficiently sample QADI-SG ground states without being sufficient to simulate QAOA.
9 Discussion
The discussion compares QAOA and stoquastic adiabatic computation as near-term candidates, emphasizing QAOA’s shallow-depth sampling hardness and the simulation consequences of Hamiltonian design.
- Discussion: Near-term gate-model devices should be evaluated partly by whether their outputs are difficult to reproduce classically.The choice of algorithms can influence hardware architecture and performance goals.
- Discussion: Stoquastic adiabatic systems may be easier to simulate than QAOA, motivating consideration of non-stoquastic Hamiltonians for future devices.The paper frames this as a simulation-based design consideration, even when stoquastic systems may retain computational value.
- Discussion: For p = 1 QAOA, efficient classical sampling would collapse PH, so plausible complexity assumptions imply that some outputs cannot be mimicked classically.This strengthens the case for running QAOA on near-term quantum devices.