Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0903.1652 · Quantum Information and Computation

Eigenpath traversal by phase randomization

Sergio Boixo, E. Knill, Rolando D. Somma

Published Sep 1, 2009• 73 citations
arXivHTMLPDF

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 $\cO(L^{2} /\Delta)$ for constant error probability, where $L$ is the length of the path of eigenstates and $\Delta$ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on $\Delta$ 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.

DOI
10.26421/qic9.9-10-7

Related papers

Eigenstate preparation by phase decoherence

Rolando D. Somma, Sergio Boixo, Emanuel H. Knill

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. The average cost of our method is O(L2/Delta) for constant error probability, where L is the length of the path of eigenstates and Delta is the minimum spectral gap of the Hamiltonian. For many cases of interest, L does not depend on Delta so the scaling of the cost with the gap is better than the one obtained in rigorous proofs of the adiabatic theorem. We give an example where this situation occurs.

Canadian Workshop on Information Theory (CWIT)•May 1, 2009•0 citations

Fast quantum algorithms for traversing paths of eigenstates

Sergio Boixo, E. Knill, Rolando D. Somma

Consider a path of non-degenerate eigenstates of unitary operators or Hamiltonians with minimum eigenvalue gap G. The eigenpath traversal problem is to transform one or more copies of the initial to the final eigenstate. Solutions to this problem have applications ranging from quantum physics simulation to optimization. For Hamiltonians, the conventional way of doing this is by applying the adiabatic theorem. We give ``digital'' methods for performing the transformation that require no assumption on path continuity or differentiability other than the absence of large jumps. Given sufficient information about eigenvalues and overlaps between states on the path, the transformation can be accomplished with complexity O(L/G log(L/e)), where L is the angular length of the path and e is a specified bound on the error of the output state. We show that the required information can be obtained in a first set of transformations, whose complexity per state transformed has an additional factor that depends logarithmically on a maximum angular velocity along the path. This velocity is averaged over constant angular distances and does not require continuity. Our methods have substantially better behavior than conventional adiabatic algorithms, with fewer conditions on the path. They also improve on the previously best digital methods and demonstrate that path length and the gap are the primary parameters that determine the complexity of state transformation along a path.

arXiv:1005.3034•May 17, 2010•36 citations

Improved bounds for eigenpath traversal

Hao-Tien Lewis Chiang, Guanglei Xu, Rolando D. Somma

We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\ensuremath{\Delta}$. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/{\ensuremath{\Delta}}^{2}$, and a method based on fixed-point search has a maximum cost of order $1/{\ensuremath{\Delta}}^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/{\ensuremath{\Delta}}^{3/2}$ and $1/\ensuremath{\Delta}$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/{\ensuremath{\Delta}}^{3}$.

arXiv:1311.7073•Physical Review A•Jan 15, 2014•18 citations

Quantum Simulated Annealing

Somma, R., Boixo, S., Howard Barnum

We develop a quantum algorithm to solve combinatorial optimization problems through quantum simulation of a classical annealing process. Our algorithm combines techniques from quantum walks, quantum phase estimation, and quantum Zeno effect. It can be viewed as a quantum analogue of the discrete-time Markov chain Monte Carlo implementation of classical simulated annealing. Our implementation scales with the inverse of the square root of the minimum spectral gap of the stochastic matrix used in the classical simulation. The quantum algorithm outperforms the classical one, which scales with the inverse of the gap.

arXiv:0712.1008•Dec 6, 2007•42 citations

Alternative adiabatic quantum dynamics with algorithmic applications

Joseph Cunningham, Jérémie Roland

In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes. As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022]. We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.

quant-pharXiv:2605.30110•May 29, 2026•2 citations

Quantum Simulations of Classical Annealing Processes

Rolando D. Somma, Sergio Boixo, Howard Barnum +1 more

We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order 1/sqrt delta steps to find an optimal solution with bounded error probability, where delta is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order 1/delta steps required by the latter.

arXiv:0804.1571•Physical Review Letters•Sep 26, 2008•190 citations
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 \cO(L2/Δ)\cO(L^{2} /\Delta)\cO(L2/Δ) for constant error probability, where LLL is the length of the path of eigenstates and Δ\DeltaΔ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on Δ\DeltaΔ is optimal. Making explicit the dependence on the path length is useful for cases where LLL 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.
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. The average cost of our method is O(L2/Delta) for constant error probability, where L is the length of the path of eigenstates and Delta is the minimum spectral gap of the Hamiltonian. For many cases of interest, L does not depend on Delta so the scaling of the cost with the gap is better than the one obtained in rigorous proofs of the adiabatic theorem. We give an example where this situation occurs.
Consider a path of non-degenerate eigenstates of unitary operators or Hamiltonians with minimum eigenvalue gap G. The eigenpath traversal problem is to transform one or more copies of the initial to the final eigenstate. Solutions to this problem have applications ranging from quantum physics simulation to optimization. For Hamiltonians, the conventional way of doing this is by applying the adiabatic theorem. We give ``digital'' methods for performing the transformation that require no assumption on path continuity or differentiability other than the absence of large jumps. Given sufficient information about eigenvalues and overlaps between states on the path, the transformation can be accomplished with complexity O(L/G log(L/e)), where L is the angular length of the path and e is a specified bound on the error of the output state. We show that the required information can be obtained in a first set of transformations, whose complexity per state transformed has an additional factor that depends logarithmically on a maximum angular velocity along the path. This velocity is averaged over constant angular distances and does not require continuity. Our methods have substantially better behavior than conventional adiabatic algorithms, with fewer conditions on the path. They also improve on the previously best digital methods and demonstrate that path length and the gap are the primary parameters that determine the complexity of state transformation along a path.
We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\ensuremath{\Delta}$. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/{\ensuremath{\Delta}}^{2}$, and a method based on fixed-point search has a maximum cost of order $1/{\ensuremath{\Delta}}^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/{\ensuremath{\Delta}}^{3/2}$ and $1/\ensuremath{\Delta}$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/{\ensuremath{\Delta}}^{3}$.
We develop a quantum algorithm to solve combinatorial optimization problems through quantum simulation of a classical annealing process. Our algorithm combines techniques from quantum walks, quantum phase estimation, and quantum Zeno effect. It can be viewed as a quantum analogue of the discrete-time Markov chain Monte Carlo implementation of classical simulated annealing. Our implementation scales with the inverse of the square root of the minimum spectral gap of the stochastic matrix used in the classical simulation. The quantum algorithm outperforms the classical one, which scales with the inverse of the gap.
In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes. As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022]. We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.
We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order 1/sqrt delta steps to find an optimal solution with bounded error probability, where delta is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order 1/delta steps required by the latter.