第三世代デジタルアニーラ
ご紹介資料

2021.2.1版

FUJITSU Quantum-Inspired
Computing Digital Annealer
富士通株式会社
関連技術を含め特許申請中

http://www.fujitsu.com/jp/digitalannealer/
Copyright 2021
2021 FUJITSU
FUJITSU LIMITEDLIMITED
Copyright第三世代デジタルアニーラ
ソフトウェア技術とハードウェア技術のHybridシステムが、大規模な実問題(100 Kbit規模)の高速求解を実現
ソフトウェアテクノロジー

ハードウェアテクノロジー

大域探索機能:超高速探索:

大規模問題にて複数の良解を抽出抽出した良解周辺の最適解を高速発見

第二世代デジタルアニーラと比較し、問題サイズ約10倍
1Copyright 2021 FUJITSU LIMITED第三世代デジタルアニーラの特徴
大規模化、高速化• 自動問題分割 :ハードウェアを超えるサイズの問題も分割技術で求解が可能に• 制約利用大域探索 :実課題にて頻出の典型的な制約(1-Hot制約)を利用することで処理を高速化

QUBO
入力部QUBO API

100K bits

ソフトウェアテクノロジー
自動問題分割

利便性

良解抽出• 制約項の係数自動調整:
チューニング作業の軽減

解出力

制約利用

制約項係数
自動調整

最適解の高速発見

ハードウェアテクノロジー• 不等式制約記述対応:- 不等式制約の直接定義・入力が可能- 補助ビットによるQUBO定式化が不要*QUBO(Quadratic Unconstrained Binary Optimization)
2

大域探索機能超高速探索

Copyright 2021 FUJITSU LIMITED第三世代デジタルアニーラ 汎用数式型 QUBO API 補足
利便性

利便性

高速性

制約項分離

不等式制約対応

1HOT制約対応

複雑な制約条件を分離入力し、QUBOのチューニングを簡単化

QUBOとは別に不等式制約を与えることにより、不等式を表す補助ビットを削減

実用問題で頻出の1HOT制約に対応
典型的な制約条件を高速に処理

目的関数

制約条件

ℋ = ෍ 𝑜𝑖𝑗 𝑥𝑖 𝑥𝑗 + 𝐴 ෍ 𝑝𝑖𝑗 𝑥 𝑖 𝑥𝑗𝑖≤𝑗𝑖 ≤𝑗

補助ビットによる不等式制約

目的関数

22𝐴 ෍ 𝑥𝑖 − 1ℋ = ෍ 𝑞𝑖𝑗 𝑥𝑖 𝑥𝑗 + ෍ 𝐿𝑘 ෍ 𝑑𝑘𝑗 𝑥𝑗 − 𝑦𝑘𝑖 ≤𝑗𝑘QUBO𝑖𝑗

不等式制約

制約項分離

1WAY-1HOT制約

෍ 𝑑𝑘𝑗 𝑥 𝑗 ≤ 𝑦𝑘

2WAY-1HOT制約
2𝐴 ෍ ෍ 𝑥 𝑖𝑗 − 1𝑖𝑗

2+ 𝐵 ෍ ෍𝑥 𝑖𝑗 − 1𝑗𝑖𝑗

デジタルアニーラ

デジタルアニーラ

係数𝑨を自動調整
チューニング作業を軽減

補助ビット𝒚𝒏 が不要に複数の不等式制約に対応
3

対象のグループ内から”１”となるビットを１つだけ選択する
より高速な探索を実現
Copyright 2021 FUJITSU LIMITED問題規模とビット数の関係例
第三世代
デジタルアニーラ

創薬（安定構造探索）

工場・製造（部品ピッキング）

交通（交通量最適化）

中分子

低分子

中分子

１フロア

数フロア

工場全体

東京湾近郊

東京都

東京圏

1K

10K

（高精度モデル）

100K

1M

ビット数
https://pr.fujitsu.com/jp/news/2018/09/18.html

4

Copyright 2021 FUJITSU LIMITEDサービス提供 ロードマップ
CY2018
第一世代
規模: 1024 bit
精度: 16 bit
65536 階調

2021

2020

2019

第三世代

第二世代
規模: 8192 bit
精度:

100k bit
精度:
64 bit規模:

64 bit

1.845x1019 階調

1.845x1019

階調ソフトウェアテクノロジー
X
ハードウェアテクノロジー

第四世代
求解速度:

次世代

10倍

求解高速化技術X
大規模問題求解技術
規模: 100k bit
精度:

64 bit

大規模問題の求解性能を向上させビジネス適用範囲拡大※ロードマップは予告なく変更される可能性があります。

5

Copyright 2021 FUJITSU LIMITED技術 ロードマップ
県域配送

全国配送

適用領域

中分子医薬
金融ポートフォリオ

要員計画

規模 ＞1M 変数

大規模実問題対応第三世代
第二世代

規模 100Kbit

規模 8192bit

第一世代
規模 1024bit

~2017

2018

※ロードマップは予告なく変更される可能性があります。

2019

2020
62021~
Copyright 2021 FUJITSU LIMITED第三世代デジタルアニーラ適用事例

7

Copyright 2021 FUJITSU LIMITEDグラフ彩色問題とその応用◼ デジタルアニーラ(DA)はより複雑なグラフ彩色問題において、商用ソルバに対し明らかな優位性が確認されている。
◼ グラフ彩色問題をベースとした実問題であるネットワークチャネル配置の最適化においても優れた結果を得た。
グラフ彩色問題

