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

Fast digital methods for adiabatic state preparation

Kianna Wan, Isaac H. Kim

Published Apr 8, 2020• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2004.04164

Related papers

Quantum adiabatic optimization without heuristics

Michael Jarret, Brad Lackey, Aike Liu +1 more

Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian $H(s)$ with spectral gap $γ(s)$. Assuming the existence of an oracle $Γ$ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that $\|dH/ds\| \approx γ(s)$ and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle $Γ$ for the problem of finding the minimum point $m = \mathrm{argmin}_u W(u)$ of the cost function $W:\mathcal{V}\longrightarrow [0,1]$, restricting ourselves to computational basis measurements and driving Hamiltonian $H(0)=I - |\mathcal{V}|^{-1}\sum_{u,v \in \mathcal{V}}\vert{u}\rangle\langle{v}\vert$. Requiring only that $W$ have a constant lower bound on its spectral gap and upper bound $κ$ on its spectral ratio, our QAO algorithm returns $m$ with probability $(1-ε)(1-e^{-1/ε})$ in time $\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])$. This achieves a quantum advantage for all $κ$, and recovers Grover scaling up to logarithmic factors when $κ\approx 1$. We implement the algorithm as a subroutine in an optimization procedure that produces $m$ with exponentially small failure probability and expected runtime $\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])$ even when $κ$ is not known beforehand.

arXiv:1810.04686•Oct 10, 2018•8 citations

Strategies for adiabatic state preparation of quantum many-body systems

Dyon van Vreumingen

Quantum computers represent a relatively new and promising development in computing technology. One of the applications of quantum computers is modelling quantum many-body systems, which describe interactions between particles on atomic and subatomic scales. Such systems are highly complex and challenging to model with classical computers due to the vast number of possible states and entanglement of the particles. In this dissertation, we examine the extent to which quantum computers can accelerate the modelling of quantum many-body systems compared to classical computers. Specifically, this dissertation presents research on adiabatic state preparation: a quantum algorithmic technique that uses the adiabatic principle from quantum mechanics to approximate eigenstates. We describe three new techniques that fall within this category and, in certain cases, offer advantages over standard methods. First, we consider cases of ground state preparation for fermionic many-body systems, where standard direct interpolation between the initial and final hamiltonian is hindered by level crossings due to discrete symmetries. As an alternative to direct interpolation, we propose adiabatic paths in a higher-dimensional space, which break the relevant symmetries. Next, we present an adiabatic echo verification protocol which mitigates both coherent and incoherent errors, arising from non-adiabatic transitions and hardware noise, respectively. We show that the estimator bias of the observable is reduced when compared to standard adiabatic preparation, achieving up to a quadratic improvement. Finally, we propose a general, fully gate-based and nonvariational quantum algorithm for counterdiabatic driving. We provide a rigorous quantum gate complexity upper bound in terms of the minimum gap $\Delta$ around this eigenstate. We find that, in the worst case, the algorithm can be run with at most $\tilde O(\Delta^{-(3 + o(1))} \epsilon^{-(1 + o(1))})$ quantum gates such that a target state fidelity of at least $1 - \epsilon^2$ is achieved. In certain cases, the gap dependence can be improved to quadratic.

•Feb 20, 2025•0 citations

Resource-Efficient Digitized Adiabatic Quantum Factorization

Felip Pellicer, Juan José García-Ripoll, Alan C. Santos

Digitized adiabatic quantum factorization is a hybrid algorithm that exploits the advantage of digitized quantum computers to implement efficient adiabatic algorithms for factorization through gate decompositions of analog evolutions. In this paper, we harness the flexibility of digitized computers to derive a digitized adiabatic algorithm able to reduce the gate-demanding costs of implementing factorization. To this end, we propose a new approach for adiabatic factorization by encoding the solution of the problem in the kernel subspace of the problem Hamiltonian, instead of using ground-state encoding considered in the standard adiabatic factorization proposed by Peng $et$ $al$. [Phys. Rev. Lett. 101, 220405 (2008)]. Our encoding enables the design of adiabatic factorization algorithms belonging to the class of Quadratic Unconstrained Binary Optimization (QUBO) methods, instead the Polinomial Unconstrained Binary Optimization (PUBO) used by standard adiabatic factorization. We illustrate the performance of our QUBO algorithm by implementing the factorization of integers $N$ up to 8 bits. The results demonstrate a substantial improvement over the PUBO formulation, both in terms of reduced circuit complexity and increased fidelity in identifying the correct solution.

