# In the quantum phase estimation algorithm, why can't we directly compute the eigenvalue from the known eigenvector?

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$$ ?

• 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. Feb 2 '21 at 14:56
• 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. Feb 3 '21 at 5:20
• 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
– glS
Feb 3 '21 at 10:23

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$$.