I am reading John Watrous' notes from his course CPSC 519 on quantum computing. In a pre-discussion before presenting Deutsch's algorithm to determine whether a function is constant or not, the author presents a function $B_f |x \rangle |y \rangle = |x \rangle |y \oplus f(x) \rangle $, and the diagram: enter image description here

The inital state is $|0 \rangle |1 \rangle$, and after the first two Hadamard transforms, will be $$\big(\frac {1} {\sqrt 2} |0\rangle +\frac {1} {\sqrt 2} |1\rangle\big)\big(\frac {1} {\sqrt 2} |0\rangle-\frac {1} {\sqrt 2} |1\rangle\big) .$$

Up to this far I understand. The author then writes: "After performing the $B_f$ operation the state is transformed to:

$$\frac {1} {2} |0 \rangle \big(|0 \oplus f(0)\rangle - |1 \oplus f(0)\rangle\big) + \frac {1} {2} |1 \rangle \big(|0 \oplus f(1)\rangle) - |1 \oplus f(1) \rangle\big).$$

I am not sure how this was obtained, from what I understand, the operation should be $$\frac {1} {\sqrt 2} \big( |0\rangle + |1\rangle\big) \otimes \big|(\frac {1} {\sqrt 2} |0\rangle +\frac {1} {\sqrt 2} |1\rangle) \oplus f(\frac {1} {\sqrt 2} |0\rangle +\frac {1} {\sqrt 2} |1\rangle) \big\rangle$$ (simply subbing in $x,y$ to $B_f$). Any insights appreciated as this subject is completely new to me, although I have a decent mathematics and computer science background.


1 Answer 1


Remember that when you define the oracle effect as $B_f |x \rangle |y \rangle = |x \rangle |y \oplus f(x) \rangle $, $f(x)$ is a classical function of a classical 1-bit argument, so you do not have a way to compute $f(\frac {1} {\sqrt 2} |0\rangle +\frac {1} {\sqrt 2} |1\rangle)$ (a function of a quantum state).

The quantum oracles that implement classical functions are defined as follows:

  1. Define the effect of the oracle on all basis states for $|x\rangle$ and $|y\rangle$: $B_f |x \rangle |y \rangle = |x \rangle |y \oplus f(x) \rangle $.

  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. So if you start with a state $\frac{1}{2} (|00\rangle + |10\rangle - |01\rangle - |11\rangle)$ (which is the state after applying Hadamard gates) and apply the oracle, you need to apply oracle to each basis state separately. You'll get

$$B_f \frac{1}{2} (|00\rangle + |10\rangle - |01\rangle - |11\rangle) = \frac{1}{2} (B_f|00\rangle + B_f|10\rangle - B_f|01\rangle - B_f|11\rangle) =$$

$$ = \frac{1}{2} (|0\rangle|0 \oplus f(0)\rangle + |1\rangle|0 \oplus f(1)\rangle - |0\rangle|1 \oplus f(0)\rangle - |1\rangle|1 \oplus f(1)\rangle)$$

Which is the same as the expression in the notes, up to a different grouping or terms.

The part about the oracles being defined by their effect on basis states is implicit in a lot of sources I've seen, and is a frequent source of confusion. If you need more mathematical details on this, we ended up writing it up here.

  • 3
    $\begingroup$ Another resource that may be helpful is Learn Quantum Computing with Python and Q# which should have the chapter on Deutsch–Jozsa algorithm up shortly! We work though implementing Deutsch–Jozsa in Q# as well as in Python with QuTiP. <manning.com/books/…> $\endgroup$ May 14, 2019 at 22:00
  • $\begingroup$ Thanks so much for your help! I am very grateful :) $\endgroup$ May 14, 2019 at 23:02
  • $\begingroup$ "Define the effect of the oracle on all basis states for |x⟩"... Doesn't it mean that $f$ has to be called twice (for $x\in\{0, 1\}$) and quantum algorithm cost is same as deterministic: two uses of black box? I am lost here... $\endgroup$ Jul 16, 2021 at 18:38

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.