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

A Note On Deutsch-Jozsa Algorithm

Zhengjun Cao, Jeffrey K. Uhlmann, Lihua Liu

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

We remark that Deutsch-Jozsa algorithm has confused two unitary transformations: one is performed on a pure state, the other is performed on a superposition. In the past decades, no constructive specifications on the essential unitary operator performed on the superposition have been found. We think the Deutsch-Jozsa algorithm needs more constructive specifications so as to check its correctness.

Related papers

Deutsch and Jozsa's Algorithm Revisited

J. Cooper

A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed

arXiv:quant-ph/0603231•Mar 27, 2006•0 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 eBooks•May 1, 2026•0 citations

Experimental implementation of the Deutsch-Jozsa algorithm for three-qubit functions using pure coherent molecular superpositions

Jiří Vala, Zohar Amitay, Bo Zhang +2 more

The Deutsch-Jozsa algorithm is experimentally demonstrated for three-qubit functions using pure coherent superpositions of ${\mathrm{Li}}_{2}$ rovibrational eigenstates. The function's character, either constant or balanced, is evaluated by first imprinting the function, using a phase-shaped femtosecond pulse, on a coherent superposition of the molecular states, and then projecting the superposition onto an ionic final state, using a second femtosecond pulse at a specific time delay.

arXiv:quant-ph/0107058•Physical Review A•Dec 26, 2002•78 citations

An implementation of the Deutsch–Jozsa algorithm on a three-qubit NMR quantum computer

Noah Linden, Hervé Barjat, Ray Freeman

Chemical Physics Letters•Oct 1, 1998•137 citations

Implementation of the Deutsch-Jozsa algorithm violates nonlocal realism

Koji Nagata

The European Physical Journal D•Dec 8, 2009•6 citations

Experimental Implementation of the Deutsch-Jozsa Algorithm for Three-Qubit Functions using Rovibrational Molecular Wave Packets Representation

Jiří Vala, Zohar Amitay, Bo Zhang +2 more

The Deutsch-Jozsa algorithm is experimentally demonstrated for three-qubit functions using pure coherent superpositions of Li$_{2}$ rovibrational eigenstates. The function's character, either constant or balanced, is evaluated by first imprinting the function, using a phase-shaped femtosecond pulse, on a coherent superposition of the molecular states, and then projecting the superposition onto an ionic final state, using a second femtosecond pulse at a specific time delay.

•Jul 10, 2001•1 citation
We remark that Deutsch-Jozsa algorithm has confused two unitary transformations: one is performed on a pure state, the other is performed on a superposition. In the past decades, no constructive specifications on the essential unitary operator performed on the superposition have been found. We think the Deutsch-Jozsa algorithm needs more constructive specifications so as to check its correctness.
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.
The Deutsch-Jozsa algorithm is experimentally demonstrated for three-qubit functions using pure coherent superpositions of Li2{\mathrm{Li}}_{2}Li2​ rovibrational eigenstates. The function's character, either constant or balanced, is evaluated by first imprinting the function, using a phase-shaped femtosecond pulse, on a coherent superposition of the molecular states, and then projecting the superposition onto an ionic final state, using a second femtosecond pulse at a specific time delay.
The Deutsch-Jozsa algorithm is experimentally demonstrated for three-qubit functions using pure coherent superpositions of Li2_{2}2​ rovibrational eigenstates. The function's character, either constant or balanced, is evaluated by first imprinting the function, using a phase-shaped femtosecond pulse, on a coherent superposition of the molecular states, and then projecting the superposition onto an ionic final state, using a second femtosecond pulse at a specific time delay.