Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1505.02984 · International Journal of Quantum Information

Quantum eigenvalue estimation for irreducible non-negative matrices

Ammar Daskin

Published Feb 1, 2016• 0 citations
arXivHTMLPDF

Abstract

Quantum phase estimation algorithm (PEA) has been successfully adapted as a sub frame of many other algorithms applied to a wide variety of applications in different fields. However, the requirement of a good approximate eigenvector given as an input to the algorithm hinders the application of the algorithm to the problems where we do not have any prior knowledge about the eigenvector. In this paper, we show that the principal eigenvalue of an irreducible non-negative operator can be determined by using an equal superposition initial state in the PEA. This removes the necessity of the existence of an initial good approximate eigenvector. Moreover, we show that the success probability of the algorithm is related to the closeness of the operator to a stochastic matrix. Therefore, we draw an estimate for the success probability by using the variance of the column sums of the operator. This provides a priori information which can be used to know the success probability of the algorithm beforehand for the non-negative matrices and apply the algorithm only in cases when the estimated probability is reasonably high. Finally, we discuss the possible applications and show the results for random symmetric matrices and 3-local Hamiltonians with non-negative off-diagonal elements.

DOI
10.1142/s0219749916500052

Related papers

Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues

Abhijeet Alase, Salini Karuvade

Quantum algorithms for estimating the eigenvalues of matrices, including the phase estimation algorithm, serve as core subroutines in a wide range of quantum algorithms, including those in quantum chemistry and quantum machine learning. The standard quantum eigenvalue (phase) estimation algorithm accepts a Hermitian (unitary) matrix and a state in an unknown superposition of its eigenstates as input, and coherently records the estimates for real eigenvalues (eigenphases) in an ancillary register. Extension of quantum eigenvalue and phase estimation algorithms to the case of non-normal input matrices is obstructed by several factors such as non-orthogonality of eigenvectors, existence of generalized eigenvectors and the fact that eigenvalues may lie anywhere on the complex plane. In this work, we propose a novel approach for estimating the eigenvalues of non-normal matrices based on preparation of a state that we call the "resolvent state". We construct the first efficient algorithm for estimating the phases of the unimodular eigenvalues of a given non-unitary matrix. We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix, achieving complexities that match the best known results while operating under significantly relaxed assumptions on the non-real part of the spectrum. The resolvent-based approach that we introduce also extends to estimating eigenvalues that lie on a parametrized complex curve, subject to explicitly stated conditions, thereby paving the way for a new paradigm of parametric eigenvalue estimation.

arXiv:2410.04837•Oct 7, 2024•7 citations

Quantum Eigensolver for Non-Normal Matrices via Ground State Energy Estimation

Honghong Lin, Yun Shang

Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error $ε$ with probability at least $1-p_{\rm fail}$. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires $O(κ^2ε^{-(2m-1)}\log(1/p_{\rm fail}))$ queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.

arXiv:2502.18119•Feb 25, 2025•3 citations

Statistical approach to quantum phase estimation

Alexandria J. Moore, Yuchen Wang, Zixuan Hu +2 more

Abstract We introduce a new statistical and variational approach to the phase estimation algorithm (PEA). Unlike the traditional and iterative PEAs which return only an eigenphase estimate, the proposed method can determine any unknown eigenstate–eigenphase pair from a given unitary matrix utilizing a simplified version of the hardware intended for the iterative PEA (IPEA). This is achieved by treating the probabilistic output of an IPEA-like circuit as an eigenstate–eigenphase proximity metric, using this metric to estimate the proximity of the input state and input phase to the nearest eigenstate–eigenphase pair and approaching this pair via a variational process on the input state and phase. This method may search over the entire computational space, or can efficiently search for eigenphases (eigenstates) within some specified range (directions), allowing those with some prior knowledge of their system to search for particular solutions. We show the simulation results of the method with the Qiskit package on the IBM Q platform and on a local computer.

arXiv:2104.10285•New Journal of Physics•Oct 21, 2021•10 citations

Quantum Filter Diagonalization: Quantum Eigendecomposition without Full Quantum Phase Estimation

Robert M. Parrish, Peter L. McMahon

