量子复杂性理论

✍ dations ◷ 2025-09-10 10:06:18 #量子复杂性理论

量子复杂性理论（Quantum complexity theory）是理论计算机科学中计算复杂性理论的一部分。该理论使用量子计算机和量子信息来研究分析复杂性类定义，量子信息是基于量子力学的计算模型。量子复杂性理论用来研究这些复杂性类的问题的困难度，和量子复杂性类与经典（非量子的）复杂性类的关系。复杂性类是指的是一群复杂度类似的问题的集合，可以用满足特定资源限制下的算法求解。例如复杂性类P就是可以用图灵机在多项式时间内求解的问题。也可以用量子算法（如量子计算机或量子图灵机）定义量子复杂性，例如复杂度BQP就是可以用量子计算机在多项式时间内解决，其错误的几率小于一定比例的问题。量子复杂性中二个比较重要的复杂性类分别是BQP及QMA（英语：QMA），分别对应复杂度P及NP (复杂度)。量子复杂性理论的一个主要目的是要找到对应传统复杂性类（如P、NP、PSPACE、PP等）的量子复杂性。在量子查询复杂性（Quantum Query Complexity）中，输入由一预言机（黑箱）提供，算法要用查询预言机的方式得到和输入相关的信息，算法由某个固定的量子状态开始，当对预言机查询时，其状态随之变化。量子查询复杂性是指要计算其对应函数，需要查询预言机的最小次数，量子查询复杂性是函数整体时间复杂性的下限。像搜索无结构数据库的Grover算法即为量子算法，其量子查询复杂性为O(N1/2)，比已知最好的传统查询复杂度有二次方的差距。

相关

VATC代码V（其他）是解剖学治疗学及化学分类系统的一个分类，这是由世界卫生组织药物统计方法整合中心（The WHO Collaborating Centre for Drug Statistics Methodology）所制定的药品
法利赛人法利赛人(.mw-parser-output .Polytonic{font-family:"SBL BibLit","SBL Greek","EB Garamond","EB Garamond 12","Foulis Greek",Cardo,"Gentium Plus",Gentium,"Theano Di
无神论者的赌注对宗教的批评 · 自由思想反教权主义 · 反宗教虚构宗教无神论者的赌注，因迈克尔·马丁（英语：Michael Martin (philosopher)）发表在他1990年出版的书《无神论：哲学的正信》中而
布宜诺斯艾利斯大学布宜诺斯艾利斯大学（西班牙语：Universidad de Buenos Aires，UBA）是阿根廷最大的大学，创立于1821年8月12日。它由13个院系、六家医院、10个博物馆和3所中学组成。下列学院组成的大
多枝霉草多枝霉草（学名：Sciaphila ramosa）为霉草科喜荫草属下的一个种。
Hsub5/subPsub3/subOsub10/sub三聚磷酸，又称三磷酸，是一种磷酸缩合而成的多酸，化学式为H5P3O10。三聚磷酸再与一分子磷酸缩合则形成四聚磷酸（H6P4O13）。一些化合物是三聚磷酸的酯，例如ATP（三磷酸腺苷）。
盎格鲁街盎格鲁街（Promenade des Anglais，意为“英国人步行道”）是法国东南部城市尼斯一条沿着地中海蔚蓝海岸的著名的海滨步行道。在尼斯城市化以前，尼斯海岸还只是一片荒芜的海滩，被大
法尔茅斯法尔茅斯（英语：Falmouth）可能是指:
李德生李德生（1922年10月17日－），中国石油地质学家。出生于上海。籍贯江苏苏州。1945年毕业于国立中央大学地质系。1991年当选为中国科学院学部委员（院士）。2001年当选为第三世界科学院院
卫满朝鲜卫满朝鲜（朝鲜语：위만조선／衛滿朝鮮 Wiman joseon；前195年—前108年），又称卫氏朝鲜（朝鲜语：위씨조선／衛氏朝鮮 Wissi joseon），是一个由燕人卫满建立的古朝鲜政权。君主 · 首都 ·