Abstract
Abstract 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.
Keywords
OracleNondeterministic algorithmQuantum computerComputer scienceExponential functionTime complexityPolynomialNPQuantum algorithmProbabilistic logicTheoretical computer scienceDecision problemQuantumAlgorithmMathematicsTuring machineArtificial intelligenceComputation
Affiliated Institutions
Related Publications
Quantum theory, the Church–Turing principle and the universal quantum computer
It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every f...
A heuristic discussion of probabilistic decoding
This is another in a series of invited tutorial, status and survey papers that are being regularly solicited by the PTGIT Committee on Special Papers. We invited Profess01 Fano ...
Theoretical Limitations on the Rate of Transmission of Information
A review of early work on the theory of the transmission of information is followed by a critical survey of this work and a refutation of the point that, in the absence of noise...
Distributed Kalman Filter with Embedded Consensus Filters
The problem of distributed Kalman filtering (DKF) for sensor networks is one of the most fundamental distributed estimation problems for scalable sensor fusion. This paper addre...
The theory of signal detectability
The problem of signal detectability treated in this paper is the following: Suppose an observer is given a voltage varying with time during a prescribed observation interval and...
Publication Info
- Year
- 2005
- Type
- article
- Pages
- 195-199
- Citations
- 19
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
19
OpenAlex
Cite This
André Berthiaume,
Gilles Brassard
(2005).
Oracle Quantum Computing.
, 195-199.
https://doi.org/10.1109/phycmp.1992.615538
Identifiers
- DOI
- 10.1109/phycmp.1992.615538