# Measurement-based deterministic imaginary time evolution

Yuping Mao  State Key Laboratory of Precision Spectroscopy, School of Physical
and Material Sciences, East China Normal University, Shanghai 200062, China
New York University Shanghai, 1555 Century Ave, Pudong, Shanghai 200122, China
Manish Chaudhary  State Key Laboratory of Precision Spectroscopy, School of
Physical and Material Sciences, East China Normal University, Shanghai 200062,
China  New York University Shanghai, 1555 Century Ave, Pudong, Shanghai
200122, China  Manikandan Kondappan  State Key Laboratory of Precision
Spectroscopy, School of Physical and Material Sciences, East China Normal
University, Shanghai 200062, China  New York University Shanghai, 1555 Century
Ave, Pudong, Shanghai 200122, China  Junheng Shi  State Key Laboratory of
Precision Spectroscopy, School of Physical and Material Sciences, East China
Normal University, Shanghai 200062, China  New York University Shanghai, 1555
Century Ave, Pudong, Shanghai 200122, China  Ebubechukwu O. Ilo-Okeke  New
York University Shanghai, 1555 Century Ave, Pudong, Shanghai 200122, China
NYU-ECNU Institute of Physics at NYU Shanghai, 3663 Zhongshan Road North,
Shanghai 200062, China  Valentin Ivannikov  New York University Shanghai, 1555
Century Ave, Pudong, Shanghai 200122, China  NYU-ECNU Institute of Physics at
NYU Shanghai, 3663 Zhongshan Road North, Shanghai 200062, China  Tim Byrnes
<EMAIL_ADDRESS>New York University Shanghai, 1555 Century Ave, Pudong,
Shanghai 200122, China.  State Key Laboratory of Precision Spectroscopy,
School of Physical and Material Sciences, East China Normal University,
Shanghai, 200062, China.  NYU-ECNU Institute of Physics at NYU Shanghai, 3663
Zhongshan Road North, Shanghai, 200062, China.  National Institute of
Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan.
Department of Physics, New York University, New York, NY, 10003, USA.

###### Abstract

We introduce a method to perform imaginary time evolution in a controllable
quantum system using measurements and conditional unitary operations. Using a
Suzuki-Trotter decomposition, a sequence of measurements can produce the
evolution approximating imaginary time evolution of an arbitrary Hamiltonian,
up to a random sign coefficient. The randomness due to measurement is
corrected using conditional unitary operations, making the evolution
deterministic. The number of gates for a single iteration typically scales as
a polynomial of the number of qubits in the system. We demonstrate the
approach with several examples, including the transverse field Ising model and
quantum search.

### Introduction

Imaginary time evolution is an important and enduring concept in several areas
of quantum physics, despite not being directly a physical process Sakurai and
Commins (1995). In imaginary time evolution (ITE) of a quantum system with
Hamiltonian $H$, time $t$ is replaced by imaginary time $t\rightarrow-i\tau$,
such that the evolution operator is $e^{-H\tau}$ Magnus (1954); Vidal (2007).
As such, for long evolution times, the state approaches the ground state of
the Hamiltonian Lin et al. (2021); Schuch et al. (2007). ITE can be directly
applied as a numerical procedure on classical computers to obtain low-energy
states McArdle et al. (2019); Chiofalo et al. (2000); Palpacelli et al.
(2007); Liu and Makri (2005). It is also central in making a formal connection
between a $d$-spatial dimensional quantum field theory and a $d+1$-dimensional
classical statistical mechanics system, through the Wick rotation Wick (1954);
Peskin (2018); Majid (1994). A variety of classical simulation methods take
advantage of this connection, such as quantum Monte Carlo and its variants
Vesely (1994); Lester Jr and Hammond (1990); Jarrell (1992); Baroni and Moroni
(1999); Byrnes et al. (2004).

As a numerical procedure on a classical computer, ITE requires exponential
resources that scale with the size of the Hilbert space. If there was a way of
implementing ITE on a quantum computer efficiently, this would potentially be
an extremely powerful tool. If the ITE operator $e^{-H\tau}$ could be directly
implemented, the complexity would scale with the number of terms in the
Hamiltonian (using for example a Suzuki-Trotter decomposition), giving an
exponential speedup in comparison to the classical simulation. In a quantum
simulation scenario, one is often interested in obtaining low-energy
eigenstates of various systems, applicable to condensed matter physics, high-
energy physics, and quantum chemistry Feynman (1982); Buluta and Nori (2009);
Georgescu et al. (2014); Cirac and Zoller (2012); Gerritsma et al. (2010);
O’Malley et al. (2016); Horikiri et al. (2016); Houck et al. (2012); Byrnes
and Ilo-Okeke (2021). More generally, it may also be used as a general
optimization tool, where a cost function is minimized Mohseni et al. (2022).
Applied to the context of solving the generalized Ising model, a problem that
can be mapped to any optimization problem in the complexity class NP in
polynomial time, the approach could be used to optimize problems in a variety
of contexts such as logistics, financial applications, artificial
intelligence, pharmaceutical and material development Lucas (2014); Tanahashi
et al. (2019); Smelyanskiy et al. (2012); Hauke et al. (2020). Another
application of ITE is as a state preparation protocol. For applications such
as measurement-based quantum computation Raussendorf and Briegel (2001) and
quantum metrology Giovannetti et al. (2011); Tóth and Apellaniz (2014); You et
al. (2017), resource states need to be generated, which are sometimes
difficult to produce. By engineering a suitable Hamiltonian where the desired
state is the ground state, ITE can be used to generate and stabilize the state
Tame et al. (2006); Bartlett and Rudolph (2006); Van den Nest et al. (2008);
Kyaw et al. (2014).

