1
$\begingroup$

I am having doubts about the physicality of the quantum oracle used in the quantum search algorithms. The standard definition of the search problem (e.g Nielsen and Chuang) states that we are searching some set for marked elements. If we let the number of elements be $N=2^{n}$, and $x$ be the index of the element then we can describe the decision variant of the problem using the following function. \begin{align} f(x)=\begin{cases} 0, & \text{element of index $x$ isn't marked}\\ 1, & \text{element of index $x$ is marked} \end{cases} \end{align} The oracle is defined as a unitary operator that takes an $n$-qubit computational basis state as an control and acts on an "oracle" qubit if the control is marked, \begin{align} \hat{O}_{f}|x\rangle|q\rangle=|x\rangle|q \oplus f(x)\rangle \end{align} My problem is, I can't see how we can physically have a quantum operator that can recognise the classical information of if an element index of a set is marked. The only way I can imagine this being possible is if the operator is designed knowing all the marked elements, in this scenario I don't see why the algorithm would even be useful. Could someone describe the physical realisation of this situation?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

You do not need to know the marked elements. In general, what the oracle does is helping you identify what you are looking for by bringing your qubits in such a state that (after applying some other gates, Hadamard is very common for example), you can tell the marked element (or whatever you are looking for, in general) from the result of the measurement/s.


Another simple illustrative example is the Deutsch algorithm: you have two types of functions: constant (either 0, or 1) or balanced (half the values are 0, and half are 1). There are such four functions given and you don't know which is which. Now pick a function at random and tell whether it is balanced or constant. I won't go into too much detail about the whole algorithm, but I just want to show what the oracle does. The quantum circuit for this problem is the following: quantum circuit

The state of the top qubit after passing through the oracle is this: enter image description here

After passing through the oracle, it gets through a Hadamard gate. It should be clear that after this, you can tell if your function is constant or balanced, because a Hadamard gate sends $ \ | + \rangle $ to $ \ | 0 \rangle $ and $ \ | - \rangle $ to $ \ | 1 \rangle $. So, depending on whether you get 0 or 1 after measuring, you get the exponents of -1 from above and therefore the function type.

$\endgroup$

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