  The original Deutsch-Jozsa (oDJ) problem is for an oracle (realized here as a
database) of size N, where, according to their claim, the deterministic
solution of the problem on a classical Turing computer requires O(N)
computational complexity. They produced the famous Deutsch-Jozsa quantum
algorithm that offered an exponential speedup over the classical computer,
namely O[log(N)] complexity for the solution in a quantum computer. In this
paper, the problem is implemented on an instantaneous noise-based logic
processor. It is shown that, similarly to the quantum algorithm, the oDJ
problem can deterministically be solved with O[log(N)] complexity. The
implication is that by adding a truly random coin to a classical Turing machine
and using this classical-physical algorithm can also speed up the deterministic
solution of the Deutsch-Jozsa problem exponentially, similarly to the quantum
algorithm. Then it is realized that the same database and the solution of the
Deutsch-Jozsa problem can also be realized by using an identical algorithmic
structure in a simpler way, even without noise/random coin. The only lost
function in this new system, as compared to noise-based logic, is the ability
to do generic parallel logic operations over the whole database. As the latter
feature is not needed for the oDJ problem, it is concluded that the problem can
be solved on a classical computer with O[log(N)] complexity even without a
random coin. Therefore, while the oDJ algorithm is historically important step
in the developments of quantum computers, it is insufficient to prove quantum
supremacy. Note, there is also simplified Deutsch-Jozsa problem proposed later,
which is more popular in the field, however it is irrelevant for the present
paper.
