Adiabatic quantum imaginary time evolution

A central step in the quantum simulation of physical systems is to prepare a relevant initial state. Taking ground-state simulation as an example, we typically wish to prepare a state with sufficient overlap with the desired ground-state $\left|\Psi_{0}\right\rangle$ of a Hamiltonian $H$. In the context of near-term quantum algorithms Preskill (2018), which minimize both qubits/ancillae and gate resources, many protocols for such ground-state preparation have been proposed. Examples include variational ansatz preparation Bauer et al. (2020); Peruzzo et al. (2014); Farhi et al. (2014); McClean et al. (2016); Schön et al. (2007); Romero et al. (2018), adiabatic state preparation (ASP) Albash and Lidar (2018); Babbush et al. (2014); Veis and Pittner (2014), and variational McArdle et al. (2019) and quantum imaginary time evolution (QITE) Motta et al. (2020); Sun et al. (2021); Yeter-Aydeniz et al. (2020); Gomes et al. (2020); Nishi et al. (2021); Kamakari et al. (2022); Yeter-Aydeniz et al. (2022), the latter being the subject of this work.

Because ground-state preparation is in general formally hard, all these methods rely on some assumptions. For example, ASP starts from an initial Hamiltonian $H(0)$, whose ground-state is simple to prepare, and defines an adiabatic path $H(s),0\leq s\leq 1$ with $H(1)\equiv H$, the desired Hamiltonian Farhi et al. (2000). To prepare the ground-state to sufficient accuracy, $H(s)$ must change slowly; an estimate of the adiabatic runtime is Messiah (2014); Albash and Lidar (2018) $T\sim\max_{s,j}\frac{\left|\left\langle\Psi_{j}(s)\right|dH/ds\left|\Psi_{0}(s)\right\rangle\right|}{\Delta^{2}}$, where $\left|\Psi_{0}(s)\right\rangle$, $|\Psi_{j}(s)\rangle$, with $j\geq 1$, denote the instantaneous ground and excited states of $H(s)$ and $\Delta(s)$ is the energy gap between the ground-state and the first excited state. For ASP to be efficient, $H(s)$ must be chosen such that $\min_{s}\Delta(s)$ is not too small, e.g. at worst $1/\mathrm{poly}(L)$ in system size $L$, for a polynomial cost algorithm.

The QITE algorithm Motta et al. (2020) on the other hand, applies $e^{-H\tau}$ ($\tau>0$) to boost the overlap of a candidate state with the ground-state of $H$; for this work, we consider Hamiltonians that are sums of local terms $H=\sum_{\alpha}h_{\alpha}$, where $h_{\alpha}$ is geometrically local (i.e. each term $h_{\alpha}$ acts on a constant number of adjacent qubits regardless of system size). Ref. Motta et al., 2020 introduced a near-term quantum algorithm to obtain the states

without employing any ancillae or postselection. The method is efficient if $|\Psi(\tau)\rangle$ has finite correlation volume $C$ for all earlier imaginary times, in which case $|\Psi(\tau)\rangle$ can be prepared by implementing a series of local unitaries acting on $O(C)$ qubits on the candidate state. By using this technique which reproduces the imaginary time trajectory, one can also use QITE as a subroutine in other ground-state algorithms, as well as to prepare non-ground-states and thermal (Gibbs) states, for example by reintroducing ancillae Kamakari et al. (2022), or by sampling Motta et al. (2020).

However, to find the unitaries in QITE one needs to perform tomography Motta et al. (2020) of the reduced density matrices of $|\Psi(\tau)\rangle$ over regions of volume $C$. Although the measurement and processing cost is polynomial in system size, it can still be prohibitive for large $C$. Despite various improvements in the QITE idea in terms of the algorithm and implementation, this remains a practical drawback Sun et al. (2021). (We briefly note also some other near-term imaginary time evolution algorithms, such as the variational ansatz-based quantum imaginary time evolution, introduced in Ref. McArdle et al. (2019), which reproduces the imaginary time evolution trajectory in the limit of an infinitely flexible variational ansatz, as well as the probabilistic imaginary time evolution algorithm (PITE) Kosugi et al. (2022), whose probability of success decreases exponentially with evolution time).

