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
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...
Item-based top-<i>N</i>recommendation algorithms
The explosive growth of the world-wide-web and the emergence of e-commerce has led to the development of recommender systems ---a personalized information filtering technology u...
ECA-Net: Efficient Channel Attention for Deep Convolutional Neural Networks
Recently, channel attention mechanism has demonstrated to offer great potential in improving the performance of deep convolutional neural networks (CNNs). However, most existing...
Handbook of Genetic Algorithms
This book sets out to explain what genetic algorithms are and how they can be used to solve real-world problems. The first objective is tackled by the editor, Lawrence Davis. Th...
Structure prediction for CASP8 with all‐atom refinement using Rosetta
Abstract We describe predictions made using the Rosetta structure prediction methodology for the Eighth Critical Assessment of Techniques for Protein Structure Prediction. Aggre...
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