A solvable model of quantum random optimization problems

Abstract

We study the quantum version of a simplified model of optimization problems, where quantum fluctuations are introduced by a transverse field acting on the qubits. We find a complex low-energy spectrum of the quantum Hamiltonian, characterized by an abrupt condensation transition and a continuum of level crossings as a function of the transverse field. We expect this complex structure to have deep consequences on the behavior of quantum algorithms attempting to find solutions to these problems.

4 pages, 3 figures, accepted version

References in corpus (13)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum Search by Local Adiabatic Evolution
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical mechanics of the random K-SAT model
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Simple Glass Models and their Quantum Annealing
• First-order transitions and the performance of quantum algorithms in random optimization problems
• The Quantum Spherical p-Spin-Glass Model
• Quantum TAP equations
• Quantum phase transition in spin glasses with multi-spin interactions
• Chaotic temperature dependence in a model of spin glasses
• Random subcubes as a toy model for constraint satisfaction problems

Cited by in corpus (18)

• Adiabatic Quantum Computing
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Quantum fluctuations can promote or inhibit glass formation
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Quantum annealing: the fastest route to quantum computation?
• Quantum algorithm for energy matching in hard optimization problems
• Algorithmic approach to adiabatic quantum optimization
• The quantum Biroli-Mézard model: glass transition and superfluidity in a quantum lattice glass model
• Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
• Clustering in Hilbert space of a quantum optimization problem
• A tentative replica theory of glassy Helium 4
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• The effect of quantum fluctuations on the coloring of random graphs
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Quantum fluctuations can enhance or reduce positional uncertainty at finite temperature