Here, we introduce an alternative near-term, ancilla-free, quantum method that generates the imaginary time evolution of a quantum state without any tomography. It thus eliminates one of the resource bottlenecks of the original QITE. The idea is to consider the imaginary time trajectory $\Psi(\tau)$ as generated by an adiabatic process under a particular Hamiltonian $\tilde{H}(\tau)$. This adiabatic Hamiltonian is approximated by the solution of an auxiliary dynamical equation that can be solved for entirely classically, i.e. without any feedback from the quantum simulation. Although propagation under $\tilde{H}$ reproduces imaginary time evolution when performed adiabatically (i.e., one stays in the ground-state of $\tilde{H}(\tau)$), this is different to the usual ASP, because $\tilde{H}$ does not approach $H$ at the end of the path, even though it shares the same final ground-state. We thus refer to this algorithm as adiabatic quantum imaginary time evolution, or A-QITE.

Like QITE, the application of A-QITE for sufficiently long imaginary time formally prepares the ground-state. But also like QITE, the imaginary time trajectory generated by A-QITE has other applications. The ability to reproduce non-unitary evolution enables applications to Lindblad simulation Kamakari et al. (2022), while for finite imaginary time, it can naturally be applied to prepare thermal states (either in a purified formulation Kamakari et al. (2022) or via sampling Motta et al. (2020); Sun et al. (2021)) or be used in a subspace expansion method for excited states Motta et al. (2020). Generally speaking, the A-QITE algorithm turns the preparation of any state that can be reached by the differential evolution of an initially known ground-state into an adiabatic state preparation process. In this work, however, we primarily focus on the generation of the imaginary time trajectory itself, and its long-time limit relevant to physical ground-state preparation.

We examine the feasibility and performance of A-QITE for the illustrative case of the Ising-like Heisenberg XXZ model in a transverse field. There we study the behaviour of the instantaneous gap and norm of $\tilde{H}$ as a function of imaginary time (as these determine the cost of integrating the classical equation to determine $\tilde{H}$ as well to implement the adiabatic quantum simulation under $\tilde{H}$). $\tilde{H}(\tau)$ becomes increasingly non-local with time, and we introduce a geometric locality heuristic to truncate terms in $\tilde{H}$, which we compare to the original inexact QITE procedure. We finish with some observations on the cost and practical implementation of the algorithm.

We now study the imaginary time trajectory generated by the $\tilde{H}$ dynamics, including the locality and gauge modifications described above. We classically propagate $\tilde{H}$ by a second-order Runge-Kutta method ¹¹1In the same fashion as Ref. Motta et al. (2020), we take the effect of separate terms of $H$ into account separately for $\tilde{H}$, so each time step consists of a sequence of substeps, each one propagating for time $\epsilon$ with a single term of $H$. with a finite time step $\epsilon$ (error $O(\epsilon^{3})$ per time-step; note we use $\epsilon$ rather than $d\tau$ here to emphasize a finite step) and then diagonalize $\tilde{H}(\tau)$ to study the trajectory of the ground-state $\Phi_{0}(\tau)$. We then monitor various quantities, such as $||\tilde{H}(\tau)||$, the gap $\tilde{\Delta}(\tau)$, the infidelity with the exact imaginary time propagated state $I^{\tau}(\tau)=1-|\langle\tilde{\phi}_{0}(\tau)|\Psi(\tau)\rangle|^{2}$, and the infidelity with the ground-state of $H$, $I^{\infty}(\tau)=1-|\langle\tilde{\phi}_{0}(\tau)|\Psi(\infty)\rangle|^{2}$, i.e. the outcome of the infinite imaginary time evolution.

We study the antiferromagnetic Heisenberg XXZ model in one dimension with open boundary conditions:

with $\lambda_{z}=2$ which results in an Ising-like anisotropy. To generate a simple initial state, we initialize the adiabatic Hamiltonian $\tilde{H}$ as a staggered transverse field: $\tilde{H}(\tau=0)=\sum_{j}\left[(-1)^{j}S^{x}_{j}+\frac{1}{2}\right]$ (where each term in brackets separately annihilates the ground-state); the resulting initial state is thus a product state. We then determine $\tilde{H}$ under the dynamics generated by Eqs. (4), (6), and  (7), and study various properties of $\tilde{H}$ and its instantaneous ground-state $\tilde{\phi}_{0}(\tau)$ which is intended to produce the imaginary-time trajectory. $\tilde{H}$ has the symmetry $\prod_{i}S^{x}_{i}$, under which $\tilde{\phi}_{0}(\tau)$ has a definite eigenvalue. Note that $H_{\lambda_{z}=2}$ has symmetry broken ground-states with long range order Orbach (1958); Mikeska and Kolezhuk (2004), but we take $\left|\Psi(\infty)\right\rangle$ to belong to the same symmetry sector as $\tilde{\phi}_{0}(\tau)$.

