I'm reading Quantum Computing: An Applied Approach, by Hidary. Chapter 8.2 (p104) says:

While it is true that Deutsch-Jozsa demonstrates an advantage of quantum over classical computing, if we allow for a small error rate, then the advantage disappears: both classical and quantum approaches are in the order of $O(1)$ time complexity.

How is it possible that classical DJ can work with a single oracle query? I am probably missing something deep about the meaning of "a small error rate". An intuitive explanation would be preferred over a heavy-math one, if possible.


2 Answers 2


Be careful to differentiate $O(1)$ queries and $1$ query. In the first case, you only need a constant number of queries, that is a number of queries not dependent on $n$.

Intuitively, if you do $100$ requests and they are all equal, either you're very unlucky, or with high probability the function is constant.

The "very unlucky" term can be quantified and is independent of $n$ : after $k$ identical queries you can return a result with low probability of error, that is around $2^{-k}$ (that may be incorrect, I haven't actually done the computations but hopefully you have the idea).

  • 1
    $\begingroup$ Oh! That make sense! The "small error" is bound by a constant (define by how small the error, not the input length) therefore it is constant complexity. Thanks! $\endgroup$
    – luciano
    Jul 30, 2021 at 14:13

Recall that the Deutsch-Jozsa algorithm is to identify the function

$$f:\{0,1,2,\cdots,2^n-1\}\rightarrow \{0,1\}$$

whether it is constant ($f(x)$ are constant for all $x$) or balanced ($f(x)=0$ for half $x$ and $f(x)=1$ for the other half $x$).

Assuming that you do $t$ queries (repetitions are allowed) to the function $f$, if there exist $x_1 \neq x_2$ among all the $x$ such that $f(x_1) \neq f(x_2)$, it would be definite that $f$ is balanced and no errors would be introduced. If $f(x)=0$ (or $f(x)=1$) for all $t$ values of $x$ but $f$ is balanced in reality, the only error case occurs and the occurring probability should be $$P_e = (2^{n-1})^t/(2^{n})^t = 2^{-t}, $$ which decreases exponentially with $t$. If $P_e$ is set to be samll but constant, constant $t$ is enough, that is, $t=O(1)$.


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.