广告

量子计算机可以做什么?

时间:2022-04-21 18:07:27 作者:Challey 阅读:
尽管大家对量子计算机期望很高,甚至希望它无所不能。但量子计算机并不是能够解决诸如停机问题等棘手问题的全能计算设备。量子计算或许是下一代科技的核心技术之一,量子计算机也是业界期待的下一代计算机,然而,量子计算机能做什么?这个问题很大,我们现在来阐述。
广告

量子计算或许是下一代科技的核心技术之一,量子计算机也是业界期待的下一代计算机,然而,量子计算机能做什么?这个问题很大,我们现在来阐述。

研究机构希望量子计算机能够加深人们对宇宙的理解,同时解决一些经典计算机无法解决的问题。然而,这要取决于这些问题是什么,以及量子计算机能在多大程度上解决这些问题。

尽管大家对量子计算机期望很高,甚至希望它无所不能。但量子计算机并不是能够解决诸如停机问题等棘手问题的全能计算设备。

相反,它们是建立在架构上的处理器,科学家希望这种架构能够让它们做经典计算机可以做的任何事情,并为它们的量子特性带来的某些问题提供额外的功能或提高性能。

充分了解量子计算机的潜在能力,以及它们如何与经典计算机相抗衡,需要深入研究计算复杂性理论。对于研究量子或对其感兴趣的人来说,最重要的是一个量子计算机可以轻松解决的问题的理论,称为 BQP——有界误差量子多项式时间。

下面,我们汇总了复杂性类别列表,以及 BQP 适合的位置。

P——多项式时间。P 是最熟悉的复杂性类别:确定性图灵机可以使用多项式时间资源解决问题。计算机需要资源来解决问题,其中时间、精力和位数是最重要的。对于 P 中的任何类型的问题,解决或检查它所需的时间量会随着问题规模的增加而基于某些多项式而增加。所以,如果问题的大小是 x,那么它所花费的时间就是 x^ n,其中n是一个常数。你的计算机每天做的事情大多是 P ——例如乘法。

理论家认为这些类型的问题对于计算机来说“容易”解决,但这在理论上很容易,而不是在实践中。多项式n可以非常大 - 100、1,000、1,000,000 等,只要它是一个常数,这会导致 P 中的一些极难解决的问题类型。在不同的计算硬件上实现给定的算法也可以改变多项式。然而,P 旨在抽象出实现细节并作为粗粒度分类存在,以便我们可以对这些问题的本质说一些基本的东西。

