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
Nondeterministic algorithmOracleQuantum computerComputer scienceExponential functionTime complexityNPPolynomialQuantum algorithmProbabilistic logicQuantumConstruct (python library)Theoretical computer scienceAlgorithmMathematicsTuring machineQuantum mechanicsArtificial intelligencePhysicsComputation
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...
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...
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f ∈ C N and a randomly chosen set of freque...
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
- 1994
- Type
- article
- Volume
- 41
- Issue
- 12
- Pages
- 2521-2535
- Citations
- 98
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
98
OpenAlex
52
CrossRef
Cite This
André Berthiaume,
Gilles Brassard
(1994).
Oracle Quantum Computing.
Journal of Modern Optics
, 41
(12)
, 2521-2535.
https://doi.org/10.1080/09500349414552351
Identifiers
- DOI
- 10.1080/09500349414552351