Several methods have been proposed to perform ITE in a controllable quantum
system. In Variational Imaginary Time Evolution (VITE) McArdle et al. (2019),
McArdle, Xiao and co-workers introduced a hybrid quantum-classical approach to
achieve ITE. Here, the Schrödinger equation is first solved in imaginary time
on a classical computer to determine the parameters of a trial state, then
this is used as the approximation of the quantum state for the quantum
circuit. This method has been used to simulate the spectra of Hamiltonian
Jones et al. (2019), perform generalized time evolution Endo et al. (2020),
and to solve quantum many-body problems Yuan et al. (2019). Motta, Chan and
co-workers proposed the Quantum Imaginary Time Evolution (QITE) method Motta
et al. (2020), where non-unitary time evolution is approximated by a unitary
operator which contains the variation of the quantum systems Yeter-Aydeniz et
al. (2020); Gomes et al. (2020); Tan (2020). This method has been applied to
the study of quantum simulation Nishi et al. (2021), nuclear energy level
computation Yeter-Aydeniz et al. (2020), and quantum chemistry Gomes et al.
(2020). In another approach, Williams proposed a probabilistic approach to
non-unitary quantum computing Williams (2004). For example, in Probabilistic
Imaginary Time Evolution (PITE) Liu et al. (2021), a $L$ qubit non-unitary
gate simulation can be probabilistically obtained by designing a $L+1$ qubit
system and measuring the ancilla qubit Gingrich and Williams (2004). When
measuring the ancilla qubit, the $L$-qubit state will collapse into the
desired state with a certain probability. PITE exploits Grover’s algorithm
Grover (1997) to enhance the probability of getting the desired state whiled
maintaining a high fidelity. PITE is promising in the field of quantum
chemistry (Kosugi et al., 2021). The above ITE methods can be applied in
various quantum algorithms. It has been shown that VITE can be applied to
variational quantum algorithms for Boltzmann machine learning Shingu et al.
(2021), while QITE can be applied to the QLanczos algorithm Motta et al.
(2020); Yeter-Aydeniz et al. (2021) and variational quantum algorithms for
Hamiltonian diagonalization Zeng et al. (2021).

In this paper, we propose a general method of performing ITE in a controllable
quantum system. Our method relies upon performing a measurements which mimics
the imaginary time evolution operator for small times. By performing a Suzuki-
Trotter decomposition of the exponentiated Hamiltonian, we reduce the ITE to a
sequence of measurements. This formulation allows for a arbitrary Hamiltonian
to be realized in terms of elementary operations, such that it is compatible
with many quantum computing systems. A key component of our approach is to
include a unitary correction step which acts conditionally on the measurement
outcome. Much like in quantum teleportation and other quantum feedforward
approaches, this converts the stochastic evolution into a deterministic one,
such that the desired state is obtained with unit probability for sufficiently
long evolution times Knill et al. (2001); Steffen et al. (2013); Ma et al.
(2012). In this way our approach differs to related works such as Refs. Liu et
al. (2021), where the desired outcome is obtained by postselection. It also
differs to approaches such as in Refs. McArdle et al. (2019); Motta et al.
(2020) since the use of measurements involves an explicitly non-unitary step.
As such, no precomputation needs to be performed to determine the evolution
path.

Figure 1: Schematic view of stabilization of states using measurements and
conditional unitary operations in Hilbert space for $N=2$. Long arrows show
the state evolution trajectories via application of one of the measurement
operators (a) $M_{00}\approx e^{-H_{00}\epsilon}/2$; (b) $M_{10}\approx
e^{-H_{10}\epsilon}/2$. Closed circles show the fixed points for the
measurement operators
$M_{\bm{k}}|E_{0}^{({\bm{k}})}\rangle\propto|E_{0}^{({\bm{k}})}\rangle$. Open
circle shows the target state $|{\cal T}\rangle$ which is stabilized by a
corrective unitary $U_{\bm{k}}$.

### General theory

We start by describing the general approach to performing imaginary time
evolution, then illustrate our approach with several examples. Our aim will be
to perform imaginary time evolution of a Hamiltonian $H=\sum_{j=1}^{N}H^{(j)}$
, such that we obtain the ground state

$\displaystyle
e^{-H\tau}|\psi_{0}\rangle\xrightarrow{\tau\rightarrow\infty}|E_{0}\rangle,$
(1)

where $|\psi_{0}\rangle$ is an arbitrary initial state and $|E_{0}\rangle$ is
the ground state of $H$. Here, $N$ is the number of terms in the Hamiltonian.
Our approach will be to perform a Suzuki-Trotter decomposition Suzuki (1993);
Kapit et al. (2012) such that

$\displaystyle
e^{-H\tau}\approx\left(\prod_{j=1}^{N}e^{-H^{(j)}\epsilon}\right)^{T}$ (2)

where $\epsilon=\tau/T$ and we take the convention that the product operator
performs the matrix multiplication in reverse order, i.e. $j=1$ to $j=N$ from
right to left. In order to perform the imaginary time evolution for the $j$th
term in the Hamiltonian, we approximate this by measurement operators that
take a similar form to the exponential factors in (2). One possible choice
that we will use here are the operators realizing a weak measurement

