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.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.

Quantum Information and ComputationSep 1, 200951 citations

Eigenstate preparation by phase decoherence

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

Canadian Workshop on Information Theory (CWIT)May 1, 20090 citations

Quantum state preparation by phase randomization

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

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/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. Making explicit the dependence on the path length is useful for cases where L does not depend on Delta. 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. If negative evolution times can be implemented with constant overhead, then the average absolute evolution time required by our method is O(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. Making explicit the dependence on the path length is useful for cases where L does not depend on Delta. 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.

arXiv:0903.1652Mar 9, 20099 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.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.3034May 17, 201012 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.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.30110May 29, 20260 citations

Eigenpath Traversal by Phase Randomization | NIST

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

Quantum Information and ComputationSep 1, 20090 citations

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.