While reading about Grover's mean estimation algorithm, I came across this post on StackExchange. As an undergrad, there are several points I don't quite understand.

  1. What is the role of $f(x)$. Consider I have a list of numbers, such as $0.1, 0.2, 0.3, 0.4$ and I want to calculate the mean. What exactly is $f(x)$ mapping? What exactly is $x$ here? My wildest guess is that the above numbers are labelled as $00, 01, 10, 11$ and these binary strings are referred to as $x$. In this sense $f(x)$ behaves more like a table to associate $00 \rightarrow 0.1$, $00 \rightarrow 0.2$, etc. Is this the correct understanding?

  2. What computation on the ancilla? The aforementioned post also suggest that perform a computation of $f(x)$ on an ancilla register. What does the computation mean?

  3. How does this controlled-rotation look like? It appears to me that three registers are needed to implement this algorithm. To achieve this controlled-rotation, which bit is used as control?

  • $\begingroup$ please try to focus your post to cover a single, very specific question. You can open multiple questions to ask multiple things $\endgroup$
    – glS
    Oct 23, 2020 at 6:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.