Quantum Supremacy through the Quantum Approximate Optimization Algorithm

Abstract

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.

23 pages. v2 fixes bug in section 4. Results unchanged

References in corpus (8)

• Quantum Computing
• A Quantum Approximate Optimization Algorithm
• Quantum computing and the entanglement frontier
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• The complexity of simulating constant-depth BosonSampling
• Computational Complexity of Some Quantum Theories in $1+1$ Dimensions

Cited by in corpus (109)

• Adiabatic Quantum Computing
• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Quantum Computational Supremacy
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum advantage with shallow circuits
• A generative modeling approach for benchmarking and training shallow quantum circuits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Strawberry Fields: A Software Platform for Photonic Quantum Computing
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Towards a Distributed Quantum Computing Ecosystem
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Quantum advantage with noisy shallow circuits in 3D
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Variational Quantum algorithm for Poisson equation
• Filtering variational quantum algorithms for combinatorial optimization
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
• Optimized Compilation of Aggregated Instructions for Realistic Quantum Computers
• Parameter Concentration in Quantum Approximate Optimization
• Quantum Algorithms for Fixed Qubit Architectures
• A case study of variational quantum algorithms for a job shop scheduling problem
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Quantum approximate optimization is computationally universal
• Genome assembly using quantum and quantum-inspired annealing
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Storing quantum information in spins and high-sensitivity ESR
• Network Community Detection On Small Quantum Computers
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Quantum walk-based portfolio optimisation
• Training Optimization for Gate-Model Quantum Neural Networks
• qTorch: The Quantum Tensor Contraction Handler
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Quantum Computing: An Overview Across the System Stack
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Experimental quantum advantage with quantum coupon collector
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Evaluation of QAOA based on the approximation ratio of individual samples
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• Quantum semi-supervised generative adversarial network for enhanced data classification
• Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
• Learning Unitaries by Gradient Descent
• Ultrafast Variational Simulation of Non-trivial Quantum States with Long Range Interactions
• Comparison of QAOA with Quantum and Simulated Annealing
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computers
• Community Detection Across Emerging Quantum Architectures
• Analytical Framework for Quantum Alternating Operator Ansätze
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Approaches to Constrained Quantum Approximate Optimization
• A review of Quantum Neural Networks: Methods, Models, Dilemma
• Quantum computing critical exponents
• Experimental demonstration of quantum advantage for NP verification with limited information
• Average-Case Quantum Advantage with Shallow Circuits
• What do QAOA energies reveal about graphs?
• Hybrid quantum variational algorithm for simulating open quantum systems with near-term devices
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Effects of Cosine Tapering Window on Quantum Phase Estimation
• Hamiltonian sparsification and gap-simulations
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• On the Need for Large Quantum Depth
• Quantum Amplitude Estimation in the Presence of Noise
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Coarse grained intermolecular interactions on quantum processors
• Hückel Molecular Orbital Theory on a Quantum Computer: A Scalable System-Agnostic Variational Implementation with Compact Encoding
• Progress towards analytically optimal angles in quantum approximate optimisation
• Complexity Classification of Conjugated Clifford Circuits
• Robust and Resource-Efficient Quantum Circuit Approximation
• Forbidden subspaces for level-1 QAOA and IQP circuits
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Graph Cut Segmentation Methods Revisited with a Quantum Algorithm
• Entanglement Scaling in Quantum Advantage Benchmarks
• A Classically Efficient Quantum Scalable Fermi-Hubbard Benchmark
• Quantum-Assisted Clustering Algorithms for NISQ-Era Devices
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• Importance of Diagonal Gates in Tensor Network Simulations
• Quantum mean value approximator for hard integer value problems
• Input Redundancy for Parameterized Quantum Circuits
• Realization of arbitrary doubly-controlled quantum phase gates
• HybridQ: A Hybrid Simulator for Quantum Circuits
• Test of Quantumness with Small-Depth Quantum Circuits
• Normalized Gradient Descent for Variational Quantum Algorithms
• A practical guide for building superconducting quantum devices
• Quantum Adiabatic Theorem Revisited
• Syndrome decoding by quantum approximate optimization
• Computability and Complexity of Unconventional Computing Devices
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
• Bayesian machine learning for Boltzmann machine in quantum-enhanced feature spaces
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem
• Electron cloud design for Rydberg multi-qubit gates
• Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm
• Topological and geometric patterns in optimal bang-bang protocols for variational quantum algorithms: application to the $XXZ$ model on the square lattice
• Quantum optimisation via maximally amplified states
• AccQOC: Accelerating Quantum Optimal Control Based Pulse Generation
• An Analysis of the Quantum Approximation Optimisation Algorithm
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation
• Optimized fermionic SWAP networks with equivalent circuit averaging for QAOA
• A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing