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:1210.4647

Digital analogue of quantum adiabatic evolution

Avatar Tulsi

Published Oct 17, 2012• 1 citation
arXivHTMLPDF

Abstract

A basic building block of many quantum algorithms is the Phase Estimation algorithm (PEA). It estimates an eigenphase $\phi$ of a unitary operator $U$ using a copy of the corresponding eigenstate $|\phi\rangle$. Suppose, in place of $|\phi\rangle$, we have a copy of an approximate eigenstate $|\psi\rangle$ whose overlap magnitude with $|\phi\rangle$ is at least $\sqrt{2/3}$. Then PEA fails with a constant probability. However, using multiple copies of $|\psi\rangle$, the failure probaility can be made to decrease exponentially with the number of copies. In this paper, we show that as long as we can perform a selective inversion of $|\psi\rangle$, a single copy is sufficient to estimate $\phi$. An important application is to improve the spatial complexity of eigenpath traversal algorithm, a digital analogue of quantum adiabatic evolution, having applications ranging from quantum physics simulation to optimization. Here the goal is to travel a path of eigenstates of $n$ different unitary operators satisfying some conditions. The fastest algorithm is due to Boixo, Knill and Somma (BKS) which needs $\Theta(\ln n)$ copies of the eigenstate. Using our algorithm, BKS algorithm can work using just a single copy of the eigenstate.

Related papers

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•12 citations

Tight Bounds for Quantum Phase Estimation and Related Problems

Nikhil S. Mande, Ronald de Wolf

