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

Proceedings of the Royal Society of London Series A Mathematical and Physical Sciences

Rapid solution of problems by quantum computation

David Deutsch, Richard Jozsa

Published Dec 8, 1992• 2,675 citations
Publisher

Abstract

Abstract A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.
DOI
10.1098/rspa.1992.0167

Related papers

Fast quantum algorithms for handling probabilistic, interval, and fuzzy uncertainty

M. Martinez, Luc Longpré, Владик Крейнович +2 more

We show how quantum computing can speed up computations related to processing probabilistic, interval, and fuzzy uncertainty.

Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS)•Jun 22, 2004•12 citations

Oracle Quantum Computing

André Berthiaume, Gilles Brassard A

Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated, nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer.

Journal of Modern Optics•Dec 1, 1994•99 citations

Solving a problem in the quantum way

M.P. John

A general quantum algorithm for solving a problem is discussed. The number of steps required to solve a problem using this method is independent of the number of cases that has to be considered classically. Hence, it is more efficient than existing classical algorithms or quantum algorithm, which requires O(sqrt(N)) steps.

arXiv:quant-ph/0301153•Jan 28, 2003•0 citations

Oracle Quantum Computing

André Berthiaume, Gilles Brassard A

Building on work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer. The results given in this paper have been presented at the 7th Annual IEEE Symposium on Structure in Complexity Theory, Boston, June 1992, and at the Workshop on Physics and Computation, PhysComp '92, Dallas, October 1992; they have appeared in preliminary form in those Proceedings [7, 8]. y Supported in part by an Nserc postgraduate fellowship. z Supported in part by Canada's Nserc E. W. R. Steacie Memorial Fellowship an...

Workshop on Physics and Computation (PhysComp)•Aug 24, 2005•20 citations

Oracle Quantum Computing

Departement Iro

This paper continues the study of the power of oracles to separate quantum com.plexity classes from classical (including probabilistic and nondeterministic) complexity classes, which we initiated in an earlier paper [5]. The new results are that, under appropriate oracles, (1) there is a decision problem that can be solved in polynomial time on the quantum computer, which would classically require exponential time in the worst case even on a nondeterministic computer (in particular QP g NP relative to this oracle), and (2) there is a decision problem that can be solved in exponential time on the quantum computer for which any deterministic classical computer would require double exponential time on all but finitely many instances.

•Jan 1, 1993•6 citations

On the Power of Quantum Computation: Oracles

Niklas Johansson

Quantum computation solve some computational problems faster than the best-known alternative in classical computation. The evidence for this consists of examples where a quantum algorithm outperfor ...

•Jan 1, 2018•0 citations
Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated, nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer.
Building on work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer. The results given in this paper have been presented at the 7th Annual IEEE Symposium on Structure in Complexity Theory, Boston, June 1992, and at the Workshop on Physics and Computation, PhysComp '92, Dallas, October 1992; they have appeared in preliminary form in those Proceedings [7, 8]. y Supported in part by an Nserc postgraduate fellowship. z Supported in part by Canada's Nserc E. W. R. Steacie Memorial Fellowship an...
This paper continues the study of the power of oracles to separate quantum com.plexity classes from classical (including probabilistic and nondeterministic) complexity classes, which we initiated in an earlier paper [5]. The new results are that, under appropriate oracles, (1) there is a decision problem that can be solved in polynomial time on the quantum computer, which would classically require exponential time in the worst case even on a nondeterministic computer (in particular QP g NP relative to this oracle), and (2) there is a decision problem that can be solved in exponential time on the quantum computer for which any deterministic classical computer would require double exponential time on all but finitely many instances.