応用例：ネットワークチャネルの最適化

グラフ彩色問題とは…

ネットワークチャネルの最適化とは…

エッジ(辺)で繋がっているノード(頂点)同士が同じ色にならないようにすべてのノードを色分けする問題• 同一周波数帯を用いる基地局間の信号⼲渉を最⼩にすることを目的として、基地局毎の信号パターンを可能な限り周辺基地局と重複しないように割り当てる問題

辺密度bit規模

正答率
商用ソルバ

50%
以上

50%未満求解速度DA8k～50k

0%

100%

8k未満

33%

100%30倍

8k～50k0%

100%

-

8k未満

100%

100%

0.9倍

-辺密度: ノード同士のエッジで繋がっている比率
正答率: 規定計算時間内(最大10分)で解を得られた割合
求解速度: 商用ソルバを１としたときのDAの倍率
データセット:以下URLのランダム/疑似ランダムグラフ(DSJ/CUL)を10個使用
https://mat.tepper.cmu.edu/COLOR/instances.html

1,000基地局を対象とした大規模問題による性能比較
1000基地局のネットワークチャネル最適化(対商用ソルバ)重複量改善率

60 % 以上(対商用ソルバ)求解速度

120 倍 以上
商用ソルバでは長時間計算してもたどり着かなかった、重複量がより少ない良解に短時間で到達8

最適化前の重複量重複量

ベンチマーク結果

1

1.6

商用ソルバ
DA
0300

12000

24000

36000

計算時間[sec]

Copyright 2021 FUJITSU LIMITED平均分散ポートフォリオ最適化とその応用◼ 一般的な平均分散ポートフォリオ最適化において、デジタルアニーラ(DA)は商用ソルバに速度面で優位性がある。
◼ 非凸型指標を用いたより実用的なモデルの最適化では、商用ソルバがたどり着けない良解に到達。

平均分散ポートフォリオ最適化

応用例:非凸型指標を用いたポートフォリオ最適化

平均分散ポートフォリオ最適化とは…

• より一般的に銘柄数や取引単位を制約した平均分散モ
デルで性能測定を実施。
• 凸性は失われるが、商用ソルバもDAも同等の良解を得られた。
• 速度面でDAが優位。

෍ 𝑥𝑖 = 12,000銘柄のポートフォリオ最適化による性能比較

𝑖𝑥𝑖 ≥ 0(𝑖 = 1, … , 𝑛)

2000銘柄のポートフォリオ最適化
リスク(分散共分散の総和)

ベンチマーク結果

𝑠. 𝑡. 𝑟ഥ𝑝 𝑇 𝒙 ≥ 𝑟𝐸

• 新たなポートフォリオ構築のため、更なる非凸型指標を用いた、単純な平均分散ではないポートフォリオ最適化の需要がある。
• 分散を非凸に加工したモデルで性能測定を実施。

2000銘柄のポートフォリオ最適化(対商用ソルバ)解精度商用ソルバがたどり着けない良解

商用ソルバ
DA

商用ソルバ
DA

リスク

• 期待収益率が投資家の要求する期待収益率以上であるという制約の下で，リスク(分散)を最⼩化する資産への投資比率を求める問題。
• 凸2次計画問題であり、一般的に高速に求解できる。

min 𝒙𝑇 𝜎 2 (𝑝) 𝒙(対商用ソルバ)求解速度

250 倍 以上
04080120 160 200 240

400
020000 40000 60000 80000 100000

計算時間 [sec]計算時間 [sec]9Copyright 2021 FUJITSU LIMITED最大独立集合問題とその応用◼ デジタルアニーラ(DA)は最大独立集合問題に対して、商用ソルバへの優位性を持っている。
◼ 独立集合問題を用いた分子類似性検索では既存手法より高精度・高機能の類似性評価を実現。
応用例: 分子類似性検索

最大独立集合問題

分子類似性検索とは…
• “類似した化合物は類似した性質を持つ”という類似性質原則に基づき、特定の性質を持つ類似分子をデータベースから検索する手法。
• 例えば、材料・薬品候補をスクリーニングする際に用いられる。

最大独立集合問題とは…
• 頂点の部分集合のうち、どの二点間も辺で結ばれていない部分集合(＝独立集合)で最大のものを求める問題

香料分子に対する類似性評価による性能比較(※)(対既存手法)目的分子検出率

ベンチマーク結果
正答率
商用ソルバ

54%

求解速度
DA

94%

60倍

データセット:以下URLのDIMACS/BHOSLIBのベンチマークデータセット(107個)を使用
http://netw orkrepository.com/DIMA CS.php
正答率: 規定計算時間内(最大5分)で解を得られた割合
求解速度: 商用ソルバを１としたときのDAの倍率 (全データセットの平均値)

1.2 倍 以上

リナロール
OH

目的分子

特性(香り): シトラス

XOCO

YO

C

出力(構造類似度)②バニリン
O

候補分子CHO(132分子)O

香りを特徴づける部分構造の抽出

O

分子構造類似度計算①シトロネラール(対既存手法)差別化機能

2分子グラフ間の最大共通部分構造

入力(分子構造)

デジタルアニーラOH

既存手法(フィンガープリント法)

目的分子検出率

52%

DA67%

(※) 第13回分子科学討論会 名古屋 2019 デジタルアニーラを用いた香料分子の類似度評価

10

Copyright 2021 FUJITSU LIMITEDCopyright 2021 FUJITSU LIMITED