Rodeo Algorithm for Quantum Computing

We present a stochastic quantum computing algorithm that can prepare any eigenvector of a quantum Hamiltonian within a selected energy interval $[E-\epsilon ,E+\epsilon ]$. In order to reduce the spectral weight of all other eigenvectors by a suppression factor $\delta$, the required computational effort scales as $O[|\log \delta |/(p\epsilon )]$, where $p$ is the squared overlap of the initial state with the target eigenvector. The method, which we call the rodeo algorithm, uses auxiliary qubits to control the time evolution of the Hamiltonian minus some tunable parameter $E$. With each auxiliary qubit measurement, the amplitudes of the eigenvectors are multiplied by a stochastic factor that depends on the proximity of their energy to $E$. In this manner, we converge to the target eigenvector with exponential accuracy in the number of measurements. In addition to preparing eigenvectors, the method can also compute the full spectrum of the Hamiltonian. We illustrate the performance with several examples. For energy eigenvalue determination with error $\epsilon$, the computational scaling is $O[(\log \epsilon {)}^2/(p\epsilon )]$. For eigenstate preparation, the computational scaling is $O(\log \mathrm{\Delta }/p)$, where $\mathrm{\Delta }$ is the magnitude of the orthogonal component of the residual vector. The speed for eigenstate preparation is exponentially faster than that for phase estimation or adiabatic evolution.

Figure 1

Circuit diagram for the rodeo algorithm. The object system starts in an arbitrary state $|{\psi }_I⟩$. Each of the ancilla qubits are initialized in the state $|1⟩$ and operated on by a Hadamard gate $H$. We use each ancilla qubit $n=1,\dots ,N$ for the controlled time evolution of the object Hamiltonian, $H_{\mathrm{obj}}$, for time $t_n$. This is followed by a phase rotation $P(E{t}_n)$ on ancilla qubit $n$, another Hadamard gate $H$, and then measurement.

Figure 2

Initial-state spectral function for the Heisenberg model. We plot the initial-state spectral function using the rodeo algorithm for the Heisenberg spin chain with 3 (thin blue line), 6 (thick green line), and 9 (medium red line) cycles. We have averaged over 20 sets of Gaussian random values for $t_n$ with $t_{\mathrm{rms}}=5$. For comparison, we also show the exact initial-state spectral function with black open circles.

Figure 3

Logarithm of the wave function error versus the total propagation time for the Heisenberg model. We plot $\log \mathrm{\Delta }$, versus the total propagation time $T$ for the Heisenberg model. We show results for the rodeo algorithm, phase estimation, and adiabatic evolution. We also show the asymptotic estimates $\log F_A$ and $\log F_G$.

Figure 4

Initial-state spectral function for the Anderson localization model with diagonal disorder $\frac{1}{2}$. We plot the initial-state spectral function using the rodeo algorithm for the Anderson localization model with the root-mean-square diagonal disorder equal to $\frac{1}{2}$. We show results for 3 (thin blue line), 6 (thick green line), and 9 (medium red line) cycles. We have averaged over 20 sets of Gaussian random values for $t_n$ with $t_{\mathrm{rms}}=10$. For comparison, we also show the exact initial-state spectral function with black open circles.