NP — 非确定性多项式时间。NP 是一个复杂性类别,包括确定性图灵机可以检查解决方案在多项式时间内是否正确的问题类型。NP 包括所有 P——但也包括我们不知道是否存在多项式时间解的问题类型。此类包括诸如分解大数之类的问题类型,其中很难将大数分开,但很容易检查两个因数乘回第一个数字。NP 构成了数学中最重要的未解决问题之一的症结所在:对于每种 NP 问题类型是否存在 P 解决方案(称为 P 与 NP 的问题)尚未得到证明。解决 P 与 NP 的尝试让数学家有很多理由相信(但同样,

这里是“问题类型”,而不是“问题实例”。“因式分解”是一种问题,而“因式分解 15”是一个问题实例。可以破解难题实例的算法可能在 P 中,但对解决整个问题类型的算法更有价值,例如 Shor 的因式分解算法旨在分解任何数字。

NP-Hard —从 NP 向外扩展的是 NP-Hard 问题类型,它们至少与 NP 中最难的问题类型一样难。此类包括一部分 NP(更多内容见下文),还包括其他可能不在 NP 中的问题类型。NP-Hard 问题似乎经常表现出一种非结构化——组合行为需要转动很多旋钮,这让求解者感觉好像他们必须依靠随机性和猜测才能找到答案。

NP-Complete —在 NP 和 NP-Hard 的交集处是 NP-Complete,即本身在 NP 中的 NP-Hard 问题类型。NP-Hard(包括 NP-Complete)展示了一个有趣的对称性:您可以使用多项式资源将 NP-Hard 问题类型的求解器转换为任何 NP 问题的求解器。换句话说,为 NP-Hard 类型的问题找到一个求解器为您提供了解开 NP 中每个问题的钥匙(这也包括 P 中的每个问题)。这意味着如果您找到任何类型的 NP 完全问题的多项式时间解,您就会发现 P=NP。这没有发生,也没有预期会发生——在任何可物理实现的计算机上,对于 NP-Hard 或 NP-Complete 复杂性类别中的任何事物,都不存在多项式时间解。

NP-Complete 包括一些计算机科学家经常谈论的非常流行的问题,例如3-SAT和旅行商问题。如果您需要算法来解决任何 nxn 网格(将数独视为问题类型),则数独是 NP-Complete,但在 P 中用于解决特定大小实例的算法。

BPP— 好吧,我们还没有完全研究量子的东西,但我们已经到了那里:在 P 周围,你可以画一条代表 BPP 或有界误差概率多项式时间的模糊线。在此之前,我们只将“资源”称为计算时间,然后还有计算空间(我们稍后会谈到)。但是,如果我们添加随机性作为计算机可以使用的资源呢?随机性是普通计算机无法模拟的东西,我们必须为计算机提供数据。BPP 是一类复杂性的问题,我们可以在多项式时间内解决和检查问题,此外还可以加入随机过程来帮助解决问题——它们是有界的,这意味着算法必须返回正确的答案概率高于大于一半的设定常数。它没有被证明,但强烈假设,

如果你去掉 BPP 的界限——你只需要算法在一半以上的时间内返回答案(但它的正确率可以任意接近 1/2),那么你就有一个更强大的复杂性类,称为PP 概率多项式时间。

BQP——最后,我们到达了具有有界误差量子多项式时间的量子世界。这些是量子计算机——即具有额外叠加、纠缠和干涉能力的计算机——可以在多项式时间内以小于设定的误差量解决的问题。而现在,对于这个博客最令人失望的部分:BQP 的边界是一条模糊的线。这条线位于 BPP 和 PP 之间,包括一些(但不清楚有多少)NP,以及一些在 NP 之外的东西。

因此,有界误差的量子计算机可以在多项式时间内解决 P 和 BPP 中的所有类型问题。它可以在多项式时间内解决一些 NP 类型的问题,其中最流行的例子是 Shor 算法的因式分解。目前尚不清楚它是否能有效地解决 NP-Complete 类中的任何问题——但研究人员怀疑它不能。关于复杂性类如何相互关联,还有很多未经证实的事情,而 BQP 是另一个没有严格定义边界的复杂性类。

然而,并非一切都是完全模糊的,我们知道 BQP 比 BPP 更强大。研究人员最近证明,BQP 包括一些在 NP 之外的问题,从技术上讲,在更大的复杂性类别 PH 之外。经典计算机很难找到检查该类问题类型的解决方案。这意味着,即使在不太可能的情况下,有人证明 P=NP,仍然会有经典计算机无法破解的 BQP 问题类型。然而,即使这种关系也有些模糊,因为 P 是否等于包含 P、NP 和 PH 的更大复杂性类别(称为 PSPACE)尚未得到解答。

小结

研究表明,与经典计算相比,量子计算有它的核心优势。研究人员已经证明了在计算中让它们相互对抗时,使用量子比特计算与经典比特计算之间存在几种理论上的分离,例如迫使经典计算机只运行嘈杂的、恒定深度的电路。像这样的证明已经证明,量子暂存空间本质上比经典暂存空间更强大。NP 之外的问题类型仍然存在那些 BQP 解决方案。

尽管量子计算的落地应用,需要弄清楚这些算法将如何为社会提供商业价值,但目前阶段,这超出了理论计算机科学的领域。

那么,量子计算机到底能做什么呢?

目前来说还是未知的,构建量子计算机需要足够强大的硬件,但是目前还做不到。

但是已知的是,量子计算机可以有效地解决当今最好的经典算法难以解决的问题,量子计算机和经典计算机之间确实存在一些分离,并且 BQP 包含多项式解决方案,甚至可以解决 NP 之外的问题。而且,随着更多的研究和硬件开发,量子计算机将取得更多优势。

责编:Challey
本文为EET电子工程专辑原创文章,禁止转载。请尊重知识产权,违者本司保留追究责任的权利。
Challey
暂无简介...
  • 后摩尔时代计算能力提升,还看量子计算? 量子计算机的计算能力随量子比特数目呈指数增长,因此量子计算研究的核心任务是多量子比特的相干操纵。根据相干操纵量子比特的规模,国际学术界公认量子计算有如下发展阶段:实现量子计算优越性、实现专用量子模拟机、实现可编程通用量子计算机……
  • 是德科技发布 2022 年科技趋势预测 2021 年,全球依然承受着新冠病毒横行所带来的压力。针对疫情视角下展现的业务运营转型和技术趋势,是德科技高管发表了他们的看法,这些趋势将对企业和社会产生深远影响......
  • IBM 发布 127 量子位 Eagle 处理器,向量子优势目标靠近 IBM的技术蓝图目标是实现“量子优势”(quantum advantage),让量子计算机在2023年执行与传统计算机相同的任务时,能更便宜、更快或更精确。
  • 中国摘得超算领域“诺贝尔奖”,国产超级计算机接近“量 在2021年全球超级计算大会(SC21)上,一支来自中国的团队摘得赫赫有名的Gordon Bell奖,该奖相当于超级计算机领域的诺贝尔奖…
  • 达摩院发布2022十大科技趋势:硅光芯片突破摩尔定律,AI技 12月28日,阿里巴巴达摩院发布2022十大科技趋势,包括AI for Science、大小模型协同进化、硅光芯片、绿色能源AI、柔性感知机器人等。这是达摩院连续第四年发布前沿科技趋势预测。
  • 新增12家中企,中科微、国科微、科大国盾量子等被美商务 美国商务部希望阻止中国军方开发反隐形技术,其中可能包括先进雷达等设备,以及海底传感器等反潜应用。商务部称,这一行动还阻止了美国的材料被用来帮助中国破解加密或开发牢不可破的加密。
  • 新款iPad Pro 2021成最受欢迎的 由于采用性能相对强大的M1处理器和mini-LED屏幕以及更多的创新,新款iPad Pro 2021已经成为消费者心目中最受欢迎。然而,iPad 2却已经在全球范围内被列入“复古和过时”的名单中。
  • 三星折叠屏手机Galaxy Z Fold 3 目前来看,折叠屏新机作为一种新的生产力工具,逐渐成为高端/平板的一种趋势,有报料称三星的Galaxy Z Fold 3发布时间或为7月,并且会引入新手势操控。
  • Porotech动态像素调整技术实现Micr 由于我们彻底巅覆 GaN 的半导体材料和结构技术,让我们突破在单位像素上呈现全光谱颜色。同时,PoroGaN微显示平台的光电特性,简化了电子和光电系统设计集成的过程。目前微米纳米级的Micro-LED 和 Mini-LED 显示器在制造所需的多阶段工艺仍然具有挑战性,凭借 Porotech 的多孔氮化镓 (GaN) 技术和架构平台,可以大幅简化现有质量转移(Mass Transfer)或拾取和放置(Pick-and-Place)等Micro-LED制程。
  • 豪威集团在AutoSens展会上首次推出 OAX4600可实现无缝隙的驾驶员/乘员监控系统功能和灵活的汽车设计,在较小的封装内集成低功耗的RGB-IR ISP和两个NPU 
广告
热门推荐
广告
广告
广告
EE直播间
在线研讨会
广告
广告
广告
向右滑动:上一篇 向左滑动:下一篇 我知道了