Abstract
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 quantum Turing machine has a polynomial-size quantum circuit. This result also enables us to construct a universal quantum computer which can simulate, with a polynomial factor slowdown, a broader class of quantum machines than that considered by E. Bernstein and U. Vazirani (1993), thus answering an open question raised by them. We also develop a theory of quantum communication complexity, and use it as a tool to prove that the majority function does not have a linear-size quantum formula.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Keywords
Quantum complexity theoryTuring machineQuantum computerQuantum algorithmComplexity classBoolean functionCircuit complexityQuantum Turing machineQuantum circuitPolynomialComputable functionQuantumDiscrete mathematicsComputer scienceTime complexityFunction (biology)Construct (python library)Class (philosophy)MathematicsAlgorithmQuantum error correctionElectronic circuitQuantum mechanicsPhysicsArtificial intelligenceProgramming language
Affiliated Institutions
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...
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...
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...
Applying the genetic approach to simulated annealing in solving some NP-hard problems
A stochastic approach called the annealing-genetic algorithm is presented for solving some well-known combinatorial optimization problems. This approach incorporates genetic alg...
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...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 352-361
- Citations
- 633
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
633
OpenAlex
0
Influential
94
CrossRef
Cite This
Andrew Chi-Chih Yao
(2002).
Quantum circuit complexity.
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
, 352-361.
https://doi.org/10.1109/sfcs.1993.366852
Identifiers
- DOI
- 10.1109/sfcs.1993.366852