0
$\begingroup$

Is there any small 'toy' oracle that can show the feasibility of Grover's algorithm for searching (without using the geometric rotation interpretation)?

It is confusing that we cannot know the solution of the search problem in one application of the oracle, as

  1. The oracle can recognize for any candidate $x$ whether it is a solution or not.
  2. The oracle is applied simultaneously to all candidates, as it is applied to an equal superposition at the beginning of the algorithm.

An example of an actual small 'toy' oracle would show why the above conjecture (find the solutions in one application of the oracle) cannot hold.

$\endgroup$

1 Answer 1

1
$\begingroup$

You don't really need a specific example of an oracle, you can see it as a general property of quantum measurement: you can perform a computation on all basis states in parallel, but measurement restricts the amount of information you get out of that computation.

For the sake of the argument let's say we're looking at an oracle that searches through all 2-bit strings to find one that equals "01".

Let's say you're using a marking oracle, and apply it to 2 qubits in equal superposition and an auxiliary qubit to mark the solution. You get the state that is a superposition of 4 basis states:

$$|00\rangle \otimes |0\rangle + |01\rangle \otimes |1\rangle + |10\rangle \otimes |0\rangle + |11\rangle \otimes |0\rangle$$

Now you need to figure out which of the basis states that are part of this superposition has the last qubit in the $|1\rangle$ state. If you just measure the last qubit, you get only 25% chance of getting the basis state that has 1 in the last bit (and produces the answer), and 75% chance of getting another state that won't produce an answer. It's the same as picking out a random input and checking whether it is the answer to the problem.

In contrast, using Grover's search yields the answer (in this case) after the same 1 iteration with 100% certainty.

$\endgroup$

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.

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