量子复杂性理论¶
简介¶
**量子复杂性理论**研究量子计算的效率边界和分类。
复杂性类¶
基本定义¶
| 复杂性类 | 描述 |
|---|---|
| BPP | 经典概率多项式时间 |
| BQP | 量子概率多项式时间 |
| QMA | 量子Merlin-Arthur |
| PSPACE | 多项式空间 |
关系¶
\[
\text{P} \subseteq \text{BPP} \subseteq \text{BQP} \subseteq \text{PSPACE}
\]
量子优势问题¶
BQP-complete 问题
- Shor算法对应的整数分解
- 模拟量子系统
- Jones多项式计算
未解问题¶
P vs BQP
P = BQP 吗？这是计算理论的重要未解问题
上一章: Grover算法详解 | 下一层: 硬件实现 (L4)