$\displaystyle M_{0}^{(j)}$ $\displaystyle=(I-\epsilon
H^{(j)})/\sqrt{2}\approx e^{-H^{(j)}\epsilon}/\sqrt{2}$ $\displaystyle
M_{1}^{(j)}$ $\displaystyle=\sqrt{I-{M_{0}^{(j)}}^{\dagger}M_{0}^{(j)}}\approx
e^{H^{(j)}\epsilon}/\sqrt{2}.$ (3)

These are measurement operators satisfying
${M_{0}^{(j)}}^{\dagger}M_{0}^{(j)}+{M_{1}^{(j)}}^{\dagger}M_{1}^{(j)}=I$,
where $I$ is the identity matrix. By adding a suitable additional energy
constant and normalizing the Hamiltonian $H$, we may define (3) such that the
operators are positive. The exponentiated form of the operators may be
verified by performing a low-order expansion of $\epsilon$. For $\epsilon\ll
1$, each of the measurement outcomes occur with a probability $\approx 1/2$. A
variety of methods could be used to implement such measurements, we give a
generic approach in the Supplementary Information. In short, an interaction
with the measurement apparatus of the form ${\cal H}=H^{(j)}\otimes Y$ can
realize such a measurement. Throughout this paper we denote Pauli spin
operators as $X,Y,Z$.

We may not simply replace the exponential factors in (2) by the measurement
operator $M_{0}^{(j)}$ since the outcomes occur randomly. Nevertheless let us
consider the sequence of measurements

$\displaystyle
M_{\bm{k}}\equiv\prod_{j=1}^{N}M_{k_{j}}^{(j)}\approx\frac{1}{\sqrt{2^{N}}}\prod_{j=1}^{N}e^{-(-1)^{k_{j}}H^{(j)}\epsilon}\approx\frac{e^{-\epsilon
H_{\bm{k}}}}{\sqrt{2^{N}}}$ (4)

where $\bm{k}=(k_{1},\dots,k_{N})$ and $k_{j}\in\\{0,1\\}$. According to (3),
this measurement sequence results in an exponential evolution with respect to
the Hamiltonian

$\displaystyle H_{\bm{k}}=\sum_{j}(-1)^{k_{j}}H^{(j)}.$ (5)

This is a modified version of the original Hamiltonian, where there is a sign
change on particular terms. For a fixed measurement sequence outcome $\bm{k}$,
the measurement sequence (4) drives an arbitrary state towards the state

$\displaystyle(M_{\bm{k}})^{T}|\psi_{0}\rangle\xrightarrow{T\rightarrow\infty}|E_{0}^{(\bm{k})}\rangle,$
(6)

where $|E_{0}^{(\bm{k})}\rangle$ is the fixed point of the operator
$M_{\bm{k}}$. Since $(M_{\bm{k}})^{T}\propto e^{-H_{\bm{k}}\tau}$, the state
$|E_{0}^{(\bm{k})}\rangle$ is approximately the ground state of (5), where the
approximation arises due to the Trotter expansion. In an physical setting
where the measurements (3) are being made, there will be a random sequence of
outcomes, labeled by $\bm{k}$. As depicted in Fig. 1, each instance of
$M_{\bm{k}}$ will pull the state towards the various fixed points in Hilbert
space. However, no convergence to a unique state is attained due to the random
nature of the outcomes.

With the additional ingredient of a unitary operator $U_{\bm{k}}$ applied
conditionally on the measurement outcomes, it is possible to stabilize
particular states in a dynamical way. Call the target state to be stabilized
$|{\cal T}\rangle$. We choose the $U_{\bm{k}}$, such that they satisfy

$\displaystyle U_{\bm{k}}M_{\bm{k}}|{\cal T}\rangle\propto|{\cal T}\rangle.$
(7)

This ensures that if the state of the quantum system reaches $|{\cal
T}\rangle$ it will stay in that state. For $|{\cal T}\rangle$ that is not an
eigenstate of $M_{\bm{k}}$, the stabilization works in a dynamical way. When a
measurement is performed, it will take the state away from $|{\cal T}\rangle$,
but $U_{\bm{k}}$ acts in such a way that it returns it back to $|{\cal
T}\rangle$.

One may ask at this point why the target state is not simply $|{\cal
T}\rangle=|E_{0}\rangle$, which would be the aim of the imaginary time
evolution. As we will explain further in the examples, this choice can be
problematic in designing a sequence that converges to a unique state. We will
see that it is advantageous to choose the target state to be a state that is a
close relation of the desired ground state

$\displaystyle|{\cal T}\rangle=V|E_{0}\rangle$ (8)

where $V$ is a readily available unitary operation. There is a freedom of
choice of the target state $|{\cal T}\rangle$ and unitaries $U_{\bm{k}},V$
because they are defined only with respect to (7) and (8). As such, the excess
degrees of freedom can be chosen at convenience according to what operations
are readily available.

Our final procedure is to perform the sequence

$\displaystyle|\psi_{T}\rangle\equiv
V^{\dagger}\left(\prod_{l=1}^{T}U_{\bm{k}_{l}}M_{\bm{k}_{l}}\right)|\psi_{0}\rangle\xrightarrow{T\rightarrow\infty}|E_{0}\rangle.$
(9)

That is, starting from a suitable initial state, a sequence of $N$
measurements are made, such that it realizes the combined measurement (4). A
unitary $U_{\bm{k}}$ is then applied, which stablizes the target state. This
is repeated $T$ times until convergence is attained. Finally, a corrective
unitary $V^{\dagger}$ is applied to obtain the desired ground state.

### Example 1: One qubit

