Fast digital methods for adiabatic state preparation

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 $\alpha$ on $\Vert H_0\Vert$ and $\Vert H_1\Vert$ along with the promise that the $k$th eigenstate $|{\psi }_k(s)⟩$ of $H(s)\equiv (1-s)H_0+s{H}_1$ is separated from the rest of the spectrum by a gap of at least $\gamma >0$ for all $s\in [0,1]$, this algorithm implements an operator $\tilde{U}$ such that $\Vert |{\psi }_k(1)⟩-\tilde{U}|{\psi }_k(s)⟩\Vert \le \epsilon$ using $O({\alpha }^2/{\gamma }^2)\text{polylog}(\alpha /\gamma \epsilon )$ 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 $|{\psi }_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 $\Vert H_1-H_0\Vert$ is small compared to $\alpha$, or when more information about the gap of $H(s)$ is available. For certain problems, the scaling can even be improved to linear in $\Vert H_1-H_0\Vert /\gamma$ up to polylogarithmic factors.

50 pages, 8 figures

References in corpus (7)

• Simulating Hamiltonian dynamics with a truncated Taylor series
• Creating superpositions that correspond to efficiently integrable probability distributions
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Optimizing Quantum Circuits for Arithmetic
• Asymptotically Efficient Quantum Karatsuba Multiplication
• Quantum adiabatic optimization without heuristics

Cited by in corpus (5)

• Quantum simulation of gauge theory via orbifold lattice
• Improved machine learning algorithm for predicting ground state properties
• Success of digital adiabatic simulation with large Trotter step
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• Quantum adiabaticity in many-body systems and almost-orthogonality in complementary subspace