Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2009 | public
Journal Article

Eigenpath traversal by phase randomization

Abstract

A computation in adiabatic quantum computing is implemented by traversing a path of nondegenerate eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a discretized form of the path: At each step we apply 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. If negative evolution times can be implemented with constant overhead, then the average absolute evolution time required by our method is O(L^2/Δ) for constant error probability, where L is the length of the path of eigenstates and Δ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on Δ is optimal. Making explicit the dependence on the path length is useful for cases where L is much less than the general bound. The complexity of our method has a logarithmic improvement over previous algorithms of this type. The same cost applies to the discrete-time case, where a family of unitary operators is given and each unitary and its inverse can be used. Restriction to positive evolution times incurs an error that decreases exponentially with the cost. Applications of this method 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.

Additional Information

© 2009 Rinton Press. Received March 11, 2009. Revised July 9, 2009. Communicated by: R Jozsa & B Terhal. We thank Howard Barnum for discussions. This work was supported by Perimeter Institute for Theoretical Physics, by the Government of Canada through Industry Canada and by the Province of Ontario through the Ministry of Research and Innovation. This work was also supported by the National Science Foundation under grant PHY-0803371 through the Institute for Quantum Information at the California Institute of Technology. Contributions to this work by NIST, an agency of the US government, are not subject to copyright laws. SB thanks the Laboratory Directed Research and Development Program at Los Alamos National Laboratory for support during the initial stages of this work.

Additional details

Created:
August 21, 2023
Modified:
October 20, 2023