We start with the simplest possible example of a single qubit with Hamiltonian
$H=-Z+I$, such that $N=1$. The measurement operators in this case are
$M_{0}=[(1-\epsilon)I+\epsilon Z]/\sqrt{2}$ and $M_{1}\approx[I-\epsilon
Z]/\sqrt{2}$. The fixed points of these operators are
$|E_{0}^{(0)}\rangle=|0\rangle,|E_{0}^{(1)}\rangle=|1\rangle$. We take the
target state to be $|{\cal
T}\rangle=V|0\rangle=|+\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$, where
$V=e^{-iY\pi/4}$.

Figure 2: Evolution of a qubit under the Hamiltonian $H=-Z+I$ with the scheme
(9). Vector map on the Bloch sphere for the change induced by the operator (a)
$U_{0}M_{0}$; (b) $U_{1}M_{1}$. (c) Fidelity of the state with respect to the
target state $|{\cal T}\rangle=|+\rangle$ after $T$ rounds of measurement and
correction under (9) for three random initial states (solid lines). Dashed
line show the averaged fidelity of 1000 evolutions starting from the initial
state $|-\rangle$. Inset shows the dependence of $\ln(1-F)$ with $T$. The
correction angles are $\theta_{0}=-0.22,\theta_{1}=0.15$. (d) Expectation
value of $Z$ after $T$ rounds of measurement under (9) for four random initial
states. Parameters used are $\epsilon=0.1$. For the measurements in (c)(d),
the outcomes are chosen randomly according to Born probabilities.

Let us first obtain some intuition about the state evolution. From the fact
that $M_{0}\approx e^{\epsilon Z}/\sqrt{2}$, it is clear that the effect of
$M_{0}$ is to drive all states towards the north pole of the Bloch sphere,
while $M_{1}$ drives all states to the south pole, following longitudinal
lines. In Fig. 2(a)(b) we show the evolution of the states on the Bloch sphere
after the combined application of the measurement and conditional unitary
operator $U_{0}M_{0}$ and $U_{1}M_{1}$. We see that the combination of the two
operations produces a pattern of evolution which tends to drive all states
towards the target state $|+\rangle$. Since both measurement outcomes have the
effect of driving the states towards the same fixed point $|+\rangle$, the
state converges to the target state deterministically as can be see in Fig.
2(c). Averaging over many random trajectories yields a smooth exponential
curve approaching the target state. A semilog plot (Fig. 2(c) inset) verifies
the exponential evolution, consistent with imaginary time evolution.

This simple example shows why the simpler strategy of making the target state
$|{\cal T}\rangle=|0\rangle$ does not give a sequence that deterministically
converges to the target state. Application of the measurement operators on
this target state gives $M_{k}|0\rangle\propto|0\rangle$ for both
$k\in\\{0,1\\}$. According to (7), this means that $U_{k}=I$. There are thus
two fixed points, equal to $|E_{0}^{(0)}\rangle=|0\rangle$ and
$|E_{0}^{(1)}\rangle=|1\rangle$. Since the measurement outcomes occur
typically with equal probability $0.5$, the evolution randomly evolves in the
north-south direction on the Bloch sphere. Due to the two fixed points, the
state converges randomly in each of these states, and does not converge to a
single state as desired (Fig. 2(d)).

Figure 3: Performance and parameters for imaginary time evolution of the
(a)(b) transverse Ising model and (c)(d) quantum search Hamiltonians. (a)(b)
show the fidelity of the state with respect to the target state $|{\cal
T}\rangle=e^{iY_{3}\pi/8}|E_{0}^{(00)}\rangle$ after $T$ rounds of measurement
and correction under (9) for three random initial states (solid lines). Dashed
lines show the averaged fidelity of 1000 evolutions. Cases shown are (a) $L=2$
for the initial state $|+-\rangle$; (b) $L=3$ with the initial state
$|++-\rangle$. (c) Correction operation angles for various values of
$\epsilon$. (d) Averaged fidelity over 1000 evolutions starting from the state
$|\perp\rangle\approx|+\rangle$ towards the target state $|{\cal
T}\rangle=(|S\rangle+|\perp\rangle)/\sqrt{2}$. Inset shows the average number
of iterations to reach 90% fidelity as a function of $\epsilon$.

### Example 2: Transverse-field Ising model

We next show a more non-trivial example involving non-commuting operators with
$N=2$. Consider the transverse-field Ising model with the Hamiltonian
$H^{(1)}=-\lambda\sum_{n=1}^{L}(X_{n}-1),H^{(2)}=-\omega\sum_{n=1}^{L-1}(Z_{n}Z_{n+1}-1),H=H^{(1)}+H^{(2)}$.
Here, $L$ is the number of qubits in the chain. The measurement operators are
$M^{(1)}_{k_{1}}\approx\prod_{n=1}^{L}e^{-(-1)^{k_{1}}\epsilon\lambda(X_{n}-1)}/\sqrt{2}$
and
$M^{(2)}_{k_{2}}\approx\prod_{n=1}^{L-1}e^{-(-1)^{k_{2}}\epsilon\omega(Z_{n}Z_{n+1}-1)}/\sqrt{2}$.
There are four fixed points $|E_{0}^{(k_{1}k_{2})}\rangle$ of the measurement
operator $M_{k_{1}k_{2}}=M^{(1)}_{k_{1}}M^{(2)}_{k_{2}}$. We take the target
state to be $|{\cal T}\rangle=e^{iY_{3}\pi/8}|E_{0}^{(00)}\rangle$. The
correction operators parametrized as
$U_{\bm{k}}=e^{i\sum_{n}\theta_{n}^{(\bm{k})}Y_{n}}e^{i\sum_{nm}\chi_{nm}^{(\bm{k})}Z_{n}Y_{m}}e^{i\sum_{n}\xi_{n}^{(\bm{k})}Y_{n}}$
such that (3) is satisfied. We show the fidelity of the procedure with respect
to the target state in Fig. 3(a)(b). Convergence is attained for all random
initial states chosen.

