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
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...
Stochastic Petri net representation of discrete event simulations
In the context of discrete event simulation, the marking of a stochastic Petri net (SPN) corresponds to the state of the underlying stochastic process of the simulation and the ...
Performance evaluation of genetic algorithms for flowshop scheduling problems
The aim of this paper is to evaluate the performance of genetic algorithms for the flowshop scheduling problem with an objective of minimizing the makespan. First we examine var...
Low-density parity-check codes
A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed number <tex xmlns:mml="http://www....
New spectral methods for ratio cut partitioning and clustering
Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...
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