Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem

Abstract

The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.

Journal-accepted version

References in corpus (40)

• Quantum Amplitude Amplification and Estimation
• Tight bounds on quantum searching
• Demonstration of the trapped-ion quantum-CCD computer architecture
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• A Race Track Trapped-Ion Quantum Processor
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Improving Variational Quantum Optimization using CVaR
• Quantum Simulations of Classical Annealing Processes
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Speed-up via Quantum Sampling
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Multistart Methods for Quantum Approximate Optimization
• Exhaustive search for low autocorrelation binary sequences
• Quantum SDP-Solvers: Better upper and lower bounds
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Quantum speedup of branch-and-bound algorithms
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Low Autocorrelation Binary Sequences
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Evaluation of QAOA based on the approximation ratio of individual samples
• Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Landscape statistics of the low autocorrelated binary string problem
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Fast Simulation of High-Depth QAOA Circuits
• On the ground states of the Bernasconi model
• Extended flag gadgets for low-overhead circuit verification
• Fast Quantum Methods for Optimization
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Characterizing Error Mitigation by Symmetry Verification in QAOA
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• On the Generation of Long Binary Sequences with Record-Breaking PSL Values

Cited by in corpus (53)

• Challenges and Opportunities in Quantum Optimization
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Constrained Optimization via Quantum Zeno Dynamics
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Certified randomness using a trapped-ion quantum processor
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Optimization by Decoded Quantum Interferometry
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Performance Analysis of Multi-Angle QAOA for p > 1
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Universal Resources for QAOA and Quantum Annealing
• Detecting Errors in a Quantum Network with Pauli Checks
• Quantum Annealing with chaotic driver Hamiltonians
• Harnessing Quantum Computing for Energy Materials: Opportunities and Challenges
• Optimization via Quantum Preconditioning
• Path Matters: Industrial Data Meet Quantum Optimization
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Exact Quantum Algorithm for Unit Commitment Optimization based on Partially Connected Quantum Neural Networks
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Quantum Circuit Design for Decoded Quantum Interferometry
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• Dual-Step Optimization for Binary Sequences with High Merit Factors
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
• Qubit-efficient quantum combinatorial optimization solver
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem
• iSwitch: QEC on Demand via In-Situ Encoding of Bare Qubits for Ion Trap Architectures
• Quantum circuit evolutionary framework applied on set partitioning problem
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization
• Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems