量子复杂性理论

✍ dations ◷ 2025-12-01 04:10:33 #量子复杂性理论

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

相关

微分干涉相差显微镜微分干涉相差显微技术(DIC),又称Normarski干涉相差显微技术或Normarski显微镜,是一种增强对比度来观察未染色的透明的样品的光学显微镜。DIC根据干涉测量获取有关样品光路长
弥漫性血管内凝血弥散性血管内凝血（英语：Disseminated Intravascular Coagulation，简称DIC），又称消耗性凝血病，是指在某些致病因子的作用下，大量促凝物质入血，凝血因子和血小板被活化，使凝血酶增多，微
丝状噬菌体科丝杆噬菌体属短杆状噬菌体属丝状噬菌体科(Inoviridae, Filamentous Bacteriophages)，又译作丝杆噬菌体科，是单链DNA病毒的一科。
论文论文是科学或者社会研究工作者在学术书籍或学术期刊上刊登的，用来进行科学研究和描述或呈现自己研究成果的文章。论文往往强调原创性的工作总结，但当然也可以是对前人工作总结
吡啶.mw-parser-output ruby.zy{text-align:justify;text-justify:none}.mw-parser-output ruby.zy>rp{user-select:none}.mw-parser-output ruby.zy>rt{font-feature-settings:
咒咒可以指：
北大西洋漂流北大西洋漂流（North Atlantic Drift），又称为北大西洋洋流（North Atlantic Current）或北大西洋暖流，为墨西哥湾暖流向北大西洋东北伸延的一个强力温暖洋流。北大西洋洋流在爱尔兰的
知识所有权工业所有权(英语：industrial rights，德语：gewerblicher Rechtsschutz，法语：propriété industrielle)又称知识所有权，系指产业上对于不具备有体性之利益的排他性支配权，与著作权同
头骨颅骨或者头骨、骷髅头是指人类或者许多脊椎动物的头部骨性结构。头骨之功能为支撑脸部，并保护脑部。头骨分为两部分：颅骨和下颌骨。一般所称之‘头颅’通常仅指颅骨，并未包含下
伦纳德·克莱因罗克伦纳德·克莱因罗克（英语：Leonard Kleinrock，1934年6月13日－），美国工程师和计算机科学家。他是加州大学洛杉矶分校亨利·萨穆埃利工程与应用科学学院计算机科学教授。他在计算机