量子计算与经典计算几次重要的“PK”，藏着怎样的发展轨迹？( 三 ) _小知识

而噪声和错误又经常是联系关系的。这有点像一句谚语“祸不单行” ，即在交互系统中，错误之间会倾标的目的于彼此联系关系。也就是说，这些错误有概率在多个量子比特同时呈现。
Kalai 在曩昔十年摆布的时候里发现，即使在小规模或中等规模的环境下，噪音程度也无法有用的降低，因为它们的能量远高于量子纠错所需的能量。而若想达到量子优势就会发生更年夜的噪音，而在此根本上建立量子纠错代码就加倍坚苦。
是以，基于纠错就与计较道理计较设备能力相矛盾，有一派说法认为，量子计较不成能实现。
不外，固然得出如许的结论，但对于 Kalai 来说，他也等候量子计较机能有很是分歧的成果呈现。究竟结果，像 IBM、英特尔和微软如许的年夜公司在量子计较方面已投入巨资。
新年夜陆：科学家发现只有量子计较机才能解决的问题
可是，抛开量子计较机实现的问题，之前的研究中不乏一些证据证实，量子计较有着经典计较无法对比的优势。
本年 5 月 31 日颁发的一篇论文中，计较机科学家终于找到了只有量子计较机才能解决的问题，即“有限错误量子多项式时候”（bounded-error quantum polynomial time ， BQP）”类问题。
理论计较机研究中的一个根基项目就是将问题按照复杂水平进行分类，也称复杂度分级（Complexity Classes），即按照解决问题所需资本（如时候和内存）的几多进行分类。
此中最驰名的两个分类是“P”和“NP” ， P 是传统计较可以快速解决的所有问题，如“这个数字是否是质数？”属于 P 类问题。 NP 是传统计较机并不克不及敏捷解决，但若是存在一个已知谜底可以或许快速验证的问题，如“这个数的质因数有哪些？”属于 NP 问题。
BQP 问题是 1993 年计较机学家 Ethan Bernstein 和 Umesh Vazirani提出的只有量子级计较才能解决的问题。该界说类中包含量子计较机可以高效解决的所有决议计划问题，即谜底为是或否的问题。两位科学家同时还证实了量子计较机可以解决传统计较机可以解决的所有问题，也就是证实了 BQP 分类中包含了 P 分类。

图 | 几种问题的分类（来历：Quanta Magazine）
但 Ethan 和 Umesh 无法确定 BQP 中是否也包含“多项式条理布局（Polynomial Hierarchy）”类问题，也称 PH类问题。 PH 是 NP 的拓展，包含所有由 NP 类延长出的问题，如“对于所有... 来说是否存在...” 。当今的传统计较机无法解决 PH中的年夜大都问题，但若是 P 等于 NP ，则可以将 PH 看作是传统计较机可以解决的所有问题。换句话说，比力 BQP 和 PH这两种问题分类，即是为了确定量子计较机是否真的较传统计较机具有优势。
区分出两个复杂类此外最好方式是，找到一个可被证实为仅属于此中一类的问题。也就是为“量子计较在能力大将远超一切传统计较”这一概念供给的科学证据。
该论文中，作者 Raz 和 Tal 实现了一种名为“Oracle”的 BQP 与 PH 区分体例。他们认为，区分 BQP 和 PH的最佳体例是测量解决每个问题所需要的时候，好比，计较出计较机在解决问题的过程中扣问“oracle”的次数。 oracle就像是一个提醒，你不知道它是如何发生的，但你知道它是靠得住的。
你可以先扣问 oracle 近似“每个发生器的第六个数字是什么？”的问题，然后，按照每种计较机所需的提醒数目来比力计较能力（需要更多提醒的计较机计较速度较慢）。

量子计算与经典计算几次重要的“PK”，藏着怎样的发展轨迹？( 三 )

猜你喜欢