计算机科学

首页 > 计算机科学

量子复杂性理论

2018-07-27 09:27:58     所属分类:计算机科学小作品

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

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

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

量子查询复杂性

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

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

像搜寻无结构数据库的Grover算法英语Grover's algorithm即为量子算法,其量子查询复杂性为O(N1/2),比已知最好的传统查询复杂度有二次方的差距。

参考资料

  • John Watrous. Quantum Computational Complexity. 2008. arXiv:0804.3401v1 quant-ph. 
  • Artem Kaznatcheev. Quantum query complexity. 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/338472.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


相关推荐