量子复杂性理论

量子复杂性理论（Quantum complexity theory）是理论计算机科学中计算复杂性理论的一部分。该理论使用量子计算机和量子信息来研究分析复杂性类定义，量子信息是基于量子力学的计算模型。量子复杂性理论用来研究这些复杂性类的问题的困难度，和量子复杂性类与经典（非量子的）复杂性类的关系。

复杂性类是指的是一群复杂度类似的问题的集合，可以用满足特定资源限制下的算法求解。例如复杂性类P就是可以用图灵机在多项式时间内求解的问题。也可以用量子算法（如量子计算机或量子图灵机）定义量子复杂性，例如复杂度BQP就是可以用量子计算机在多项式时间内解决，其错误的几率小于一定比例的问题。

量子复杂性中二个比较重要的复杂性类分别是BQP及QMA，分别对应复杂度P及NP (复杂度)。量子复杂性理论的一个主要目的是要找到对应传统复杂性类（如P、NP、PSPACE、PP等）的量子复杂性。

量子查询复杂性

在量子查询复杂性（Quantum Query Complexity）中，输入由一预言机（黑箱）提供，算法要用查询预言机的方式得到和输入相关的信息，算法由某个固定的量子状态开始，当对预言机查询时，其状态随之变化。

量子查询复杂性是指要计算其对应函数，需要查询预言机的最小次数，量子查询复杂性是函数整体时间复杂性的下限。

像搜索无结构数据库的Grover算法即为量子算法，其量子查询复杂性为O(N^1/2)，比已知最好的传统查询复杂度有二次方的差距。

参考资料

• John Watrous. Quantum Computational Complexity. 2008. arXiv:0804.3401v1  [quant-ph]. 
• Artem Kaznatcheev. Quantum query complexity. [2015-05-03]. （原始内容存档于2020-11-27）. 
• Nielsen, Michael; Chuang, Isaac. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. 2000. ISBN 978-0-521-63503-5. OCLC 174527496. 
• Arora, Sanjeev; Barak, Boaz. Computational Complexity: A Modern Approach. Cambridge University Press. 2016: 201–236. ISBN 978-0-521-42426-4. 
• Watrous, John. Quantum Computational Complexity. 2008. arXiv:0804.3401v1  [quant-ph]. 
• Watrous J. (2009) Quantum Computational Complexity （页面存档备份，存于互联网档案馆）. In: Meyers R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY

外部链接

• MIT lectures （页面存档备份，存于互联网档案馆） by Scott Aaronson