BQP (复杂度)

✍ dations ◷ 2025-04-03 18:22:57 #几率复杂度类,量子复杂度理论,计算机科学中未解决的问题

在计算复杂度理论内,有限错误量子多项式时间(英语:bounded error quantum polynomial time,BQP)是一个决定性问题的复杂度类,并且其内的问题可以在多项式时间内以量子电脑解决,错误的几率小于1/3。BQP也可以视为是复杂度类BPP的量子电脑版。

换句话说,对BQP里面的问题,存在一个使用量子电脑的算法(量子算法)花费多项式时间运作,并且有很高的几率回答正确的答案。对任何状况,回答错误答案的几率小于三分之一。

与其他“有限错误”的几率算法相同,这里所提到的1/3是一个比较随意的定义。如果原本算法的错误几率比较大,我们可以运作多次该算法,然后取多数回答正确的答案以取得比较高的准确率。详细的分析显示错误的下限可以高达1/2 − −或者低达2−,所包含的题目范围均不会有变化。这里是一个正数的常数,是输入的长度。

算法所使用量子位元的数目可以为输入大小的任何多项式。举例来说,因式分解位元整数的算法使用大约2'n'个量子位元(参考秀尔算法)。

一般状况之下,量子电脑的计算停止于量子测量上面。测量行为会导致量子位元塌缩到其中一个量子态上。我们可以说量子位元在经过运算之后,最终的测量会让他有极高的机会出现正确的答案。

量子电脑受到许多瞩目,因为有许多问题已知在BQP内,但是一般认为在P之外(换句话说,使用量子电脑比起一般电脑,能大幅缩短计算这些问题的时间)。一些著名的例子有:

相关

  • 基因检测基因检测(Genetic Test)是从染色体结构,DNA序列,DNA变异位点或基因表现程度,提供受检者与医疗研究人员评估一些与基因遗传有关的疾病、体质或个人特质的依据,也是精准医学分析的一
  • 动脉动脉(希腊语:αρτηρία)是指在生物体内、从心脏运送血液到全身各器官(包括心脏本身)的多条血管。除了肺循环的动脉以及脐动脉,动脉运送的是含氧量高的血液(因此也有称之为“动
  • Right右束支传导阻滞(Right bundle branch block,简称RBBB)是一类心脏电传导系统阻滞疾病(英语:heart block)。乃肇因于心脏的右束支传导阻断,进而造成电讯号无法经由此途径传入右心室,而
  • 孝道四配颜回 · 孟子 · 曾参 · 孔伋日本藤原惺窝 · 林罗山 · 室鸠巢新井白石 · 雨森芳洲朝鲜薛聪 · 权近 · 吉再 · 安珦 · 李穑李滉 · 王仁 · 李齐贤 
  • 李渊唐高祖李渊(566年4月7日-635年6月25日),字叔德,陇西成纪人,唐朝开国皇帝及奠基者,618年6月18日-626年9月4日在位共8年 。玄武门之变后不久禅位于唐太宗,称号“太上皇”。据《旧唐书》
  • 黄金时段黄金时段艾美奖(Primetime Emmy Awards),是电视艺术科学学院(Academy of Arts and Science of Television)为了表扬美国电视产业于黄金时段(泛指晚间时段)播映的杰出电视节目。首届
  • 庐陵郡庐陵郡是中国汉朝至唐朝的一个郡,其范围历代均有变化,但核心区域一直在吉泰盆地,大致相当于今吉安市辖境。东汉灵帝末(184-189),扬州刺史刘遵上书请置庐陵郡,初平二年(191),分豫章郡置
  • 崖柏属崖柏属(学名:)是柏科下的一个属,为常绿乔木植物。该属共有约6种,分布于北美和东亚。
  • 埃及蓝睡莲'Nymphaea caerulea)已知主要名称:蓝睡莲 blue lotus(或埃及蓝色莲花 Blue Egyptian Lotus)。 如同其他的睡莲属种,植物含有精神性生物碱:荷叶碱、阿朴啡 aporphine(不要与阿朴吗啡
  • 土光敏夫土光敏夫(日语:土光 敏夫/どこう としお ;1896年9月15日-1988年8月4日),日本昭和时代企业家,工商界人士。石川岛播磨重工业社长、东芝社长、日本经济团体联合会第4代会长。