量子计算模型

量子计算用可以叠加和纠缠的量子态取代经典比特，定义了诸如量子电路和复杂性类BQP等模型，这些模型似乎比任何经典方法都能更快地解决某些问题。

Definition

量子计算模型处理存储在量子比特中的信息，量子比特的状态是复数空间中的单位向量；计算应用可逆量子门来创建叠加和纠缠，最终测量产生一个经典结果，其概率由量子态决定。

Scope

本主题涵盖量子比特和量子门、量子电路模型及其与量子图灵机的等效性、高效量子计算的复杂性类BQP及其与经典类的关系、Shor因式分解和Grover搜索等基础算法，以及测量和退相干在定义模型中的作用。

Core questions

• 叠加和纠缠如何改变计算的能力？
• 高效量子类BQP与经典类之间有什么关系？
• 对于哪些问题，量子算法能提供可证明或明显的加速？
• 测量和不可克隆原理如何限制量子计算？

Key theories

量子电路模型和BQP

高效量子计算由通用门集上的多项式大小量子电路捕获，定义了BQP类，该类包含P，并被认为扩展了P，同时仍位于PSPACE内。

量子加速

Shor算法在多项式时间内分解整数，Grover算法以二次加速搜索非结构化空间，展示了量子模型在特定任务上的具体优势。

Clinical relevance

量子模型指导量子硬件和算法的设计；Shor因式分解算法威胁到其安全性依赖于因式分解难度的公钥密码系统，从而推动了后量子密码学的发展，而量子模拟有望在化学和材料科学领域取得进展。

History

费曼于1982年提出使用量子系统模拟物理，Deutsch于1985年将量子图灵机形式化。Shor的1994年因式分解算法和Grover的1996年搜索算法显示出具体的加速，使量子计算成为复杂性理论的一个主要分支和实验努力的驱动力。

Debates

量子优势有多大，它能否在大规模上物理实现？

量子计算机与经典计算机计算相同的功能，因此问题在于效率。BQP与经典类之间的精确关系尚未解决，尽管存在退相干，但能否构建大型容错量子计算机仍然是一个开放的科学和工程问题。

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

量子计算机能计算经典计算机无法计算的东西吗？

不能。量子计算机解决的问题类别与经典计算机完全相同；区别在于速度。对于某些问题，例如分解大数，量子模型似乎要快得多，但它并没有扩展原则上可计算的边界。

为什么量子计算对密码学很重要？

Shor算法将使大型量子计算机能够高效地分解大整数和计算离散对数，从而破解保护当今大部分通信的公钥系统。这一前景推动了基于即使对于量子机器也认为困难的问题的后量子方案的探索。