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

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.

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

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