# What is the actual power of Quantum Phase Estimation?

I have some perplexity concerning the concept of phase estimation: by definition, given a unitary operator $U$ and an eigenvector $|u\rangle$ with related eigenvalue $\text{exp}(2\pi i \phi)$, the phase estimation allows to find the value of $\phi$. This would mean that I would be able to determine an eigenvalue of a certain matrix given that I know already one of its eigenvectors? But isn't the fact that needing an eigenvector beforehand would quite reduce the usefulness of the phase estimation itself?

• The point is that if I have already the eigenvectors of a given operator, what is the point of having the eigenvalues of such operator? I probably have some gaps to fully comprehend the process, but I imagine that it would be great if, given any matrix, I am able to find in a fast way its eigenvalues. I said "any" because I was also wondering if there would be some way to transpose any kind of matrix in a unitary version and then find its eigenvalues for instance to solve a linear problem related to it. I don't know if what I am saying is making any sense. – FSic Jun 13 '18 at 9:49
• You can do that. It’s essentially the content of what is known as the HHL algorithm (Harrow, Hassidim and Lloyd), but that does not really correspond to what your question is asking! – DaftWullie Jun 15 '18 at 8:10

If you don't supply a $|u\rangle$ as an input, there are two possible things you might want to get out:

1. The $\varphi$ for a randomly chosen (but unknown) eigenstate $|u\rangle$;

2. Both $\varphi$ and $|u\rangle$ for one or more eigenstates.

Let's first look at 1. Since eigenstates form a complete basis, any input state you use can be interpreted as a superposition of the eigenstates of $U$. Due to the linearity of quantum mechanics, the algorithm would then run for all these states at once. Then at the end, when you measure the output, it will randomly collapse to a given instance. This means that you'll be given a $\varphi$ for a randomly chosen eigenstate, but you won't know which it is. The existing phase estimation algorithm therefore can supply us with the first possible application.

The second application is something we can't do with standard phase estimation, but let's consider it hypothetically. Any algorithm that could do this would be giving us an eigenstate $|u\rangle$ as part of the output. So if you want to actually know what $|u\rangle$ is, you'd have to do tomography on the output. Since tomography is inefficient, there would probably be better ways to go about doing this.

Sometimes, you might know the eigenvector, and the computational question that you want to answer is what the eigenvalue is. For example, any function evaluation $f(x)$ defined by the action of a $U$ $$U:|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle$$for $x\in\{0,1\}^n$, $y\in\{0,1\}$ has well defined eigenvectors, $$|x\rangle(|0\rangle\pm|1\rangle)/\sqrt{2},$$ but whether the eigenvalue is $\pm 1$ is absolutely vital: that is essentially the question being asked in things like Deutsch's algorithm, Deutsch-Jozsa, Simon's algorithm, Bernstein-Vazirani etc. It's also the way that the oracle for quantum search is often constructed.

In a slightly more generalised setting (that applies, for example, to Shor's algorithm), you might not need to find a specific eigenvalue, but a random choice from some subset will do. So it might be that there's a standard state (e.g. $|00\ldots 01\rangle$) that has support on all of the eigenvectors from which you want to pick an eigenvalue randomly, but you have no idea what the individual eigenvectors are, but you can run phase estimation with that input, and you'll be just fine.