The Abrams-Lloyd quantum algorithm computes an eigenvalue and the corresponding eigenstate of a unitary matrix from an approximate eigenvector Va . The eigenstate is a basis vector in the orthonormal eigenspace. Finding another eigenvalue, using a random approximate eigenvector, may require many trials as the trial may repeatedly result in the eigenvalue measured earlier. We present a method involving orthogonalization of the eigenstate obtained in a trial. It is used as the Va for the next trial. Because of the orthogonal construction, Abrams-Lloyd algorithm will not repeat the eigenvalue measured earlier. Thus, all the eigenvalues are obtained in sequence without repetitions. An operator that anticommutes with a unitary operator orthogonalizes the eigenvectors of the unitary. We implemented the method on the programming language model of quantum computation and tested it on a unitary matrix representing the time evolution operator of a small spin chain. All the eigenvalues of the operator were obtained sequentially. Another use of the first eigenvector from Abrams-Lloyd algorithm is preparing a state that is the uniform superposition of all the eigenvectors. This is possible by nonorthogonalizing the first eigenvector in all dimensions and then applying the Abrams-Lloyd algorithm steps stopping short of the last measurement.
The Abrams-Lloyd quantum algorithm computes an eigenvalue and the corresponding eigenstate of a unitary matrix from an approximate eigenvector Va . The eigenstate is a basis vector in the orthonormal eigenspace. Finding another eigenvalue, using a random approximate eigenvector, may require many trials as the trial may repeatedly result in the eigenvalue measured earlier. We present a method involving orthogonalization of the eigenstate obtained in a trial. It is used as the Va for the next trial. Because of the orthogonal construction, Abrams-Lloyd algorithm will not repeat the eigenvalue measured earlier. Thus, all the eigenvalues are obtained in sequence without repetitions. An operator that anticommutes with a unitary operator orthogonalizes the eigenvectors of the unitary. We implemented the method on the programming language model of quantum computation and tested it on a unitary matrix representing the time evolution operator of a small spin chain. All the eigenvalues of the operator were obtained sequentially. Another use of the first eigenvector from Abrams-Lloyd algorithm is preparing a state that is the uniform superposition of all the eigenvectors. This is possible by nonorthogonalizing the first eigenvector in all dimensions and then applying the Abrams-Lloyd algorithm steps stopping short of the last measurement.
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.
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values ⟨x∣M∣x⟩, where ∣x⟩ is a prepared eigenstate and M is an observable. For an n×ns-sparse Hermitian matrix H, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n3) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n2s) time in exact arithmetic, but recovering all eigenvectors still requires O(n3) time. In contrast, our algorithm runs in time O~(ns2log2n/Δmin), where Δmin denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δmin−1=O(n), the most favorable scaling for n distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to s=o(n/logn), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n3) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
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.