We present an efficient method for preparing the initial state required by the eigenvalue approximation quantum algorithm of Abrams and Lloyd. Our method can be applied when solving continuous Hermitian eigenproblems, e.g., the Schrödinger equation, on a discrete grid. We start with a classically obtained eigenvector for a problem discretized on a coarse grid, and we efficiently construct, quantum mechanically, an approximation of the same eigenvector on a fine grid. We use this approximation as the initial state for the eigenvalue estimation algorithm, and show the relationship between its success probability and the size of the coarse grid.
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.
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.
Abstract This paper presents a hybrid variational quantum algorithm that finds a random eigenvector of a unitary matrix with a known quantum circuit. The algorithm is based on the SWAP test on trial states generated by a parametrized quantum circuit. The eigenvector is described by a compact set of classical parameters that can be used to reproduce the found approximation to the eigenstate on demand. This variational eigenvector finder can be adapted to solve the generalized eigenvalue problem, to find the eigenvectors of normal matrices and to perform quantum principal component analysis on unknown input mixed states. These algorithms can all be run with low-depth quantum circuits, suitable for an efficient implementation on noisy intermediate-scale quantum computers and, with some restrictions, on linear optical systems. In full-scale quantum computers, where there might be optimization problems due to barren plateaus in larger systems, the proposed algorithms can be used as a primitive to boost known quantum algorithms. Limitations and potential applications are discussed.
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.
Finding a good approximation of the top eigenvector of a given
d×d matrix
A is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix
A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity
O~(d1.75) and one with time complexity
d1.5+o(1) (the first algorithm has a slightly better dependence on the
ℓ2-error of the approximating vector than the second, and uses different techniques of independent interest). Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs
Ω(d2) queries to entries of
A, and hence
Ω(d2) time. We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-
q eigenvectors in time
qd1.5+o(1). We also prove a nearly-optimal lower bound of
Ω~(d1.5) on the quantum query complexity of approximating the top eigenvector. Our quantum algorithms run a version of the classical power method that is robust to certain benign kinds of errors, where we implement each matrix-vector multiplication with small and well-behaved error on a quantum computer, in different ways for the two algorithms. Our first algorithm estimates the matrix-vector product one entry at a time, using a new "Gaussian phase estimation" procedure. Our second algorithm uses block-encoding techniques to compute the matrix-vector product as a quantum state, from which we obtain a classical description by a new time-efficient unbiased pure-state tomography procedure.