Quantum algorithm for spectral projection by measuring an ancilla iteratively

We propose a quantum algorithm for projecting a quantum system to eigenstates of any Hermitian operator, provided one can access the associated control-unitary evolution for the ancilla and the system, as well as the measurement of the controlling ancillary qubit. Such a Hadamard-test-like primitive is iterated so as to achieve the spectral projection, and the distribution of the projected eigenstates obeys the Born rule. This algorithm can be used as a subroutine in the quantum annealing procedure by measurement to drive the system to the ground state of a final Hamiltonian, and we simulate this for quantum many-body spin chains.

Figure 1

Basic picture of our algorithm. (a) The primitive: one ancilla is used as the control qubit for the control unitary, which is jointly applied to the ancilla and the system, $\mathrm{cU}=|0\rangle \langle 0|\otimes I+|1\rangle \langle 1|\otimes e^{-i\mathrm{\Delta }t\widehat{h}}$, followed by a measurement on the ancilla in the $X\equiv {\sigma }^x$ basis. (b) Summary of the action on the input system state: $|{\psi }_m^{\prime }\rangle \sim e^{{\widehat{Q}}_m}|\psi \rangle$. This leads to a random-walk picture for the algorithm.

Figure 2

The iteration procedure using various choices of $\mathrm{\Delta }t$ (arbitrary unit) and $\varphi$. See the main text for detailed discussions of the four types of choices I–IV. In (a) the energy is in an arbitrary unit and the values are recorded in the iteration; in (b) the energy variances (also in arbitrary units) are recorded.

Figure 3

The iteration procedure using various choices of $\mathrm{\Delta }t$ (arbitrary unit) and $\varphi$ similar to those in Fig. 2, except that $\alpha =\sqrt{3}/2$ and $\beta =1/2e^{i\varphi }$. See the main text for detailed discussions of the four types of choices I–IV. In (a) the energy values (arbitrary unit) are recorded in the iteration; in (b) the energy variances (also in arbitrary units) are recorded.

Figure 4

The iteration procedure using varying $\mathrm{\Delta }t$ and random $\varphi$. This corresponds to the choice IV in the main text. Here, $\mathrm{\Delta }t$ is chosen from the set $\{100,100/3,100/3^2,100/3^3,100/3^4,100/3^5\}$, but perturbed by 1% of random fluctuations: $\mathrm{\Delta }t\to \mathrm{\Delta }t(1+0.01x)$ with $x\in [0,1)$. There are four different runs but with the same initial state of the system. In (a) the energy values are recorded in the iteration; in (b) the energy variances are recorded. Both the energy and its variance are displayed in arbitrary units.

Figure 5

Eigenstates distribution $p_n$ after the procedure (simulations vs ideal Born rule). The Born rule predicts that $p_n={\left|\langle E_n|{\psi }_0\rangle \right|}^2$. The model under consideration is the $H_5$ Hamiltonian in Eq. (21) with the initial state in Eq. (22). The horizontal axis $n$ labels the index of eigenstates with eigenenergies ($E_n$) ordered from the lowest to the highest. $\mathrm{\Delta }t\in \{100,100/3,100/3^2,100/3^3,100/3^4,100/3^5\}$ and $\varphi$ is chosen randomly each time in $[0,2\pi )$, and for each $\mathrm{\Delta }t$ value we iterate five times. Each run is terminated when $\langle {\left(\mathrm{\Delta }h\right)}^2\rangle <{10}^{-10}$ and if more iterations are needed when all values in the $\mathrm{\Delta }t$ list are used we recycle the $\mathrm{\Delta }t$ list from the beginning. The statistics were obtaining by averaging over 10 000 runs. The final distribution obtained from the simulations is $\{0.5557,0.0733,0.2617,0.0077,0.1016\}$.

Figure 6

Histograms of the number of iterations to reach an eigenstate with an accuracy $\langle {\left(\mathrm{\Delta }h\right)}^2\rangle <{10}^{-10}$.

Figure 7

Example simulations on spectral projection for the five-qubit transverse-field Ising model. (a, b) Traces of energy and its variance in arbitrary units, respectively. There are three different runs (but with the same initial state of the system). Each run is terminated when $\langle {\left(\mathrm{\Delta }h\right)}^2\rangle <{10}^{-10}$. The phase parameter $\varphi$ in the ancilla state is chosen randomly at each step and $\mathrm{\Delta }t$ is chosen from the set $\{100,100/3,100/3^2,100/3^3,100/3^4,100/3^5\}$ and each $\mathrm{\Delta }t$ repeated five times. The iterations continue by recycling the $\mathrm{\Delta }t$ set until the desired precision is met. (c) The bottom panel compares the distribution of projected eigenstates in 10 000 simulation runs with the ideal Born rule.