quant-pharXiv:2602.04740•Feb 5, 2026•0 citations

Large time-step discretization of adiabatic quantum dynamics

Dong Un An, Pedro C. S. Costa, Dominic William Berry

Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time-step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time-step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, we provide strong evidence for a superpolynomial convergence of first-order Trotter with uniform time-step size. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterized adiabatic approach: It can match the Grover lower bound, it does not require knowledge of the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm.

arXiv:2509.00171•Physical Review Research•Oct 2, 2026•0 citations

Digital quantum state preparation by nucleation

Jean Paul Sadia, Morten Hjorth-Jensen, Dean Lee +1 more

Quantum state preparation is crucial for quantum algorithms, and improved state preparation methods can reduce resource requirements by orders of magnitude. In this work, we introduce a state preparation method for lattice Hamiltonians on digital quantum computers inspired by nucleation. In our method, the exact ground state of a small lattice Hamiltonian is prepared in a quantum circuit, then a series of growth stages are performed via Trotterized adiabatic evolution to increase the size of the lattice to the desired model. Using the adiabatic theorem and Trotter error bounds, we provide sufficient conditions on the total evolution time and number of Trotter steps required for nucleation to prepare an initial state with desired fidelity. In addition, we introduce optimized nucleation which considers variational optimization on top of the nucleation structure. For a two-dimensional Ising model, we show that optimized nucleation can outperform a current leading method for state preparation on digital quantum computers.

quant-pharXiv:2609.37527•Sep 30, 2026•0 citations

On the power of coherently controlled quantum adiabatic evolutions

Mária Kieferová, Nathan Wiebe

We provide a new approach to adiabatic state preparation that uses coherent control and measurement to average different adiabatic evolutions in ways that cause their diabatic errors to cancel, allowing highly accurate state preparations using less time than conventional approaches. We show that this new model for adiabatic state preparation is polynomially equivalent to conventional adiabatic quantum computation by providing upper bounds on the cost of simulating such evolutions on a circuit-based quantum computer. Finally, we show that this approach is robust to small errors in the quantum control register and that the system remains protected against noise on the adiabatic register by the spectral gap.

