量子计算相关的最新进展2024

HilarieOrmanhilarie@purplestreak.com 2024年3月6日 抽象的 未来的量子计算机可能能够分解大数，这对目前使用的一些公钥和密钥交换系统构成威胁。本文概述了设计量子算法和构建量子计算设备的最新进展，旨在帮助技术人员了解量子工程师正在研究的难题、取得的进展以及这些因素如何影响对大规模量子计算是否可能发生以及何时发生的估计。 1简介：寻求跨越式发展 几年前，总结使用逻辑量子计算进行因式分解的现状相对容易，因为该领域才刚刚起步[Orm21]。有几个小组生产量子比特芯片用于演示，并且都使用基于超导transmon量子比特的相同技术。 如今，硬件的创新种类更加丰富，扩展挑战也更加明显。鉴于精通量子设备物理和工程的人员数量迅速增加，并考虑到他们最近取得的成果，未来5‑10年内很有可能出现有用的量子计算机。尽管RSA公钥系统并未面临迫在眉睫的危险，但10年后可能会出现具有足够原始量子位的设备来开始解决2048位数字因式分解问题。到那时我们应该知道量子设备是否具有成功所需的速度和可靠性。 量子计算技术的改进速度开始看起来像许多经济上有用的制造业中看到的一般规则，其中生产率增长缓慢并且 与互联网安全相关的量子计算最新进展2 每个设备的量子比特数。不过，我们仍处于一个模糊的比3年前。这转化为更多的改进新技术，就像半导体专家在其中一组是“本领域技术人员”，这些人员的数量工程设计更多类型的设备，这导致未来。20世纪50年代和1960年代。由于对量子计算的投资不断增加，如今有更多的人可以构建量子设备然后变得相当快。感知到的指数级改进在人类发展的早期阶段，人们的产品的诞生归功于流程各个方面的一系列改进。 有70多家公司从事开发或支持量子计算机[Dar23]，考虑到该技术，这似乎很了不起 尚未展示任何令人信服的用途。研究和工程活动已经不仅仅是展示大量可用的 量子比特。可扩展性、相干时间、纠错和门实现，所有这些都是大规模计算的关键，正在受到关注，但还没有一种方法取得重大进展。相反，不同的团体正在尝试不同类型的物理实现 该行业似乎正进入一个动荡和可能颠覆的时期，这令人兴奋，但却没有迹象表明量子量子比特，因此每个组都有不同的学习曲线和不同的量子器件在各个方面的优点的进展速度。 如果我们的目标是可行的，那么我们比几年前就更接近目标了。大规模计算可能会实现。我们可以自信地说，如果 可用于实验的计算技术的数量级要高得多。人工智能领域陷入低迷，从巧妙的技巧转向大规模图分析，最终进入了当前的海量时代报纸，小公司兴起并蓬勃发展。一些有先见之明的观察家大约45年前，人工智能也处于大致相同的状态。[Mor76]认为除非有计算机科学聚焦人工智能，研究会议发表数千篇论文 预测了大规模计算和巨大神经网络融合的时间表。如果量子计算能够达到这样的程度计算和大型模型。虽然已经预见到了，但没有人能够 逻辑量子比特，如果相干时间可以延长，如果量子比特互连图密集，并且门时间在亚纳秒级能够生产出几万甚至几十万的廉价机器 范围，然后是依赖于大整数问题的安全机制将落在新机器的身上，科学中的许多其他难题将 与互联网安全相关的量子计算最新进展3 得到解决。每个“如果”对于物理学家和工程师来说都是一个大问题，而我们以我们今天所知道的情况无法预测时间表。 2算法 量子算法必须比其相应的经典算法快得多，这通常意味着量子版本应该即使在理论上，即使在实践中，与经典算法相比具有明显速度优势的量子算法也很少。为了获得优势， 经典版本。Shor的大整数因式分解算法仍然存在最明显的例子。有一些有利的量子方法可用于研究大随机态（随机电路、自旋态阵列、一些与次指数或指数时间相比，在多项式时间内运行 随机编码问题等），但它们的实用性目前还值得怀疑。量子计算仍然笼罩在量子工程的迷雾中。还有一个扩展问题，经典算法的改进仍然存在将交叉点转移到更大的问题上。 另一方面，量子算法是在没有反馈的情况下在状态叠加上运行的电路。量子计算理论已经看到大量的量子算法。其一，量子存储设备是有限的，而今天的经典计算机装有内存，有一些理论上的原因表明我们不太可能 值得关注。例如，虽然Grover的量子搜索算法与经典方法相比优势不大，但有一个搜索获得了一些有趣的结果和观点[Aar22]，[BMN+21] 伪随机数据方法[YZ22]即量子多项式与经典的指数。 性能来自于对最佳利用机器能力的细致关注。然而，对于量子计算机来说，硬件是一个移动的对于当今正在研究的算法而言，将它们与可用的量子硬件相匹配以解决重大问题本身就是一个难题。就像经典计算机一样，细节决定成败，最大程度地保证 目标，因此编译器和基于每台机器的代码优化是解决方案的重要组成部分。例如，IonQ能够实现 量子计算的已知计算优势区域通过改进编译器来实现他们的演示目标。这导致了仍在不断变化，并将持续一段时间。目前，其核心功能之一的2量子位门减少了95%。只有有前途的算法才是统计导向的、明显 与互联网安全相关的量子计算最新进展4 将量子资源用于重要算法，我们可能很快就会获得量子有用性，但理论发现是不可预测的。尺寸有限。如果有理论发现可以减少 2.1Regev版本的Shor量子分解算法 在简化方面，有一项有趣的发现可以应用于因式分解。OdedRegev是格约化问题方面的专家，他发现了一种通过计算多维格中的点来改进量子因式分解的方法。与Shor算法（计算2的多个不同幂以目标数N为模）不同，Regev的方法[Reg24]计算许多小素数的乘积，这些小素数的乘积以N为模，以许多不同的大幂为模。这些乘积可以看作是多维空间中的点，其中维度是小素数的数量，坐标是幂的指数。量子FFT算法在这些点上计算，当测量这个量子态时，它会产生一个与群周期（以及N的因子）相关的随机选择的多维向量。只要有足够的这些估计值，经典计算机上的格约化就可以高效且高概率地找到群周期。Regev发现，当将格子缩减用于此目的时，效果“出奇地好”。 在大N的渐近情况下，门数量的减少意味着状态相干时间可能比Shor算法所需的时间短得多。Regev最初认为他的方法对于小至2000位的数字是有利的，但在他2024年1月的修订论文中，这种假设被削弱，并指出在声称改进之前需要实际的编码实现。我们的粗略计算表明，Regev的方法可能比Shor的方法多使用30%的门（注意，量子机必须重新初始化以重新运行算法约45次，才能获得足够的样本用于晶格约简）。注意：我们专注于2048位数字，因为这是经典计算机无法攻击的范围的开始，并且在听到量子计算的轰动之前它被认为是“安全的”。由2048位密钥保护的数据将是第一个 与互联网安全相关的量子计算最新进展5 如果量子因子分解满足了其对无差错计算的所有疯狂期望，就会遭受损失。 值得理解为什么更少的门和采样数据在设计量子算法时如此有用。使用小数进行乘法的优点是，与肖尔算法中的大数相比，处理它们的量子电路的运算量更少。一般来说，较小的电路意味着量子位所需的相干时间较小，而这反过来可能意味着更容易实现因子分解量子计算机的工程要求。Regev多维方法的格约简步骤需要大约sqrt(n)个样本，以确保格约简算法具有非常高的概率找到群的周期。看起来该算法较短的电路时间是毫无意义的，因为整个系统必须运行很多次。 这给我们带来了Regev方法的第二个有趣方面独立量子估计。独立性是指算法运行后，为一个向量产生一个测量结果，然后重新初始化并再次为另一个向量运行，产生另一个测量结果，等等。这意味着小电路只需在算法每次运行期间保存其结果以计算指数和一个多维量子FFT。样本可以在经典计算机上进行后处理这一事实是一种新颖的特性，它很可能使它对非常大的数字进行改进（假设一台拥有数万亿量子比特的量子超级计算机被建造出来）。 Regev算法说明了两点，它们可能对进一步的量子数论计算方法有用。第一点是，可以用少量指数较小的数字代替一个指数较大的数字；第二点是，可以多次运行多维算法来收集样本，以便在经典计算机上进行分析（这类似于进行量子高斯玻色子采样）。 这两种想法的结合为量子因式分解带来了新颖的改进。值得注意的是，量子测量是一种真正随机选择的方法，不会产生任何计算成本。量子是免费随机的。 Regev指出，如果格约化方面有重大改进，那么他的方法将变得更加有效，而且“后量子”密码学的世界将基本上缺乏安全算法。 到目前为止，人们一直担心因式分解是否会取得突破，而格解已经成为公钥密码学的难题。 与互联网安全相关的量子计算最新进展6 如果这两类问题从本质上来说有着深刻的关联，那么这将是令人惊讶和讽刺的。 但是，期望不应该超越建造一台足够大的量子计算机来处理大量数据的现实。当我们说“量子比特”时，我们指的是纠错或逻辑量子比特，而这又是由许多物理量子比特、许多快速、高保真门和许多互连实现的。我们还没有看到哪怕一个逻辑量子比特被演示出来，更不用说几千个了。尽管如此，Regev的算法可能是量子因式分解最终（遥远的未来）取得成功的重要一步。 2.1.1Regev算法的更多细节 表明通过使用少于50个小素数的计算可以准确地完成2000位数字的多维晶格计算并不明显，Regev的论文主要关注于证明将计算空间的维度与概率相关联的误差界限。在后量子处理步骤中解决问题的能力。这一步就是经过充分研究的LLL晶格缩减算法[LLL82]，它是一种神奇的方法，它采用一组n维向量并非常有效地找到缩减表示。Shor算法还具有一个后处理步骤，尽管非常简单。该算法计算与目标数的因子相关的数R，但该计算只需近似到一定的精度即可。R是长度为2L位的有理数，其中L是要因式分解的数的位长度。R与被分解数的乘法群中的元素的周期有关。一个非平凡元素的周期是群大小的一个因子，很容易（在时间L中）使用该信息找到目标数的一个因子。这个重要的数R从哪里来？它是对群元素的幂进行QFFT模N缩减，可以使用具有2N个量子位的量子计算机并行 计算这些幂，并且可以根据小素数的幂的叠加来计算FFT。 3渐近地，这可以在时间n内完成，但出于实际目的，运行时间与n成正比2 、。 Regev意识到，量子计算机可以使用多个元素（小素数），而不是计算群中一个元素的幂，并计算这些元素幂对目标数N的模的乘积。这些乘积在由小素数定义的多维空间中具有周期性重复模式。多维FFT 与互联网安全相关的量子计算最新进展7 将这些幂叠加起来可得到多维值R，而R在多维格中具有重复模式，可以用一组基向量来描述。这些向量与群序有关，因此也与N的素因子有关。 在Shor算法中，从R计算群阶相当简单。多维对应物则更复杂，但在经典计算领域中完全易于处理。寻找重复的基向量是由经典计算机使用LLL算法完成的，LLL算法是现代格约化的主力。LLL的运行时间大约按(1.01)d缩放，其中d是空间的维度。为了以高概率计算2048位数字的R，需要几十个不同的小素数。 Regev的方法对模素数的离散对数有效吗？根据MartinEkera和JoelGartner最近的一篇论文[EG23]，显然是有效的。Diffie‑Hellman密钥交换方法取决于此问题的难度，常用于SSL等互联网协议中。 此方法适用于椭圆曲线场吗？根据埃克拉的说法，可能不会。格子构造的小素数和椭圆曲线点之间没有有用的类比。然而，PsiQuantum的Litinski[Lit23]概述了一种可能更有效的量子算法，它可以“仅”使用50M门破解256位EC密钥。它假设光子量子计算机可以与“非局部”量子位连接并行执行许多门操作。这尚未实施。 3硬件 经过近25年的发展，“计算量子比特的物理实现是什么？”这个问题的明确答案是：超导量子比特、捕获离子、中性原子、自旋量子比特或光子。互连拓扑是线性、2D网格、3D或动态。对于量子，我们看到了不断拓宽的前沿。 寻找最佳量子技术不仅要考虑广度，还要考虑深度。研究人员需要制造易于初始化和操作的量子比特设备，这些设备在快速稳定的同时，可