# 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, 2018 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! Jun 15, 2018 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.

In addition to the other two excellent answers, this appears to be a common problem in quantum chemistry. A recent paper of Gharibian and le Gall might also shed some light on the question about how much knowledge of the eigenvector is needed, a-priori, and what is the power of the quantum phase estimation. The TL/DR is that a decent, but not necessarily perfect, overlap to the eigenvector of interest is needed, and quantum computers really shine in giving a very accurate assessment of the eigenvalues - but a less accurate assessment may still be calculated classically, with a dequantization of the quantum algorithm!

That is, in certain chemistry problems one is provided a Hamiltonian $$\mathcal H$$, and one uses various heuristics, such as the Hartree-Fock method, to determine a description of a "guiding vector" $$|u\rangle$$ that is believed to have significant components/significant overlap with the ground state.

Because it is, in general, QMA-complete to determine the ground state unconditionally, these heuristics likely often fail to provide good descriptions of the guiding vectors (or the guiding vectors have poor overlap with the eigenvector of interest).

Nonetheless Gharibian and le Gall show that under certain access conditions and with certain promises, if a suitable description of the guiding state $$|u\rangle$$ can be provided, then the accuracy of the smallest eigenvalue of $$\mathcal H$$ provided by the quantum phase estimation algorithm that can realize controlled versions of $$e^{-i\mathcal H t}$$ is split between being

• BQP-complete for inverse-polynomial precision, and
• In P for constant precision.

Their proof of BQP-completeness with inverse-polynomial precision appears standard and similar to, e.g., other Feynman-Kitaev clock constructions, while their proof that the constant-accuracy problem is in P follows mostly from the dequantization program initiated by Tang.

They have some follow-up conclusions and conjectures related to the quantum PCP conjecture that I only sort of understand, but their main conclusion appears to be that the accuracy of the overlap provides a nice split between the classical world (from dequantization) and the quantum world (from the phase estimation algorithm).