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

Wiley eBooks

Quantum Parallelism

Sándor Imre, Ferenc Balázs

Published Nov 19, 2004• 0 citations
Publisher

Abstract

This chapter contains sections titled: Introduction Deutsch–Jozsa Algorithm Simon Algorithm Further Reading
DOI
10.1002/9780470869048.ch5

Related papers

The Deutsch-Jozsa Algorithm

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 9.1 The Algorithm, 9.2 The Analysis, 9.3 Problems, 9.4 Summary and Notes

•Jan 1, 2014•0 citations

Two Simple Quantum Algorithms

Sándor Imre, Ferenc Balázs

This chapter contains sections titled: Superdense Coding Quantum Teleportation Further Reading

Wiley eBooks•Nov 19, 2004•1 citation

Quantum Algorithms

Seyed Massoud Amini

We give a short overview of quantum algorithms. Some famous algorithms such as Deutsch-Jozsa and Simon are covered with more details. The directions for further development are addressed,

•Jun 1, 2009•0 citations

Quantum Algorithms

David McMahon

This chapter contains sections titled: Hadamard Gates The Phase Gate Matrix Representation of Serial and Parallel Operations Quantum Interference Quantum Parallelism and Function Evaluation Deutsch-Jozsa Algorithm Quantum Fourier Transform Phase Estimation Shor's Algorithm Quantum Searching and Grover's Algorithm Exercises

Wiley eBooks•Mar 23, 2007•0 citations

An Overview of Quantum Algorithms: Detailed Analysis of the Deutsch-Jozsa and Grover's Algorithms

Daniil Krizhanovskyi

•Jan 1, 2024•2 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•36 citations
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.