Tracing the origin of a quantum advantage in simulated annealing
Elias Starchl, Helmut Ritsch · arXiv (Cornell University) · 2020
Quantum annealing aims at finding optimal solutions to complex classical optimization problems using suitable quantum many body Hamiltonians encoding the desired solution in their ground state. In practice one slowly evolves the ground state of a simple initial Hamiltonian adiabatically into the ground state of the designated final Hamiltonian. Here we explore whether and when exploiting the full quantum dynamics generates an efficiency advantage to find a solution when compared to corresponding classical simulations. As simple but nontrivial example we use interacting bosons trapped in a tight binding lattice with small disorder and cavity generated long range interactions. Already two atoms in four sites interacting via two cavity modes prove complex enough to exhibit significant differences between the full quantum model and a classical field approximation. Indeed we find a large parameter region of successful quantum annealing where the semi-classical approach largely fails. We see strong evidence for the importance of entanglement in finding an optimal solution and reducing the minimal time for a successful annealing. As a surprise, different numerical cut-offs of the mode Hilbert space reveal a counter-intuitively improved performance for lower cut-offs at short simulation times. Hence a less faithful representation of the full quantum dynamics creates a higher success probability even in shorter time. However, higher cut-offs are still prove relevant to obtain near perfect fidelity for long simulation time. These results exhibit a clear advantage of quantum dynamics versus simulations using a classical field approximation.