By allowing measurements of observables other than the state of the qubits in a quantum computer, one can find eigenvectors very quickly. If a unitary operation U is implemented as a time-independent Hamiltonian, for instance, one can collapse the state of the computer to a nearby eigenvector of U with a measurement of the energy. We examine some recent proposals for quantum computation using time-independent Hamiltonians and show how to convert them into ``artificial orbitals'' whose energy eigenstates match those of U. This system can be used to find eigenvectors and eigenvalues with a single measurement. We apply this technique to Grover's algorithm and the continuous variant proposed by Farhi and Gutmann.By allowing measurements of observables other than the state of the qubits in a quantum computer, one can find eigenvectors very quickly. If a unitary operation U is implemented as a time-independent Hamiltonian, for instance, one can collapse the state of the computer to a nearby eigenvector of U with a measurement of the energy. We examine some recent proposals for quantum computation using time-independent Hamiltonians and show how to convert them into ``artificial orbitals'' whose energy eigenstates match those of U. This system can be used to find eigenvectors and eigenvalues with a single measurement. We apply this technique to Grover's algorithm and the continuous variant proposed by Farhi and Gutmann.

Aug 25, 20210 citations

Rodeo Algorithm for Quantum Computing

Kenneth Choi, Dean Lee, Joey Bonitati +2 more