arXiv:1403.6545•New Journal of Physics•Dec 15, 2014•20 citations
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.
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s)H(s)H(s) with spectral gap γ(s)γ(s)γ(s). Assuming the existence of an oracle ΓΓΓ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that ∥dH/ds∥≈γ(s)\|dH/ds\| \approx γ(s)∥dH/ds∥≈γ(s) and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle ΓΓΓ for the problem of finding the minimum point m=argminuW(u)m = \mathrm{argmin}_u W(u)m=argminu​W(u) of the cost function W:V⟶[0,1]W:\mathcal{V}\longrightarrow [0,1]W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I−∣V∣−1∑u,v∈V∣u⟩⟨v∣H(0)=I - |\mathcal{V}|^{-1}\sum_{u,v \in \mathcal{V}}\vert{u}\rangle\langle{v}\vertH(0)=I−∣V∣−1∑u,v∈V​∣u⟩⟨v∣. Requiring only that WWW have a constant lower bound on its spectral gap and upper bound κκκ on its spectral ratio, our QAO algorithm returns mmm with probability (1−ε)(1−e−1/ε)(1-ε)(1-e^{-1/ε})(1−ε)(1−e−1/ε) in time O~(ε−1[∣V∣+(κ−1)2/3∣V∣2/3])\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])O(ε−1[∣V∣​+(κ−1)2/3∣V∣2/3]). This achieves a quantum advantage for all κκκ, and recovers Grover scaling up to logarithmic factors when κ≈1κ\approx 1κ≈1. We implement the algorithm as a subroutine in an optimization procedure that produces mmm with exponentially small failure probability and expected runtime O~(ε−1[∣V∣+(κ−1)2/3∣V∣2/3])\widetilde{\mathcal{O}}(ε^{-1}[\sqrt{|\mathcal{V}|} + (κ-1)^{2/3}|\mathcal{V}|^{2/3}])O(ε−1[∣V∣​+(κ−1)2/3∣V∣2/3]) even when κκκ is not known beforehand.
Quantum computers represent a relatively new and promising development in computing technology. One of the applications of quantum computers is modelling quantum many-body systems, which describe interactions between particles on atomic and subatomic scales. Such systems are highly complex and challenging to model with classical computers due to the vast number of possible states and entanglement of the particles. In this dissertation, we examine the extent to which quantum computers can accelerate the modelling of quantum many-body systems compared to classical computers. Specifically, this dissertation presents research on adiabatic state preparation: a quantum algorithmic technique that uses the adiabatic principle from quantum mechanics to approximate eigenstates. We describe three new techniques that fall within this category and, in certain cases, offer advantages over standard methods. First, we consider cases of ground state preparation for fermionic many-body systems, where standard direct interpolation between the initial and final hamiltonian is hindered by level crossings due to discrete symmetries. As an alternative to direct interpolation, we propose adiabatic paths in a higher-dimensional space, which break the relevant symmetries. Next, we present an adiabatic echo verification protocol which mitigates both coherent and incoherent errors, arising from non-adiabatic transitions and hardware noise, respectively. We show that the estimator bias of the observable is reduced when compared to standard adiabatic preparation, achieving up to a quadratic improvement. Finally, we propose a general, fully gate-based and nonvariational quantum algorithm for counterdiabatic driving. We provide a rigorous quantum gate complexity upper bound in terms of the minimum gap Δ\DeltaΔ around this eigenstate. We find that, in the worst case, the algorithm can be run with at most O~(Δ−(3+o(1))ϵ−(1+o(1)))\tilde O(\Delta^{-(3 + o(1))} \epsilon^{-(1 + o(1))})O~(Δ−(3+o(1))ϵ−(1+o(1))) quantum gates such that a target state fidelity of at least 1−ϵ21 - \epsilon^21−ϵ2 is achieved. In certain cases, the gap dependence can be improved to quadratic.
Digitized adiabatic quantum factorization is a hybrid algorithm that exploits the advantage of digitized quantum computers to implement efficient adiabatic algorithms for factorization through gate decompositions of analog evolutions. In this paper, we harness the flexibility of digitized computers to derive a digitized adiabatic algorithm able to reduce the gate-demanding costs of implementing factorization. To this end, we propose a new approach for adiabatic factorization by encoding the solution of the problem in the kernel subspace of the problem Hamiltonian, instead of using ground-state encoding considered in the standard adiabatic factorization proposed by Peng etetet alalal. [Phys. Rev. Lett. 101, 220405 (2008)]. Our encoding enables the design of adiabatic factorization algorithms belonging to the class of Quadratic Unconstrained Binary Optimization (QUBO) methods, instead the Polinomial Unconstrained Binary Optimization (PUBO) used by standard adiabatic factorization. We illustrate the performance of our QUBO algorithm by implementing the factorization of integers NNN up to 8 bits. The results demonstrate a substantial improvement over the PUBO formulation, both in terms of reduced circuit complexity and increased fidelity in identifying the correct solution.
Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time-step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time-step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, we provide strong evidence for a superpolynomial convergence of first-order Trotter with uniform time-step size. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterized adiabatic approach: It can match the Grover lower bound, it does not require knowledge of the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm.
Quantum state preparation is crucial for quantum algorithms, and improved state preparation methods can reduce resource requirements by orders of magnitude. In this work, we introduce a state preparation method for lattice Hamiltonians on digital quantum computers inspired by nucleation. In our method, the exact ground state of a small lattice Hamiltonian is prepared in a quantum circuit, then a series of growth stages are performed via Trotterized adiabatic evolution to increase the size of the lattice to the desired model. Using the adiabatic theorem and Trotter error bounds, we provide sufficient conditions on the total evolution time and number of Trotter steps required for nucleation to prepare an initial state with desired fidelity. In addition, we introduce optimized nucleation which considers variational optimization on top of the nucleation structure. For a two-dimensional Ising model, we show that optimized nucleation can outperform a current leading method for state preparation on digital quantum computers.
We provide a new approach to adiabatic state preparation that uses coherent control and measurement to average different adiabatic evolutions in ways that cause their diabatic errors to cancel, allowing highly accurate state preparations using less time than conventional approaches. We show that this new model for adiabatic state preparation is polynomially equivalent to conventional adiabatic quantum computation by providing upper bounds on the cost of simulating such evolutions on a circuit-based quantum computer. Finally, we show that this approach is robust to small errors in the quantum control register and that the system remains protected against noise on the adiabatic register by the spectral gap.