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.

14 pages, 12 figures

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• 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
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Theory of overparametrization in quantum neural networks
• Scrambling and Complexity in Phase Space

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