2
$\begingroup$

I have been puzzling over the fact that Grover's algorithm seems to require an exponential number of ancilla qubits in the input size $n$ in order to function. My reasoning is that at every step of the Grover iteration, the reflection operator $U_\omega$ relies on an ancilla qubit which takes on the value $0$ or $1$ depending on the value of $f(x)$ for each $|x\rangle$. But at the end of the iteration, we cannot afford to clear, replace or tamper with this ancilla qubit, because it is highly entangled with the rest of the system and will cause superpositions to collapse. Thus, it seems that at every iteration of the Grover subroutine, we must add an additional ancilla qubit, which remains entangled with all the other qubits as the algorithm runs. In other words, it seems that the qubit demands of Grover's algorithm should be $O(2^{n/2})$ to search $\{0,1\}^n$. Doesn't this make Grover's algorithm substantially harder to implement than the classical analogue, which only uses $n$ bits? In other words, aren't we trading a quadratic decrease in runtime for an exponential increase in memory requirements?

$\endgroup$
3
  • $\begingroup$ You're right, Grover's algorithm is substantially more difficult that classical search. $\endgroup$ Aug 18, 2023 at 17:49
  • $\begingroup$ @user1271772: But then why is it considered an improvement on classical search? It seems like if the quantum version is less powerful than the classical version, it hardly deserves recognition. $\endgroup$ Aug 18, 2023 at 20:30
  • $\begingroup$ It is considered an improvement by people who do not know better, or who want to make people think it's an improvement so that they can get funding or so that they don't need to learn how to do research in unfamiliar fields. I would call it a "potential improvement" in which the word "potential" depends on the ability to make quantum computers that are good enough. Currently it's not foreseeable that we will see that happen in the next 20 or maybe 70 years, unless a breakthrough discovery is made. For hardware, in ~30 yrs I only seem to see incremental improvements rather than breakthroughs. $\endgroup$ Aug 18, 2023 at 22:19

2 Answers 2

3
$\begingroup$

The ancilla shouldn't be entangled with the main register after every iteration and the same ancilla qubit should be able to be reused for every iteration, in fact the ancilla's state shouldn't change at all due to phase kickback.

The ancilla-aided version of the Grover oracle is implemented as a controlled gate targeting the ancilla applied depending on whether a computational basis state on the main register is marked by the oracle or not, but the ancilla and the gate are such that the gate only applies a global phase of $\pi$ to it (multiplication by -1), implemented typically as either a $Z$ on $|1\rangle$ or an $X$ on $|-\rangle$. When the main register is in a superposition of both marked and unmarked computational basis states, the phase kickback created by this will result in the state of the ancilla being unaffected and remain unentangled and the portions of the main register's superposition that did trigger the gate (the "marked" ones) will have their phases reversed, which allows the diffusion operator to then reverse back and boost the magnitude of their amplitudes compared to the ones that were unmarked.

$\endgroup$
1
  • $\begingroup$ I think you're assuming that quantum computers can implement quantum circuits exactly as they appear in textbooks. In the real world CNOT|11> is not |10>, and qubits don't evolve according to e^(-iHt) with H being defined only by your circuit. Phase kick-back is a concept that is derived from assuming that qubits evolve according to simple Markov chains of matrix multiplication. That's not how they evolve though. $\endgroup$ Aug 18, 2023 at 22:26
1
$\begingroup$

There is an explicit example of solving constraint satisfaction problems by the Grover's algorithm. It needs only a single ancillary spin. Although strong entanglement is generated during physical implementation of the oracle, the state of this ancillary spin is trivial at the end of each computation step. https://arxiv.org/pdf/2304.10488.pdf

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.