3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.