Abstract
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 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 function, 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 probabilistic Turing Machine. In fact, drawing on this work, Shor (1994) has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Keywords
Turing machineProbabilistic logicQuantum Turing machineQuantum computerComplexity classQuantum algorithmOracleComputer scienceQuantumFunction (biology)LogarithmTheoretical computer scienceClass (philosophy)Discrete mathematicsComputationTime complexityAlgorithmMathematicsArtificial intelligenceQuantum error correctionQuantum mechanicsPhysics
Affiliated Institutions
Related Publications
On the Power of Quantum Computation
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...
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...
Quantum circuit complexity
We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a qua...
Algorithms for quantum computation: discrete logarithms and factoring
A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation tim...
An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
A cryptographic system is described which is secure if and only if computing logarithms over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 116-123
- Citations
- 476
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
476
OpenAlex
132
Influential
256
CrossRef
Cite This
Damien Simon
(2002).
On the power of quantum computation.
Proceedings 35th Annual Symposium on Foundations of Computer Science
, 116-123.
https://doi.org/10.1109/sfcs.1994.365701
Identifiers
- DOI
- 10.1109/sfcs.1994.365701