We develop a quantum filter diagonalization method (QFD) that lies somewhere between the variational quantum eigensolver (VQE) and the phase estimation algorithm (PEA) in terms of required quantum circuit resources and conceptual simplicity. QFD uses a set of of time-propagated guess states as a variational basis for approximate diagonalization of a sparse Pauli Hamiltonian. The variational coefficients of the basis functions are determined by the Rayleigh-Ritz procedure by classically solving a generalized eigenvalue problem in the space of time-propagated guess states. The matrix elements of the subspace Hamiltonian and subspace metric matrix are each determined in quantum circuits by a one-ancilla extended swap test, i.e., statistical convergence of a one-ancilla PEA circuit. These matrix elements can be determined by many parallel quantum circuit evaluations, and the final Ritz estimates for the eigenvectors can conceptually be prepared as a linear combination over separate quantum state preparation circuits. The QFD method naturally provides for the computation of ground-state, excited-state, and transition expectation values. We numerically demonstrate the potential of the method by classical simulations of the QFD algorithm for an N=8 octamer of BChl-a chromophores represented by an 8-qubit ab initio exciton model (AIEM) Hamiltonian. Using only a handful of time-displacement points and a coarse, variational Trotter expansion of the time propagation operators, the QFD method recovers an accurate prediction of the absorption spectrum.

arXiv:1909.08925•Sep 19, 2019•189 citations

Phase estimation with randomized Hamiltonians

Ian Kivlichan, Christopher Granade, Nathan Wiebe

Iterative phase estimation has long been used in quantum computing to estimate Hamiltonian eigenvalues. This is done by applying many repetitions of the same fundamental simulation circuit to an initial state, and using statistical inference to glean estimates of the eigenvalues from the resulting data. Here, we show a generalization of this framework where each of the steps in the simulation uses a different Hamiltonian. This allows the precision of the Hamiltonian to be changed as the phase estimation precision increases. Additionally, through the use of importance sampling, we can exploit knowledge about the ground state to decide how frequently each Hamiltonian term should appear in the evolution, and minimize the variance of our estimate. We rigorously show, if the Hamiltonian is gapped and the sample variance in the ground state expectation values of the Hamiltonian terms sufficiently small, that this process has a negligible impact on the resultant estimate and the success probability for phase estimation. We demonstrate this process numerically for two chemical Hamiltonians, and observe substantial reductions in the number of terms in the Hamiltonian; in one case, we even observe a reduction in the number of qubits needed for the simulation. Our results are agnostic to the particular simulation algorithm, and we expect these methods to be applicable to a range of approaches.

arXiv:1907.10070•Jul 23, 2019•18 citations

Simulation of a quantum algorithm for phase estimation

Alexander N. Prokopenya

A quantum algorithm for estimating the phase, which determines the eigenvalue of a unitary operator, is discussed. It is assumed that the eigenvector of this operator and the corresponding quantum circuit are given. The memory register where the approximate phase value is stored consists of n qubits, which makes it possible to determine the phase accurate to 2 −n with the probability greater than 8/π 2 . By way of example, computations for the case of the quantum phase shift operator are performed. The simulation of the quantum algorithm and the computation of the eigenvalue are performed using the QuantumCircuit package written in the Wolfram Mathematica computer algebra system. This system is also used to perform all the computations and visualize the results.

