I'm new to quantum computing and trying to learn the basics. In the Deutsch–Jozsa algorithm, the oracle function $ f: \{ 0,1 \}^n \to \{0, 1\}$ is defined as a quantum circuit, which doesn't change the input bits if feed-in $|0\rangle$ or $|1\rangle$. But somehow feeding all $|+\rangle$, the input is changed based on whether $f$ is balanced or constant. This is a bit confusing since by definition function doesn't change input.


1 Answer 1


This is the whole magic of quantum computing with oracles. The mechanism is called "phase kickback".

You say

by definition function doesn't change input

This is not quite true. The function doesn't change the input if the input is a basis state.

But quantum mechanics is a linear theory. This means that the action on superpositions is entirely defined by the action on basis states. In particular, if you have two inputs that have different outputs, $$ |x\rangle|0\rangle\mapsto |x\rangle|0\rangle,\qquad |y\rangle|0\rangle\mapsto |y\rangle|1\rangle $$ and you supply them in superposition, the whole output is entangled. $$ (|x\rangle+|y\rangle)|0\rangle\mapsto|x\rangle|0\rangle+|y\rangle|1\rangle $$ There's no way that you can talk about just the input by itself, and you certainly cannot say that the input is unchanged.

The whole trick then is to prepare states very carefully so that they change the input qubits in just the way we want. Let's say you had an oracle evaluating a function $f:\{0,1\}^n\rightarrow\{0,1\}$. Classically, you get at most 1 bit of information from a single run because the only information available is at the output. Quantumly, you can now get information from the $n$ input bits as well (in practice, it's $n$ bits of information not $n+1$). Hence the potential for a huge speed-up in our gain of information.

  • $\begingroup$ right. but probably use a different term other than function ? as function is by definition a mapping. highlight the difference between quantum circuit implementation of function and a mathematical function really helps on reduce confusion. $\endgroup$
    – yupbank
    May 26, 2022 at 14:54
  • 1
    $\begingroup$ OK, so if I was being more careful, I'd probably talk about the "unitary implementation of the function" (or even just reversible implementation), but the language gets sufficiently clunky that it very quickly becomes synonymous with "the function". $\endgroup$
    – DaftWullie
    May 26, 2022 at 15:58

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.