促进组合优化方法在实际问题中应用的技术 利用量子计算技术,将“数字退火”应用于化学及金融领域

本技术介绍参考了以下链接
English

2018年07月27日

促进组合优化方法在实际问题中应用的技术
利用量子计算技术,将“数字退火”应用于化学及金融领域

株式会社富士通研究所(注1)(以下简称,富士通研究所)采用计算机结构“数字退火(Digital Annealer)(注2)”,开发了一项无需设置复杂参数便可解决组合优化问题的技术。其中“数字退火”是解决组合优化问题的通用硬件加速器。

开发背景

在现实社会的每个领域,都需要从各种可能的组合中选择最佳解,这种要求被归类为组合优化问题。由于需要考虑的因素越多,组合数量就越多,甚至呈爆炸式增加。因此,组合优化问题无法通过传统处理器得到快速解决。

为此,富士通研究所开发了快速解决组合优化问题的数字退火技术。

课题

退火方法类似于金属退火原理,将金属加热到高温后再逐渐冷却,目的是使材料的晶体结构收敛到最佳状态。即通过逐渐降低处于高状态的参数(相当于温度),逐步缩小解的搜索范围,并最终找到能量最低的状态。在快速搜索这个状态时,存在一种权衡关系:缓慢降低温度(参数)进行操作的话可获得解的最佳精度,但计算时间会变长;相反,快速降低温度(参数)进行操作的话计算时间变短,但解的精度会降低。应用的问题类型不同,参数设置的最佳值,包括初始值、操作过程中的降低方式等也会有所不同。

将退火方法用于至今从未应用过的问题时,如比较分子相似性或投资组合优化等,通过为每种类型的问题寻找最佳参数设置,此类问题今后便可实现快速计算。但是,为了能够在短时间内获得高精度解的最佳参数设置,有时需要重复几万次,花费数周的时间进行不同参数设置的退火计算。

开发的技术

为了扩大数字退火的应用领域,富士通研究所开发了一种无需提前设置复杂参数的新技术来提高易用性。

本技术为在数字退火中进行优化处理的多个基本电路提供简单的初始参数,并进行并行操作。另外,基于设置在基本电路外的状态控制电路,通过按一定频率观测运算中的状态,适当改变参数,可实现对最佳解的高效搜索。

将传统的数字退火技术应用到新型问题时的流程

图1 将传统的数字退火技术应用到新型问题时的流程

装载了状态控制电路的新型数字退火

图2 装载了状态控制电路的新型数字退火

效果

利用该技术,用户可以在事先不进行复杂参数设置的情况下以高概率获得最佳解。因此,用户不再需要投入人力进行手工调整作业,即使是初次应用的问题,准备时间也可缩短至原来的1/10~1/100。这样,用户可以在短时间内获得数字退火的性能,并开始使用真实数据进行操作。

此次,富士通研究所通过应用了1QB Information Technologies Inc.(注3)量子计算技术的软件,对化学领域和金融领域的实用规模问题进行了效果验证。结果显示,对于化学领域50个原子规模的分子相似性比较问题(注4),和金融领域使用了500种股票的投资组合优化问题(注5),过去为获得所需精度的解,需要花费大约2周的准备时间,而现在缩短到不到一天就能完成。

50个原子规模的分子相似性比较问题应用实例

图3 50个原子规模的分子相似性比较问题应用实例

500种股票的投资组合优化问题应用实例

图4 500种股票的投资组合优化问题应用实例

今后

富士通研究所目标于2018年度实现该技术的商用化,将其应用到化学、金融、能源、流通等各领域的组合优化问题,为客户创造新业务做出贡献。

注释

 注1 株式会社富士通研究所:
社长 佐佐木 繁
总公司所在地 日本神奈川县川崎市
 注2数字退火(Digital Annealer):
“Fujitsu Laboratories Develops New Architecture that Rivals Quantum Computers in Utility”(2016年10月20日新闻稿)
 注31QB Information Technologies Inc.:
总部位于加拿大温哥华市,首席执行官Andrew Fursman。
自2017年5月起,富士通研究所与1Qbit开始在组合优化、机器学习等AI领域开展合作。
“Fujitsu and 1QBit Collaborate on Quantum Inspired AI Cloud Service”(2017年5月16日新闻稿)
 注4 分子相似性比较问题:
比较判断两个分子中结构和分子相似性的问题。
 注5 投资组合优化问题:
确定分布式投资的分配,使风险最小化的问题。