Finding spin glass ground states using quantum walks
Open Access
- 1 December 2019
- journal article
- research article
- Published by IOP Publishing in New Journal of Physics
- Vol. 21 (12) , 123022
Abstract
Quantum computation using continuous-time evolution under a natural hardware Hamiltonian is a promising near- and mid-term direction toward powerful quantum computing hardware. We investigate the performance of continuous-time quantum walks as a tool for finding spin glass ground states, a problem that serves as a useful model for realistic optimization problems. By performing detailed numerics, we uncover significant ways in which solving spin glass problems differs from applying quantum walks to the search problem. Importantly, unlike for the search problem, parameters such as the hopping rate of the quantum walk do not need to be set precisely for the spin glass ground state problem. Heuristic values of the hopping rate determined from the energy scales in the problem Hamiltonian are sufficient for obtaining a better quantum advantage than for search. We uncover two general mechanisms that provide the quantum advantage: matching the driver Hamiltonian to the encoding in the problem Hamiltonian, and an energy redistribution principle that ensures a quantum walk will find a lower energy state in a short timescale. This makes it practical to use quantum walks for solving hard problems, and opens the door for a range of applications on suitable quantum hardware.Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council (EP/L016524/1)
This publication has 66 references indexed in Scilit:
- Finding low-energy conformations of lattice protein models by quantum annealingScientific Reports, 2012
- Quantum annealing with manufactured spinsNature, 2011
- Absence of an Almeida-Thouless Line in Three-Dimensional Spin GlassesPhysical Review Letters, 2004
- Random knapsack in expected polynomial timeJournal of Computer and System Sciences, 2004
- Spatial search by quantum walkPhysical Review A, 2004
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Infinite-range Ising spin glass in a transverse fieldJournal of Physics A: General Physics, 1989
- Equilibrium behavior of the spin-glass ordered phasePhysical Review B, 1988
- A recursive branch-and-bound algorithm for the exact ground state of Ising spin-glass modelsComputer Physics Communications, 1984
- The order parameter for spin glasses: a function on the interval 0-1Journal of Physics A: General Physics, 1980