量子复杂性理论

✍ dations ◷ 2025-11-04 13:23:46 #量子复杂性理论

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

相关

特异性灵敏度和特异度（Sensitivity and specificity），是统计学中用来表征二项分类测试特征的数据。灵敏度可以作为避免假阴性的量化指标，而特异度可以作为避免假阳性的量化指标。对于
随机对照试验随机对照试验（英语：randomized controlled trial，RCT）是一种对医疗卫生服务中的某种疗法或药物的效果进行检测的手段，特别常用于医学、药学、护理学研究中，在司法、教育、社会科学
舍曲林舍曲林（英语：Sertraline）（商品名：左洛复、彼迈乐等）是一种选择性5-羟色胺再吸收抑制剂（SSRI）类抗抑郁药，1991年由辉瑞制药公司发明。舍曲林主要用于治疗成人重度抑郁症（MDD），也用来治疗
热导率热导率(英语：Thermal conductivity）其符号为 k {\displaystyle k} 、 λ {\displaystyl
爆炸极限点燃在空气中的气体，气体可能会引爆，或者会很快停止，这种情况是由气体在空气中的浓度来决定的。当气体浓度太低，没有足够燃料来维持爆炸；当气体浓度太高，没有足够氧气燃烧。气体只
伍德兰期疏林时代（Woodland Period）是一个专门名称，指称美国中东部地区前哥伦布时期的古代印第安人文化位于公元前11世纪至公元11世纪之间的阶段。北美洲中东部是一片广阔平坦的大平原，
阿道弗·苏亚雷斯阿道弗·苏亚雷斯·冈萨雷斯（西班牙语：Adolfo Suárez González，1932年9月25日－2014年3月23日），佛朗哥独裁统治后西班牙第一位民选首相（1976-1981）。为西班牙民主转型的关键人物。
施蕴渝施蕴渝（1942年4月－），上海崇明人，分子生物物理学家，中国科学技术大学教授、博士生导师。1965年毕业于中国科学技术大学物理系生物物理专业，1965年至1970年在卫生部中医研究院任实习
德康斯坦保罗-亨利-邦雅曼·德斯图内勒·德康斯坦（法语：Paul-Henri-Benjamin d'Estournelles de Constant，1852年11月22日－1924年5月15日），法国外交家、政治家，国际仲裁倡议者，因为促进美法
人力发电人力发电，常指以人力驱动以电磁感应原里的小型发电机的发电的方式。或是利用压电效应，以步行或运动时的动能产生电力。目前已开发出利用指压的能源发动的遥控开关，不需要装填电