I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution without 'knowing' it. I somehow understood what is meant by recognizing and knowing the solution but the fact that the function processes all the superposition of states in parallel and gives an output is confusing! What does the function actually do? Does it match integers or can it detect other things like an intersection of two lines? I am sick of taking it as a black box. Without knowing how the function works I am incapable of knowing it's potential. Please help me.

Bottom line: how does $f(x)$ find the searched item amongst the superpositioned states and evaluate to 1? How are the superpositioned states evaluated by the function?


1 Answer 1

  1. Let $f$ be your favorite $\mathrm{SAT}$ problem. For example, one that I like is:

Are there integers $x_1, x_2, x_3$, each $-2^{50}\le x_1,x_2,x_3 \le 2^{50}$, with $x_1^3+x_2^3+x_3^3=42?$

  1. Write $f$ as a sequence of irreversible $\mathsf{NAND}$ gates, etc., and convert them to a sequence of reversible $\mathsf{CCNOT}$ gates, etc. to determine a unitary $U_f$. In the example problem, this unitary will take the $103$ bits of $x_i$ to a single output $y$. Here $y$ is $1$ if and only if the $\mathrm{SAT}$ problem is solved.

  2. Take a first register initially at $\vert 0\rangle$, and apply a Hadamard to put it in the uniform superposition of all states. In the example problem, the first register is $153$ qubits ($50$ plus $1$ sign bit each.)

  3. Apply $U_f$ to the second register conditioned on the first register. Thus, in the sample problem, the system is in the state $\vert x_1,x_2,x_3\rangle \vert f(x_1,x_2,x_3)\rangle$, where $x_1,x_2,x_3$ are between $-2^{50}$ and $2^{50}$ and $f$ is $1$ if and only if $x_1^3+x_2^3+x_3^3=42$

  4. Apply a phase shift to the first register conditioned on the value of the second register

  5. Apply the Grover diffusion operator to the first register

  6. Repeat steps 5 and 6 $O(\sqrt N)$ times. (With the sample problem, apply this $O(\sqrt {2^{153}})$ times.)

  7. If there's only one solution, the first register should be in the state that satisfies $f(x)=1$. With the sample problem, it should be in the state $\vert x_1,x_2,x_3\rangle$ solving $x_1^3+x_2^3+x_3^3=42$.

The heart of Grover is steps 5, 6, and 7. Steps 1-4 can be fiddled with.


$f$ is applied to the second register based on the values of the first register. The first register is left unchanged upon the application of $f$ to the second register. If the first register is in a uniform superposition over all states initially, then after application of $U_f$, acting on both the first register and the second register, the first register will still be in a uniform superposition. $U_f$ relies on the contents of $x$ to determine the contents of $y$ but it leaves the contents of $x$ unchanged.

For example, from the questions in your comments, I can tell that you understand that $f$ can be written classically as a set of irreversible $\mathsf{NAND},\mathsf{NOR},\mathsf{AND}$, etc. gates. Classically if we were to apply $f$, then we may lose the value of $x$. But remember quantum-mechanically the states must be reversible. Thus from your questions I think you also recognize that $\mathsf{NAND}$ gates etc. need to be converted to $\mathsf{CCNOT}$ gates etc. It's no surprise that these gates tend to leave some inputs unchanged - the qubits that are left unchanged would correspond to $x$, and the qubits that are changed would correspond to $f(x)$.

After application of $U_f$, for each possible value of the first register, a different value is stored in the second register, but the first register is unchanged.

Shor's algorithm is a little different - initially a uniform superposition is applied to a first register, then a value of some function is calculated in the second register. In Shor, we can throw away the second register; in Grover, we need to save the second register for the repeated conditional rotations (this part I think you understand).

  • $\begingroup$ I am pretty much still unsure about how the function evaluates superposition of 2^153 states at one go and decides if f(x) is 1 or 0. It iterates sqrt(N) times to make the reversed phase more prominent to occur as an output. But how does f actually work on x? Is it because of the series of quantum gates that you talked about? If it is, could you elaborate more about it? $\endgroup$ Commented Mar 28, 2019 at 7:23
  • $\begingroup$ @DebojyotiSarkar- were you able to solve the conundrum you had? $\endgroup$ Commented Apr 23, 2021 at 5:05

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.