浅谈概率计算的若干 *** （概率算法求解整数因子）

如何算数字出现的概率 技经观察丨概率计算——向量子计算过渡的中间方案

量子计算机基于量子比特（又称“量子位”）执行运算任务，在解决多体问题、路径规划问题等复杂问题方面相较经典计算机有巨大优势。，由于量子计算需要通过昂贵的实验设备构建，且在低温操作、相干时间控制、容错等方面仍面临巨大挑战，仍需经历较长的发展阶段。在此背景下，研究人员基于电子集成电路开发出具有概率比特（又称“概率位”）的概率计算机，并将其视作向量子计算过渡的中间方案。这种计算机通过对概率的数值运算进行问题求解，在解决非线性规划、多体系统问题方面具有性能优势，且能在常温条件下运行，更加接近实用。

一、概率计算原理简介

多年来，研究人员不断探索蒙特卡洛算法在金融风险分析、药物开发、供应链物流以及物理和化学研究工作中的潜在应用。蒙特卡洛算法以概率统计理论为指导，通过统计与数值分析来求解复杂问题。经典计算机在这一问题上的效率较低，需要耗费大量的时间与能源。

量子计算机中，量子位组成的系统可以通过许多可能路径演化到最终状态，而选择哪种路径完全是一种偶然。通过将每种路径的概率振幅相加来得到最终的概率振幅，将总概率振幅的模进行平方运算得到最终的实际概率。由于量子位可以并行工作，量子计算机对于某些特定任务的运算速率远超经典计算机。，概率振幅是一个复数，可能出现“负概率”的错误情况，需要通过Shor算法、Grover算法等算法来精心编排运算路径，从而抵消错误的“负概率”路径的影响。

工程师正探索噪声位的性能（图片来源IEEE Spectrum）

研究人员参考了量子计算机的工作原理，设计了使用概率位工作的概率计算机，将所有实现路径的概率相加来得到最终概率。量子计算机需要屏蔽电磁场干扰、在接近绝对零度的超低温下才能进行工作，而概率计算机可以基于硅基电子电路设计，可以在常温下工作。，普渡大学电气和计算机工程教授、概率计算先驱之一苏普里约·达塔（Supriyo Datta）认为，对于涉及复数的算法，量子计算机能够展现出无与伦比的优越性，但对于解决涉及正数数值运算的随机变量问题，概率计算可能具有相当大的竞争力。

一般而言，研究人员使用自旋态粒子构建单个概率位，利用其随机的“上”和“下”两种状态表示二进制运算中的0和1，每种状态的概率均为50%。概率位表现为随机的纯噪声，不携带任何信息。，将多个概率位耦合，利用概率位之间相互影响的复杂相关性，可以构建概率计算机，从而有效地解决优化问题。

二、概率计算机的实现方式

目前，研究人员提出了两种构建概率计算机的方式，分别是通过传统电路与随机数生成器，以及通过专用硬件设备。

（一）通过传统电路与随机数生成器实现概率计算

由于集成电路中的晶体管都是基于确定性而制造，很难自然产生随机的不确定性，需要通过算法生成伪随机序列来实现概率位。

日本富士通公司正使用普通硬件结合随机数生成器构建概率计算机，以模拟概率位翻转。随后，使用电子自旋的伊辛模型（Ising model）和退火（Annealing）算法来实现非线性规划功能。退火算法受到自然系统总是趋于向更低能量状态演化这一规律的启发，通过模拟自然系统的自演化来处理信息。算法终止时的当前解即为所得近似更优解。，只要能将组合优化问题翻译成伊辛模型问题，然后通过退火算法求出伊辛模型的更优解，再将结果反向翻译的系统，就能得到用来解决组合优化问题的新型计算机。这种 的缺点是功耗较高。2020年4月，日本东京工业大学、日立公司、北海道大学和东京大学研究人员开发出随机元细胞自动机退火器架构（Stochastic Cellular Automata Annealer Architecture，STATICA），也采取了类似的构建原理。

（二）开发专用硬件设备

由于概率运算依赖于概率位的随机性，研究人员尝试通过本身具有随机性的器件来构建概率计算机。这也是目前全球研究人员不断尝试攻克的重要方向。

