TY - GEN
T1 - Quantum circuit complexity
AU - Yao, Andrew Chi Chih
PY - 1993
Y1 - 1993
N2 - 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 Bernstein and Vazirani [BV93], thus answering an open question raised in [BV93]. 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.
AB - 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 Bernstein and Vazirani [BV93], thus answering an open question raised in [BV93]. 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.
UR - https://www.scopus.com/pages/publications/0027873262
M3 - 会议稿件
AN - SCOPUS:0027873262
SN - 0818643706
T3 - Annual Symposium on Foundatons of Computer Science (Proceedings)
SP - 352
EP - 361
BT - Annual Symposium on Foundatons of Computer Science (Proceedings)
A2 - Anon, null
PB - Publ by IEEE
T2 - Proceedings of the 34th Annual Symposium on Foundations of Computer Science
Y2 - 3 November 1993 through 5 November 1993
ER -