Quantum Computational Phase Transition in Combinatorial Problems

Abstract

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that $BQP\ne NP$, it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT -- random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithm lies. Then, we show that the high problem density region, which limits QAOA's performance in hard optimization problems ({\it reachability deficits}), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

arXiv comment14 pages, 12 figures

References in corpus (26)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Ising formulations of many NP problems
• Barren plateaus in quantum neural network training landscapes
• QuTiP: An open-source Python framework for the dynamics of open quantum systems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Adiabatic Quantum Computing
• Strong quantum computational advantage using a superconducting quantum processor
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Operator Spreading in Random Unitary Circuits
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Chaos and complexity by design
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• First order phase transition in the Quantum Adiabatic Algorithm
• Theory of overparametrization in quantum neural networks
• Reachability Deficits in Quantum Approximate Optimization
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Scrambling and Complexity in Phase Space
• Symmetries on Spin Chains: Limited Controllability and Minimal Controls for Full Controllability
• Improved Error Bounds for the Adiabatic Approximation
• Controllability of Symmetric Spin Networks
• The Phase Transition in Exact Cover

Cited by in corpus (15)

• Barren Plateaus in Variational Quantum Computing
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• Building spatial symmetries into parameterized quantum circuits for faster training
• Probing quantum complexity via universal saturation of stabilizer entropies
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Energy-dependent barren plateau in bosonic variational quantum circuits
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• A Comprehensive Cross-Model Framework for Benchmarking the Performance of Quantum Hamiltonian Simulations
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Quantum Inception Score
• Information scrambling and entanglement in quantum approximate optimization algorithm circuits
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems