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 speed-up 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 with 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 a historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also a simplified Deutsch–Jozsa problem proposed later, which is more popular in the field; however, it is irrelevant for the present paper.

arXiv:2210.07088Royal Society Open ScienceFeb 28, 202312 citations

uantum Advantage and the Evolution of Query Complexity a Critical Analysis of the Deutsch, Deutsch–Jozsa, and Simon Algorithms

Medak Srinivas

Quantum computation transformed our thinking about computational complexity by showing that quantum mechanical principles can be used to reduce the number of queries needed to solve some problems. The work constitutes a critical analysis of the evolution of the query complexity through three fundamental quantum algo rithms: the Deutsch algorithm, the Deutsch–Jozsa algorithm and Simon’s algorithm. Together, these algorithms illustrate the emergence of quantum advantage where quantum systems outperform classical deterministic and probabilistic approaches by exploiting superposition, interference, entanglement and unitary evolution.The study begins with the Deutsch algorithm, the first demonstration that a quantum computer can compute a global property of a Boolean function with fewer oracle queries than any deterministic classical algorithm. We further extend the analysis to the Deutsch–Jozsa algorithm, which generalizes this speedup to the exponential level by distinguishing between balanced and constant Boolean functions with one quantum query. Then we study Simon’s Algorithm, a milestone that achieved an exponential separation between classical randomized and quantum query complexity. The groundwork for many later advances, such as Shor’s algorithm for factoring integers, was established by this body of work. The discussion continues with an emphasis on Linear Algebra and the use of Hilbert spaces, Tensor Products, Unitary Transformations, and Fourier based interference methods. As the report describes, significant advancements toward reducing the time it takes for quantum systems to perform calculations are made possible through use of Oracle construction, Spectral Decomposition, and Mea surement Theory. This comparative analysis explores the use of computational queries in deterministic, probabilistic, and quan tum models while examining the transition from classical decision tree complexities into quantum computation paradigms. Ultimately, the results of this analysis show that the early quantum algorithms must be recognized not merely as isolated computational oddities, but rather as crucial components of the development of quantum information sci ence. They provided a conceptual and mathematical framework for the modern understanding of what constitutes a quantum advantage; Moreover, they also provide valuable insight into how quantum mechanical systems influ ence both computational efficiency and complexity theory, specifically as well as future information processing system design.

Iterative International Publishers eBooksMay 1, 20260 citations