Programming and Computer Software•Mar 1, 2015•7 citations
Quantum phase estimation algorithm (PEA) has been successfully adapted as a sub frame of many other algorithms applied to a wide variety of applications in different fields. However, the requirement of a good approximate eigenvector given as an input to the algorithm hinders the application of the algorithm to the problems where we do not have any prior knowledge about the eigenvector. In this paper, we show that the principal eigenvalue of an irreducible non-negative operator can be determined by using an equal superposition initial state in the PEA. This removes the necessity of the existence of an initial good approximate eigenvector. Moreover, we show that the success probability of the algorithm is related to the closeness of the operator to a stochastic matrix. Therefore, we draw an estimate for the success probability by using the variance of the column sums of the operator. This provides a priori information which can be used to know the success probability of the algorithm beforehand for the non-negative matrices and apply the algorithm only in cases when the estimated probability is reasonably high. Finally, we discuss the possible applications and show the results for random symmetric matrices and 3-local Hamiltonians with non-negative off-diagonal elements.
Quantum algorithms for estimating the eigenvalues of matrices, including the phase estimation algorithm, serve as core subroutines in a wide range of quantum algorithms, including those in quantum chemistry and quantum machine learning. The standard quantum eigenvalue (phase) estimation algorithm accepts a Hermitian (unitary) matrix and a state in an unknown superposition of its eigenstates as input, and coherently records the estimates for real eigenvalues (eigenphases) in an ancillary register. Extension of quantum eigenvalue and phase estimation algorithms to the case of non-normal input matrices is obstructed by several factors such as non-orthogonality of eigenvectors, existence of generalized eigenvectors and the fact that eigenvalues may lie anywhere on the complex plane. In this work, we propose a novel approach for estimating the eigenvalues of non-normal matrices based on preparation of a state that we call the "resolvent state". We construct the first efficient algorithm for estimating the phases of the unimodular eigenvalues of a given non-unitary matrix. We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix, achieving complexities that match the best known results while operating under significantly relaxed assumptions on the non-real part of the spectrum. The resolvent-based approach that we introduce also extends to estimating eigenvalues that lie on a parametrized complex curve, subject to explicitly stated conditions, thereby paving the way for a new paradigm of parametric eigenvalue estimation.
Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error εεε with probability at least 1−pfail1-p_{\rm fail}1−pfail​. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires O(κ2ε−(2m−1)log⁡(1/pfail))O(κ^2ε^{-(2m-1)}\log(1/p_{\rm fail}))O(κ2ε−(2m−1)log(1/pfail​)) queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.
Abstract We introduce a new statistical and variational approach to the phase estimation algorithm (PEA). Unlike the traditional and iterative PEAs which return only an eigenphase estimate, the proposed method can determine any unknown eigenstate–eigenphase pair from a given unitary matrix utilizing a simplified version of the hardware intended for the iterative PEA (IPEA). This is achieved by treating the probabilistic output of an IPEA-like circuit as an eigenstate–eigenphase proximity metric, using this metric to estimate the proximity of the input state and input phase to the nearest eigenstate–eigenphase pair and approaching this pair via a variational process on the input state and phase. This method may search over the entire computational space, or can efficiently search for eigenphases (eigenstates) within some specified range (directions), allowing those with some prior knowledge of their system to search for particular solutions. We show the simulation results of the method with the Qiskit package on the IBM Q platform and on a local computer.
We develop a quantum filter diagonalization method (QFD) that lies somewhere between the variational quantum eigensolver (VQE) and the phase estimation algorithm (PEA) in terms of required quantum circuit resources and conceptual simplicity. QFD uses a set of of time-propagated guess states as a variational basis for approximate diagonalization of a sparse Pauli Hamiltonian. The variational coefficients of the basis functions are determined by the Rayleigh-Ritz procedure by classically solving a generalized eigenvalue problem in the space of time-propagated guess states. The matrix elements of the subspace Hamiltonian and subspace metric matrix are each determined in quantum circuits by a one-ancilla extended swap test, i.e., statistical convergence of a one-ancilla PEA circuit. These matrix elements can be determined by many parallel quantum circuit evaluations, and the final Ritz estimates for the eigenvectors can conceptually be prepared as a linear combination over separate quantum state preparation circuits. The QFD method naturally provides for the computation of ground-state, excited-state, and transition expectation values. We numerically demonstrate the potential of the method by classical simulations of the QFD algorithm for an N=8 octamer of BChl-a chromophores represented by an 8-qubit ab initio exciton model (AIEM) Hamiltonian. Using only a handful of time-displacement points and a coarse, variational Trotter expansion of the time propagation operators, the QFD method recovers an accurate prediction of the absorption spectrum.
Iterative phase estimation has long been used in quantum computing to estimate Hamiltonian eigenvalues. This is done by applying many repetitions of the same fundamental simulation circuit to an initial state, and using statistical inference to glean estimates of the eigenvalues from the resulting data. Here, we show a generalization of this framework where each of the steps in the simulation uses a different Hamiltonian. This allows the precision of the Hamiltonian to be changed as the phase estimation precision increases. Additionally, through the use of importance sampling, we can exploit knowledge about the ground state to decide how frequently each Hamiltonian term should appear in the evolution, and minimize the variance of our estimate. We rigorously show, if the Hamiltonian is gapped and the sample variance in the ground state expectation values of the Hamiltonian terms sufficiently small, that this process has a negligible impact on the resultant estimate and the success probability for phase estimation. We demonstrate this process numerically for two chemical Hamiltonians, and observe substantial reductions in the number of terms in the Hamiltonian; in one case, we even observe a reduction in the number of qubits needed for the simulation. Our results are agnostic to the particular simulation algorithm, and we expect these methods to be applicable to a range of approaches.
A quantum algorithm for estimating the phase, which determines the eigenvalue of a unitary operator, is discussed. It is assumed that the eigenvector of this operator and the corresponding quantum circuit are given. The memory register where the approximate phase value is stored consists of n qubits, which makes it possible to determine the phase accurate to 2 −n with the probability greater than 8/π 2 . By way of example, computations for the case of the quantum phase shift operator are performed. The simulation of the quantum algorithm and the computation of the eigenvalue are performed using the QuantumCircuit package written in the Wolfram Mathematica computer algebra system. This system is also used to perform all the computations and visualize the results.