Quantum Supremacy through the Quantum Approximate Optimization Algorithm

By Edward Farhi, Aram Wettroth Harrow. 2016

579 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/ff788000623a621a864cda108a2ac9b9fb855b15

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

Variational quantum algorithms (2020, background): “In general, even p = 1 QAOA ansatz cannot be efficiently simulated on any classical device [252].”
Adiabatic Quantum Computing (2016, methodology): “…along a path composed entirely of stoquastic frustration-free Hamiltonians (recall Definition 4) may be simulated by a sequence of classical random walks, i.e., is contained in BPP. 30 See also (Farhi and Harrow, 2016), where gapped StoqAQC was called stoquastic gapped adiabatic evolution, QADI-SG.”
Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices (2018, background): “Interestingly, even when restricting the number of QAOA parameters to 2q = 10, the FOURIER[5,10] strategy closely matches the performance of other heuristics at low p and beats the R = 0 heuristic at large p.”
Noise-induced barren plateaus in variational quantum algorithms (2020, methodology): “First, the end goal of certain algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) [47] is to extract an optimized set of parameters, rather than the optimal cost value.”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, methodology): “Farhi and Harrow [21] proved that, under reasonable complexity assumptions, the output distribution of even QAOA1 circuits cannot be efficiently sampled classically.”
Strawberry Fields: A Software Platform for Photonic Quantum Computing (2018, methodology): “Popular techniques include variational quantum eigensolvers [5, 6], quantum approximate optimization algorithms [7, 8], sampling from computationally hard probability distributions [9–17], and quantum annealing [18, 19].”
Ising machines as hardware solvers of combinatorial optimization problems (2022, methodology): “Then in a similar way to thermal annealing, the temperature is gradually lowered in order to obtain a low-energy state.”
Parameterized quantum circuits as machine learning models (2019, background): “Researchers have also begun to explore connections between quantum supremacy proposals and quantum algorithms for optimization [109], getting us closer to practical utility if some key requirements can bemet [110–112].”