In Fig. 1 we first consider $\tilde{H}$ generated by Eq. (4), and the infidelities $I(\tau)$, $I^{\infty}(\tau)$, $||\tilde{H}(\tau)||$ and $\tilde{\Delta}(\tau)$ as a function of time-step $\epsilon$ used in the classical integration of Eq. (4). As seen, for all step-sizes, at early times the infidelity with the ground-state of $H$, $I^{\infty}(\tau)$, decreases exponentially quickly, to $10^{-2}$ or less. (Although this is a small system, we note that achieving finite infidelities of $O(10^{-1})$ is already important for ground-state preparation applications as it enables variants of quantum phase estimation adapted to the near-term setting Ding and Lin (2023)). The achieved infidelities decrease as $\epsilon$ is decreased towards an infinitesimal step size in the classical integrator, which would give $I^{\tau}(\tau)=0$ at all times and $I^{\infty}(\tau)\to 0$ at long times. For a finite step size $\epsilon$, we see $I^{\infty}(\tau)$ reaches a minimum value while $I^{\tau}(\tau)$ first increases with time, reaches a maximum and then plateaus. The time for the minimum $I^{\infty}$ is close to (slightly after) the time for the maximum $I^{\tau}$; we refer to this (approximate) time as $\tau_{c}$. $||\tilde{H}||$ increases exponentially, while $\tilde{\Delta}$ decreases exponentially until about $\tau_{c}$, before slowly increasing again. The above is consistent with our analysis that for a finite time-step it is only possible to determine the adiabatic Hamiltonian accurately up to a maximum time $\tau_{c}$ .

We next study $\tilde{H}$ generated by the exact Eq. (6), i.e. without enforcing locality, as a function of system size $L$, and a fixed classical time step $\epsilon=0.05$ in Fig. 2. The results are similar to those using $\tilde{H}$; both formally generate the exact imaginary-time trajectory for infinitesimal step size. Using a finite time-step, examining $I^{\infty},I^{\tau}$, we see the same behaviour of reaching a minimum $I^{\infty}$ and a maximum $I^{\tau}$ at some approximate time $\tau_{c}$. Surprisingly, this does not seem to change the maximum reliable propagation time, $\tau_{c}\approx 1.8$, between $L=6-12$.

The above two numerical studies illustrate the formal exactness of the A-QITE procedure, as well as the numerical challenges in its implementation arising from the behaviour of $||\tilde{H}(\tau)||$ and $\tilde{\Delta}(\tau)$. We now study the impact of heuristics at controlling these quantities. We first apply the locality heuristic for the generation of $\tilde{H}$, implemented using Eq. (6) with finite width $w=5$ in Fig. 3. We study range of system sizes and integration time-steps. Although the finite width means that we no longer follow the imaginary-time trajectory exactly (even for infinitesimal time step), we still see exponential decay of the infidelity with the ground-state to useful values of $\sim 10^{-2}$ or less. Overall, the infidelity dynamics shows similar behaviour to previous examples, and at longer times there is a $\tau_{c}$ corresponding to a change in the behaviour of the infidelities and gaps. However, as the time-step goes to $0$, the minimum $I_{\infty}$ does not keep decreasing, because of the finite width error. From the perspective of the classical integration and quantum implementation, the dynamics generated under the locality heuristic is much more favourable than under the exact A-QITE $\tilde{H}$ dynamics. In particular, $\|\tilde{H}\|$ grows orders of magnitude more slowly with $\tau$, and (for fixed $\tau$) close to linearly with $L$, while $\tilde{\Delta}$ appears to decrease like $\mathrm{poly}(1/L)$.

In Fig. 4, we show $\tilde{H}$ generated by Eq. (6), using the locality heuristic with widths $3,5,7$, and timestep $\epsilon=0.05$, as well as a protocol where the width is increased at increasing times. For comparison, we also show data from the original quantum imaginary time evolution scheme with widths $2,4,6$ and for time step $\epsilon=0.08$. As expected, the best achievable fidelity with the exact state $I^{\infty}(\tau)$ increases with $w$, however, the best $I(\infty)$ in fact decreases moving from $w=5$ to $w=7$. Compared to the original QITE scheme, the achievable infidelity appears to be better (i.e. lower) using the adiabatic Hamiltonian $\tilde{H}$ with a similar locality definition. Further work is required to establish a more precise relationship between these approximations.

