5
$\begingroup$

Why is the application of an oracle function not a measurement, causing the collapse of the system? How can you know the state of the system (the input of the oracle function) without measurement?

$\endgroup$
  • $\begingroup$ I do not find the two answers very satisfying. An oracle function in e.g. the Grover algorithm returns a value based on the state of the system, correct? How can this be? Perhaps I miss the point here but the question seems logical. The same can be asked about conditional gates, I don't quite understand those either... $\endgroup$ – michiel perdeck Jun 2 at 15:18
  • $\begingroup$ I think this comment does a good job at highlighting the source of confusion. You indeed seem to be wondering more generally about the ideas behind unitary gates and in particular conditional ones. I would suggest asking more directly about this misconception is in a separate post though, as although the matter is related, it would require changing the question here and thus make some of the answers less apt to the question. You could ask something along the lines of "Why don't conditional gates involve measurements?" (or whatever best captures your confusion) $\endgroup$ – glS Jun 2 at 22:29
  • 1
    $\begingroup$ Well, an oracle in practice is a bunch of gates, organised in a specific fashion, so if you accept that gates are not measurements, then automatically oracles cannot be measurements. $\endgroup$ – onurcanbektas Jun 15 at 5:17
3
$\begingroup$

An application of an oracle does not return a value; rather, it modifies the state of the system in a non-collapsing way. The oracles are a bit similar to controlled gates in this respect (in fact, a lot of oracles rely on controlled gates for their implementation). Consider, for example, CNOT gate: it does not measure the control qubit and apply an X gate to the target qubit based on measurement results, but rather it is a unitary gate described by a matrix

$$\mathrm{CNOT} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

The oracles are the same: they do not return any value; instead they are unitary transformations which implement classical functions in the following way:

  1. Define the effect of the oracle on all basis states, using the classical function it implements.
  2. This will automatically define the effect of the oracle on all superposition states: the oracle is a quantum operation and has to be linear in the state on which it acts. The oracle will be applied to superposition states - this is what "calculating the value of the function on all inputs at once" formulation you sometimes see refers to.

CNOT is an example of an oracle which implements classical function $f(x) = x$: you can check that its effects on basis states follow the rule $\mathrm{CNOT} |x \rangle |y \rangle = |x \rangle |y \oplus x \rangle = |x \rangle |y \oplus f(x) \rangle$, which is the definition of the oracle effect.


The second part - about the oracles being defined by their effect on basis states using linearity - is implicit in a lot of sources I've seen, and is a frequent source of confusion - the definition of oracle effects on basis states makes it very tempting to try and measure the input state. If you need more mathematical details on this, we ended up writing it up here.

There are also lots of questions about quantum oracles on this site - it is a bit weird that there is no "oracle" tag, but if you look for Deutsch, Deutsch-Jozsa or Grover algorithms, a lot of the questions are about the oracles.

$\endgroup$
2
$\begingroup$

Since this question seems to be in the context of Grover's search, I will explain using what happens in Grover's search, however, this is way more general.

The oracle function $f$ itself can be thought of a specification as to what should happen given various basis states (in fact, just classical bit strings to classical bit strings). For example, $f$ can be: $$ |00\rangle \rightarrow |0\rangle \\ |01\rangle \rightarrow |1\rangle \\ |10\rangle \rightarrow |0\rangle \\ |11\rangle \rightarrow |0\rangle \\$$

At this point, you need not think about implementation. However, when we do implement it, we want to ensure there is no reduction in qubits, and the gate is unitary, so we make a unitary version of any function as follows:

$$U(|x\rangle \otimes |y\rangle) = |x\rangle \otimes |\bar x \oplus f(x)\rangle $$

Now we have a unitary gate with a specification of what happens to every basis state, so we implement it as we would a unitary.

I don't know the exact physics of how a unitary gate is implemented, but it is not a state-dependent process, so it is not necessary to know the state before applying the gate, hence, knowing the input state, or measuring it beforehand is not necessary.

Hence application of an oracle does not cause the state to collapse.

$\endgroup$
  • 1
    $\begingroup$ Did you mean to write $|00\rangle$ four times there? $\endgroup$ – user2357112 supports Monica Jun 3 at 6:25
  • $\begingroup$ @user2357112, thanks, edited! $\endgroup$ – Mahathi Vempati Jun 3 at 7:22
1
$\begingroup$

It's hard to know what are you referring to without context, but a "quantum oracle" is just a type of (generally unitary) gate. As such, it does not provide information about the system, and neither it induces collapse. You can find more details about oracles in this other question (and links therein).

You cannot know the state of the system without measurement, that is true, but that is not what an oracle does. A measurement will most probably be performed at some stage after the oracle was applied.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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