Edit - Quantum Computing Stack Exchange

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome all constructive edits, but please make them substantial. Avoid trivial edits unless absolutely necessary.

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?

Answer

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.

Edit Summary

cancel

How to Tag

A tag is a keyword or label that categorizes your question with other, similar questions. Choose one or more (up to 5) tags that will help answerers to find and interpret your question.

► complete the sentence: my question is about...

► use tags that describe things or concepts that are essential, not incidental to your question

► favor using existing popular tags

► read the descriptions that appear below the tag

If your question is primarily about a topic for which you can't find a tag:

► combine multiple words into single-words with hyphens (e.g. quantum-computer), up to a maximum of 35 characters

► creating new tags is a privilege; if you can't yet create a tag you need, then post this question without it, then ask the community to create it for you

popular tags »

Stack Exchange Network

current community

your communities

more stack exchange communities

What is the actual power of Quantum Phase Estimation?

Answer

How to Edit

How to Format

How to Tag