Reachability Deficits in Quantum Approximate Optimization of Graph Problems
arXiv:2007.09148 · doi:10.22331/q-2021-08-30-532
Abstract
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the \emph{density} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.
arXiv comment(feedback welcome) 11 pages; 5 composite figures
References in corpus (20)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Machine Learning
- Quantum Annealing in the Transverse Ising Model
- The theory of variational hybrid quantum-classical algorithms
- Simulated Quantum Computation of Molecular Energies
- Scalable Quantum Simulation of Molecular Energies
- Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
- Reachability Deficits in Quantum Approximate Optimization
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Quantum Machine Learning for Electronic Structure Calculations
- Benchmarking the Quantum Approximate Optimization Algorithm
- Implementation of the XY interaction family with calibration of a single pulse
- Universal Variational Quantum Computation
- On the Universality of the Quantum Approximate Optimization Algorithm
- Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
- Variationally Learning Grover's Quantum Search Algorithm
- A quantum walk assisted approximate algorithm for bounded NP optimisation problems
Cited by in corpus (15)
- Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
- Quantum optimization via four-body Rydberg gates
- Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
- An entanglement perspective on the quantum approximate optimization algorithm
- An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
- QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
- On Circuit Depth Scaling For Quantum Approximate Optimization
- An evolving objective function for improved variational quantum optimisation
- Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
- Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
- Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
- Progress towards analytically optimal angles in quantum approximate optimisation
- Ion native variational ansatz for quantum approximate optimization
- Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
- A Quantum Constraint Generation Framework for Binary Linear Programs