We present a stochastic quantum computing algorithm that can prepare any eigenvector of a quantum Hamiltonian within a selected energy interval $[E\ensuremath{-}\ensuremath{\epsilon},E+\ensuremath{\epsilon}]$. In order to reduce the spectral weight of all other eigenvectors by a suppression factor $\ensuremath{\delta}$, the required computational effort scales as $O[|\mathrm{log}\ensuremath{\delta}|/(p\ensuremath{\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 $\ensuremath{\epsilon}$, the computational scaling is $O[(\mathrm{log}\ensuremath{\epsilon}{)}^{2}/(p\ensuremath{\epsilon})]$. For eigenstate preparation, the computational scaling is $O(\mathrm{log}\mathrm{\ensuremath{\Delta}}/p)$, where $\mathrm{\ensuremath{\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.We present a stochastic quantum computing algorithm that can prepare any eigenvector of a quantum Hamiltonian within a selected energy interval $[E\ensuremath{-}\ensuremath{\epsilon},E+\ensuremath{\epsilon}]$. In order to reduce the spectral weight of all other eigenvectors by a suppression factor $\ensuremath{\delta}$, the required computational effort scales as $O[|\mathrm{log}\ensuremath{\delta}|/(p\ensuremath{\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 $\ensuremath{\epsilon}$, the computational scaling is $O[(\mathrm{log}\ensuremath{\epsilon}{)}^{2}/(p\ensuremath{\epsilon})]$. For eigenstate preparation, the computational scaling is $O(\mathrm{log}\mathrm{\ensuremath{\Delta}}/p)$, where $\mathrm{\ensuremath{\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.

arXiv:2009.04092Physical Review LettersJul 23, 202191 citations

Quantum algorithm for finding periodicities in the spectrum of a black-box Hamiltonian or unitary transformation

Dominik Janzing, Thomas Beth

Estimating the eigenvalues of a unitary transformation U by standard phase estimation requires the implementation of controlled-U-gates which are not available if U is only given as a black box. We show that a simple trick allows to measure eigenvalues of U\otimes U^\dagger even in this case. Running the algorithm several times allows therefore to estimate the autocorrelation function of the density of eigenstates of U. This can be applied to find periodicities in the energy spectrum of a quantum system with unknown Hamiltonian if it can be coupled to a quantum computer.Estimating the eigenvalues of a unitary transformation U by standard phase estimation requires the implementation of controlled-U-gates which are not available if U is only given as a black box. We show that a simple trick allows to measure eigenvalues of U\otimes U^\dagger even in this case. Running the algorithm several times allows therefore to estimate the autocorrelation function of the density of eigenstates of U. This can be applied to find periodicities in the energy spectrum of a quantum system with unknown Hamiltonian if it can be coupled to a quantum computer.

arXiv:quant-ph/0108053Aug 10, 20013 citations

A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems

Qing‐Xing Xie, Zhao Yan

Developing efficient quantum computing algorithms is essential for tackling computationally challenging problems across various fields. This paper presents a novel quantum algorithm, XZ24, for efficiently computing the eigen-energy spectra of arbitrary quantum systems. Given a Hamiltonian $\hat{H}$ and an initial reference state $|ψ_{\text{ref}} \rangle$ , the algorithm extracts information about $\langle ψ_{\text{ref}} | \cos(\hat{H} t) | ψ_{\text{ref}} \rangle$ from an auxiliary qubit's state. By applying a Fourier transform, the algorithm resolves the energies of eigenstates of the Hamiltonian with significant overlap with the reference wavefunction. We provide a theoretical analysis and numerical simulations, showing XZ24's superior efficiency and accuracy compared to existing algorithms. XZ24 has three key advantages: 1. It removes the need for eigenstate preparation, requiring only a reference state with non-negligible overlap, improving upon methods like the Variational Quantum Eigensolver. 2. It reduces measurement overhead, measuring only one auxiliary qubit. For a system of size $L$ with precision $ε$ , the sampling complexity scales as $O(L \cdot ε^{-1})$ . When relative precision $ε$ is sufficient, the complexity scales as $O(ε^{-1})$ , making measurements independent of system size. 3. It enables simultaneous computation of multiple eigen-energies, depending on the reference state. We anticipate that XZ24 will advance quantum system simulations and enhance applications in quantum computing.Developing efficient quantum computing algorithms is essential for tackling computationally challenging problems across various fields. This paper presents a novel quantum algorithm, XZ24, for efficiently computing the eigen-energy spectra of arbitrary quantum systems. Given a Hamiltonian $\hat{H}$ and an initial reference state $|ψ_{\text{ref}} \rangle$, the algorithm extracts information about $\langle ψ_{\text{ref}} | \cos(\hat{H} t) | ψ_{\text{ref}} \rangle$ from an auxiliary qubit's state. By applying a Fourier transform, the algorithm resolves the energies of eigenstates of the Hamiltonian with significant overlap with the reference wavefunction. We provide a theoretical analysis and numerical simulations, showing XZ24's superior efficiency and accuracy compared to existing algorithms. XZ24 has three key advantages: 1. It removes the need for eigenstate preparation, requiring only a reference state with non-negligible overlap, improving upon methods like the Variational Quantum Eigensolver. 2. It reduces measurement overhead, measuring only one auxiliary qubit. For a system of size $L$ with precision $ε$, the sampling complexity scales as $O(L \cdot ε^{-1})$. When relative precision $ε$ is sufficient, the complexity scales as $O(ε^{-1})$, making measurements independent of system size. 3. It enables simultaneous computation of multiple eigen-energies, depending on the reference state. We anticipate that XZ24 will advance quantum system simulations and enhance applications in quantum computing.

arXiv:2406.00296Jun 1, 20243 citations

Quantum algorithm for measuring the eigenvalues of UÄU-1 for a black-box unitary transformation U

Dominik Janzing, T. Beth

Estimating the eigenvalues of a unitary transformation U by standard phase estimation requires the implementation of controlled-U-gates which are not available if U is only given as a black box. We show that a simple trick allows to measure eigenvalues of U\otimesU^\deggar even in this case. Running the algorithm several times allows therefore to estimate the autocorrelation function of the density of eigenstates of U. This can be applied to find periodicities in the energy spectrum of a quantum system with unknown Hamiltonian if it can be coupled to a quantum computer.Estimating the eigenvalues of a unitary transformation U by standard phase estimation requires the implementation of controlled-U-gates which are not available if U is only given as a black box. We show that a simple trick allows to measure eigenvalues of U\otimesU^\deggar even in this case. Running the algorithm several times allows therefore to estimate the autocorrelation function of the density of eigenstates of U. This can be applied to find periodicities in the energy spectrum of a quantum system with unknown Hamiltonian if it can be coupled to a quantum computer.

Quantum Information and ComputationApr 1, 20021 citation

Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

Lawrence M. Ioannou

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.

Jan 1, 20024 citations

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 $\ensuremath{\epsilon}$, the computational scaling is $O[(\mathrm{log}\ensuremath{\epsilon}{)}^{2}/(p\ensuremath{\epsilon})]$. For eigenstate preparation, the computational scaling is $O(\mathrm{log}\mathrm{\ensuremath{\Delta}}/p)$, where $\mathrm{\ensuremath{\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.

\hat{H}

and an initial reference state

|ψ_{\text{ref}} \rangle

, the algorithm extracts information about

\langle ψ_{\text{ref}} | \cos(\hat{H} t) | ψ_{\text{ref}} \rangle

from an auxiliary qubit's state. By applying a Fourier transform, the algorithm resolves the energies of eigenstates of the Hamiltonian with significant overlap with the reference wavefunction. We provide a theoretical analysis and numerical simulations, showing XZ24's superior efficiency and accuracy compared to existing algorithms. XZ24 has three key advantages: 1. It removes the need for eigenstate preparation, requiring only a reference state with non-negligible overlap, improving upon methods like the Variational Quantum Eigensolver. 2. It reduces measurement overhead, measuring only one auxiliary qubit. For a system of size

L

with precision

ε

, the sampling complexity scales as

O(L \cdot ε^{-1})

. When relative precision

ε

is sufficient, the complexity scales as

O(ε^{-1})

, making measurements independent of system size. 3. It enables simultaneous computation of multiple eigen-energies, depending on the reference state. We anticipate that XZ24 will advance quantum system simulations and enhance applications in quantum computing.