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/9807012 · Physical Review A

Deutsch-Jozsa algorithm as a test of quantum computation

David C. Collins, K. W. Kim, William C. Holton

Published Sep 1, 1998• 144 citations
arXivHTMLPDF

Abstract

A redundancy in the existing Deutsch-Jozsa quantum algorithm is removed and a refined algorithm, which reduces the size of the register and simplifies the function evaluation, is proposed. The refined version allows a simpler analysis of the use of entanglement between the qubits in the algorithm and provides criteria for deciding when the Deutsch-Jozsa algorithm constitutes a meaningful test of quantum computation.

DOI
10.1103/physreva.58.r1633

Related papers

Scheme for Implementing Refined Deutsch–Jozsa Algorithm via Superconducing Qubits

Zheng Xiao-Hu, YU Ben-li, Zhang Gang +1 more

We propose a scheme of implementing the Deutsch–Jozsa algorithm based on superconducing charge qubits, which would be a key step to scale more complex quantum algorithms and very important for constructing a real quantum computer via superconducting charge qubits. The present scheme is simple but fairly efficient, and easily manipulated because arbitrary two-qubit can be selectively and effectively coupled by a common inductance. More manipulations can be carried out before decoherence sets in. The proposed scheme is in line with current technology.

Communications in Theoretical Physics•Apr 1, 2008•0 citations

Quantum Computing Concepts with Deutsch Jozsa Algorithm

Poornima Aradyamath, N. M. Naghabhushana, Rohitha Ujjinimatad

In this paper, we briefly review the basic concepts of quantum computation, entanglement, quantum cryptography and quantum fourier transform. Quantum algorithms like Deutsch Jozsa, Shor’s factorization and Grover’s data search are developed using fourier transform and quantum computation concepts to build quantum computers. Researchers are finding a way to build quantum computer that works more efficiently than classical computer. Among the standard well known algorithms in the field of quantum computation and communication we describe mathematically Deutsch Jozsa algorithm in detail for 2 and 3 qubits. Calculation of balanced and unbalanced states is shown in the mathematical description of the algorithm.

JOIV International Journal on Informatics Visualization•Jan 10, 2019•6 citations

Quantum correlations in Deutsch-Jozsa algorithm via deterministic quantum computation with one qubit model

Marcio M. Santos, Eduardo I. Duzzioni

Quantum correlations have been pointed out as the most likely source of the speed-up in quantum computation. Here we analyzed the presence of quantum correlations in the implementation of Deutsch-Jozsa algorithm running in the DQC1 and DQCp models of quantum computing. For some balanced functions, the qubits in DQC1 model are quantum correlated just in the intermediate steps of the algorithm for a given decomposition into one and two qubits gates. In the DQCp model the final state is strongly quantum correlated for some balanced functions, so that the pairwise entanglement between blocks scales with the system size. Although the Deutsch-Jozsa algorithm is efficiently implemented in both models of computation, the presence of quantum correlations is not a sufficient property for computational gain in this case, since the performance of the classical probabilistic algorithm is better than the quantum ones. The measurement of other qubits than the control one showed to be inefficient to turn the algorithm deterministic.

arXiv:1307.6286•Jul 24, 2013•0 citations

Demonstração óptica do algoritmo de Deutsch-Jozsa com 1 qubit

Mariana R. Barros

In this work we implement the Deutsch-Jozsa algorithm with one qubit by removing a redundancy on it, which reduces the size of the register and simpli es the function evaluation. In order to do this, we used a pair of photons produced by down convertion, where one of them is used as triguer and the other passes trougth a double slit; as result its output is in a superposition of paths, i.e., one qubit. Using a spatial light modulator (SLM) that puts phases on the paths of the photons, and detecting in coincidence, we demonstrate the Deutsch-Jozsa algorithm with photons, and using only one qubit.

•May 7, 2010•0 citations

Implementation of the Deutsch-Jozsa algorithm on an IBM quantum Computer

Sergeicheva, Skvortsov, Hismatov +1 more

