Paper detail

Fast digital methods for adiabatic state preparation

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.