### Example 3: Quantum search

For our final example, we examine an application of ITE to quantum search.
Here the aim is to obtain the ground state of $H=-|S\rangle\langle S|$, where
$|S\rangle$ is the desired unknown solution state in the computational basis.
The Hilbert state dimension is $D$. As with Grover’s algorithm Grover (1996),
we initially prepare the state in an equal superposition state of all states
$|+\rangle=\sum_{n=1}^{D}|n\rangle$. For an ideal ITE, application of
$e^{-H\tau}|+\rangle\rightarrow|S\rangle$ in a timescale $\tau\sim O(1)$,
since the energy difference imposed by $H$ between $|S\rangle$ and the
remaining states is 1. If this were possible, this would allow for database
search with complexity that is independent of the Hilbert space size. This is
peculiar, since it would be an exponential improvement over all classical and
quantum algorithms, including Grover’s algorithm.

Similar to arguments proving Grover’s algorithm, the evolution of the state
remains in a two-dimensional subspace spanned by $|S\rangle$ and
$|\perp\rangle=\sum_{n\neq S}|n\rangle/\sqrt{D-1}$ Nielsen and Chuang (2002).
Thus in fact the evolution can be reduced to the qubit case of Example 1 with
the replacements $|0\rangle\rightarrow|S\rangle$ and
$|1\rangle\rightarrow|\perp\rangle$. The key difference to the qubit case is
that making the correction operation $U_{k}$ is non-trivial here, since we
would like to make a $Y$-rotation in the two-dimensional subspace without
knowledge of the state $|S\rangle$. Such a rotation is possible using the same
oracle and phase inversion operator familiar from Grover’s algorithm (see
Supplementary Information). The rotation angle on the Bloch sphere that is
possible is however limited by $D$, and is given by
$\theta=2\arcsin(1/\sqrt{D})\approx 2/\sqrt{D}$ Nielsen and Chuang (2002).
This limits the angle of the correction operation $U_{k}$, which in turn
limits the parameter $\epsilon$ appearing in the measurement operator. Fig.
3(c) shows the angular correction that is required for a given $\epsilon$,
which shows an approximately linear relation. In Fig. 3(d) we show the average
fidelity as a function of the iteration number $T$ for various values of
$\epsilon$. This shows an approximate scaling as $T\propto 1/\epsilon^{2}$.
Combining these relations we finally obtain a scaling as $T\propto D$, which
(reassuringly) shows that the scaling is still exponential with the qubit
number. It is interesting to see that the limiting factor for the ITE as a
search algorithm is eventually the necessity of performing the correction
operation. If this could be freely performed, then there would be no
exponential overhead to the quantum search.

### Conclusions

We have proposed a method of performing deterministic ITE, using measurements
and conditional unitary operations. Due to use of quantum measurements, the
evolution is stochastic within Hilbert space on a shot-to-shot basis.
Averaging over trajectories reveals an exponential evolution that is
consistent with ITE. One of the important tricks to make a deterministic
evolution is to assume a target state such that there is only one fixed point
for the combined measurement and correction evolution. We have applied our
methods to several key examples, such as the transverse field Ising model and
quantum search and found that in all cases the desired target state is
obtained for all initial conditions.

The gate complexity of a single iteration of our procedure typically scales
with the number of terms in the Hamiltonian to be simulated, which is
typically a polynomial of the number of qubits. For example, to implement the
measurement operators for the transverse field Ising model, $O(L)$ operations
are needed, and similarly for the correction operation. For the quantum search
example, to implement a phase inversion on a single state requires $O(L^{2})$
operations Nielsen and Chuang (2002); Byrnes et al. (2018). The total gate
complexity is $T$ times this, which depends upon what types of gates are
readily available. As we saw in the quantum search example, if only the oracle
and phase inversion operator is available, then $T$ scales exponentially with
the number of qubits. On the other hand, if it is assumed an arbitrary unitary
is possible, then $T$ is $O(1/\epsilon^{2})$, independent of the number of
qubits.

Our method is potentially applicable in a wide variety of contexts. For
example, in cold atomic systems the phase contrast imaging technique can
readout the total spin of an atomic ensemble in a weak measurement Ilo-Okeke
and Byrnes (2014, 2016). The general approach considered here can be used to
prepare singlet states deterministically Chaudhary and Byrnes (2022); Ilo-
Okeke and Byrnes (2022); Ilo-Okeke et al. (2018). An interesting future
direction is to investigate ITE as a general optimization scheme Mohseni et
al. (2022) for more complex energy spectra than the simple quantum search
problem shown here.

This work is supported by the National Natural Science Foundation of China
(62071301); State Council of the People’s Republic of China (D1210036A); NSFC
Research Fund for International Young Scientists (11850410426); NYU-ECNU
Institute of Physics at NYU Shanghai; the Science and Technology Commission of
Shanghai Municipality (19XD1423000); the China Science and Technology Exchange
Center (NGA-16-001); the NYU Shanghai Boost Fund.

