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:0810.2285

An elementary derivation of the Deutsch-Jozsa algorithm

Neda Amin, Patrick Labelle

Published Oct 13, 2008• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0810.2285

Related papers

A Pedagogical Introduction to the Deutsch and Deutsch-Jozsa Algorithms

Aniket Guchhait

The Deutsch and Deutsch-Jozsa algorithms are foundational in the study of quantum computing, providing early and elegant demonstrations of quantum speedup over classical computation. This paper offers a pedagogical exposition of both algorithms, beginning with the necessary background in quantum computation and culminating in detailed, step-by-step derivations of the algorithms, complete with mathematical formulations and circuit diagrams. Simulations using quantum gates are also discussed to enhance understanding. The aim is to make these seminal algorithms accessible to readers with a basic background in linear algebra and quantum mechanics.

•Jan 1, 2025•0 citations

Classical realization of the quantum Deutsch algorithm

Yohan Vianna de Almeida, Mariana R. Barros, Malena O. Hor-Meyll

In the rapidly growing area of quantum information, the Deutsch algorithm is ubiquitous and, in most cases, the first one to be introduced to any student of this relatively new field of research. The reason for this historical relevance stems from the fact that, although extremely simple, the algorithm conveys all the main features of more complex quantum computations. In spite of its simplicity, the uncountable experimental realizations of the algorithm in a broad variety of physical systems are in general quite involved. The aim of this work is two-fold: to introduce the basic concepts of quantum computation for readers with just a minimum knowledge of quantum mechanics and to present a novel and entirely accessible implementation of a classical analogue of the quantum Deutsch algorithm. By employing only elementary optical devices, such as lenses and diode lasers, this experimental realization has a striking advantage over all previous implementations: it can easily be understood and reproduced in most basic undergraduate or even high-level school laboratories.

arXiv:1903.06655•American Journal of Physics•Nov 20, 2018•7 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

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•2 citations

How to introduce techinical details of quantum computing in a theory of computation class: using the basic case of the Deutsch-Jozsa algorithm

Olga M. Kosheleva, Владик Крейнович

Many students taking the theory of computation class have heard about quantum computing and are curious about it. However, the usual technical description of quantum computing requires a large amount of preliminary information, too much to fit into an already packed class. In this paper, we propose a way to introduce technical details of quantum computing that does not require much time – it can be described in less than an hour. As such an introduction, we use a simplified description of the basic case of one of the pioneering algorithms of quantum computing. 1 Formulation of the Pedagogical Problem Quantum computing is very promising. It is known that quantum computing is a promising direction in computing; see, e.g., [4]. Let us just give two examples: • a quantum computing algorithm proposed by Grover enables us to search in an unsorted array of size n in time √ n [2, 3]; • a quantum computing algorithm proposed by Shor enables us to factorize large integers in polynomial time [5]. Since the difficulty of eavesdropping on RSA-encrypted messages – which underlie most current encryption schemes – relies on the difficulty of factoring large integers, this will enable us to read all encrypted messages.

International Journal of Computing and Optimization•Jan 1, 2016•4 citations

A Generalization of Deutch-Jozsa Algorithm

Elton Ballhysa

Quantum Computation is seen as an alternative paradigm for computing as the physical implentations for the basic information unit, the binary digit, approach the atomic level. As the laws of quantum mechanics take over at this level, quantum phenomena such as superposition, the ensuing parallelism and entanglement can be harnessed to offer faster algorithms. Deutch- Jozsa was the first problem for such an algorithm was exhibited that was provably faster than any deterministic classical algorithm. Here we make an attempt at a generalization of this algorithm, hoping that it could lead to similar generalizations for other quantum algorithms.

•Jun 30, 2009•0 citations
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.
The Deutsch and Deutsch-Jozsa algorithms are foundational in the study of quantum computing, providing early and elegant demonstrations of quantum speedup over classical computation. This paper offers a pedagogical exposition of both algorithms, beginning with the necessary background in quantum computation and culminating in detailed, step-by-step derivations of the algorithms, complete with mathematical formulations and circuit diagrams. Simulations using quantum gates are also discussed to enhance understanding. The aim is to make these seminal algorithms accessible to readers with a basic background in linear algebra and quantum mechanics.
In the rapidly growing area of quantum information, the Deutsch algorithm is ubiquitous and, in most cases, the first one to be introduced to any student of this relatively new field of research. The reason for this historical relevance stems from the fact that, although extremely simple, the algorithm conveys all the main features of more complex quantum computations. In spite of its simplicity, the uncountable experimental realizations of the algorithm in a broad variety of physical systems are in general quite involved. The aim of this work is two-fold: to introduce the basic concepts of quantum computation for readers with just a minimum knowledge of quantum mechanics and to present a novel and entirely accessible implementation of a classical analogue of the quantum Deutsch algorithm. By employing only elementary optical devices, such as lenses and diode lasers, this experimental realization has a striking advantage over all previous implementations: it can easily be understood and reproduced in most basic undergraduate or even high-level school laboratories.
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.
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.
Many students taking the theory of computation class have heard about quantum computing and are curious about it. However, the usual technical description of quantum computing requires a large amount of preliminary information, too much to fit into an already packed class. In this paper, we propose a way to introduce technical details of quantum computing that does not require much time – it can be described in less than an hour. As such an introduction, we use a simplified description of the basic case of one of the pioneering algorithms of quantum computing. 1 Formulation of the Pedagogical Problem Quantum computing is very promising. It is known that quantum computing is a promising direction in computing; see, e.g., [4]. Let us just give two examples: • a quantum computing algorithm proposed by Grover enables us to search in an unsorted array of size n in time √ n [2, 3]; • a quantum computing algorithm proposed by Shor enables us to factorize large integers in polynomial time [5]. Since the difficulty of eavesdropping on RSA-encrypted messages – which underlie most current encryption schemes – relies on the difficulty of factoring large integers, this will enable us to read all encrypted messages.
Quantum Computation is seen as an alternative paradigm for computing as the physical implentations for the basic information unit, the binary digit, approach the atomic level. As the laws of quantum mechanics take over at this level, quantum phenomena such as superposition, the ensuing parallelism and entanglement can be harnessed to offer faster algorithms. Deutch- Jozsa was the first problem for such an algorithm was exhibited that was provably faster than any deterministic classical algorithm. Here we make an attempt at a generalization of this algorithm, hoping that it could lead to similar generalizations for other quantum algorithms.