Quantum algorithm for energy matching in hard optimization problems

Christopher L. Baldwin

doi:10.1103/PhysRevB.97.224201

2018-06-11

Christopher L. Baldwin *

Chris R. Laumann

DOI：10.1103/PhysRevB.97.224201

原文链接

查看原文

摘要

En 中文

We consider the ability of local quantum dynamics to solve the energy-matching problem: given an instance of a classical optimization problem and a low-energy state, find another macroscopically distinct low-energy state. Energy matching is difficult in rugged optimization landscapes, as the given state provides little information about the distant topography. Here, we show that the introduction of quantum dynamics can provide a speedup over classical algorithms in a large class of hard optimization problems. Tunneling allows the system to explore the optimization landscape while approximately conserving the classical energy, even in the presence of large barriers. Specifically, we study energy matching in the random p-spin model of spin-glass theory. Using perturbation theory and exact diagonalization, we show that introducing a transverse field leads to three sharp dynamical phases, only one of which solves the matching problem: (1) a small-field trapped phase, in which tunneling is too weak for the system to escape the vicinity of the initial state; (2) a large-field excited phase, in which the field excites the system into high-energy states, effectively forgetting the initial energy; and (3) the intermediate tunneling phase, in which the system succeeds at energy matching. The rate at which distant states are found in the tunneling phase, although exponentially slow in system size, is exponentially faster than classical search algorithms.

Keyword:

RANDOM SATISFIABILITY PROBLEMS

SPIN-GLASS

METASTABLE STATES

TRANSVERSE FIELD

MODELS

PHASE

SYSTEMS

FAIL