Phase estimation, due to Kitaev \cite{Kit95}, is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary U , and an eigenstate | ψ ⟩ of U with unknown eigenvalue e i θ , and the task is to estimate the eigenphase θ within ± δ , with high probability. The cost of an algorithm for us is the number of applications of U and U − 1 .We tightly characterize the cost of several variants of phase estimation where we are no longer given an eigenstate, but are required to estimate the maximum eigenphase of U , aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap γ with the top eigenspace.We give algorithms and nearly matching lower bounds for all ranges of parameters.We show that a small number of copies of the advice state (or of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having lots of advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of U . We immediately obtain a lower bound on the complexity of the Unitary recurrence time problem, resolving an open question of She and Yuen \cite{SY23}.Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision δ and error probability ϵ has cost Ω ( 1 δ log ⁡ 1 ϵ ) , matching an easy upper bound. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor O ( log ⁡ ( 1 / ϵ ) ) . Our lower bound uses a variant of the polynomial method with trigonometric polynomials.

arXiv:2305.04908•Quantum•Jun 15, 2026•7 citations

A simpler algorithm to mark the unknown eigenstates

Avatar Tulsi

For an unknown eigenstate $|ψ\rangle$ of a unitary operator $U$, suppose we have an estimate of the corresponding eigenvalue which is separated from all other eigenvalues by a minimum gap of magnitude $Δ$. In the eigenstate-marking problem (EMP), the goal is to implement a selective phase transformation of the $|ψ\rangle$ state (known as \emph{marking} the $|ψ\rangle$ state in the language of the quantum search algorithms). The EMP finds important applications in the construction of several quantum algorithms. The best known algorithm for the EMP combines the ideas of the phase estimation algorithm and the majority-voting. It uses $Θ(\frac{1}Δ\ln \frac{1}ε)$ applications of $U$ where $ε$ is the tolerable error. It needs $Θ\left(\ln \frac{1}Δ\right)$ ancilla qubits for the phase estimation and another $Θ\left(\ln \frac{1}ε\right)$ ancilla qubits for the majority-voting. In this paper, we show that the majority-voting is not a crucial requirement for the EMP and the same purpose can also be achieved using the fixed-point quantum search algorithm which does not need any ancilla qubits. In the case of majority-voting, these ancilla qubits were needed to do controlled transformations which are harder to implement physically. Using fixed-point quantum search, we get rid off these $Θ\left(\ln \frac{1}ε\right)$ ancilla qubits and same number of controlled transformations. Thus we get a much simpler algorithm for marking the unknown eigenstates. However, the required number of applications of $U$ increases by the factor of $Θ\left(\ln \frac{1}ε\right)$. This tradeoff can be beneficial in typical situations where spatial resources are more constrained or where the controlled transformations are very expensive.

arXiv:1611.02680•Nov 8, 2016•0 citations

Eigenpath traversal by phase randomization

Sergio Boixo, E. 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 $\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 Computation•Sep 1, 2009•51 citations

Adiabatic Quantum Phase Estimation

Alexander Schmidhuber, Seth Lloyd

Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision $ε$ in Heisenberg-limited time $T=Θ(1/ε)$. Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware. Here, we present a simple adiabatic protocol for QPE that achieves (up to logarithmic factors) the optimal Heisenberg-limited scaling $T = O\left( \frac{1}ε \log\left(δ^{-1}\right)\right)$ in both the precision $ε$ and failure probability $δ$. By encoding eigenvalues in populations of computational basis states rather than complex phases, our approach is naturally robust against certain dephasing errors. The adiabatic protocol only requires the ability to couple a single ancilla qubit to the system Hamiltonian as well as pairwise couplings within the ancilla register.

quant-pharXiv:2605.22770•May 22, 2026•0 citations

Fast digital methods for adiabatic state preparation

Kianna Wan, Isaac H. Kim

We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error. Our algorithm digitally simulates the adiabatic evolution between two self-adjoint operators $H_0$ and $H_1$, exponentially suppressing the diabatic error by harnessing the theoretical concept of quasi-adiabatic continuation as an algorithmic tool. Given an upper bound $α$ on $\|H_0\|$ and $\|H_1\|$ along with the promise that the $k$th eigenstate $|ψ_k(s)\rangle$ of $H(s) \equiv (1-s)H_0 + sH_1$ is separated from the rest of the spectrum by a gap of at least $γ> 0$ for all $s \in [0,1]$, this algorithm implements an operator $\widetilde{U}$ such that $\||ψ_k(1)\rangle - \widetilde{U}|ψ_k(s)\rangle\| \leq ε$ using $O(α^2/γ^2)\text{polylog}(α/γε)$ queries to block-encodings of $H_0$ and $H_1$. In addition, we develop an algorithm that is applicable only to ground states and requires multiple queries to an oracle that prepares $|ψ_0(0)\rangle$, but has slightly better scaling in all parameters. We also show that the costs of both algorithms can be further reduced under certain reasonable conditions, such as when $\|H_1 - H_0\|$ is small compared to $α$, or when more information about the gap of $H(s)$ is available. For certain problems, the scaling can even be improved to linear in $\|H_1 - H_0\|/γ$ up to polylogarithmic factors.

arXiv:2004.04164•Apr 8, 2020•8 citations
A basic building block of many quantum algorithms is the Phase Estimation algorithm (PEA). It estimates an eigenphase ϕ\phiϕ of a unitary operator UUU using a copy of the corresponding eigenstate ∣ϕ⟩|\phi\rangle∣ϕ⟩. Suppose, in place of ∣ϕ⟩|\phi\rangle∣ϕ⟩, we have a copy of an approximate eigenstate ∣ψ⟩|\psi\rangle∣ψ⟩ whose overlap magnitude with ∣ϕ⟩|\phi\rangle∣ϕ⟩ is at least 2/3\sqrt{2/3}2/3​. Then PEA fails with a constant probability. However, using multiple copies of ∣ψ⟩|\psi\rangle∣ψ⟩, the failure probaility can be made to decrease exponentially with the number of copies. In this paper, we show that as long as we can perform a selective inversion of ∣ψ⟩|\psi\rangle∣ψ⟩, a single copy is sufficient to estimate ϕ\phiϕ. An important application is to improve the spatial complexity of eigenpath traversal algorithm, a digital analogue of quantum adiabatic evolution, having applications ranging from quantum physics simulation to optimization. Here the goal is to travel a path of eigenstates of nnn different unitary operators satisfying some conditions. The fastest algorithm is due to Boixo, Knill and Somma (BKS) which needs Θ(ln⁡n)\Theta(\ln n)Θ(lnn) copies of the eigenstate. Using our algorithm, BKS algorithm can work using just a single copy of the eigenstate.
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.
Phase estimation, due to Kitaev \cite{Kit95}, is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary U , and an eigenstate | ψ ⟩ of U with unknown eigenvalue e i θ , and the task is to estimate the eigenphase θ within ± δ , with high probability. The cost of an algorithm for us is the number of applications of U and U − 1 .We tightly characterize the cost of several variants of phase estimation where we are no longer given an eigenstate, but are required to estimate the maximum eigenphase of U , aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap γ with the top eigenspace.We give algorithms and nearly matching lower bounds for all ranges of parameters.We show that a small number of copies of the advice state (or of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having lots of advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of U . We immediately obtain a lower bound on the complexity of the Unitary recurrence time problem, resolving an open question of She and Yuen \cite{SY23}.Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that a phase-estimation algorithm with precision δ and error probability ϵ has cost Ω ( 1 δ log ⁡ 1 ϵ ) , matching an easy upper bound. This contrasts with some other scenarios in quantum computing (e.g., search) where error-probability reduction costs only a factor O ( log ⁡ ( 1 / ϵ ) ) . Our lower bound uses a variant of the polynomial method with trigonometric polynomials.
For an unknown eigenstate ∣ψ⟩|ψ\rangle∣ψ⟩ of a unitary operator UUU, suppose we have an estimate of the corresponding eigenvalue which is separated from all other eigenvalues by a minimum gap of magnitude ΔΔΔ. In the eigenstate-marking problem (EMP), the goal is to implement a selective phase transformation of the ∣ψ⟩|ψ\rangle∣ψ⟩ state (known as \emph{marking} the ∣ψ⟩|ψ\rangle∣ψ⟩ state in the language of the quantum search algorithms). The EMP finds important applications in the construction of several quantum algorithms. The best known algorithm for the EMP combines the ideas of the phase estimation algorithm and the majority-voting. It uses Θ(1Δln⁡1ε)Θ(\frac{1}Δ\ln \frac{1}ε)Θ(Δ1​lnε1​) applications of UUU where εεε is the tolerable error. It needs Θ(ln⁡1Δ)Θ\left(\ln \frac{1}Δ\right)Θ(lnΔ1​) ancilla qubits for the phase estimation and another Θ(ln⁡1ε)Θ\left(\ln \frac{1}ε\right)Θ(lnε1​) ancilla qubits for the majority-voting. In this paper, we show that the majority-voting is not a crucial requirement for the EMP and the same purpose can also be achieved using the fixed-point quantum search algorithm which does not need any ancilla qubits. In the case of majority-voting, these ancilla qubits were needed to do controlled transformations which are harder to implement physically. Using fixed-point quantum search, we get rid off these Θ(ln⁡1ε)Θ\left(\ln \frac{1}ε\right)Θ(lnε1​) ancilla qubits and same number of controlled transformations. Thus we get a much simpler algorithm for marking the unknown eigenstates. However, the required number of applications of UUU increases by the factor of Θ(ln⁡1ε)Θ\left(\ln \frac{1}ε\right)Θ(lnε1​). This tradeoff can be beneficial in typical situations where spatial resources are more constrained or where the controlled transformations are very expensive.
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 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.
Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision εεε in Heisenberg-limited time T=Θ(1/ε)T=Θ(1/ε)T=Θ(1/ε). Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware. Here, we present a simple adiabatic protocol for QPE that achieves (up to logarithmic factors) the optimal Heisenberg-limited scaling T=O(1εlog⁡(δ−1))T = O\left( \frac{1}ε \log\left(δ^{-1}\right)\right)T=O(ε1​log(δ−1)) in both the precision εεε and failure probability δδδ. By encoding eigenvalues in populations of computational basis states rather than complex phases, our approach is naturally robust against certain dephasing errors. The adiabatic protocol only requires the ability to couple a single ancilla qubit to the system Hamiltonian as well as pairwise couplings within the ancilla register.
We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error. Our algorithm digitally simulates the adiabatic evolution between two self-adjoint operators H0H_0H0​ and H1H_1H1​, exponentially suppressing the diabatic error by harnessing the theoretical concept of quasi-adiabatic continuation as an algorithmic tool. Given an upper bound ααα on ∥H0∥\|H_0\|∥H0​∥ and ∥H1∥\|H_1\|∥H1​∥ along with the promise that the kkkth eigenstate ∣ψk(s)⟩|ψ_k(s)\rangle∣ψk​(s)⟩ of H(s)≡(1−s)H0+sH1H(s) \equiv (1-s)H_0 + sH_1H(s)≡(1−s)H0​+sH1​ is separated from the rest of the spectrum by a gap of at least γ>0γ> 0γ>0 for all s∈[0,1]s \in [0,1]s∈[0,1], this algorithm implements an operator U~\widetilde{U}U such that ∥∣ψk(1)⟩−U~∣ψk(s)⟩∥≤ε\||ψ_k(1)\rangle - \widetilde{U}|ψ_k(s)\rangle\| \leq ε∥∣ψk​(1)⟩−U∣ψk​(s)⟩∥≤ε using O(α2/γ2)polylog(α/γε)O(α^2/γ^2)\text{polylog}(α/γε)O(α2/γ2)polylog(α/γε) queries to block-encodings of H0H_0H0​ and H1H_1H1​. In addition, we develop an algorithm that is applicable only to ground states and requires multiple queries to an oracle that prepares ∣ψ0(0)⟩|ψ_0(0)\rangle∣ψ0​(0)⟩, but has slightly better scaling in all parameters. We also show that the costs of both algorithms can be further reduced under certain reasonable conditions, such as when ∥H1−H0∥\|H_1 - H_0\|∥H1​−H0​∥ is small compared to ααα, or when more information about the gap of H(s)H(s)H(s) is available. For certain problems, the scaling can even be improved to linear in ∥H1−H0∥/γ\|H_1 - H_0\|/γ∥H1​−H0​∥/γ up to polylogarithmic factors.