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

IEEE Symposium Series on Computational Intelligence (SSCI)

How to Use Quantum Computing to Check Which Inputs Are Relevant: A Proof That Deutsch-Jozsa Algorithm Is, In Effect, the Only Possibility

Владик Крейнович, Martine C. Ceberio, Ricardo O. de Alba Alvarez

Published Dec 1, 2019• 3 citations
Publisher

Abstract

One of the main reasons why computations - in particular, engineering computations - take long is that, to be on the safe side, models take into account all possible affecting features, most of which turn out to be not really relevant for the corresponding physical problem. From this viewpoint, it is desirable to find out which inputs are relevant. In general, the problem of checking the input's relevancy is itself NP-hard, which means, crudely speaking, that no feasible algorithm can always solve it. Thus, it is desirable to speed up this checking as much as possible. One possible way to speed up such a checking is to use quantum computing, namely, to use the Deutsch-Josza algorithm. However, it is not clear whether a more efficient quantum algorithm is possible for solving this problem. In this paper, we show that the Deutsch-Josza algorithm is, in effect, the only possible way to use quantum computing for checking which inputs are relevant - so no alternative quantum algorithms are possible.

DOI
10.1109/ssci44817.2019.9002709

Related papers

More advanced quantum algorithms

Jonathan A. Jones, Dieter Jaksch

Deutsch's algorithm and Grover's quantum search are theoretically interesting, but it is not obvious that these two algorithms are actually useful for anything important. We next consider a selection of more advanced algorithms, several of which may have real-life applications. Some of these will be too complicated to explain fully, and their properties will only be sketched briefly. The Deutsch–Jozsa algorithm Deutsch's algorithm is simple, but important, as it shows that a quantum algorithm can find a property of an unknown function (its parity) with a smaller number of queries than any possible classical algorithm (one rather than two). For this reason we can say that quantum computing is more efficient than classical computing within the oracle model of function evaluation. (It is widely believed that quantum computing is more efficient than classical computing in general, but this is a surprisingly hard thing to prove.) The simplicity of the algorithm is also an advantage, as it can be implemented on very primitive quantum computers. Beyond this, however, Deutsch's algorithm is also important as the simplest member of a large family of quantum algorithms, including most notably Shor's quantum factoring algorithm. The second simplest algorithm in the family is the Deutsch–Jozsa algorithm, which solves a very closely related problem. Consider an unknown binary function with n input bits, giving N = 2 n possible inputs, and a single output bit.

Cambridge University Press eBooks•Jul 19, 2012•0 citations

The Deutsch-Josza algorithm for n-qudits

Gabriela Mogos

Abstract: Over the last decade has been a lot of interest in new types of computable machines, due partly over the fears on conventional, classical, computing. Research by leading physicists, mathematicians and computer scientists has shown quantum computers could be the future, as they may be able to solve some computationally difficult problems much faster than is currently possible on a classical computer. David Deutsch has already created a working model for a quantum computer, the quantum Turing machine or QTM Deutsch [1985]. This has been proved as a model for computation on a quantum and has allowed algorithms to be developed. Deutsch-Josza’s algorithm, as all known quantum algorithms that provide exponential speedup over classical systems do, answers a question about a global property of a solution space. This paper describes the generalization of the Deutsch-Josza algorithm to n d-dimensional quantum systems or qudits. Key–Words: quantum computing, quantum dits, quantum algorithm 1

•Nov 21, 2007•2 citations

A Good First Impression for Quantum Algorithms

Sandeep K. Shukla

What is the first quantum algorithm that students should learn? A common choice is the Deutsch-Jozsa algorithm because of its historical importance. However, the algorithm and the problem it solves are disconnected from familiar computational tasks and approaches. This paper provides an alternate starting point: the decision version of search. The main algorithmic idea is simple, involving encoding a function into a quantum state, and checking whether this quantum state is equal to a reference state. Moreover, we retain the Deutsch-Jozsa problem and algorithm as a special case of this presentation. We hope that students will find this a more satisfying start to studying quantum algorithms.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Deutsch-Jozsa algorithm via deterministic quantum computaion 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 study the presence of quantum correlations on the implementation of Deutsch- Jozsa algorithm running in the DQC1 model. We extend the analysis to a previous experimental realization of this computation presented in Phys. Rev. A 78, 022317 (2008). The Deutsch-Jozsa algorithm, an oracle based problem, can efficiently be solved in this model. Although there is no quantum correlations in the initial and final states of the computation, we find quantum correlations in intermediate steps of the algorithm. 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 one. The reason for this unexpected result relies on the fact that we have access to the outcomes of the control qubit only. A comparison between the efficiency of DQC1 and DQCp circuits to solve the Deustch-Jozsa problem is also presented.

•Jul 24, 2013•0 citations

Efficient classical simulation of the Deutsch-Jozsa algorithm

Niklas Johansson, Larsson, Jan-Åke

In 1985, David Deutsch challenged the Church-Turing thesis by stating that his quantum model of computation "could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine". While this is thought to be true in general, there is usually no way of knowing that the corresponding classical algorithms are the best possible solutions. Here we provide an efficient classical simulation of the Deutsch-Jozsa algorithm, which was one of the first examples of quantum computational speed-up. Our conclusion is that the Deutsch-Jozsa quantum algorithm owes its speed-up to resources that are not necessarily quantum-mechanical, and when compared with the classical simulation offers no speed-up at all.

arXiv:1506.04627•Jun 15, 2015•1 citation

