Quantum state preparation by phase randomization

A computation in adiabatic quantum computing is implemented by traversing a path of eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a discretized form of the path by applying, at each step, the instantaneous Hamiltonian for a random time. The resulting decoherence approximates a projective measurement onto the desired eigenstate, achieving a version of the quantum Zeno effect. The average absolute evolution time required by our method is proportional to the square of the length of the path of eigenstates, and inversely proportional to the minimum energy gap. The dependence of the cost on the gap is optimal. Our method can be viewed as a rigorous, and more general, adiabatic approximation. It is a conceptually clear example of how sometimes some decoherence helps. Applications to unstructured search and quantum sampling are considered. In particular, we discuss the quantum simulated annealing algorithm for solving combinatorial optimization problems. This algorithm provides a quadratic speed-up in the gap of the stochastic matrix over its classical counterpart implemented via Markov chain Monte Carlo.