# Grover Search / Amplitude Amplification vs. real world Quantum Computer

I read the literature about Grover's Algorithm and Amplitude AmplificationI understand why it delivers (in theory) a quadratic speedup. However I somewhat wonder how this translates to a real world quantum computer.

As I understand it a crucial step for Grover's algorirthm is to be able to prepare a n-Qbit system in the state

$$\Psi = \frac{1}{\sqrt{2^n}}\sum_k |k\rangle$$

In particular this implies that the precision of the preparation needs to increase as the number $n$ of Qbits is scaled up. However (as a none physicist) I assume that preparation of such a state to some arbitrary precision is impossible with practical available technology. Or to put it in numbers, for $n=100$ I assume it would require a precision somewhat better than $10^{-15}$ and for $n=1000$ even better than $10^{-15}$. My naive assumption is that we cannot prepare much better than we are able to measure.

First question: is this assumption true?

Second question which rests on my assumption above: Obviously scientists are researching quantum error correction and always better algorithms. The current solution seems to be to add more quantum bits plus clever maths to resolve this. Under the assumption of limited preparation precision but perfect quantum operations, what is the order of the minimal number of additional Qbits required to still get a solution to the Grover problem?

My naive assumption would be that the additional precision requirements imply that one would need $O(n)$ physical Qbits per perfect Qbit thus leading to the need for $O(n^2)$ physical Qbits.

With other words I suspect that Grover would not be able to realize the theoretical quadratic boost on a real quantum computer due to the limited capabilities in preparing quantum states.

Is this true or false? And why?

Third and final question: if my conclusions so far are right. Are there known theoretical limits on how precise we might prepare a quantum system? I know that there is something like a Planck limit but my lack of physical expertise makes it impossible for me to decide if this applies here or not.

Hints to the literature are also welcome of course.

• So I don't know enough about Grover's algorithm to make specific statements about how to do error correction on it. However, I will point out that while current quantum computers struggle to factor 15 into 3 and 5, that's just the beginning. The ENIAC in its entire operational history of 10 years did fewer calculations than a modern GPU can do in half a second. If quantum computers take a path remotely similar, we're going to see some pretty impressive improvements in the next few decades. – Cort Ammon Mar 21 '17 at 17:01
• I do not want to learn about possible promises of the benefits of such a technology. Even if we would not end up with the desired better quantum computers it will proceed science. I am interested in the question if there are "somewhat less obvious theoretical obstacles" to practical implementations or not. The question if there are practical obstacles is already answered by the fact that we do not yet have such computers. – Udo Klein Mar 22 '17 at 6:59

I assume that preparation of [the state $\frac{1}{\sqrt{2^n}}\sum_k |k\rangle$] to some arbitrary precision is impossible with practical available technology. [...] for $n=100$ I assume it would require a precision somewhat better than $10^{-15}$ [...]

First question: is this assumption true?

Nope. Preparing that state is actually really, really easy. You just start in the all-qubits-0 state then separately hit every qubit with a Hadamard operation.

As an analogy, suppose I flipped a thousand coins and asked you to describe the probability distribution. That distribution has super tiny probabilities, but that doesn't mean it's hard to prepare.

An important fact to keep in mind is that smaller amplitudes don't make errors worse. Speaking very informally, even though a $\pm 0.01$ error may dwarf your amplitudes by a factor of $2^{100}$, that error will ultimately only push the final output around by $\approx \pm 0.01$. Unitary operations don't amplify errors.

what is the order of the minimal number of additional Qbits required to still get a solution to the Grover problem? [I think it's] $O(n^2)$ physical Qbits.

Your guess is way too high. In an error correcting code targeting a specific error rate, each logical qubit can be represented by a constant number of physical qubits.

As the computation gets longer the constant factor does get a bit worse, because you need each operation to have less error for the total to stay under budget, but the factor only gets worse polylogarithmically.

You can think of the overhead as being something like $n \rightarrow n \cdot O((\lg t)^{O(1)})$ where $t$ is the number of steps. To understand why the overhead is not awful, just read up on quantum error correcting codes.

Are there known theoretical limits on how precise we might prepare a quantum system?

Precision isn't really a problem. The problem is complexity. An arbitrary 100-qubit quantum state is described by $2^{100}$ complex numbers. Preparing some of those states necessarily requires circuits with on the order of $2^{100}$ gates! That's completely intractable; we have to stick with states that can be prepared by reasonably sized circuits.

• Thanks for the explanation. Can you recommend any specific piece of literature where I should start reading about quantum error correction? – Udo Klein Mar 22 '17 at 19:45