3
$\begingroup$

The Quantum Phase Estimation algorithm wants to approximate the phase $\varphi$ of an eigenvalue $\lambda = e^{2\pi i \varphi}$ of a unitary operator $U$. Besides $U$ an eigenvector $x$ corresponding to $\lambda$ is given, that is, we know, $U x = \lambda x$. However, isn't computing the eigenvalue of a given eigenvector fairly simple?

  • Let $i$ be an index with $x_i \neq 0$,
  • compute $U x$,
  • compute $\frac{(Ux)_i}{x_i}$​​ which equals $\lambda$.

What am I missing? Is it the fact that it might not be easy to find an index $i$ with $x_i \neq 0$ ?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ The point is more that QPE finds an estimate of the eigenvalue very efficiently. To employ traditional classical eigensolvers you would need to do linear algebra over an exponentially large space, eg. if you have $n$ qubits then the space is $2^n$ dimensional. Where as QPE doesn't suffer from this exponential overhead. $\endgroup$
    – Condo
    Feb 2, 2021 at 14:56
  • $\begingroup$ Thanks for your reply, but I still find it confusing that in the formulation of QPE the (or a) eigenvector is assumed to be known. If so, it can be easily computed as mentioned above. The classical algorithms you refer to do in my understanding not require that a eigenvector is known. $\endgroup$
    – Night Heron
    Feb 3, 2021 at 5:20
  • 2
    $\begingroup$ but in the QPE algorithm you are not given a classical description of the eigenstate, what you have is the state itself. You cannot efficiently recover its classical description without performing full tomography $\endgroup$
    – glS ♦
    Feb 3, 2021 at 10:23

1 Answer 1

Reset to default
5
$\begingroup$

There are two different issues at play here. First is the difficulty of the calculation. If you have an $n$-qubit unitary $U$, then to evaluate $Ux$, you have to multiply a $2^n\times 2^n$ matrix with a $2^n$-element vector. This takes a long time (by naive methods, $O(4^n)$), even if you understand that the method seems simple and straightforward. There's just so much data. In comparison, phase estimation is much quicker (depending on what assumptions you make, based on how easily you can produce controlled-$U^{2^k}$). But sometimes, as in the case of order finding, you get down to something that's polynomial in $n$.

The second issue is the application. Yes, it can seem pretty dumb that if you know the eigenvector, you have to make the eigenvector to find the eigenvalue. That, as a general rule, is not how the algorithms that use phase estimation actually work. For example, order finding does not input an eigenstate, it's just that you need the understanding of how it works on eigenstates in order to be able to process the overall function. Much the same is true of other algorithms such as HHL. Indeed, these algorithms use phase estimation to decompose an input state in terms of the eigenbasis even though you don't know what that basis is.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for this answer as well. $\endgroup$
    – Night Heron
    Feb 4, 2021 at 7:15

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.