Figure 8

Energy variance (in arbitrary units) in presence of decoherence. We apply the depolarizing channel at each step of the iteration, with two different $\epsilon ={10}^{-3}$ and ${10}^{-6}$. Two runs are performed for each respective $\epsilon$. The Hamiltonian is the transverse-field Ising model with $g=0.5$. It is seen that the energy variance is larger than $5\epsilon$. There are 204 steps in each run.

Figure 9

Energy (top) and energy variance (bottom), similar to the simulations in Fig. 8, except that $\epsilon =0.01$ and the depolarizing channel applies only every 30 steps, starting at step 1 and ending at step 181. There are 204 steps in each run of the three runs. Both the energy and its variance are displayed in arbitrary units.

Figure 10

Application of our spectral projection algorithm in the quantum annealing as the subroutine. The figures display the energy (in arbitrary units) after projecting to the eigenstates vs $g$ for the transverse-field $XzY$ model at $r=0.5$, i.e., $H_{XzY}(g=0,r=0.5)$ for (a) $N=5$ qubits and (b) $N=6$ qubits. The curves represent eigenenergies as a function of $g$. The procedure starts with two different initial states: (1) [(blue) dots that start on the lowest curve] the ground state $|00000\rangle$ of $H_{XzY}(g=0,r=0.5)$ and (2) [(red) dots that start on the top curve] the highest-energy state $|11111\rangle$ of $H_{XzY}(g=0,r=0.5)$. All the energy levels of $H_{XzY}(g,r=0.5)$ are also shown by solid curves. (a) Due to energy-level crossings, the ground state transits to a higher excited state after the crossing, and the highest-energy state transits to a lower-energy state after an associated crossing. Quantum annealing does not work if there is any level crossing. (b) Due to the existence of a respective small gap, the initial ground state ends up at the final ground state and the initial highest-energy state ends up also at the final highest-energy state.

Figure 11

Application of our spectral projection algorithm in the quantum annealing as the subroutine for the transverse-field Ising model $H_{\mathrm{TFI}}\left(g\right)$. The figure shows the energy (in arbitrary units) after projecting to the eigenstates vs $g$ for the five-qubit [top panel (a)] and six-qubit [bottom panel (b)] transverse-field Ising model. The procedure starts with two different initial states: (1) [(blue) dots that start on the lowest curve] the ground state $|00000\rangle$ of $H_{\mathrm{TFI}}(g=0)$ and (2) [(red) dots that start on the top curve] the highest-energy state $|11111\rangle$ of $H_{\mathrm{TFI}}(g=0)$.

Figure 12

Application of our spectral projection algorithm in the quantum annealing as the subroutine that carries out the measurement to project to eigenstates [3]. (a) The top figure shows the energy (in arbitrary units) after projecting to the eigenstates vs $g$. Different colors represent different qubit numbers $N_q=14,16,18,20,\text{and}22$. The procedure starts with the ground state $|00\cdots 0\rangle$ of $H_{\mathrm{TFI}}(g=0)$. (b) The bottom figures shows the energy variance (in arbitrary units) at each step of projection (showing only for $N_q=14,18,\text{and}22$ for illustration), which can be used as a figure of merit for the error in the energy. Generally, the variance is the largest around $g=0.5$, which is the critical point of the model in the thermodynamic limit. The curves are drawn to connect dots and to guide the eye. There are in total 210 steps in each projection run. The parameter $\mathrm{\Delta }t$ is chosen from the list with number of repetitions shown in the parentheses: $\left[0.01\right(\times 10),0.1(\times 10),0.03(\times 50),0.01(\times 100),0.003(\times 40\left)\right]$ The ancillary state is chosen as $(\alpha =1/\sqrt{2},\beta =e^{i\varphi }/\sqrt{2})$ with $\varphi$ chosen randomly in $[0,2\pi )$.

Figure 13

The effect of decoherence on the quantum annealing. We use the contrived scenario that the decoherence with $\epsilon =0.01$ occurs at every 31th step in our spectral projection subroutine, where the primitive is run for 180 steps. We use the five-qubit transverse-field Ising model $H_{\mathrm{TFI}}\left(g\right)$ and carry out three different runs. The energy (a) [top] and its variance (b) [bottom] are shown as $g$ is varied. Both the energy and its variance are displayed in arbitrary units. The initial state is the ground state $|00000\rangle$ of $H_{\mathrm{TFI}}(g=0)$. The final grounds are doubly degenerate and are $|+-+-+\rangle$ and $|-+-+-\rangle$.

Figure 14

The diagram that illustrates the attempted algorithm for implementing one Trotter imaginary-time step.

Figure 15

The first 100 values of $r_n$, starting with $r_1=1$.