2020/04/08 by Kianna Wan, Wan, Kianna, Isaac H. Kim +1 · 3 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum and electron transport phenomena
paper · pdf · doi:10.48550/arxiv.2004.04164
openalex publication_date 2020/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 H0 and H1, exponentially suppressing the diabatic error by harnessing the theoretical concept of quasi-adiabatic continuation as an algorithmic tool. Given an upper bound α on ‖H0‖ and ‖H1‖ along with the promise that the kth eigenstate |ψk(s)⟩ of H(s) ≡ (1-s)H0 + sH1 is separated from the rest of the spectrum by a gap of at least γ> 0 for all s ∈ [0,1], this algorithm implements an operator \widetildeU such that ‖|ψk(1)⟩ - \widetildeU|ψk(s)⟩‖ ≤ ε using O(α2/γ2)polylog(α/γε) queries to block-encodings of H0 and H1. In addition, we develop an algorithm that is applicable only to ground states and requires multiple queries to an oracle that prepares |ψ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‖ 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 ‖H1 - H0‖/γ up to polylogarithmic factors.