Quantum annealing: the fastest route to quantum computation?
arXiv:1411.5710 · doi:10.1140/epjst/e2015-02344-2
Abstract
In this review we consider the performance of the quantum adiabatic algorithm for the solution of decision problems. We divide the possible failure mechanisms into two sets: small gaps due to quantum phase transitions and small gaps due to avoided crossings inside a phase. We argue that the thermodynamic order of the phase transitions is not predictive of the scaling of the gap with the system size. On the contrary, we also argue that, if the phase surrounding the problem Hamiltonian is a Many-Body Localized (MBL) phase, the gaps are going to be typically exponentially small and that this follows naturally from the existence of local integrals of motion in the MBL phase.
16 pages, 1 figure
References in corpus (18)
- Many body localization in Heisenberg XXZ magnet in a random field
- Phenomenology of fully many-body-localized systems
- Integrals of motion in the Many-Body localized phase
- Ergodicity breaking in a model showing many-body localization
- Many-body mobility edge in a mean-field quantum spin glass
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- 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
- Simple Glass Models and their Quantum Annealing
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Cavity method for quantum spin glasses on the Bethe lattice
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- On quantum mean-field models and their quantum annealing
- A solvable model of quantum random optimization problems
- On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
- Statistical Mechanics of the Quantum K-Satisfiability problem
- Limitations of some simple adiabatic quantum algorithms
- Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem