谷歌 DQI：纠错码还能兼职加速量子计算？

　　完成优化问题的超多项式加快不断是量子算法的焦点方针。组合优化范畴正在已往三十年里不断将量子算法作研究的热门^[1]，迷信家们致力于寻觅能正在组合优化问题上完成超多项式加快的量子算法。近日，Google Quantum AI团队开发了一种“解码量子干预干与丈量（Decoded Quantum Interferometry，简称 DQI）”的全新量子算法。正在max-XORSAT问题中 DQI 寻到类似最优解的速率远快于通用经典开导式算法。当正在有限域上解决类似最优多项式拟合问题时，DQI 绝对已知经典算法完成了超多项式加快。相干研究论文于2025年10月22日“Optimization by decoded quantum interferometry”为题颁发正在国际学术期刊《Nature》上[Nature 646, 831 (2025)]。

　　要懂得这一冲破的意思，咱们无妨先相识甚么是“难以估计”的问题。假定此刻某宝“双十一”起头了，自始自终地推出了法则庞大的优惠勾当：有四个商品，你可以抉择买此中的1/2/3/4个，凭据没有同的采办组合，有没有同的优惠。

优惠勾当法则举例

　　为了拿到最年夜优惠，你可能会穷举16种商品组合，并计较他们各自的优惠，然后选出最优的方案。计较16种组合只要要花你几分钟时间，是值患上一算的。但若此刻有1000个商品以及1000条法则，就发生了2¹⁰⁰⁰种方案——10的301次方)之多，哪怕用今朝最快的超等计较机，穷举一遍也需求远超宇宙春秋的时间。近似如许的问题被叫做max-XORSAT问题，是让迷信家头疼的“不成计较”问题之一。给max-XORSAT问题寻觅最优解的耗时跟着问题的变量范围呈指数爆炸型增加，是以穷举的要领一定没有是久长之计。

　　为应答这一难题，正在经典计较机上，迷信家可以设计一些伶俐的算法来尽可能高效地寻到较优解。而极新的量子计较范畴也供给了QAA（量子绝热算法）、QAOA（量子类似优化算法）等计较东西，它们都极年夜的优化相识决max-XORSAT的速率与精确率。下图为经典以及量子算法搜刮最优方案的典型特性示用意，越深的谷代表越好的方案。

经典以及量子算法搜刮最优方案的典型特性示用意

　　但迷信家们对经典算法和传统的量子算法的效率仍然感应没有称心，但又暂时寻没有到更好的要领来解决max-XORSAT问题。莫非咱们只能止步于此了吗？2024年，google量子AI团队给出了否定谜底：“没有，咱们此刻有了DQI算法！”

DQI算法特性示用意

　　DQI技能把问题的约束间接编码到量子态上，再用纠错码的解码技能完成反计较（uncomputation）而消弭会影响量子干预干与历程的中心态。最初，带有约束信息的量子体系发生干预干与，餍足约束前提最多的方案正在干预干与历程中会得到最年夜的振幅，天然地“浮出水面”。相较已有的经典以致量子算法而言，DQI算法与经典解码器的互助相对是使人线人一新的设法。解码技能正在这个历程中起到了很是要害的作用。由于反计较的历程中触及到欠定线性方程组，其刚好对应着经典纠错码中的“随同式（syndrome）解码问题”。而经典解码的技能曾经绝对成熟，可以细心抉择与问题的数学布局最适配的解码器，进而高几率地实现反计较^[2]。

DQI算法完成流程

　　为验证DQI的机能，研究团队正在含有31,216个变量与50,000个约束的max-XORSAT问题上，DQI技能共同信念流传（BP）解码要领，可以正在8秒时间寻到餍足83.1%约束的方案。虽然餍足率不凌驾专门为max-XORSAT问题定制的Tailored heuristic算法，但耗时远短于Tailored heuristic的7分钟。

DQI+BP与定制开导式算法比照

　　若与退火算法（一种经常使用且较为普适的算法）比照，限制8秒的求解时间下，退火算法只能给出76.4%的餍足率，显著低于DQI+BP算法。要是退火算法要到达83.2%的餍足率，需求73小时的漫永劫间来寻觅，而且需求同时占用5个CPU焦点（其余算法只用1个焦点）。

DIQ+BP与退火算法比照

　　从这些成果来瞅，DQI联合BP解码作为刚提出的算法，长短常具备后劲的。尤为是它立异地将编码解码技能融入到计较历程里，这将会给量子算法范畴带来很多的新思绪。不只云云，研究发明，DQI算法正在餍足一些限制前提的最优多项式交加（Optimal Polynomial Intersection，OPI）问题中，对一切已知经典算法都完成了超多项式级加快。

　　需求出格注重的是懂得以上详细例子比照的公允性。DQI+BP的8秒是指正在经典计较机上摹拟DQI量子算法中心的经典解码器的机能，仅用于预计餍足率。而这并无获得问题详细的解，而作为比照的经典开导式优化算法是实其实正在的计较获得问题的解。DQI量子算法要获得问题的解，需求正在容错量子计较机上运转完备的DQI算法，出格是中心的解码算法的完成需求用可逆量子路线来摹拟经典运转，是以需求思量CPU以及量子处置惩罚器（QPU）的时钟频次差别、可逆编译的开支以及容错开支（这个例子需求几万个逻辑比特，对应几万万个物理比特），总时间估计凌驾73小时。同时，DQI的上风今朝仅限于“有代数布局或稀少约束的问题”。关于不固定布局的问题（如随机图的最年夜自力集、无纪律的旅行商问题），今朝DQI算法尚未措施加快计较。

　　参考文献

　　[1] Farhi, E. et al. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001).

　　[2] Jordan, S.P., Shutty, N., Wootters, M. et al. Optimization by decoded quantum interferometry. Nature 646, 831–836 (2025).