Abstract
The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of functions, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the PTM. In fact, drawing on this work, Shor has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.
Keywords
Quantum algorithmQuantum computerTuring machineComplexity classQuantum Turing machineQuantumMathematicsProbabilistic logicQuantum sortOracleDiscrete mathematicsComputationTime complexityComputer scienceQuantum error correctionAlgorithmQuantum mechanicsPhysics
Related Publications
On the power of quantum computation
The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum me...
Strengths and Weaknesses of Quantum Computing
Recently a great deal of attention has focused on quantum computation following a sequence of results suggesting that quantum computers are more powerful than classical probabil...
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...
The quantum challenge to structural complexity theory
A nontechnical survey of recent quantum-mechanical discoveries that challenge generally accepted complexity-theoretic versions of the Church-Turing thesis is presented. In parti...
Oracle Quantum Computing
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 polyno...
Publication Info
- Year
- 1997
- Type
- article
- Volume
- 26
- Issue
- 5
- Pages
- 1474-1483
- Citations
- 1261
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1261
OpenAlex
731
CrossRef
Cite This
Daniel Simón
(1997).
On the Power of Quantum Computation.
SIAM Journal on Computing
, 26
(5)
, 1474-1483.
https://doi.org/10.1137/s0097539796298637
Identifiers
- DOI
- 10.1137/s0097539796298637