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

Efficient Simulation of Deutsch's Algorithm.

Niklas Johansson

Published Jan 1, 2014• 0 citations
OpenAlex

Abstract

It is shown that Deutsch’s algorithm and the Deutsch-Jozsa algorithm for two and three qubits can be efficiently implemented on a classical computer. This is done by analysing the structure of the oracles contained in these algorithms, followed by an implementation in the toy theory proposed by Robert W. Spekkens which uses 2 classical bits to simulate a qubit. Further discussion is given about how to analyse, and possible implementations, of the Deutsch-Jozsa for higher number of qubits in the toy theory.

Related papers

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

Implementation of the Four-Bit Deutsch-Jozsa Algorithm with Josephson Charge Qubits

Norbert Schuch, Jens Siewert

We show that the Deutsch-Jozsa algorithm for up to four qubits can be realized with a setup of Josephson charge qubits. While existing proposals for the implementation of the algorithm (for up to three qubits) are based on certain classifications of the oracles, this approach becomes increasingly cumbersome for higher qubit numbers. Here we present a method to implement all balanced functions for the four-qubit algorithm by a fixed sequence of operations. The free parameters which define the implemented function are the rotation angles of 15 one-qubit operations.

physica status solidi (b)•Oct 1, 2002•10 citations

Efficient classical simulation of the Deutsch–Jozsa and Simon’s algorithms

Niklas Johansson, Jan-Åke Larsson

A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch–Jozsa and Simon’s problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch–Jozsa problem with probability 1 using only one oracle query, and Simon’s problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch–Jozsa and Simon’s problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.

arXiv:1508.05027•Quantum Information Processing•Aug 12, 2017•29 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

Efficient algorithms for the Deutsch-Jozsa and Simon's problems that only use classical resources

Niklas Johansson, Jan-Åke Larsson

A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch-Jozsa and Simon's problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch-Jozsa problem with probability 1 using only one oracle query, and Simon's problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch-Jozsa and Simon's problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms, and calls for further study of oracle separation between quantum and classical computation.

•Aug 20, 2015•1 citation

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
It is shown that Deutsch’s algorithm and the Deutsch-Jozsa algorithm for two and three qubits can be efficiently implemented on a classical computer. This is done by analysing the structure of the oracles contained in these algorithms, followed by an implementation in the toy theory proposed by Robert W. Spekkens which uses 2 classical bits to simulate a qubit. Further discussion is given about how to analyse, and possible implementations, of the Deutsch-Jozsa for higher number of qubits in the toy theory.
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.
We show that the Deutsch-Jozsa algorithm for up to four qubits can be realized with a setup of Josephson charge qubits. While existing proposals for the implementation of the algorithm (for up to three qubits) are based on certain classifications of the oracles, this approach becomes increasingly cumbersome for higher qubit numbers. Here we present a method to implement all balanced functions for the four-qubit algorithm by a fixed sequence of operations. The free parameters which define the implemented function are the rotation angles of 15 one-qubit operations.
A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch–Jozsa and Simon’s problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch–Jozsa problem with probability 1 using only one oracle query, and Simon’s problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch–Jozsa and Simon’s problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.
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.
A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch-Jozsa and Simon's problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch-Jozsa problem with probability 1 using only one oracle query, and Simon's problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch-Jozsa and Simon's problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms, and calls for further study of oracle separation between quantum and classical computation.
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.