First-order transitions and the performance of quantum algorithms in random optimization problems

Abstract

We present a study of the phase diagram of a random optimization problem in presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the Quantum Adiabatic Algorithm requires a time growing exponentially with system size to find the ground state of this problem.

4 pages, 4 figures; final version accepted on Phys.Rev.Lett

References in corpus (9)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• First order phase transition in the Quantum Adiabatic Algorithm
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Simple Glass Models and their Quantum Annealing
• Quantum Belief Propagation
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Cavity method for quantum spin glasses on the Bethe lattice
• Coarse grained belief propagation for simulation of interacting quantum systems at all temperatures
• Statistical Mechanics of the Quantum K-Satisfiability problem

Cited by in corpus (68)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Quantum annealing with more than one hundred qubits
• Anderson localization casts clouds over adiabatic quantum optimization
• Quantum Annealing: An Overview
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Coherent and dissipative dynamics at quantum phase transitions
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• On quantum mean-field models and their quantum annealing
• Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
• Driver Hamiltonians for constrained optimization in quantum annealing
• Quantum annealing: the fastest route to quantum computation?
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Quantum annealing with longitudinal bias fields
• Algorithmic approach to adiabatic quantum optimization
• Ground-state fidelity at first-order quantum transitions
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• A solvable model of quantum random optimization problems
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• The quantum Biroli-Mézard model: glass transition and superfluidity in a quantum lattice glass model
• Equation Planting: A Tool for Benchmarking Ising Machines
• Dissipative dynamics at first-order quantum transitions
• Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
• Greedy parameter optimization for diabatic quantum annealing
• Quantum Annealing - Foundations and Frontiers
• Quantum search by partial adiabatic evolution
• Quantum annealing of pure and random Ising chains coupled to a bosonic environment
• On the relation between kinetically constrained models of glass dynamics and the random first-order transition theory
• Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
• Solving Optimization Problems by the Public Goods Game
• Spectral Analysis of the Quantum Random Energy Model
• Universal scaling in quenches across a discontinuity critical point
• Enhancing quantum annealing performance by a degenerate two-level system
• Classical and Quantum Annealing in the Median of Three Satisfiability
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Optimal exploration of random walks with local bias on networks
• Bounding first-order quantum phase transitions in adiabatic quantum computing
• Obstacles to quantum annealing in a planar embedding of XORSAT
• The quantum annealing gap and quench dynamics in the exact cover problem
• Dissipative failure of adiabatic quantum transport as a dynamical phase transition
• Tensor network method for reversible classical computation
• An Evolutionary Strategy based on Partial Imitation for Solving Optimization Problems
• Out-of-equilibrium dynamics across the first-order quantum transitions of one-dimensional quantum Ising models
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Quantum annealing sampling with a bias field
• The effect of quantum fluctuations on the coloring of random graphs
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Quantum Phase Transition in Fully-Connected Quantum Wajnflasz-Pick Model
• Computational Bottlenecks of Quantum Annealing
• Tensor networks for $p$-spin models
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Asymptotic Exceptional Steady States in Dissipative Dynamics
• Duality approach to quantum annealing of the 3-XORSAT problem
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Quantum quenches across continuous and first-order quantum transitions in one-dimensional quantum Ising models
• Steady state distributions of network of degenerate optical parametric oscillators in solving combinatorial optimization problems
• Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses