All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

Fast Quantum Algorithms for Traversing Paths of Eigenstates

Rolando Somma, Los Alamos National Laboratory

(Session 7 : Saturday from 2:30-3:00)

Abstract. We present optimal quantum algorithms to traverse the path of eigenstates of a discrete or continuous family of Hamiltonians. The implementation cost of the algorithms is the total evolution time with the Hamiltonians. Under some assumptions, the cost of the method is proportional to the ratio of the length of the eigenstate path to the minimum eigenvalue gap of the Hamiltonians. When no assumptions are made, the worst-case cost scales with the inverse of the gap squared. Our algorithms advance by preparing eigenstates from previous ones through a version of fixed point search that is approximated using the phase estimation algorithm. The cost of our methods is optimal and significantly improves upon the cost of known general methods for quantum adiabatic state preparation. In some cases, our methods yield a quantum speed-up over well-known classical annealing methods. (Unitary versions of the method can also be considered.)