The Deutsch-Jozsa algorithm has been implemented using the Qiskit software development kit and the IBM Quantum Lab. The accuracy of the algorithm is analyzed depending on the number of qubits and the results obtained on a real quantum computer and an emulator are compared.

Herald of Omsk University•Jun 10, 2025•0 citations

Efficient Simulation of the Deutsch-Jozsa Algorithm

Niklas Johansson

We provide a framework wherein one can simulate the Deutsch-Jozsa quantum algorithm on a regular computer within polynomial time, and with linear memory consumption. Under certain reasonable assumptions the simulation solves the problem with a bounded error of probability with only one function evaluation, which is comparable with the efficiency of the quantum algorithm. The provided framework lies within a slight extension of the toy model purposed by Robert W. Spekkens Phys. Rev. A 75 (2007), and consists of transformations that are reminiscent of transformations in quantum mechanics.

•Jan 1, 2015•1 citation
A redundancy in the existing Deutsch-Jozsa quantum algorithm is removed and a refined algorithm, which reduces the size of the register and simplifies the function evaluation, is proposed. The refined version allows a simpler analysis of the use of entanglement between the qubits in the algorithm and provides criteria for deciding when the Deutsch-Jozsa algorithm constitutes a meaningful test of quantum computation.
We propose a scheme of implementing the Deutsch–Jozsa algorithm based on superconducing charge qubits, which would be a key step to scale more complex quantum algorithms and very important for constructing a real quantum computer via superconducting charge qubits. The present scheme is simple but fairly efficient, and easily manipulated because arbitrary two-qubit can be selectively and effectively coupled by a common inductance. More manipulations can be carried out before decoherence sets in. The proposed scheme is in line with current technology.
In this paper, we briefly review the basic concepts of quantum computation, entanglement, quantum cryptography and quantum fourier transform. Quantum algorithms like Deutsch Jozsa, Shor’s factorization and Grover’s data search are developed using fourier transform and quantum computation concepts to build quantum computers. Researchers are finding a way to build quantum computer that works more efficiently than classical computer. Among the standard well known algorithms in the field of quantum computation and communication we describe mathematically Deutsch Jozsa algorithm in detail for 2 and 3 qubits. Calculation of balanced and unbalanced states is shown in the mathematical description of the algorithm.
Quantum correlations have been pointed out as the most likely source of the speed-up in quantum computation. Here we analyzed the presence of quantum correlations in the implementation of Deutsch-Jozsa algorithm running in the DQC1 and DQCp models of quantum computing. For some balanced functions, the qubits in DQC1 model are quantum correlated just in the intermediate steps of the algorithm for a given decomposition into one and two qubits gates. In the DQCp model the final state is strongly quantum correlated for some balanced functions, so that the pairwise entanglement between blocks scales with the system size. Although the Deutsch-Jozsa algorithm is efficiently implemented in both models of computation, the presence of quantum correlations is not a sufficient property for computational gain in this case, since the performance of the classical probabilistic algorithm is better than the quantum ones. The measurement of other qubits than the control one showed to be inefficient to turn the algorithm deterministic.
In this work we implement the Deutsch-Jozsa algorithm with one qubit by removing a redundancy on it, which reduces the size of the register and simpli es the function evaluation. In order to do this, we used a pair of photons produced by down convertion, where one of them is used as triguer and the other passes trougth a double slit; as result its output is in a superposition of paths, i.e., one qubit. Using a spatial light modulator (SLM) that puts phases on the paths of the photons, and detecting in coincidence, we demonstrate the Deutsch-Jozsa algorithm with photons, and using only one qubit.
We provide a framework wherein one can simulate the Deutsch-Jozsa quantum algorithm on a regular computer within polynomial time, and with linear memory consumption. Under certain reasonable assumptions the simulation solves the problem with a bounded error of probability with only one function evaluation, which is comparable with the efficiency of the quantum algorithm. The provided framework lies within a slight extension of the toy model purposed by Robert W. Spekkens Phys. Rev. A 75 (2007), and consists of transformations that are reminiscent of transformations in quantum mechanics.