## References

  * Sakurai and Commins (1995) J. J. Sakurai and E. D. Commins, _Modern quantum mechanics, revised edition_ (1995).
  * Magnus (1954) W. Magnus, Communications on pure and applied mathematics 7, 649 (1954).
  * Vidal (2007) G. Vidal, Physical review letters 98, 070201 (2007).
  * Lin et al. (2021) S.-H. Lin, R. Dilip, A. G. Green, A. Smith, and F. Pollmann, PRX Quantum 2, 010342 (2021).
  * Schuch et al. (2007) N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac, Physical review letters 98, 140506 (2007).
  * McArdle et al. (2019) S. McArdle, T. Jones, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan, npj Quantum Information 5, 1 (2019).
  * Chiofalo et al. (2000) M. L. Chiofalo, S. Succi, and M. Tosi, Physical Review E 62, 7438 (2000).
  * Palpacelli et al. (2007) S. Palpacelli, S. Succi, and R. Spigler, Phys. Rev. E 76, 036712 (2007).
  * Liu and Makri (2005) J. Liu and N. Makri, Molecular Physics 103, 1083 (2005).
  * Wick (1954) G.-C. Wick, Physical Review 96, 1124 (1954).
  * Peskin (2018) M. E. Peskin, _An introduction to quantum field theory_ (CRC press, 2018).
  * Majid (1994) S. Majid, Journal of Mathematical Physics 35, 5025 (1994).
  * Vesely (1994) F. J. Vesely, _Computational Physics_ (Springer, 1994).
  * Lester Jr and Hammond (1990) W. A. Lester Jr and B. L. Hammond, Annual Review of Physical Chemistry 41, 283 (1990).
  * Jarrell (1992) M. Jarrell, Physical review letters 69, 168 (1992).
  * Baroni and Moroni (1999) S. Baroni and S. Moroni, Physical review letters 82, 4745 (1999).
  * Byrnes et al. (2004) T. Byrnes, M. Loan, C. Hamer, F. D. Bonnet, D. B. Leinweber, A. G. Williams, and J. M. Zanotti, Physical Review D 69, 074509 (2004).
  * Feynman (1982) R. P. Feynman, International Journal of Theoretical Physics 21 (1982).
  * Buluta and Nori (2009) I. Buluta and F. Nori, Science 326, 108 (2009).
  * Georgescu et al. (2014) I. M. Georgescu, S. Ashhab, and F. Nori, Reviews of Modern Physics 86, 153 (2014).
  * Cirac and Zoller (2012) J. I. Cirac and P. Zoller, Nature physics 8, 264 (2012).
  * Gerritsma et al. (2010) R. Gerritsma, G. Kirchmair, F. Zähringer, E. Solano, R. Blatt, and C. Roos, Nature 463, 68 (2010).
  * O’Malley et al. (2016) P. J. O’Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, et al., Physical Review X 6, 031007 (2016).
  * Horikiri et al. (2016) T. Horikiri, M. Yamaguchi, K. Kamide, Y. Matsuo, T. Byrnes, N. Ishida, A. Löffler, S. Höfling, Y. Shikano, T. Ogawa, et al., Scientific reports 6, 1 (2016).
  * Houck et al. (2012) A. A. Houck, H. E. Türeci, and J. Koch, Nature Physics 8, 292 (2012).
  * Byrnes and Ilo-Okeke (2021) T. Byrnes and E. O. Ilo-Okeke, _Quantum atom optics: Theory and applications to quantum technology_ (Cambridge university press, 2021).
  * Mohseni et al. (2022) N. Mohseni, P. L. MacMahon, and T. Byrnes, Nature Reviews Physics (2022).
  * Lucas (2014) A. Lucas, Frontiers in physics 2, 5 (2014).
  * Tanahashi et al. (2019) K. Tanahashi, S. Takayanagi, T. Motohashi, and S. Tanaka, Journal of the Physical Society of Japan 88, 061010 (2019).
  * Smelyanskiy et al. (2012) V. N. Smelyanskiy, E. G. Rieffel, S. I. Knysh, C. P. Williams, M. W. Johnson, M. C. Thom, W. G. Macready, and K. L. Pudenz, arXiv preprint arXiv:1204.2821 (2012).
  * Hauke et al. (2020) P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, Reports on Progress in Physics 83, 054401 (2020).
  * Raussendorf and Briegel (2001) R. Raussendorf and H. J. Briegel, Physical Review Letters 86, 5188 (2001).
  * Giovannetti et al. (2011) V. Giovannetti, S. Lloyd, and L. Maccone, Nature photonics 5, 222 (2011).
  * Tóth and Apellaniz (2014) G. Tóth and I. Apellaniz, Journal of Physics A: Mathematical and Theoretical 47, 424006 (2014).
  * You et al. (2017) C. You, S. Adhikari, Y. Chi, M. L. LaBorde, C. T. Matyas, C. Zhang, Z. Su, T. Byrnes, C. Lu, J. P. Dowling, et al., Journal of Optics 19, 124002 (2017).
  * Tame et al. (2006) M. Tame, M. Paternostro, M. Kim, and V. Vedral, Physical Review A 73, 022309 (2006).
  * Bartlett and Rudolph (2006) S. D. Bartlett and T. Rudolph, Physical Review A 74, 040302 (2006).
  * Van den Nest et al. (2008) M. Van den Nest, K. Luttmer, W. Dür, and H. Briegel, Physical Review A 77, 012301 (2008).
  * Kyaw et al. (2014) T. H. Kyaw, Y. Li, and L.-C. Kwek, Physical Review Letters 113, 180501 (2014).
  * Jones et al. (2019) T. Jones, S. Endo, S. McArdle, X. Yuan, and S. C. Benjamin, Physical Review A 99, 062304 (2019).
  * Endo et al. (2020) S. Endo, J. Sun, Y. Li, S. C. Benjamin, and X. Yuan, Physical Review Letters 125, 010501 (2020).
  * Yuan et al. (2019) X. Yuan, S. Endo, Q. Zhao, Y. Li, and S. C. Benjamin, Quantum 3, 191 (2019).
  * Motta et al. (2020) M. Motta, C. Sun, A. T. Tan, M. J. O’Rourke, E. Ye, A. J. Minnich, F. G. Brandão, and G. K.-L. Chan, Nature Physics 16, 205 (2020).
  * Yeter-Aydeniz et al. (2020) K. Yeter-Aydeniz, R. C. Pooser, and G. Siopsis, npj Quantum Information 6, 1 (2020).
  * Gomes et al. (2020) N. Gomes, F. Zhang, N. F. Berthusen, C.-Z. Wang, K.-M. Ho, P. P. Orth, and Y. Yao, Journal of Chemical Theory and Computation 16, 6256 (2020).
  * Tan (2020) K. C. Tan, arXiv preprint arXiv:2009.12239 (2020).
  * Nishi et al. (2021) H. Nishi, T. Kosugi, and Y.-i. Matsushita, npj Quantum Information 7, 1 (2021).
  * Williams (2004) C. P. Williams, in _Quantum Information and Computation II_ (International Society for Optics and Photonics, 2004), vol. 5436, pp. 297–306.
  * Liu et al. (2021) T. Liu, J.-G. Liu, and H. Fan, Quantum Information Processing 20, 1 (2021).
  * Gingrich and Williams (2004) R. M. Gingrich and C. P. Williams (2004).
  * Grover (1997) L. K. Grover, Phys. Rev. Lett. 79, 325 (1997).
  * Kosugi et al. (2021) T. Kosugi, Y. Nishiya, and Y.-i. Matsushita, arXiv preprint arXiv:2111.12471 (2021).
  * Shingu et al. (2021) Y. Shingu, Y. Seki, S. Watabe, S. Endo, Y. Matsuzaki, S. Kawabata, T. Nikuni, and H. Hakoshima, Physical Review A 104, 032413 (2021).
  * Yeter-Aydeniz et al. (2021) K. Yeter-Aydeniz, G. Siopsis, and R. C. Pooser, New Journal of Physics 23, 043033 (2021).
  * Zeng et al. (2021) J. Zeng, C. Cao, C. Zhang, P. Xu, and B. Zeng, Quantum Science and Technology 6, 045009 (2021).
  * Knill et al. (2001) E. Knill, R. Laflamme, and G. J. Milburn, nature 409, 46 (2001).
  * Steffen et al. (2013) L. Steffen, Y. Salathe, M. Oppliger, P. Kurpiers, M. Baur, C. Lang, C. Eichler, G. Puebla-Hellmann, A. Fedorov, and A. Wallraff, Nature 500, 319 (2013).
  * Ma et al. (2012) X.-S. Ma, T. Herbst, T. Scheidl, D. Wang, S. Kropatschek, W. Naylor, B. Wittmann, A. Mech, J. Kofler, E. Anisimova, et al., Nature 489, 269 (2012).
  * Suzuki (1993) M. Suzuki, Physics Letters A 180, 232 (1993).
  * Kapit et al. (2012) E. Kapit, P. Ginsparg, and E. Mueller, Physical Review Letters 108, 066802 (2012).
  * Grover (1996) L. K. Grover, in _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ (1996), pp. 212–219.
  * Nielsen and Chuang (2002) M. A. Nielsen and I. Chuang, _Quantum computation and quantum information_ (2002).
  * Byrnes et al. (2018) T. Byrnes, G. Forster, and L. Tessler, Physical review letters 120, 060501 (2018).
  * Ilo-Okeke and Byrnes (2014) E. O. Ilo-Okeke and T. Byrnes, Physical review letters 112, 233602 (2014).
  * Ilo-Okeke and Byrnes (2016) E. O. Ilo-Okeke and T. Byrnes, Physical Review A 94, 013617 (2016).
  * Chaudhary and Byrnes (2022) M. Chaudhary and T. Byrnes, (in preparation) (2022).
  * Ilo-Okeke and Byrnes (2022) E. Ilo-Okeke and T. Byrnes, (in preparation) (2022).
  * Ilo-Okeke et al. (2018) E. O. Ilo-Okeke, L. Tessler, J. P. Dowling, and T. Byrnes, npj Quantum Information 4, 1 (2018).
  * Mitchison et al. (2007) G. Mitchison, R. Jozsa, and S. Popescu, Phys. Rev. A 76, 062105 (2007).
  * Svensson (2013) B. E. Svensson, Quanta 2, 18 (2013).
  * Korotkov and Averin (2001) A. Korotkov and D. Averin, Physical Review B 64, 165310 (2001).
  * Lloyd (1995) S. Lloyd, Physical Review Letters 75, 346 (1995).

