Reachability Deficits in Quantum Approximate Optimization
arXiv:1906.11259 · doi:10.1103/PhysRevLett.124.090504
Abstract
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithms ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratiothis problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such persist even in the absence of barren plateaus [McClean et al., 2018] and are outside of the recently reported level-1 QAOA limitations [Hastings 2019]. These findings are among the first to determine strong limitations on variational quantum approximate optimization.
arXiv commentfeedback welcome; 8 pages; 4 composite figures; RevTeX
References in corpus (15)
- A variational eigenvalue solver on a quantum processor
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Barren plateaus in quantum neural network training landscapes
- A Quantum Approximate Optimization Algorithm
- Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
- Demonstration of a small programmable quantum computer with atomic qubits
- Digitized adiabatic quantum computing with a superconducting circuit
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- Variationally Learning Grover's Quantum Search Algorithm
- Ground State Spin Logic
- Classical and Quantum Bounded Depth Approximation Algorithms
Cited by in corpus (100)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Noise-Induced Barren Plateaus in Variational Quantum Algorithms
- Quantum algorithms for quantum chemistry and quantum materials science
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Quantum Computing for Finance: State of the Art and Future Prospects
- Quantum simulation and computing with Rydberg-interacting qubits
- Warm-starting quantum optimization
- Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
- Barren Plateaus in Variational Quantum Computing
- Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
- Emerging quantum computing algorithms for quantum chemistry
- Differentiable Quantum Architecture Search
- Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- On barren plateaus and cost function locality in variational quantum algorithms
- Parameter Concentration in Quantum Approximate Optimization
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
- Universal Variational Quantum Computation
- Neural Predictor based Quantum Architecture Search
- On the Universality of the Quantum Approximate Optimization Algorithm
- Machine Learning Phase Transitions with a Quantum Processor
- Variational Quantum Eigensolver for Frustrated Quantum Systems
- Error mitigation for variational quantum algorithms through mid-circuit measurements
- Empirical performance bounds for quantum approximate optimization
- The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
- Graph neural network initialisation of quantum approximate optimisation
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Training Saturation in Layerwise Quantum Approximate Optimisation
- Error propagation in NISQ devices for solving classical optimization problems
- Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
- Quantum optimization via four-body Rydberg gates
- Low depth mechanisms for quantum optimization
- To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
- Towards large-scale quantum optimization solvers with few qubits
- Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
- Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
- Quantum Architecture Search with Meta-learning
- Scaling Quantum Approximate Optimization on Near-term Hardware
- GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
- An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
- Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
- Quantum Computational Phase Transition in Combinatorial Problems
- Hamiltonian operator approximation for energy measurement and ground state preparation
- Sampling on NISQ Devices: "Who's the Fairest One of All?"
- Analytical Framework for Quantum Alternating Operator Ansätze
- Approximating the quantum approximate optimization algorithm with digital-analog interactions
- Reachability Deficits in Quantum Approximate Optimization of Graph Problems
- On Circuit Depth Scaling For Quantum Approximate Optimization
- Threshold-Based Quantum Optimization
- Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
- A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem
- Quantum Machine Learning Tensor Network States
- HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
- Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
- Variational Simulation of Schwinger's Hamiltonian with Polarisation Qubits
- Certified variational quantum algorithms for eigenstate preparation
- Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
- Transfer learning of optimal QAOA parameters in combinatorial optimization
- The Quantum Alternating Operator Ansatz for Satisfiability Problems
- Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
- Pauli path simulations of noisy quantum circuits beyond average case
- Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
- Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
- Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
- Progress towards analytically optimal angles in quantum approximate optimisation
- Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
- Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
- Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
- Variational quantum computing for quantum simulation: principles, implementations, and challenges
- Ion native variational ansatz for quantum approximate optimization
- Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
- Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
- Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
- Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
- A Comprehensive Cross-Model Framework for Benchmarking the Performance of Quantum Hamiltonian Simulations
- Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
- Modelling noise in global Molmer-Sorensen interactions applied to quantum approximate optimization
- Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
- Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
- Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
- A quantum algorithm to count weighted ground states of classical spin Hamiltonians
- Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
- The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
- Noise tailoring for Robust Amplitude Estimation
- Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
- A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
- qLEET: Visualizing Loss Landscapes, Expressibility, Entangling Power and Training Trajectories for Parameterized Quantum Circuits
- Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
- Syndrome decoding by quantum approximate optimization
- Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
- Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
- Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
- QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
- Quantum-Assisted Graph Clustering and Quadratic Unconstrained D-ary Optimisation
- Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems
- Role of overparametrization in quantum approximate optimization
- Decoded Quantum Interferometry Under Noise
- A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating
- Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems