QAOA for Max-Cut requires hundreds of qubits for quantum speed-up

Abstract

Computational quantum technologies are entering a new phase in which noisy intermediate-scale quantum computers are available, but are still too small to benefit from active error correction. Even with a finite coherence budget to invest in quantum information processing, noisy devices with about 50 qubits are expected to experimentally demonstrate quantum supremacy in the next few years. Defined in terms of artificial tasks, current proposals for quantum supremacy, even if successful, will not help to provide solutions to practical problems. Instead, we believe that future users of quantum computers are interested in actual applications and that noisy quantum devices may still provide value by approximately solving hard combinatorial problems via hybrid classical-quantum algorithms. To lower bound the size of quantum computers with practical utility, we perform realistic simulations of the Quantum Approximate Optimization Algorithm and conclude that quantum speedup will not be attainable, at least for a representative combinatorial problem, until several hundreds of qubits are available.

References in corpus (24)

• Quantum Computing in the NISQ era and beyond
• Quantum Mechanics helps in searching for a needle in a haystack
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• A Quantum Approximate Optimization Algorithm
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum annealing with more than one hundred qubits
• Scalable Quantum Simulation of Molecular Energies
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Quantum computing and the entanglement frontier
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Practical optimization for hybrid quantum-classical algorithms
• Quantum Algorithms for Fixed Qubit Architectures
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Restless Tuneup of High-Fidelity Qubit Gates
• MAX 2-SAT with up to 108 qubits
• Two-step approach to scheduling quantum circuits
• Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization
• Noise gates for decoherent quantum circuits

Cited by in corpus (109)

• Parameterized quantum circuits as machine learning models
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Computing for Finance: State of the Art and Future Prospects
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Benchmarking the Quantum Approximate Optimization Algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Intel Quantum Simulator: A cloud-ready high-performance simulator of quantum circuits
• Benchmarking the performance of portfolio optimization with QAOA
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Multistart Methods for Quantum Approximate Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Biology and medicine in the landscape of quantum advantages
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
• Efficient evaluation of quantum observables using entangled measurements
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Empirical performance bounds for quantum approximate optimization
• Network Community Detection On Small Quantum Computers
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Analyzing the Performance of Variational Quantum Factoring on a Superconducting Quantum Processor
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• Constrained mixers for the quantum approximate optimization algorithm
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Entangled multiplets and unusual spreading of quantum correlations in a continuously monitored tight-binding chain
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Towards large-scale quantum optimization solvers with few qubits
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Challenges of variational quantum optimization with measurement shot noise
• Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Evaluation of QAOA based on the approximation ratio of individual samples
• Scaling Quantum Approximate Optimization on Near-term Hardware
• An entanglement perspective on the quantum approximate optimization algorithm
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Quantum Divide and Compute: Exploring The Effect of Different Noise Sources
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Parity Quantum Optimization: Compiler
• Analytical Framework for Quantum Alternating Operator Ansätze
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Subdivided Phase Oracle for NISQ Search Algorithms
• A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem
• Topology-Driven Quantum Architecture Search Framework
• Calibrating the role of entanglement in variational quantum circuits
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
• Optimizing Counterdiabaticity by Variational Quantum Circuits
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
• Quantum Annealing for Neural Network optimization problems: a new approach via Tensor Network simulations
• What do QAOA energies reveal about graphs?
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• Robustness to spontaneous emission of a variational quantum algorithm
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Quantum Approximate Optimization Algorithm for Test Case Optimization
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Accelerating Variational Quantum Algorithms Using Circuit Concurrency
• Faster variational quantum algorithms with quantum kernel-based surrogate models
• Progress towards analytically optimal angles in quantum approximate optimisation
• Quantum-machine-assisted Drug Discovery
• Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Noise-Agnostic Quantum Error Mitigation with Data Augmented Neural Models
• Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
• Max-cut Clustering Utilizing Warm-Start QAOA and IBM Runtime
• Quantum computing for genomics: conceptual challenges and practical perspectives
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Accelerating Simulation of Quantum Circuits under Noise via Computational Reuse
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• Graph Neural Networks for Parameterized Quantum Circuits Expressibility Estimation
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• Error Analysis of the Variational Quantum Eigensolver Algorithm
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
• Exploring Airline Gate-Scheduling Optimization Using Quantum Computers
• Depth Optimized Ansatz Circuit in QAOA for Max-Cut
• From barren plateaus through fertile valleys: Conic extensions of parameterised quantum circuits
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
• Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems
• Exploring Entanglement and Parameter Sensitivity in QAOA through Quantum Fisher Information
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization
• Quantum Computation
• Quantum imaginary time evolution and UD-MIS problem
• Introductory Tutorial for SPSA and the Quantum Approximation Optimization Algorithm
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing
• Verifiable cloud-based variational quantum algorithms