# How does the complexity of extracting eigenvalues via quantum phase estimation compare with the classical one?

Suppose, I have ideal quantum computer that allows me to find exact eigenvalues with QPE algorithm under perfect matrix, eigenvectors and eigenvalues conditions. How the complexity of this algorithm differs from classical problem of finding the eigenvalue? What are the benifits? Would be glad to see both: short answers and links to the sources.

## 1 Answer

Even eigenvalue sampling itself is BQP-complete; thus, a quantum computer most likely provides an exponential speedup to finding such eigenvalues (under the standard assumption that BPP$$\subsetneq$$BQP).

That is, given an arbitrary (pure) state $$|\psi\rangle$$, along with some local Hamiltonian $$H$$, we can simulate $$U=\exp(-iHt)$$ and use the Quantum Phase Estimation (QPE) algorithm to sample from $$H$$'s eigendecomposition of $$|\psi\rangle$$. Every time we run the algorithm we could get different eigenvalues, but the BQP-completeness results above show that even this is classically intractable.

Note that there will be errors in both (1) the local Hamiltonian simulation of $$H$$, and also (2) in the precision of the Quantum Phase Estimation algorithm. So I don't know what to make of your comment about "exact eigenvalues under perfect matrix conditions", other than to say that those errors can be suppressed at a polynomial cost to the complexity of the quantum algorithm.

Classically, it's probably hard to even hold the matrix in memory, much less to do the Fourier transform or Gaussian Elimination to sample therefrom. But see, for example, the dequantization efforts to Singular Value Decomposition.