For faster navigation, this Iframe is preloading the Wikiwand page for 量子复杂性理论.

量子复杂性理论

维基百科,自由的百科全书

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

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

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

量子查询复杂性

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

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

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

参考资料

外部链接

{{bottomLinkPreText}} {{bottomLinkText}}
量子复杂性理论
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.