##  I Implementation of weak measurements

Numerous methods for realizing weak measurements exist and could be adapted
for our proposed method Mitchison et al. (2007); Svensson (2013); Korotkov and
Averin (2001). Since the way measurements are performed tends to depend
greatly upon the particular implementation, here we show a generic approach
which may be used as a starting point to obtain the desired measurement. It
may also be used more literally as an ancilla based scheme. Consider a
measurement apparatus giving a two-valued pointer state outcomes
$|P_{0}\rangle,|P_{1}\rangle$. If we wish to implement the measurements (3)
with the Hamiltonian $H^{(j)}$ then we apply a system-apparatus Hamiltonian of
the form ${\cal H}=H^{(j)}\otimes Y_{P}$ to a pointer state initially prepared
in $|P_{+}\rangle=(|P_{0}\rangle+|P_{1}\rangle)/\sqrt{2}$, where $Y_{P}$ is a
Pauli matrix on the measurement apparatus. Evolving the Hamiltonian for a time
$\epsilon$ and performing the measurement then gives (3). For example, for a
qubit Hamiltonian $H^{(j)}=-Z$, the system and apparatus evolves as

$\displaystyle e^{-i{\cal
H}\epsilon}(\alpha|0\rangle+\beta|1\rangle)|P_{+}\rangle$ (10)
$\displaystyle=$
$\displaystyle[\alpha\cos(\tfrac{\pi}{4}-\epsilon)|0\rangle+\beta\sin(\tfrac{\pi}{4}+\epsilon)|1\rangle]|P_{0}\rangle$
$\displaystyle+[\alpha\sin(\tfrac{\pi}{4}-\epsilon)|0\rangle+\beta\cos(\tfrac{\pi}{4}+\epsilon)|1\rangle]|P_{1}\rangle$
$\displaystyle\approx$ $\displaystyle\frac{1}{\sqrt{2}}(\alpha
e^{\epsilon}|0\rangle+\beta
e^{-\epsilon}|1\rangle)|P_{0}\rangle+\frac{1}{\sqrt{2}}(\alpha
e^{-\epsilon}|0\rangle+\beta e^{\epsilon}|1\rangle)|P_{1}\rangle,$

