Abstract
A nontechnical survey of recent quantum-mechanical discoveries that challenge generally accepted complexity-theoretic versions of the Church-Turing thesis is presented. In particular, the authors construct an oracle relative to which there exists a set that can be recognized in quantum polynomal time (QP), yet any Turing machine that recognizes it would require exponential time even if allowed to be probabilistic, provided that errors are not tolerated. In particular, QP is not contained in or equal to ZPP relative to this oracle. Furthermore, there are cryptographic tasks that are demonstrably impossible to implement with unlimited computing power probabilistic interactive turning machines, yet they can be implemented even in practice by quantum mechanical apparatus.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Keywords
OracleTuring machineProbabilistic logicComputer scienceTime hierarchy theoremTheoretical computer scienceTuringConstruct (python library)Quantum Turing machineSet (abstract data type)QuantumQuantum computerCryptographyUniversal Turing machineDiscrete mathematicsAlgorithmMathematicsArtificial intelligenceProgramming languageQuantum 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...
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...
Antenna systems for base station diversity in urban small and micro cells
The authors describe cross-correlation properties for compact urban base station antenna configurations, nearly all of which result in very low envelope cross-correlation coeffi...
Distributed code assignments for CDMA packet radio networks
Code-division multi-access (CDMA) techniques allow many users to transmit simultaneously in the same band without substantial interference by using approximately orthogonal (low...
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 ...
Publication Info
- Year
- 2003
- Type
- article
- Pages
- 132-137
- Citations
- 74
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
74
OpenAlex
4
Influential
21
CrossRef
Cite This
André Berthiaume,
Gilles Brassard
(2003).
The quantum challenge to structural complexity theory.
[1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference
, 132-137.
https://doi.org/10.1109/sct.1992.215388
Identifiers
- DOI
- 10.1109/sct.1992.215388