We additionally consider the modified $\tilde{H}$ generated in a different gauge using Eq. (7). As an illustrative example, we consider the case $u_{1}=1/2$, $u_{2}=2$, with the locality constraint $w=5$. In Fig. 5, we see that although the behaviour of the infidelities $I_{\infty}$ and $I^{\tau}$ are qualitatively similar to what we have seen previously (corresponding to $u_{1}=u_{2}=0$) with a similar $\tau_{c}$, the detailed form is different; for example, the infidelity has a flatter plateau region. In addition, $||H||$ grows even more slowly with $\tau$ (with a flattened region between $\sim 1<\tau<3$) while still being close to linear in $L$, while $\Delta$ (at $\tau_{c}$) again appears to have a $\mathrm{poly}(1/L)$ behaviour. This indicates that a suitable choice of $f(u)$ can meaningfully modify the dynamics and the achievable infidelities at finite times.

We now briefly discuss the implications for implementations in the near-term setting. For a given width $w$ and Trotter time-step, the gate cost of implementing an A-QITE time-step is the same as that of QITE, namely it is the cost to implement a time-step under a $w$-qubit unitary, and importantly the A-QITE time-step requires no measurements. However, one difference with the original QITE is the need to maintain adiabaticity during the A-QITE simulation, which governs the time of Hamiltonian simulation for the given $\tau$. The (limited) numerical data above on the scaling of $\tilde{H}$ and $\tilde{\Delta}$ when using the heuristic modifications in the Ising problem suggests that (for given $\tau$) the total adiabatic evolution time is polynomial in system size (as $||H||,||\tilde{H}||$ scale like $\mathrm{poly}(L)$ and $\tilde{\Delta}\sim\mathrm{poly}(1/L)$). The Hamiltonian simulation is still likely the most challenging aspect of the algorithm for near-term hardware. However, for modest widths, e.g. $w=3$, implementing the A-QITE protocol is similar to implementing ASP with geometric 3-local Hamiltonians, which has already been demonstrated on near-term hardware using error mitigation and circuit recompilation Tan et al. (2023). Alternatively, it may be beneficial to relax the adiabaticity requirement by employing A-QITE within a version of the quantum approximation optimization algorithm (QAOA) Farhi et al. (2014); Blekos et al. (2024), where $\tilde{H}$ provides the form of the operators in the ansatz.

We have described an adiabatic state preparation protocol that implements the imaginary time evolution trajectory without any need for quantum tomography or ancilla resources. This hybrid algorithm involves a classical time integration to generate the adiabatic Hamiltonian, but does not require any measurements on the quantum system. When implemented faithfully, the algorithm leads to an exponential decrease of the infidelity with the ground-state of a desired Hamiltonian with adiabatic time. However, the cost of evolving exactly to long imaginary times grows rapidly with imaginary time both in the classical and quantum parts of the protocol. The growth in cost as a function of imaginary time arises from several sources, including the nonlocality of the derived adiabatic Hamiltonian. We introduce a heuristic to control this nonlocality by truncating terms in the adiabatic Hamiltonian. Another source of growing cost at long imaginary time is related to the norm of the adiabatic Hamiltonian and its gap. We show that modifying the generating equation of the adiabatic Hamiltonian can be used to control these quantities at finite imaginary times. Both heuristics enable one to propagate for short times and to observe a large improvement in the approximate ground-state.

In the near-term quantum hardware setting, one advantage of the current approach is that each time-step can be implemented without measurements. On the other hand, preserving the strict adiabatic formulation may lead to long Hamiltonian simulation times for some problems.

More generally, the A-QITE procedure we have introduced extends the types of states that be generated using an adiabatic simulation protocol; the target state need not be expressed as the ground-state of a known Hamiltonian, but rather can be expressed implicitly through the differential evolution of a known ground-state. In addition, with respect to standard ground-state adiabatic state preparation, A-QITE expands the set of possible adiabatic paths. This potentially allows for introduction of new quantum adiabatic routines consisting of composite adiabatic paths (with A-QITE as one of them) with applications such as the introduction of novel adiabatic catalysts Albash and Lidar (2018); Farhi et al. (2002), as directions to be explored in the future.

We thank Yu Tong, Alex Dalzell and Anthony Chen for helpful discussions.
KH and GKC were supported by the US Department of Energy, Office of Science, Basic Energy Sciences, under grant no. DE-SC-0019374. GKC acknowledges support from the Simons Foundation.