An elementary derivation of the Deutsch-Jozsa algorithm

Neda Amin, Patrick Labelle

Quantum computing takes fully advantage of the superposition principle to increase greatly (even exponentially) the speed of calculations, relative to the classical approach. The Deutsch-Jozsa algorithm is the simplest quantum algorithm illustrating this power. Unfortunately, the standard derivation involves several ingenious steps which usually leave students feeling that they could never have figured out the algorithm by themselves. We present here a different formulation of the problem which allows students to derive the algorithm using only basic knowledge of quantum mechanics and linear algebra.

arXiv:0810.2285•Oct 13, 2008•0 citations
One of the main reasons why computations - in particular, engineering computations - take long is that, to be on the safe side, models take into account all possible affecting features, most of which turn out to be not really relevant for the corresponding physical problem. From this viewpoint, it is desirable to find out which inputs are relevant. In general, the problem of checking the input's relevancy is itself NP-hard, which means, crudely speaking, that no feasible algorithm can always solve it. Thus, it is desirable to speed up this checking as much as possible. One possible way to speed up such a checking is to use quantum computing, namely, to use the Deutsch-Josza algorithm. However, it is not clear whether a more efficient quantum algorithm is possible for solving this problem. In this paper, we show that the Deutsch-Josza algorithm is, in effect, the only possible way to use quantum computing for checking which inputs are relevant - so no alternative quantum algorithms are possible.
Deutsch's algorithm and Grover's quantum search are theoretically interesting, but it is not obvious that these two algorithms are actually useful for anything important. We next consider a selection of more advanced algorithms, several of which may have real-life applications. Some of these will be too complicated to explain fully, and their properties will only be sketched briefly. The Deutsch–Jozsa algorithm Deutsch's algorithm is simple, but important, as it shows that a quantum algorithm can find a property of an unknown function (its parity) with a smaller number of queries than any possible classical algorithm (one rather than two). For this reason we can say that quantum computing is more efficient than classical computing within the oracle model of function evaluation. (It is widely believed that quantum computing is more efficient than classical computing in general, but this is a surprisingly hard thing to prove.) The simplicity of the algorithm is also an advantage, as it can be implemented on very primitive quantum computers. Beyond this, however, Deutsch's algorithm is also important as the simplest member of a large family of quantum algorithms, including most notably Shor's quantum factoring algorithm. The second simplest algorithm in the family is the Deutsch–Jozsa algorithm, which solves a very closely related problem. Consider an unknown binary function with n input bits, giving N = 2 n possible inputs, and a single output bit.
Abstract: Over the last decade has been a lot of interest in new types of computable machines, due partly over the fears on conventional, classical, computing. Research by leading physicists, mathematicians and computer scientists has shown quantum computers could be the future, as they may be able to solve some computationally difficult problems much faster than is currently possible on a classical computer. David Deutsch has already created a working model for a quantum computer, the quantum Turing machine or QTM Deutsch [1985]. This has been proved as a model for computation on a quantum and has allowed algorithms to be developed. Deutsch-Josza’s algorithm, as all known quantum algorithms that provide exponential speedup over classical systems do, answers a question about a global property of a solution space. This paper describes the generalization of the Deutsch-Josza algorithm to n d-dimensional quantum systems or qudits. Key–Words: quantum computing, quantum dits, quantum algorithm 1
What is the first quantum algorithm that students should learn? A common choice is the Deutsch-Jozsa algorithm because of its historical importance. However, the algorithm and the problem it solves are disconnected from familiar computational tasks and approaches. This paper provides an alternate starting point: the decision version of search. The main algorithmic idea is simple, involving encoding a function into a quantum state, and checking whether this quantum state is equal to a reference state. Moreover, we retain the Deutsch-Jozsa problem and algorithm as a special case of this presentation. We hope that students will find this a more satisfying start to studying quantum algorithms.
Quantum correlations have been pointed out as the most likely source of the speed-up in quantum computation. Here we study the presence of quantum correlations on the implementation of Deutsch- Jozsa algorithm running in the DQC1 model. We extend the analysis to a previous experimental realization of this computation presented in Phys. Rev. A 78, 022317 (2008). The Deutsch-Jozsa algorithm, an oracle based problem, can efficiently be solved in this model. Although there is no quantum correlations in the initial and final states of the computation, we find quantum correlations in intermediate steps of the algorithm. 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 one. The reason for this unexpected result relies on the fact that we have access to the outcomes of the control qubit only. A comparison between the efficiency of DQC1 and DQCp circuits to solve the Deustch-Jozsa problem is also presented.
In 1985, David Deutsch challenged the Church-Turing thesis by stating that his quantum model of computation "could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine". While this is thought to be true in general, there is usually no way of knowing that the corresponding classical algorithms are the best possible solutions. Here we provide an efficient classical simulation of the Deutsch-Jozsa algorithm, which was one of the first examples of quantum computational speed-up. Our conclusion is that the Deutsch-Jozsa quantum algorithm owes its speed-up to resources that are not necessarily quantum-mechanical, and when compared with the classical simulation offers no speed-up at all.
Quantum computing takes fully advantage of the superposition principle to increase greatly (even exponentially) the speed of calculations, relative to the classical approach. The Deutsch-Jozsa algorithm is the simplest quantum algorithm illustrating this power. Unfortunately, the standard derivation involves several ingenious steps which usually leave students feeling that they could never have figured out the algorithm by themselves. We present here a different formulation of the problem which allows students to derive the algorithm using only basic knowledge of quantum mechanics and linear algebra.