Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Eigenpath Traversal by Phase Randomization



S. Boixo, Emanuel Knill, Rolando Somma


A computation in adiabatic quantum computing is achieved 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 evolve with 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. For bounded error probability, the average evolution time required by our method is O(L*L/D)$, where L is the length of the path of eigenstates and D the minimum spectral gap of the Hamiltonian. The randomization also works in the discrete-time case, where a family of unitary operators is given, and each unitary can be used a finite amount of times. Applications of this method for unstructured search and quantum sampling are considered. We discuss the quantum simulated annealing algorithm to solve combinatorial optimization problems. This algorithm provides a quadratic speed-up (in the gap) over its classical counterpart implemented via Markov chain Monte Carlo.
Quantum Information & Computation
9 & 10


Quantum computing, adiabatic quantum computing, decoherence, Zeno effect


Boixo, S. , Knill, E. and Somma, R. (2009), Eigenpath Traversal by Phase Randomization, Quantum Information & Computation, [online], (Accessed May 21, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created August 31, 2009, Updated October 12, 2021