A Quantum Approximate Optimization Algorithm

By Edward Farhi, Jeffrey Goldstone, Sam Gutmann. 2014

4,436 citations recorded by the source corpus.

We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

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

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 Atomic and Molecular Physics, and Optics

Citations in the corpus

Quantum error mitigation (2022, background): “Motivating examples include variational quantum circuits in physics simulations (McClean et al. , 2016; Peruzzo et al. , 2014; Wecker et al. , 2015), approximate optimisation algorithms (Farhi et al. , 2014), and even heuristic algorithms for quantum machine learning (Biamonte et al. , 2017).”
The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size (2019, methodology): “(58) Here we label the 2p + 1 strings as z([1]), z([2]), .”
QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits (2021, methodology): “The variational method has shown huge potentials in applications such as quantum machine learning [4], [7], [56], [63], numerical analysis [37], [39], quantum simulation [30], [31], [52], and optimizations [18], [47].”
Quantum machine learning (2016, positive): “The quantum approximate optimization algorithm (QAOA, or QAO algorithm) [50] provides a unique approach to optimization based on alternating qubit rotations with the application of the problem’s penalty function.”
Benchmarking an 11-qubit quantum computer (2019, background): “Universal quantum computing offers efficiency in approaching problems of scientific and commercial interest, such as factoring large numbers,[1] searching databases,[2] simulating intractable models from quantum physics,[3] and optimizing complex cost functions.[4] Here, we present an 11qubit fully-”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, background): “In modern quantum computing research, the design and implementation of quantum approximate optimization algorithms (QAOAs) are of great interest [177], [178].”
Quantum Machine Learning for 6G Communication Networks: State-of-the-Art and Vision for the Future (2019, methodology): “In this regard, a quantum approximate optimization algorithm based on alternating qubit rotations for penalty function problems has been proposed in [201].”
Warm-starting quantum optimization (2020, methodology): “[16] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “A quantum approximate optimization algorithm,” (2014), arXiv:1411.”
Simulating Large Quantum Circuits on a Small Quantum Computer. (2019, methodology): “…is a variational method for ﬁnding the lowest eigenvalue of an n -qubit Hamiltonian H by applying some parameterized circuit U ( θ ) to | 0 ⊗ n and minimizing the expectation with H : ( This method has many applications, such as in quantum chemistry [30, 32] and combinatorial optimization [5].”
Evaluating analytic gradients on quantum hardware (2018, background): “Examples of such algorithms are variational quantum eigensolvers [1], quantum approximate optimization [2], variational autoencoders [3], quantum feature embeddings [4, 5] and variational classifiers [6, 7], but also more general hybrid optimization frameworks [8].”
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].”
Diagnosing Barren Plateaus with Tools from Quantum Optimal Control (2021, methodology): “Here, p is the order of the discretized adiabatic transformation and it determines the precision of the solution [19].”
Quantum computing for energy systems optimization: Challenges and opportunities (2019, methodology): “Approximate solutions for combinatorial optimization problems can be produced by Quantum Approximate Optimization Algorithm (QAOA) [30].”
Rydberg atom quantum technologies (2019, methodology): “strated using Rydberg arrays, and a robust algorithm for preparing atoms in the ground state through either quantum annealing [94{96] or variational quantum approximate optimisation algorithms (QAOA) [97] using a classical optimiser to drive the parameters controlling the quantum hardware. Recent st”
Towards quantum machine learning with tensor networks (2018, background): “Our approach is therefore conceptually related to the quantum variational eigensolver [23, 24] and to the quantum approximate optimization algorithms [25], where quantum circuit parameters are discovered with the help of an auxiliary classical algorithm.”
Error mitigation with Clifford quantum-circuit data (2020, methodology): “Here we illustrate this application with the Quantum Alternating Operator Ansatz (QAOA) [4, 5], which can serve as an ansatz for Hamiltonian ground states.”