How come classical Deutsch-Jozsa is $O(1)$ when allowing "a small error rate"?

Question

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.

Answer 1

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).

Answer 2

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)$.