量子复杂性理论
图灵机
量子计算机
量子算法
复杂度等级
布尔函数
电路复杂度
量子图灵机
量子电路
多项式的
可计算函数
量子
离散数学
计算机科学
时间复杂性
功能(生物学)
构造(python库)
班级(哲学)
数学
算法
量子纠错
电子线路
量子力学
物理
人工智能
程序设计语言
数学分析
计算
进化生物学
生物
标识
DOI:10.1109/sfcs.1993.366852
摘要
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.< >
科研通智能强力驱动
Strongly Powered by AbleSci AI