之一种 是利用铁磁体中的磁隧道结（Magnetic Tunneling Junction，MTJ）。磁性隧道结的电阻取决于其磁性状态，且不稳定，它在两个磁态之间快速翻转，导致其电阻在两个值之间不断变化，可用于创建概率位。早期的计算机使用磁隧道结构建磁芯存储器，但很难将磁存储器小型化，因为磁体越小越不稳定。研究人员正是利用了磁隧道结的不稳定性质，结合若干个晶体管来构建概率位。其中的一个晶体管由输入电压控制，其他的仅用于缓冲输出。2017年，美国普渡大学的苏普里约·达塔（Supriyo Datta）教授与加州大学圣芭芭拉分校的凯雷姆·坎萨里（Kerem Camsari）助理教授提出了使用设备的噪声与不确定性创建具有随机性的概率计算机，被认为是概率计算的先驱。2019年，在日本东北大学合作者的帮助下，达塔与坎萨里教授团队构建了一台具有8个概率位的概率计算机。通过找到特定的连接模式，并正确连接概率位，概率位电路将通过输出峰值信号的形式给出答案。通过这种 构建的概率计算机比经典计算机上的优化算法快了6个数量级，并且采样速度提高了5-18倍，能耗降低了10倍、占用面积减小了100倍。，这种概率计算机也具有将概率位扩大到5000个的潜力，有望用于处理更复杂的问题。目前，中国北京航空航天大学的曾琅、曹凯华等研究人员也在进行类似的概率计算器件研究。

通过磁隧道结构建的概率位 （图片来源IEEE Spectrum）

另一种构建概率计算机的方式利用了闪存设备的噪声和不确定性来模拟事件的随机性。美国佐治亚理工学院、英特尔和韩国科学技术高等研究院通过闪存中鳍式晶体管（FinFET）的固有时间噪声作为随机性的模拟源，替代了隧道结，在闪存中实现了概率计算机。

三、应用前景

（一）解决非线性规划问题与多体问题

概率计算机基于随机性进行并行计算，适用于求解路径规划、投资组合问题等非线性规划问题，以及求解物理、化学反应模拟和蛋白质结构预测等多体问题。路径规划问题是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。多体问题需要在拥有大量粒子构成的微观系统中求解，其中的粒子之间不断相互作用，产生复杂的相关性。，系统的波函数很复杂，并含有大量信息，常常无法进行精确或可分析的计算。概率计算机的并行计算方式可以提高计算速度、扩大求解规模，因而适合解决大而复杂的计算问题。

蛋白质结构模拟示意图

（二）与人工智能结合的可能性

研究人员认为概率计算机可能有助于机器学习技术开发。人工智能和机器学习的一个关键步骤是根据不完整的数据做出决策，更好的 是输出每个可能答案的概率。目前的经典计算机无法以节能的方式做到这一点，而概率计算机的出现有望填补这一空缺。加州大学圣芭芭拉分校坎萨里教授团队计划探索概率计算机中的深度学习算法。佐治亚理工学院研究团队也表示，强化学习的过程需要随机探索训练环境，或许可以通过概率计算提供解决方案。

参考资料

https://spectrum.ieee.org/waiting-for-quantum-computing-try-probabilistic-computing

https://spectrum.ieee.org/probablistic-computing

作者简介

唐乾琛 国务院发展研究中心国际技术经济研究所研究二室，三级分析员

研究方向信息领域战略、技术和产业前沿

联系方式tangqc96@163.com

编辑丨郑实

研究所简介

国际技术经济研究所（IITE）成立于1985年11月，是隶属于国务院发展研究中心的非营利性研究机构，主要职能是研究我国经济、科技社会发展中的重大政策性、战略性、前瞻性问题，跟踪和分析世界科技、经济发展态势，为中央和有关部委提供决策咨询服务。“全球技术地图”为国际技术经济研究所官方微信账号，致力于向公众传递前沿技术资讯和科技创新洞见。

地址北京市海淀区小南庄20号楼A座

010-82635522

微信iite_er

概率算法求解整数因子 概率算法的三种