How to use the measurement in quantum phase estimation?

Question

Reading the quantum phase estimation algorithm on Wikipedia, I am wondering how exactly the measurements are used to obtain the phase $\delta$. I understand that the value of phase is encoded into the binary string that represents a computational state. My question is more about what extra information can be extracted from the probabilities. If I perform the measurement in the computational basis, i.e., $|a\rangle$ in the notation used on Wikipedia, what I obtain is a list of probabilities for each state. (Imagine the case $\delta\neq 0$). How exactly can I get this $\delta$ from these probabilities? Since the probability $\text{Pr}(a)$ is what I get and is expressed in terms of $\delta$, do I have to inverse the following function

$\text{Pr}(a) = \frac{1}{2^{2^{n}}}\frac{|\sin(\pi 2^{n}\delta)|^{2}}{|\sin(\pi\delta)|^{2}}$

in order to get $\delta$?

Meanwhile, how does the algorithm recognise the nearest integer to $2^{n}\theta$? The only way I can imagine is that the probability that corresponds to a certain state is greater than other. Imagine I do not approximate, $\textit{a priori}$, $2^{n}\theta = a + 2^{n}\delta$, then what I obtain is this list of probabilities for each $a$. It appears I can use any of them to estimate the phase. In this case, which probability shall I use?

Answer 1

To answer your first question, whenever you run a QPE circuit on, let's say, $n$ ancilla qubits, you will be left with the binary representation of the phase $\theta$, encoded in the ancilla qubits. Measuring these ancillary qubits provides you an estimate of the phase $\theta$ (up to n-bit precision). Note, the probabilities of the states are there to provide you an insight as to which measurement outcome is the phase approximation.

Considering an example of $\theta = \frac{1}{5}$, let's say we want to determine the phase up to 4-bit precision. $\frac{1}{5}$ is represented as $\theta = 0.0011$ for the first four bits. You may look at a circuit that I ran for this particular phase and these were the results -

Results

What these results show is that since the probability of measuring 0011 is the highest, it is indeed the phase approximation and the probability of that measurement outcome helped us to identify that.

To answer your second question, as to how the algorithm identifies the nearest integer to $2^{n}\theta$, I would say that this book's section 7.1.1 does a far better job at explaining that than I could here.

I hope this helps!

Answer 2

When you run a real quantum circuit, you do not get a list of the probabilities of each outcome. At best you get an estimate with accuracy depending on how many times you have run the thing. But ultimately, the idea is to run these algorithms on large systems and you only want to run it a small number of times. The accuracy of your probability estimate is so awful you shouldn't be using it for anything. The only real information you can extract from that resolution of information is in a case where only a couple of options have high probabilities (perhaps at least $4/\pi^2$ for the sake of argument). You run your circuit a very small number of times and the answer that is repeated the most is highly likely to be one of those cases. You very much do not need full probability data, just enough to ensure that you have resolved the difference between the most probable answer (the one you want) and everything else.

Indeed, a lot of the time, (e.g. Shor's algorithm) you ideally rely on being able to recognise the right answer when it comes along in order to help you minimise the number of repetitions.