Title: Quantum Algorithms for Classical Sampling Problems
Abstract: Sampling from a classical, thermal distribution is, in general, a computationally hard problem. In particular, standard Monte Carlo algorithms converge slowly close to a phase transition or in the presence of frustration. In this work, we explore whether a quantum computer can provide a speedup for problems of this type. The sampling problem can be reduced to the task of preparing a pure quantum state, the so-called Gibbs state [1]. Samples from the thermal distribution are obtained by performing projective measurements on this state. To prepare the Gibbs state, we exploit a mapping from a classical Monte Carlo algorithm to a quantum Hamiltonian whose ground state is the Gibbs state [2]. We demonstrate with concrete examples that a quantum speedup can be achieved by identifying optimal adiabatic trajectories in an extended parameter space of the quantum Hamiltonian. Our approach elucidates intimate connections between computational complexity and phase transitions. Finally, we propose a realistic implementation of the algorithm using Rydberg atoms suitable for near-term quantum devices.
References
[1] R. D. Somma and C. D. Batista, Phys. Rev. Lett. 99, 030603 (2007).
[2] F. Verstraete, M. M. Wolf, D. Perez-Garcia, and J. I. Cirac, Phys. Rev. Lett. 96, 220601 (2006).
LOCATION:Jefferson 356 STATUS:CONFIRMED DTSTART:20200211T203000Z DTEND:20200211T203000Z END:VEVENT END:VCALENDAR