Understand
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 $\|H_0\|$ and $\|H_1\|$ along with the promise that the $k$th eigenstate $|\psi_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 $\gamma > 0$ for all $s \in [0,1]$, this algorithm implements an operator $\widetilde{U}$ such that $\||\psi_k(1)\rangle - \widetilde{U}|\psi_k(s)\rangle\| \leq \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)\rangle$, but has slightly better scaling in all parameters.