Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0603231

Deutsch and Jozsa's Algorithm Revisited

J. Cooper

Published Mar 27, 2006• 0 citations
arXivHTMLPDF

Abstract

A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed
DOI
10.48550/arxiv.quant-ph/0603231

Related papers

Quantum computation with classical light: Implementation of the Deutsch–Jozsa algorithm

Benjamin Perez-García, Melanie G. McLaren, Sandeep K. Goyal +3 more

Physics Letters A•Apr 10, 2016•19 citations

The Deutsch-Jozsa Algorithm Can Be Used for Quantum Key Distribution

Koji Nagata, Tadao Nakamura

We review the new type of Deutsch-Jozsa algorithm proposed in [K.Nagata and T.

OALib•Jan 1, 2015•20 citations

Implementation of Deutsch and Deutsch–Jozsa-like algorithms involving classical entanglement of elastic bits

Pierre A. Deymier, Keith Runge, M. Arif Hasan

Wave Motion•Jun 18, 2022•3 citations

‘Quantum supremacy’ revisited: low-complexity, deterministic solutions of the original Deutsch–Jozsa problem in classical physical systems

László B. Kish

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.07088•Royal Society Open Science•Feb 28, 2023•15 citations

The Deutsch-Jozsa algorithm and the bulk ensemble NMR quantum computer

Ryuichi Sawae, Y. Mori, Minaru Kawamura +2 more

In a bulk quantum computing it is shown by Collins that the iteration number of the Grover's algorithm will be decreased as compared with that number in case of a single quantum computer system. We discuss some of the implications on the Deutsch-Jozsa algorithm in a bulk quantum computing, and have a plan to prove them experimentally.

International Conference Physics and Control•Oct 4, 2006•1 citation

Analysis of Deutsch-Jozsa Quantum Algorithm.

Zhengjun Cao, Jeffrey K. Uhlmann, Lihua Liu

•Jan 1, 2018•1 citation
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.