since
$\cos(\tfrac{\pi}{4}\mp\epsilon)=\sin(\tfrac{\pi}{4}\pm\epsilon)\approx(1\pm\epsilon)/\sqrt{2}\approx
e^{\pm\epsilon}$. When the measurement collapses the states to the pointer
states, we obtain the outcomes of the measurement as given in (3).
Alternatively, the pointer states may be considered to be an ancilla qubit,
and a projective measurement of (10) in the $|P_{0}\rangle,|P_{1}\rangle$
basis constitutes the weak measurement.

##  II Grover iterations for conditional unitary

Here we show that the oracle and phase inversion operations in Grover’s
algorithm can implement arbitrary $Y$-rotations in the space of $|S\rangle$
and $|\perp\rangle$.

Firstly the oracle is by definition a unitary operation that applies a $-1$
phase to the solution state, and can be written

$\displaystyle O$ $\displaystyle=I-2|S\rangle\langle S|$
$\displaystyle=e^{-iH_{O}\pi},$ (11)

where we defined the oracle Hamiltonian

$\displaystyle H_{O}=-|S\rangle\langle S|=-\frac{1}{2}(I+Z).$ (12)

Meanwhile the phase inversion operator is

$\displaystyle G$ $\displaystyle=I-2|+\rangle\langle+|$
$\displaystyle=e^{-iH_{G}\pi}$ (13)

where the equal superposition state can be written

$\displaystyle|+\rangle=\frac{1}{\sqrt{D}}|S\rangle+\sqrt{\frac{D-1}{D}}|\perp\rangle.$
(14)

We defined the phase inversion Hamiltonian

$\displaystyle H_{G}$ $\displaystyle=-|+\rangle\langle+|$
$\displaystyle=-\frac{I}{2}+\frac{(D-2)}{2D}Z-\frac{\sqrt{D-1}}{D}X.$ (15)

We may see why a single iteration of Grover’s algorithm produces a $Y$-axis
rotation by directly multiplying the two operators. First we can rewrite

$\displaystyle O$ $\displaystyle=I+2H_{O}$ $\displaystyle=-Z$ (16)

and

$\displaystyle G$ $\displaystyle=I+2H_{G}$
$\displaystyle=\frac{(D-2)}{D}Z-2\frac{\sqrt{D-1}}{D}X.$ (17)

Now we may easily evaluate

$\displaystyle GO=\frac{(D-2)}{D}I-2i\frac{\sqrt{D-1}}{D}Y$ (18)

which is a unitary rotation around the $Y$-axis.

Equation (18) performs a fixed angle rotation around the $Y$-axis, but for a
general correction operation we may desire some other angles. Using the
arguments in Ref. Lloyd (1995) and the Hamiltonians $H_{O}$ and $H_{G}$, it is
possible to perform an arbitrary angle rotation. Making use of the relation

$\displaystyle\left(e^{-iH_{O}\sqrt{\phi/n}}e^{-iH_{G}\sqrt{\phi/n}}e^{iH_{O}\sqrt{\phi/n}}e^{iH_{G}\sqrt{\phi/n}}\right)^{n}\approx
e^{[H_{O},H_{G}]\phi}$ (19)

for large $n$, it is possible to produce an arbitrary angle rotation for the
operator

$\displaystyle i[H_{O},H_{G}]=-\frac{\sqrt{D-1}}{D}Y.$ (20)

In the interest of minimizing the gate count, it is desirable to produce the
largest rotations as possible. In this sense (18) is rather efficient, as it
only requires a single call of the oracle. For this reason, when performing
our complexity analysis we use this best-case scenario, which still gives an
exponential overhead.