はじめに
現 在、 第 三 次 AI ブ ー ム と い わ れ、 数 多 く の AIを利用した自動化システムが出現しています。これは、ディープラーニング（Deep learning）または深層学習とよばれる、脳神経を模した多層の人
工ニューラルネットワークを用いた認識技術の劇的向上がきっかけでした。

をうたった D-Wave One を発表したのが、実用化のきっかけとなりました。
量子アニーリングとは、1998 年に東工大西森秀稔教授らが提唱した手法です。
モバイルコンピューティング推進コンソーシア
ム（MCPC）（会長：安田靖彦）では、このような2012 年、ジェフリー・ヒントン率いるトロント

量子コンピュータ関連技術の進展を受け、2018 年

大学のチームが、物体の認識率を競う ILSVRC にお

５月、AI ＆ロボット委員会内に量子コンピュータ

いてディープラーニングによって従来の手法（エ推進 WG を発足させました。

ラ ー 率 26%） に 比 べ て エ ラ ー 率 17% と 実 に 10%

本 WG では、コミュニケーションハブとして理もの劇的な進歩を遂げたことがその発端でした。

論・コンピューティング・応用 分野を融合させる

以降、ディープラーニングは、画像認識や音声取り組みを進めており、メンバーは、国内 IT メー

認識といった特定の知的作業では人間の能力をしカ含め 20 社・団体を集め、情報交換やディスカッのぐまでになっています。囲碁の世界チャンピオ

ションを進めてきました。

ンに勝った人工知能「Alpha Go」も、この技術を応用したものです。

活動開始以来、アニーリングコンピュータ技術の進化や、それを支える定式化アルゴリズムの蓄

この技術の登場により、人工知能は実用レベル

積・コンピューティング環境の整備が進んでおり、が高まり、適用の幅、可能性が大きく広がってい従来のコンピュータ方式では計算コストに難題をます。

抱えていた課題解決へ向けて、適用効果が見込め

一方、これを支える計算機の能力は、2 年で 2

るソリューション実装の兆しが見えています。

倍向上するという、ムーアの法則（経験則）が限

さらに、2019 年 9 月、このタイミングを逃すこ界となり、現行アーキテクチャによる高速化は、となくプロジェクトを立ち上げ、実用効果指標と並列化以外には難しい状況です。

なる社会課題テーマを選定し、有効性仮説の実験

そこで、新しいアーキテクチャである量子コン

成果を社会へ還元することを目的とした実証実験

ピュータに注目が集まっています。量子理論を基を開始しました。 現在３つの題材を選定し、準備にした量子コンピュータは、IBM や Google の米国を進めています。

勢、中国を中心に世界的な開発競争に突入してい一般向けへの啓もうと情報提供として、５回のます。日本でも産総研を中心に開発中ですが、実量子コンピュータシンポジウムも盛況裡に開催で用レベルにはもう少し時間が掛かりそうです。

きました。

量子コンピュータとは厳密には違いますが、「疑本冊子は、WG 参加企業による、今までの活動を似」量子コンピュータとでもよべる、量子アニー

まとめたものです。広く一般に公開し、量子コン

リング理論を応用した商用コンピュータが実用化

ピュータの正しい理解と活用の一助となれば、幸さ れ、 特 定 用 途 に お い て は 従 来 コ ン ピ ュ ー タ のいです。

１億倍の高速処理能力を持つことが実証されました。

なお、来年度以降も活動を継続しますので、ご興味ある企業の方の参加を歓迎いたします。

2011 年 5 月にカナダのベンチャー企業 D-Wave

2022 年 3 月

システムズが「世界初の商用量子コンピュータ」

前 AI& ロボット委員会副委員長 岡本 利夫

-1-

目
1.

次

量子コンピューティング技術 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3■

イジングマシン技術の研究開発動向 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3
早稲田大学グリーン・コンピューティング・システム研究機構 /科学技術振興機構さきがけ■

シミュレーテッド分岐マシンの概要
株式会社東芝■白根 昌之、矢田部 彰宏、山本 剛

大規模な組合せ最適化問題に向けたスケーラブルな CMOS アニーリングプロセッサ ．．．．．．．．22

川合 遼 、左尾 将隆、渡邉 裕之、武捨 悠一、宇都宮 啓宏、橋本 伸一

社会実装技術の紹介■

林 真人、竹本 享史、吉村 地尋、山岡 雅直

組合せ最適化問題を高速に解くデジタルアニーラの活用技術 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．28
富士通株式会社

2.

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．34

アニーリングマシンを活用した LTE のパラメータ最適化
株式会社 KDDI 総合研究所

■

■

■

大野 真一朗、八代 夕紀子、高橋 是清

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．53

田中 孝

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．59

全体最適とパーソナライズの両立を目指して ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．59
株式会社ナビタイムジャパン

■

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．．48

寺部 雅能

AI による予測と組み合わせ最適化の業務適用

新しい分野への挑戦

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．38

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．44

量子アニーリングで切り拓くモビリティ社会の未来

株式会社グルーヴノーツ

3.

田中 政晃、岡本 浩尚

事例紹介：機械学習と最適化の活用に向けた取組

株式会社デンソー

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．34

植田 徹史

株式会社 野村総合研究所■

齋藤 和広、 KDDI 株式会社

事例紹介：物流センターにおける人員配置最適化の取組
住友商事株式会社■

岩崎 元一

量子ビットの様々な方式と超伝導パラメトロンデバイス ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．16

株式会社日立製作所

■

．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．9

酒井 良哲、 東芝デジタルソリューソンズ株式会社

日本電気株式会社■

田中 宗

菊池 新、小田中 育生

Malware Cyber-Security への量子コンピューティング応用可能性に関する考察

．
．
．
．
．
．
．
．
．
．
．
．63

量子コンピュータ推進 WG 主査
株式会社ゼネテック / 慶應義塾大学 SFC 研究所

４．付録
■

柏山 正守

．．．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．67

量子アニーリング早わかり

．
．
．
．
．
．
．．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．
．67

モバイルコンピューティング推進コンソーシアム

竹井 俊文

-2-

<MCPC 量子コンピュータ推進 WG 2019>

イジングマシン技術の研究開発動向
田中 宗*1,*2
早稲田大学グリーン・コンピューティング・システム研究機構*1
科学技術振興機構さきがけ*2

Research and Development of Ising Machines
Shu Tanaka*1,*2
Green Computing Systems Research Organization, Waseda University*1
JST, PRESTO*2
論文概要
イジングマシンと呼ばれる組合せ最適化問題に特化した新しい計算技術に対する研究開発が近年盛んに行われている。イジングマシン領域の研究開発は，ハードウェア，ソフトウェア，アプリケーションの 3 側面，ならびにそれらを支える理論研究からなる。これらを相互に協調させながら研究開発をすすめることが，イジングマシン領域が真に使われる技術となるために重要であると考えられる。本原稿では，イジング
マシンを用いる方法について説明する。次に，ハードウェア，ソフトウェア，アプリケーション，理論の観点からイジングマシン領域の研究開発の概要について紹介し，今後の研究開発に必要となる項目について述べる。
Keyword: Ising machine, Quantum annealing, Combinatorial optimization problem, Machine learning

1. 緒言
近年，イジングマシンと呼ばれる，組合せ最適化問題に特化した新しい計算技術が注目を集めている。組合せ最適化問題とは，「膨大な選択肢の中から，制約を満たしかつ最適な選択肢を選び出す」という問題を指す。ここで，選択肢の良さを定量付けるのは目的関数であり，目的関数を最小もしくは最大にする選択肢を最適な選択肢という。組合せ最適化問題の例としてよく用いられる巡回セールスマン問題をもとに，上記について説明する。
巡回セールスマン問題とは，いくつかの訪問すべき場所があったとき，すべての場所を一度ずつ訪問する経路のうち，最も短い経路を探索する問題である。ここで制約条件は，すべての場所を一-3-度ずつ訪問しなければならない，という条件に相当し，目的関数は経路の長さに相当する。訪問するべき場所数に対して，訪問経路の候補数は指数関数的に増大する。そのため，訪問するべき場所
数が少ない場合には，全ての経路候補を列挙し，その中で最適な選択肢を選択する，という方策が簡単に取ることが可能だが，訪問するべき場所数が増えていくに従って，この方策は事実上不可能になる。
この困難を組合せ爆発と呼ぶ。そのため，組合せ最適化問題の高精度な答え（ベターな選択
肢）を高速に探索することが可能になる計算技術のニーズが高まっている。
組合せ最適化問題は多様な業種における様々な社会課題に内在する普遍的な問題である。店舗

等の人員シフト表の作成問題や，工場等における最適工程スケジューリング問題や，集積回路の設計問題など，組合せ最適化問題が内在するシーン
は枚挙にいとまがない。また近年，Internet-ofThings (IoT) 社会や Society5.0 と呼ばれる新しい社会観が醸成されてきたことによる，新しいタイプの組合せ最適化問題が潜在的に内在し得るフ
ェーズに突入している。このように，イジングマ
シンと呼ばれる組合せ最適化問題に特化した新しい計算技術への期待につながっていると言える。
本原稿では，イジングマシン領域における研究開発の現状と今後の展望について述べる。2 章ではイジングマシンの使い方の流れについて紹介し，続く 3 章ではハードウェア，ソフトウェア，アプ
図 1：イジングマシンの使い方の流れ。
リケーション探索，理論の観点からイジングマシ
り，𝑥𝑥𝑥𝑥𝑖𝑖𝑖𝑖 はバイナリ変数である。また，{𝒙𝒙𝒙𝒙}は𝑁𝑁𝑁𝑁個あるン領域の研究開発について説明する。4 章で結論
バイナリ変数をひとまとめで表したものである。イ
と今後の展望について述べる。
2. イジングマシンの使い方の流れ

この章では，イジングマシンを用いて組合せ最適化問題を処理する方法について紹介する。図 1にイジングマシンの使い方の流れを示す。
第 1 段階として，社会課題から組合せ最適化問
題を抽出し，その組合せ最適化問題を高速高精度に処理するビジネス価値があるかを判断する。ビ
ジネス価値の有無の判断については，イジングマ
シンの計算技術としての側面というよりかは，社会課題が内在する産業種のドメイン知識によるものであるため，本原稿では議論しない。
第 2 段階として，第 1 段階で抽出した組合せ最適化問題をイジングモデルないしは Quadratic
Unconstraint Binary Optimization (QUBO) 形
式で表現する 1,2)。イジングモデルは𝐸𝐸𝐸𝐸 Ising ({𝒔𝒔𝒔𝒔}) = � ℎ𝑖𝑖𝑖𝑖 𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖 + � 𝐽𝐽𝐽𝐽𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖 𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖 ,𝑖𝑖𝑖𝑖∈𝑉𝑉𝑉𝑉(𝑖𝑖𝑖𝑖,𝑖𝑖𝑖𝑖)∈𝐸𝐸𝐸𝐸

𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖 ∈ {+1, −1}で表される関数である。イジングモデルは無向グラ
フ𝐺𝐺𝐺𝐺 = (𝑉𝑉𝑉𝑉, 𝐸𝐸𝐸𝐸 ) 上に定義されるモデルである。ここで𝑉𝑉𝑉𝑉, 𝐸𝐸𝐸𝐸はそれぞれ無向グラフの頂点集合，辺集合を表す。また，ℎ𝑖𝑖𝑖𝑖 , 𝐽𝐽𝐽𝐽𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 はそれぞれ局所磁場，相互作用と呼ばれる量であり，実数値である。さらに𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖 はスピン変数と呼ばれる変数であり，{𝒔𝒔𝒔𝒔}は無向グラフ𝐺𝐺𝐺𝐺の頂点数個，つまり，|𝑉𝑉𝑉𝑉| = 𝑁𝑁𝑁𝑁個あるスピン変数をひとまとめで表したものである。また，QUBO 形式は
𝐸𝐸𝐸𝐸 QUBO ({𝒙𝒙𝒙𝒙}) =� 𝑄𝑄𝑄𝑄𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑥𝑥𝑥𝑥𝑖𝑖𝑖𝑖 𝑥𝑥𝑥𝑥𝑖𝑖𝑖𝑖 , 𝑥𝑥𝑥𝑥𝑖𝑖𝑖𝑖 ∈ {0,1}1≤𝑖𝑖𝑖𝑖≤𝑖𝑖𝑖𝑖≤𝑁𝑁𝑁𝑁

ジングモデルと QUBO はスピン変数とバイナリ変数の変換：
𝑠𝑠𝑠𝑠𝑖𝑖𝑖𝑖 = 1 − 2𝑥𝑥𝑥𝑥𝑖𝑖𝑖𝑖
によって互いに等価であることが示せる。イジング
モデルや QUBO は 2 値をとる変数（スピン変数，バ
イナリ変数）の 2 次の関数になっている。
第３段階として，第２段階で得られたイジングモ
デルないしは QUBO（論理イジングモデルないしは
論理 QUBO と呼ぶ）に対して，イジングマシンに入力するための前処理を行い，利用しようと考えているイジングマシンに即したイジングモデルないしはQUBO（物理イジングモデルないしは物理 QUBO と呼ぶ）を生成する。
第４段階として，物理イジングモデルないしは物理 QUBO をイジングマシンに入力し，イジングマシ
ンを動作させる。詳細な動作原理については 3.1 節
で説明する。
第５段階として，イジングマシンを動作させ最終的に得られた解を後処理することで，もとの論理イ
ジングモデルないしは論理 QUBO と整合性の合う解へ変換する。イジングマシンは確率的挙動を元にしているため，この補正が必要となる場合がある。
以下では，イジングマシン領域の研究開発について，ハードウェア，ソフトウェア，アプリケーショ
ン，理論の観点から紹介する。

3. イジングマシン領域の研究開発
3-1. イジングマシン（ハードウェア）の研究開発

イジングマシン研究開発のきっかけとなったので表される関数である。ここで𝑄𝑄𝑄𝑄𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 は実数値であ-4-

は，2011 年に D-Wave Systems によって発表された世界初の商用量子アニーリングマシン DWave3)がきっかけであると言えよう。量子アニー
リングマシンは，門脇，西森によって提案された量子アニーリング 4)や，Farhi らによって提案された断熱量子計算 5)に基づくハードウェアである。
門脇，西森の論文 4)によれば，量子アニーリングはイジングモデルのエネルギーが最小となる状態（基底状態）を探索するために，横磁場と呼ばれる量子
ゆらぎを導入し，それを徐々に弱めるという操作を行う。量子アニーリングを実装するハードウェア開発については，産業技術総合研究所や理化学研究所
が新エネルギー・産業技術総合開発機構（NEDO）の事業「組合せ最適化処理に向けた革新的アニーリン
グマシンの研究開発」で推進しており，また，NECが同じく NEDO の事業「超電導パラメトロン素子を用いた量子アニーリング技術の研究開発」において量子アニーリングを実装するハードウェア開発を推進している 6)。産業技術総合研究所は問題特化型の量子アニーリングマシンとして，Application SpecificAnnealing Circuit (ASAC) と呼ばれる方式を提案している 7)。上記のデバイスはいまのところ超電導エ
レクトロニクス技術を用いたものが開発されている。
量子アニーリングは，最適化問題に対する有用な
メタヒューリスティクスとして知られるシミュレー
テッドアニーリング（焼きなまし法）における温度
効果を量子効果に置き換えた計算技術と見ることができる。シミュレーテッドアニーリングをベースとしたイジングマシンは，日立による CMOS アニーリ
ングマシン 8)や富士通ならびに富士通研究所によるデジタルアニーラ 9)が挙げられる。これらは半導体
エレクトロニクス技術を元にしている。
さらに，量子アニーリングやシミュレーテッドア
ニーリングとは異なる原理でイジングモデルの基底状態を探索する計算原理に基づくハードウェア開発も進んでいる。NTT による光パルスを用いたイジン
グマシンであるコヒーレントイジングマシン
LASOLV10)や，東芝によるシミュレーテッド分岐ア
ルゴリズムを用いた Graphics Processing Unit (GPU)ならびに Field-Programmable Gate Array (FPGA) 実装
11)
等が挙げられる。更に最近，フィックスターズにより，GPU によるイジングマシン実装についても発表されている 12)。
3-2. イジングマシン向けソフトウェアの研究開発
イジングマシンのハードウェア制約を補完する-5-役割を果たすソフトウェア開発は着実に進められている。イジングマシンのハードウェア制約として代表的なものとして，イジングマシンにおけるスピン変数（バイナリ変数）の結合ネットワーク
形状の制限や，イジングマシンで一度に使えるス
ピン変数（バイナリ変数）の個数の制限が挙げられる。論理イジングモデル（論理 QUBO）はイジ
ングマシンのハードウェア制約を考慮せずに構築されたモデルである。
ここで結合ネットワーク形状の制限を補完する方法を紹介する。論理イジングモデルが定義される無向グラフを𝐺𝐺L とする。また，イジングマシンの結合ネットワークを表現する無向グラフを𝐺𝐺Pとする。このとき，グラフ変換𝐺𝐺M → 𝐺𝐺O を施すこと
により，制限のあるネットワーク構造に論理イジ
ングモデルを埋め込むことが可能となる。結合ネットワークに制限があるイジングマシンのいくつかについて，この埋め込みについてはソフトウェ
アで自動的に処理することが可能になっている。
また，より効率の良い埋め込み方法を探求するア
ルゴリズム開発が進められている。
またスピン変数（バイナリ変数）の個数制限を補完する方法として，大きな問題を複数の小規模の部分問題に分割することをソフトウェアで自動的に処理することが可能になっている。これについても，より効率の良い問題分割方法を探求する
アルゴリズム開発が進められている。
また，イジングマシンを用いたアプリケーショ
ン探索をより効率的に行うための有用なソフトウ
ェア開発も進められている。早稲田大学，東京工業大学，
国立情報学研究所，
産業技術総合研究所，
豊田通商，
フィックスターズ，
NEC により，
NEDO
事業「イジングマシン共通ソフトウェア基盤の研究開発」が進められている。また，フィックスタ
ーズによる開発支援環境の発表 12)なども最近行われた。更に，オープンソースソフトウェア開発として，リクルートコミュニケーションズの棚橋氏による PyQUBO2),13)や Jij による OpenJij14)なども重要な役割を果たしている。
さらに，イジングマシンの利用を促進するために，イジングマシンの入力を視覚的に行うことを可能にした Annealing Cloud Web15)が NEDO 事
業「組合せ最適化処理に向けた革新的アニーリング
マシンの研究開発」の活動として公開されており，多くのユーザによって利用されている（図 2）。

テリアルズ・インフォマティクスに対する応用について提案がなされている 24)。
物理モデルや化学モデルのシミュレーションに分類される例として，D-Wave Systems により，イジングモデルで表現される磁性体や相転移物質のシミュレーションを量子アニーリングで実行する取り組みが進められている 25),26)。また，量子ア
ニーリングマシンを用いた量子化学計算に対する性能評価についても進められている 27),28)。

図 2：Annealing-Cloud Web15)におけるイジ
ングエディタ（上）と，画像のノイズリダクシ
ョンのデモンストレーション（下）。
3-3. イジングマシンを用いたアプリケーションの研究開発

イジングマシンを用いたアプリケーションの研究開発は大きく３つに分類することができる。組合せ最適化問題，機械学習，物理モデルや化学モ
デルのシミュレーションである。
組合せ最適化問題に分類される例としては，フォルクスワーゲンによる渋滞回避のための経路選
択問題 16)やデンソーと東北大学による工場内のAutomated Guided Vehicle (AGV) の経路選択問
題 17)，リクルートコミュニケーションズと早稲田大学による広告配信最適化問題 2),18)，早稲田大学
らによる矩形パッキング問題 19)やスロット配置
問題 20)などが挙げられる。
機械学習に分類される例として，機械学習における学習を高度化する研究として，特徴量選択を
イジングマシンで実行する枠組みを構築する取り組みが複数のグループによって行われてい る21),22),23)。また最近，東京大学，物質・材料研究機
構，早稲田大学により機械学習における推論をイ
ジングマシンによって高速化する方法を用いたマ

また，イジングマシンを用いたアプリケーションの研究開発を加速させるための取り組みも進められている。文献 29）では様々な企業における取り組みについて，とくに現場エンジニアの声が多く収録されている。また，早稲田大学と富士通研究所において，
デジタルアニーラに関する包括的連携活動協定を締結 30)し，様々な分野の研究者による最先端の応用探索を進めている。また，2018 年度より情報処理推進
機構（IPA）による未踏ターゲット事業 31)が発足した。
これはイジングマシンや量子コンピュータを利用するソフトウェア開発人材の育成を目的とした事業である。イジングマシンを活用する例として，バイオ
インフォマティクス，スケジューリング問題，モビリティ（陸上交通ならびに海運），画像解析等さまざ
まな適用の検討が進められている。さらに，モバイ
ルコンピューティング推進コンソーシアム（MCPC）
AI&ロボット委員会量子コンピュータ推進 WG では2019 年 9 月にイジングマシンの産業応用実装に向けた実証実験を開始した 32)。これは社会課題を有する3 企業（KDDI 総合研究所，野村総合研究所，住友商事），定式化／検証を行う 3 企業（Jij，フィックスタ
ーズ，Quemix），並びに環境提供／実行を行う 3 企
業（日立製作所，NEC，富士通）の計９つの企業からなる大きな取り組みである。筆者は定式化検討並びに全体監修を務める。

3-4. イジングマシン領域の理論研究
イジングマシンをより高度化させること，
また，
イジングマシンのポテンシャルを引き出すことを目指した理論研究が進められている。その一端を紹介するため，量子アニーリングに対する理論研究について紹介する。
量子アニーリングでは，アニーリング途中過程
における基底状態と第一励起状態（基底状態の直上の状態）の間のエネルギーギャップが小さいと計算性能が悪くなることが断熱定理により理解することができる。特に，量子１次相転移と呼ばれ-6-る現象が生じる際には，問題サイズに対してエネ
ルギーギャップが指数関数的に小さくなることがあり，この場合には量子アニーリングは非効率である。そのため，量子１次相転移を避けるための方法を構築する研究がいくつかなされている。量子ゆらぎとして横磁場を用いた場合に量子１次相転移を引き起こす系に対し，横磁場とは別のタイプの量子ゆらぎを導入することで，量子１次相転移を回避する場合があることが示されている
33),34)。また，横磁場の弱め方を不均一にすること
で，ある種の量子１次相転移を除去することも示されている 35)。
他にも量子アニーリングのさまざまな理論について研究が展開されており，それについては文献
36)に詳しい。
4. 結言
本原稿では，イジングマシンの使い方の流れ，並びに，イジングマシン領域におけるハードウェ
ア，ソフトウェア，アプリケーション，理論の研究開発について紹介した。イジングマシン領域は研究開発が本格化してからまだ間もない段階である。イジングマシンがより広く使われる計算技術と成るためには，イジングマシン領域における多様なレイヤー間の研究開発の協調が必要不可欠である。特に応用探索の観点からは，3-3 節で述べた各種取組により，様々な実例が世に出ることで，より広くの業種，分野からの新たな挑戦が生まれてくると期待される。
参考文献
1) S. Tanaka, R. Tamura, and B. K. Chakrabarti,“Quantum spin glasses, annealing and computation,”
Cambridge University Press (2017).
2) K. Tanahashi, S. Takayanagi, T. Motohashi, and S.
Tanaka, J. Phys. Soc. Jpn. 88, 061010 (2019).
3) M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting,
F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J.
Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P.
Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I.
Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S.
Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose,
Nature 473, 194 (2011).
4) T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355
(1998).
5) E. Farhi, J. Goldstone, S. Gutmann and M. Sipser,-7-

quant-ph/0001106 (2000); E. Farhi, J. Goldstone, S.
Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science
292, 472 (2001).
6) https://jpn.nec.com/press/201810/20181009_04.html
7) M. Maezawa , G. Fujii, M. Hidaka, K. Imafuku, K.
Kikuchi, H. Koike, K. Makise, S. Nagasawa, H.
Nakagawa, M. Ukibe, and S. Kawabata, J. Phys. Soc.
Jpn. 88, 061012 (2019).
8) M. Yamaoka, C. Yoshimura, M. Hayashi, T. Okuyama,
H. Aoki, and H. Mizuno, IEEE Journal of Solid-State
Circuits 51, 303 (2016).
9) S. Matsubara, H. Tamura, M. Takatsu, D. Yoo, B.
Vatankhahghadim, H. Yamasaki, T. Miyazawa, S.
Tsukamoto, Y. Watanabe, K. Takemoto, and A.
Sheikholeslami, Conference on Complex, Intelligent, andSoftware Intensive Systems 432 (2017).
10) T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S.
Tamate, T. Honjo, A. Marandi, P. L. McMahon, T.
Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K.
Aihara, K. Kawarabayashi, K. Inoue, S. Utsunomiya, and
H. Takesue, Science 354, 603 (2016); P. L. McMahon, A.
Marandi, Y. Haribara, R. Hamerly, C. Langrock, S.
Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K.
Aihara, R. L. Byer, M. M. Fejer, H. Mabuchi, and Y.
Yamamoto, Science 354, 614 (2016).
11) H. Goto, K. Tatsumura, and A. R. Dixon, Science
Advances 5, eaav2372 (2019).
12) https://quantum.fixstars.com
13) https://pyqubo.readthedocs.io/en/latest/14) https://github.com/OpenJij/OpenJij15) https://annealing-cloud.com
16) F. Neukart, G. Compostella, C. Seidel, D. Von
Dollen, S. Yarkoni, and B. Parney, Frontiers in ICT 4, 29(2017).
17) M. Ohzeki, A. Miki, M. J. Miyama, and M. Terabe,
Frontiers in Computer Science 1, 9 (2019).
18) 田中宗，棚橋耕太郎，本橋智光，高柳慎一，低温工学 53, 287 (2018).
19) K. Terada, D. Oku, S. Kanamaru, S. Tanaka, M.
Hayashi, M. Yamaoka, M. Yanagisawa, and N. Togawa,Proceedings of 2018 International Symposium on VLSI
Design, Automation and Test (VLSI-DAT) (2018).
20) S. Kanamaru, D. Oku, M. Tawada, S. Tanaka, M.
Hayashi, M. Yamaoka, M. Yanagisawa, and N. Togawa,Proceedings of 2019 IEEE International Conference on
Consumer Electronics (ICCE) (2019).

21) H. Neven, V. S. Denchev, M. Drew-Brook, J. Zhang,
W. G. Macready, and G. Rose, NIPS 2009
Demonstration, (2009); H. Neven, V. S. Denchev, G.
Rose, and W. G. Macready, JMLR Workshop andConference Proceedings 25, 333 (2012).
22) D. O'Malley, V. V. Vesselinov, B. S. Alexandrov, andL. B. Alexandrov, PLOS ONE, 13, e0206653 (2018).
23) K. Tanahashi, S. Takayanagi, T. Motohashi, and S.
Tanaka, Adiabatic Quantum Computing Conference
2018, (2018).
24) K. Kitai, J. Guo, S. Ju, S. Tanaka, K. Tsuda, J.
Shiomi, and R. Tamura, arXiv:1902.06573 (2019).
25) R. Harris, Y. Sato, A. J. Berkley, M. Reis, F.
Altomare, M. H. Amin, K. Boothby, P. Bunyk, C. Deng,
C. Enderud, S. Huang, E. Hoskinson, M. W. Johnson, E.
Ladizinsky, N. Ladizinsky, T. Lanting, R. Li, T. Medina,
R. Molavi, R. Neufeld, T. Oh, I. Pavlov, I. Perminov, G.
Poulin-Lamarre, C. Rich, A. Smirnov, L. Swenson, N.
Tsai, M. Volkmann, J. Whittaker, and J. Yao, Science
361, 162 (2018).
26) A. D. King, J. Carrasquilla, J. Raymond, I. Ozfidan,
E. Andriyash, A. Berkley, M. Reis, T. Lanting, R. Harris,
F. Altomare, K. Boothby, P. I. Bunyk, C. Enderud, A.
Fr¥'echette, E. Hoskinson, N. Ladizinsky, T. Oh, G.
Poulin-Lamarre, C. Rich, Y. Sato, A. Y. Smirnov, L. J.
Swenson, M. H. Volkmann, J. Whittaker, J. Yao, E.
Ladizinsky, M. W. Johnson, J. Hilton, and M. H. Amin,
Nature 560, 456 (2018).
27) R. Xia, T. Bian, and S. Kais, J. Phys. Chem. B 122,
3384 (2018).
28) M. Streif, F. Neukart, and M. Leib, arXiv:1811.05256(2018).
29) 寺部雅能，大関真之，『量子コンピュータが買える未来』（オーム社，2019 年）30) https://www.waseda.jp/top/news/61199
31) https://www.ipa.go.jp/jinzai/target/index.html32) http://www.mcpcjp.org/press/pdf/press_20190919.pdf33) Y. Seki and H. Nishimori, Phys. Rev. E 85, 051112(2012).
34) Y. Seki, S. Tanaka, and S. Kawabata, J. Phys. Soc.
Jpn. 88, 054006 (2019).
35) Y. Susa, Y. Yamashiro, M. Yamamoto, and H.
Nishimori, J. Phys. Soc. Jpn. 87, 023002 (2018).
36) 西森秀稔，大関真之，『量子アニーリングの基礎』（共立出版，2018）-8-

<MCPC 量子コンピュータ推進 WG 2019>

シミュレーテッド分岐マシンの概要
酒井 良哲*1（株）東芝*1

岩崎 元一*2

東芝デジタルソリューソンズ（株）*2

Simulated Bifurcation Machine: An Overview
Yoshisato Sakai*1
Toshiba Corporation*1

Motokazu Iwasaki*2

Toshiba Digital Solutions Corporation*2

論文概要
シミュレーテッド分岐マシンは大規模な組合せ最適化問題を解くために開発された高速なソルバである。そのアルゴリズムは量子計算の研究の過程で生まれたものであるが，従来のソフトウエア技術やディジタル回路技術を用いて実施できる。その柔軟性を活かして社会実装への取り組みが様々な形で進められている。

Keyword: Optimization Methods, Nonlinear Dynamical Systems, Parallel Processing

1. はじめに2. 開発の経緯

本稿では大規模な組合せ最適化問題を解くために開発されたシミュレーテッド分岐マシン（Simulated
Bifurcation Machine，以下 SBM と呼ぶ）について，
その開発の経緯と特徴，および社会実装に向けた取り組みについて述べる。
SBM はいわゆるイジングマシンの一種としてイ
ジ ン グ 模 型 の 形 式 も し く は QUBO (Quadratic
Unconstrained Binary Optimization)という形式の最適化問題を解くことができる。これらの形式に変換することで他の種類の問題にも適用できる。
そのアルゴリズムは量子計算の研究の過程で生まれたものであるが，既存の（古典計算機のための）ソフトウエア技術やディジタル回路技術を使って実装可能であり，しかも従来の最適化手法を上回る性能を示す。その特徴を活かして，従来は解決をあきらめていた社会課題を SBM で解決するための検討が進められている。

SBM の開発の端緒は 2016 年に後藤によって提案された量子分岐マシン(quantum bifurcation machine)[1]である。これは非線形発振器を素子として用いる
量子計算機の提案であった。その性能に対する量子性の寄与について論じるため，[1]では古典力学的な近似についても考察していた。後藤はそこで，この古典力学的な方程式を簡略化すれば，新しい最適化
アルゴリズムが得られることに気づいた。このアルゴリズムは既存の古典計算機で高速に実行可能であり，しかも大規模な問題事例を扱う能力を持っていた。
このアルゴリズムを実装したものをシミュレーテ
ッド分岐マシン(SBM)と呼んでいる（ソフトウエア
としての実装や専用のディジタル回路を含む）。このア ル ゴ リ ズ ム は 2019 年 に 発 表 さ れ た (Goto,
Tatsumura, & Dixon [2])。その原理や開発の経緯に関しては後藤による解説[3]が詳しい。

-9-

表 1

3. アルゴリズムの詳細
SBM はイジング模型の形式を借りた次のタイプの組合せ最適化問題を解くことができる。ここで𝑛𝑛は決定変数の数，𝐽𝐽𝑖𝑖,𝑗𝑗 は所与の定数（ただし𝐽𝐽𝑖𝑖,𝑗𝑗 = 𝐽𝐽𝑗𝑗,𝑖𝑖 ,𝐽𝐽𝑖𝑖,𝑖𝑖 = 0）である。
𝑛𝑛

𝑛𝑛

1
minimize 𝐸𝐸 = − ∑ ∑ 𝐽𝐽𝑖𝑖,𝑗𝑗 𝑠𝑠𝑖𝑖 𝑠𝑠𝑗𝑗
2
𝑖𝑖=1 𝑗𝑗=1

入力(1)

subject to 𝑠𝑠𝑖𝑖 ∈ {−1, 1} (𝑖𝑖 = 1, … , 𝑛𝑛)

言い換えるとこの問題は「与えられた𝐽𝐽𝑖𝑖,𝑗𝑗 に対して上記の目的関数𝐸𝐸 の値が小さくなるように決定変数
𝑠𝑠1 , … , 𝑠𝑠𝑛𝑛 の値をそれぞれ1または−1のどちらかに決めよ」という内容である。
問題(1)を解くために SBM ではある種のハミルト
ニアンで指定される力学系（微分方程式）を数値的に解くという手段をとる。その際に数値解法として簡単で高速なシンプレクティック・オイラー法を適用できるようにハミルトニアンの形式が工夫されている。それを用いて位置や運動量に相当する𝑥𝑥𝑖𝑖 , 𝑦𝑦𝑖𝑖 の値を計算し，最終的には𝑥𝑥𝑖𝑖 の符号に合わせて𝑠𝑠𝑖𝑖 の値を1または−1に定めて出力する。
そのアルゴリズムの具体例を疑似コードの形で図1 に示す。表 1 はその入出力の一覧である。このア
ルゴリズムの使い方としては，𝑥𝑥𝑖𝑖 , 𝑦𝑦𝑖𝑖 の初期値を変えながら実行を繰り返し，結果の分布を調べるというのが標準的な手順となる。
なお，図 1 の元となったハミルトニアンは次式の通りである。ただし簡略化のために𝐾𝐾 = 1, 𝐷𝐷 = 1としている。
for 𝑖𝑖 ≔ 1, … , 𝑛𝑛 {𝑥𝑥𝑖𝑖 , 𝑦𝑦𝑖𝑖 を乱数で決める;}
for 𝑡𝑡 from 0 to 𝑇𝑇 − 1 {𝑝𝑝 ≔ 𝑡𝑡/𝑇𝑇 ;for 𝑖𝑖 ≔ 1, … , 𝑛𝑛 {𝑥𝑥𝑖𝑖 ≔ 𝑥𝑥𝑖𝑖 + Δ𝑡𝑡 𝑦𝑦𝑖𝑖 ;}for 𝑖𝑖 ≔ 1, … , 𝑛𝑛 {𝑦𝑦𝑖𝑖 ≔ 𝑦𝑦𝑖𝑖 + Δ𝑡𝑡 ((𝑝𝑝 − 1 − 𝑥𝑥𝑖𝑖2 )𝑥𝑥𝑖𝑖 + 𝑐𝑐 ∑𝑛𝑛𝑗𝑗=1 𝐽𝐽𝑖𝑖,𝑗𝑗 𝑥𝑥𝑗𝑗 ) ;}}for 𝑖𝑖 ≔ 1, … , 𝑛𝑛 {𝑠𝑠𝑖𝑖 ≔ sgn 𝑥𝑥𝑖𝑖 ;}図 1 SBM のアルゴリズムの例

出力

SBM のアルゴリズム（図 1）の入出力

記号
𝐽𝐽𝑖𝑖,𝑗𝑗 ∈ ℝ(𝑖𝑖, 𝑗𝑗 = 1, … , 𝑛𝑛)
ただし𝐽𝐽𝑖𝑖,𝑗𝑗 = 𝐽𝐽𝑗𝑗,𝑖𝑖 , 𝐽𝐽𝑖𝑖,𝑖𝑖 = 0
𝑇𝑇 ∈ ℕ

意味
目的関数を表す行
列

メインループの繰り返し回数
時間の刻み幅
勾配の大きさを調節する定数
問 題 (1) の 近 似 的 な
解Δ𝑡𝑡 ∈ ℝ𝑐𝑐 ∈ ℝ

𝑠𝑠1 , … , 𝑠𝑠𝑛𝑛 ∈ {−1,1}
𝑛𝑛

𝐷𝐷
𝐾𝐾
𝐷𝐷
𝐻𝐻(𝒙𝒙, 𝒚𝒚, 𝑡𝑡) = ∑ [ 𝑦𝑦𝑖𝑖2 + 𝑥𝑥𝑖𝑖4 + (1 − 𝑝𝑝(𝑡𝑡))𝑥𝑥𝑖𝑖2 ]
2
4
2
𝑖𝑖=1

𝑛𝑛

𝑛𝑛

𝑐𝑐
− ∑ ∑ 𝐽𝐽𝑖𝑖,𝑗𝑗 𝑥𝑥𝑖𝑖 𝑥𝑥𝑗𝑗
2
𝑖𝑖=1 𝑗𝑗=1

4. 適用例
ここで最大カット問題を題材として簡単な SBMの適用例を示そう。最大カット問題とは，与えられた無向グラフの頂点を 2 つのグループに分割するときに，グループ間をまたがる辺の数が最大となるよ
うに分割方法を決めるという問題である。
手順としては，まずグラフに合わせて𝐽𝐽𝑖𝑖,𝑗𝑗 の値を決め，それから問題(1)を解く。すると，𝑠𝑠𝑖𝑖 = 1に対応する𝑖𝑖のグループと𝑠𝑠𝑗𝑗 = −1に対応する𝑗𝑗のグループへの分割という形で元のグラフの最大カットが判明する。
具体的な事例として，図 2 のような 4 つの頂点と3 つの辺を持つグラフを考える。このグラフは1 − 3間，1 − 4間，2 − 4間に辺を持つので，それらに対応

図 2- 10 -

最大カット問題の簡単な事例

(a)

(b)

図 3

最大カット問題での SBM の実行例

する形で𝐽𝐽1,3 = 𝐽𝐽1,4 = 𝐽𝐽2,4 = 𝐽𝐽3,1 = 𝐽𝐽4,1 = 𝐽𝐽4,2 = −1とし，他の𝐽𝐽𝑖𝑖,𝑗𝑗 は0とする。すると，この𝐽𝐽𝑖𝑖,𝑗𝑗 に対して問題(1)の 目 的 関 数 𝐸𝐸 は (𝑠𝑠1 , 𝑠𝑠2 , 𝑠𝑠3 , 𝑠𝑠4 ) = (1,1, −1, −1) ま た は(𝑠𝑠1 , 𝑠𝑠2 , 𝑠𝑠3 , 𝑠𝑠4 ) = (−1, −1,1,1)のときに最小値−3を取る。これらの解はいずれも{1, 2}と{3, 4}という分割を表しており，図 2 のグラフの最大カットに対応する
ことが確認できる。
上記の𝐽𝐽𝑖𝑖,𝑗𝑗 を入力として SBM（図 1 のアルゴリズ
ム）を実行した結果が図 3 である。この図の(a)は，
時刻𝑡𝑡 = 0に原点近傍から出発した𝑥𝑥𝑖𝑖 が時間経過とともに正または負の向きに分かれる様子を示している。 (b)は相空間において点(𝑥𝑥𝑖𝑖 , 𝑦𝑦𝑖𝑖 )が原点近傍から離れていく様子を示している。この図では最終的に𝑥𝑥1 , 𝑥𝑥2 > 0, 𝑥𝑥3 , 𝑥𝑥4 < 0となっているので，SBM の出力としては(𝑠𝑠1 , 𝑠𝑠2 , 𝑠𝑠3 , 𝑠𝑠4 ) = (1,1, −1, −1)が得られたことになる。
5. アルゴリズムの特徴
SBM のアルゴリズムは微分方程式の数値解法に基づいているため，科学技術計算や信号処理の分野で開発された数値計算の技術との親和性が高い。特に並列化をしやすいことは大きな利点といえる。た- 11 -

とえば図 1 における for 𝑖𝑖 ≔ 1, … , 𝑛𝑛 { … } というループは並列化可能である。また，加算と乗算だけから成るため，ハードウエア化（ディジタル回路としての実装）にも向いている。
そのため SBM のアルゴリズムは（従来の集中型
計 算 機 で も 実 行 可 能 で あ る が ） GPU (graphics
processing unit)や FPGA (field programmable gate array)のように並列計算に向いた新しいタイプの計算資源の特徴を活かしやすいものとなっている。
さらに，ソフトウエアとして実装できることの利点として，ハードウエア構造に由来する制約の影響を避けやすいことが挙げられる。特殊なハードウエ
アを用いたソルバでは 𝐽𝐽𝑖𝑖,𝑗𝑗 （決定変数の間の結合の係数）の設定方法に制限があることが多い。それによって問題の変換が必要になれば，結果として利用可能な決定変数の個数が実質的に減少してしまう。
これに対して SBM ではメモリ容量が許す限り任意の𝑖𝑖, 𝑗𝑗 (𝑖𝑖 ≠ 𝑗𝑗)に対して自由に 𝐽𝐽𝑖𝑖,𝑗𝑗 の値を設定できるので，そのような影響は受けない。
計算機クラスタ（GPU の利用時も含む）や FPGAを用いた場合の性能が[2]で議論されており，そこでは従来技術と比較して SBM が大規模な問題を高速に解くのに向くことが示されている。FPGA による

実装例については Tatsumura, Dixon, & Goto [4]に詳しい。
6. 社会実装に向けた取り組み
SBM は，以上述べたように大きな可能性を持ったイジングマシンと考えており，広く使っていただけ
るよう，現在事業化に取り組んでいるところである（ 図 4 ）。 こ の 手 始 め に ， 2019 年 7 月 ， AWS
Marketplace 上に PoC（Proof of Concept, 概念実証）版を公開した [5]。
PoC 版では，多くのユーザに手軽にイジングマシ
ンを使っていただき，さまざまな取り組みを始めていただくため，期間限定で SBM 部分を無償とし，ユーザ自身で契約したクラウド事業者(AWS)の料金だ
けで利用いただける設定としている。インタフェー
スとして，イジング（QUBO）形式だけでなく，最大カット問題や充足最大化問題(MaxSAT)のソルバも用意し，イジングモデルに慣れていないユーザにも触っていただけるようにした。
PoC 版の公開後，国内外のさまざまな企業からお問い合わせ・試用をいただき，その中からより実用化に近い取り組みも始まっている。並行して，ユー
ザと SBM の間のバリューチェーンをつなぐためのさまざまな協業も進めている。SBM を広く使っていhttps://www.toshiba-sol.co.jp/pro/sbm/index_j.htm

図 4 シミュレーテッド分岐マシンの紹介ページ

ただけるようにするためには，次のような企業と協力して一緒に進めていく必要があると考えている。

業種ごとのソリューションパートナ（フィンテック，人工知能，物流など）やシステムイ
ンテグレータ
数理最適化のスキルのあるコンサルタント

数理最適化ソルバのパートナ
イジングモデルを扱うテクノロジパートナ

SBM による事業を開発する事業パートナ
現在実問題の検証を進めながらこうしたパートナとの協業を進めており，今後もさまざまな分野のユーザやクラウド事業者，さらにはハードウエアベン
ダも含めて，連携をより拡大したいと考えている。
7. SBM の特長と適合する領域
SBM の特長は，前述のようにあくまでアルゴリズ
ムであり，ハードウエアのアーキテクチャに制約がないことにある。このためにアプリケーションが求める要件に従って，さまざまな環境に移植することができ，現在のコンピュータ技術における最新環境のそれぞれの利点を活かすことができる。
たとえば最新の大規模並列環境を活かし，大量のデータ・大きな問題を扱いたい場合には，巨大クラウド事業者の大量の GPU 環境が適している。クラウド環境であれば，全世界で利用することができ，すでにその環境でさまざまなアプリケーションを動かしているユーザや，アプリケーションを開発するためのツールを提供しているベンダなど多数のプレー
ヤに届くため，相互に連携することで，新たなアプ
リケーションの可能性も期待できる。
一方で少量のデータをリアルタイム・高速に扱う
アプリケーションや，秘匿性の高い情報を扱うアプ
リケーションのためには，オンプレミスの形態が適している。さらに計算と処理の間で最高度の低遅延を狙う場合には，FPGA を使う選択肢もある。
SBM は必ずしも常に厳密解を出力するわけではないが，比較的短時間に良解に到達するという性質を持っていることから，時間的な制約がある問題に対するチューニングの余地が大きい。厳密解ではな
いものの，コンピュータリソースの範囲であれば大規模問題を扱うことができるという特長もある。
現在，さまざまな PoC を通じて，こうした特長が活きる領域，適合するアプリケーションを探っているところである。イジングマシンの社会実装はまだ始まったばかりと言って良く，業界全体として，市- 12 -

場立ち上げに向けてイジングマシンに対する需要とそれに応えるサービスの供給の双方のバランスの取れた拡大に取り組むべき状況と認識している。こうした状況の中，大規模な問題を高速に解くことができ，柔軟な運用が可能な SBM を活用してイジング
マシンの需要拡大に貢献していきたいと考えている。

こうした SBM の社会実装への取り組みの中で，有力なターゲットが金融分野である。
金融分野に向けては，これまで 2 種類の PoC を実施している。一つは外国為替市場における裁定取引をモチーフにした PoC であり[6]，もう一つはパッシ
ブファンドを想定したポートフォリオ最適化の PoCである。それぞれの想定される適用シーンにおけるリアルタイム性の要求と必要とされるデータ量の違いから，前者は FPGA・オンプレミス環境，後者はGPU・クラウド環境を想定した PoC を実施した（表2）。
8-1 外国為替市場における裁定取引機会の発見
外国為替市場において多数の市場参加者がさまざ
まな通貨を交換することで時々刻々と相場が変動する間に，例外的な状態として，瞬間的に無条件に収益を挙げられる取引の組合せ（裁定取引機会）が生

外国為替
取引所

PoC
裁定取引
機会発見
ポートフォ

規模

€

￥

CAD

最良の裁定取引経路

＄

€

大規模

不要

小

取引アルゴリズム処理回路

低遅延専用インターフェース回路

市況パケットpair ID⑤①④①専用インターフェース②

為替レート ￥
マトリックス
管理回路 ＄€￥＄ €②為替マトリックス管理

イベントドリブン動作
1クロック超ワイドパラレル出力③SBの専用処理回路
最良裁定取引経路の探索④取引アルゴリズム回路発見された経路に基づく注文
パケット生成⑤専用インターフェース
発注パケットの発送

FPGA

裁定取引機会の発見に関する PoC（FPGA を用いた実装）- 13 -FPGA・オ
ンプレミス

通貨ペアの市況パケットの取込み(不定期、シーケンシャル動作)

10Gb Ethernet
cable

図 5

形態

GPU・
クラウド

じることがある。こうした機会をいち早く発見し，取引を行うことができれば，市場の例外状態を解消しながら，同時に収益を上げることができる。
裁定取引機会を発見する問題は，重み付きグラフの最適経路問題として定式化できることが知られて
おり[7]，組合せ最適化問題としてイジング問題に変換できるので，SBM で扱える。このときシステムとして外国為替の取引を行うことを想定すると，単にSBM によって裁定取引機会を発見するだけでは不充分で，この処理の前後に通信回線を通して市況の最新情報を取り込み，内部に保持し，機会を発見した後には通信回線を通して市場に注文を出すという一連の処理もシステム化する必要がある。
裁定取引のアプリケーションの場合，リアルタイ
ム性が重要であり，機会発見から発注までの処理をできるだけ早く完了させる必要がある。現状の高速取引の例から考えるとクラウドに問い合わせての計
算では間に合わず，オンプレミスのシステムが必須

③

取引注文
パケット

秘匿性

大

30マイクロ秒￥

SBアルゴリズムの専用処理回路イム性
必須

重み付き有向グラフにおける最適経路問題

＄

リアルタ

小規模

裁定取引マシンのPoC機￥

CAD

金融分野における 2 種の PoC の想定環境

リオ最適化

8. 金融分野での 2 つの PoC＄

表 2である。さらにより高速な処理のためには FPGA の利用が適している。裁定取引機会発見のためにはある時点における市況の情報のみが重要で，処理に必要なデータ量は多くなく，この点でも FPGA での処理が適している。
こうしたことからこの PoC では，関連する処理を
すべて一台の FPGA 内で行うようにした(図 5)。たとえば通信パケットを処理するためのプロトコルもFPGA 内に実装し，また必要なデータも FPGA 内で保持しているため，外部のプロセッサでの処理は不要となっている。
こうした工夫により，SBM による高速な裁定取引
機会発見の機能をベースとしたシステムでは，市況の情報を受け取ってから取引の発注までを 30 マイ
クロ秒以内に行うことが可能であることを実証した。
このとき市況データの事後的な解析から，SBM は市場に実際に発生した裁定取引機会の 98%を発見し，また最も期待収益率の高い機会の 91%を発見していることを確認している。裁定取引機会の発見の確率はもっと上げることができるが，比較的早く良解に到達できるという SBM の特性を考慮しながら，30
マイクロ秒という目標時間の中で工夫・調整した結果である。
8-2 ポートフォリオ最適化
金融分野には一般にポートフォリオ最適化と呼ばれる，資産の最適な組合わせを求める問題が広く現れる。ポートフォリオ最適化には，扱う資産の種類
や，保有の方針などによってさまざまなタイプがあ

図 6

りえるが，基本的に組合せ最適化問題として定式化
でき，SBM で扱うことができる。たとえば金融機関
がファンドを組む際に，ファンドの運用方針に照らしてどの株式を何株保有するのが最適かを決める問題などがあり，今回の PoC ではそのうちでも特にパッシブファンドを組むケースをモチーフに PoC を実施した。
この PoC では，TOPIX（東証株価指数）を構成す
る約 2000 銘柄から 500 銘柄を選んでポートフォリ
オを組み，TOPIX との間でトラッキングエラー（ポートフォリオのリターンとベンチマークのリターンとの乖離の大きさ）が最小になるようなファンドを組むという課題を設定した。この際，仮説的に「ある時点から見て過去一定期間トラッキングエラー値が小さかったポートフォリオは，その後も短期間であればトラッキングエラー値が小さい」という性質を仮定し，SBM を使って過去データからトラッキン
グエラー値が最小のポートフォリオを求めた。
ポートフォリオを求める計算には過去 3 年分の株価データを使い，1 か月に 1 回ポートフォリオの組
み替えを行い 1 か月保持する，という運用を繰り返す想定とした。ポートフォリオを組む際は，TOPIXにおける構成比とあまり大きく離れないようにするなど，2000 銘柄それぞれに対する制約を含む数千の制約を満たしつつ，高速に計算ができるよう工夫した。
これらの条件で SBM によりポートフォリオを決め，2016 年 4 月から 2018 年 3 月までの 2 年間を対象にバックテストを実施した結果，実績トラッキン
グエラー値で 0.2%の運用となった（図 6）。この PoC

ポートフォリオ最適化の実施例（TOPIX への追従）- 14 -

により，数千の資産候補から，目標関数を設定した上で，一定の制約を満たしながら，保有資産を選定し，保有量を決定するという基本的な動作について，
SBM の計算能力を確認できたものと考えている。
ポートフォリオ最適化の場合，リアルタイム性は必須ではなく，たとえば一定頻度で行われる組み換えの際に所定の時間内で計算が終われば良い。計算には候補となる全資産の過去の数年間のデータが必要である。また使用するのは市場データであり高度の秘匿性を求められるものではない。これらを考慮するとオンプレミス環境にこだわる必要はなく，クラウド環境で処理を行えば良い。また，問題のサイズから，FGPA ではなく GPU が適する。以上から，
この PoC では，GPU を使用して実施している。
9. むすび
量子計算を実現する物理現象への洞察から生まれた SBM は，量子計算機ではなく既存の計算機で，大規模かつ高速な計算を可能にする。SBM によって今まであきらめていた問題を今解くことができるようにすることで，本格的な量子計算機の登場を待たずにさまざまな産業のイノベーションに貢献したいと考えている。
参考文献[1] Goto, H.: Bifurcation-based adiabatic quantum
computation with a nonlinear oscillator network,
Sci. Rep. 6, 21686 (2016).
[2] Goto, H., Tatsumura, K. and Dixon, A. R.:
Combinatorial optimization by simulating adiabatic
bifurcations in nonlinear Hamiltonian systems,
Science Advances, 5, eaav2372 (2019).
[3] 後藤隼人： 量子計算から生まれた組合せ最適化
アルゴリズム ― 古典力学の断熱変化とエルゴ
ード性を利用して解を探索する, 日本物理学会
誌, vol. 75, no. 2 (2020).
[4] Tatsumura, K., Dixon, A. and Goto, H.: FPGA-based
simulated bifurcation machine, Proc. 29th
International Conference on Field Programmable
Logic and Applications (FPL 2019), pp. 59-66(2019).
[5] 東芝デジタルソリューションズ（株）: 大規模
組合せ最適化を高速に実行するソフトウェア「シミュレーテッド分岐マシン」を AWS- 15 -

Marketplace 上に公開, ニュースリリース（オンライン）, 入手先 <https://www.toshibasol.co.jp/news/detail/20190717.htm> (2019-7-17).
[6] （株）東芝: シミュレーテッド分岐アルゴリズ
ムを搭載した超高速な金融取引マシンのコンセ
プト実証機を開発，ニュースリリース（オンライン），入手先<http://www.toshiba.co.jp/rdc/detail/1910_02.htm>(2019-10-17).
[7] Soon, W. and Ye, H. Q.: Currency arbitrage detection
using a binary integer programming model, Int’l J.
Math. Edu. Sci. Tech., vol. 42, no. 3, pp. 369-376(2011).

<MCPC 量子コンピュータ推進 WG 2019>

量子ビットの様々な方式と超伝導パラメトロンデバイス
白根 昌之

矢田部 彰宏日本電気株式会社 システムプラットフォーム研究所

山本 剛〒305-8501 茨城県つくば市御幸が丘 34 番地

Various Types of Quantum Bits andSuperconducting Parametron Oscillator
Masayuki Shirane

Akihiro Yatabe

Tsuyoshi Yamamoto

System Platform Research Laboratories, NEC Corporation, 34 Miyukigaoka, Tsukuba, Ibaraki 305-8501
論文概要
量子コンピュータは量子力学の性質を利用し，特定の問題に対して従来のコンピュータよりも超高速に計算することができると期待されている。量子コンピュータは，素因数分解等いくつかのアルゴリズムが超高速に計算ができると証明されているゲート方式と，組合せ最適化に特化したアニーリング方式に大別され，それらの心臓部に用いられるものが量子ビットである。いま研究開発されている量子ビットには超伝導体，イオン，光，固体中の電子・核スピンなどがあり，その中で NEC は超伝導現象に由来する強固な量子コヒーレンスと固体素子であるが故の集積性の良さに注目し，超伝導量子ビットに取り組んでいる。本論文では，NEC が開発する超伝導パラメトロンデバイスに関して詳しく解説する。
Keyword: 量子ビット，超伝導，超伝導パラメトロン，量子ゲート方式，量子アニーリング方式

1. 量子ビット
1-1 量子ビットと量子コンピュータ
量子コンピュータは，重ね合わせといった量子力
学の性質を利用することで，従来のコンピュータ（古典コンピュータ）と比べて，特定の問題に対しては圧倒的に高速に計算を行うことが期待されている。
図１に示すように，従来のコンピュータで使われる従来ビット（または古典ビット）は 0 または 1 で表され，それを N 個並べたものを考えると，その並べ方は 2N 個の可能な組み合わせの中の一組を表している。一方，量子コンピュータで使われる量子ビットに関しては，測定をするまでは 0 である状態と1 である状態が重ね合わされた状態をとることができる。そのため，量子ビットを N 個並べたものを考えると，それは 2N 個の組み合わせを同時に表現していることになる。このように，従来のコンピュータ
では同時に一つの状態しか考慮することしかできないのに対し，量子コンピュータでは同時に複数の状態を扱うことができるため，量子ビットの数が増えると指数関数的に扱える状態が増える。この性質が量子コンピュータで超高速演算できる理由の一つである。
量子コンピュータは，その計算方式の違いによって大まかにゲート方式とアニーリング方式に分けることができる。いずれの方式であっても計算の準備である量子ビットの初期化と，計算結果の読み出し
図 1)- 16 -

量子ビットのイメージである測定を行う。
ゲート方式ではまず量子ビットの初期化を行う。
例えば，図 2 では量子ビットの状態を表すブロッホ
球の上向き状態（“1”）の状態に設定する。その後，目的とする計算に相当する量子ゲート操作によって量子ビットの状態を変化させ，全ての量子ゲート操
作がすべて終了したら，量子ビットの状態を測定して，結果の読み出し（“1”または下向き状態“0”状態）をする。
一方，アニーリング方式では，例えば特定の方向の磁場（横磁場とよばれる）によって量子ビットの状態を初期化する。また，解きたい問題に対応する
量子ビット同士の相互作用の強さを設定しておく．
その後，磁場を徐々に弱めていくと求める解の状態に近づいていく。図の例では，磁場が弱めていくに従い，上向きの状態の方が下向きの状態よりも高い確率で観測される量子ビットと逆に下向きの方が高い確率で観測される量子ビットがあることを示している。最終的に横磁場がなくなった時の状態が答えである。
このようにゲート方式とアニーリング方式では計算方法が異なるものの，どちらも重ね合わせを実現する量子ビットを用いている。量子ビットを実現する物理系の候補は複数あり，以降では様々な量子ビットの方式を紹介し，特に NEC が開発している超伝
導パラメトロン素子について解説する。
図 2)ゲート方式とアニーリング方式の計算方法- 17 -

1-2 量子ビットの様々な方式
表１に研究開発が進められている量子ビットの様々な方式をまとめた。
まず、超伝導体から説明する。これは，超伝導体
アルミニウムのような超伝導体で酸化アルミニウムのような薄い絶縁体を挟んだジョセフソン接合を利用する量子ビットである(解説記事として[1])。超伝
導量子ビットを使った量子アニーリングマシンを
D-Wave が商用化しており、ゲート方式では Google
や IBM が開発競争をしている[2]。固体素子であるが故に集積化の点で有利であり、大規模化がなされている．量子性が保たれる時間であるコヒーレンス時
間は 100 マイクロ秒オーダの報告もある[3]。
ただし，超伝導量子ビットを動作させるためには絶対零度に近い 0.01K 程度にまで冷却しなければならないため，希釈冷凍機が必須で装置が大型であるというデメリットがある。
続いて，イオントラップでは、原子のイオンを 3次元空間上に浮遊させたものを量子ビットとして用いる。IonQ[4]のゲート型量子コンピュータは 160 量
子ビットを持ち，79 量子ビットの演算を行っている[5]。また，イッテルビウムイオン 13 個からなる量子コンピュータでは全結合の量子ビットとして計算できるのは 11 量子ビットである[6]。他にも 20 量子ビットの量子コンピュータが作られている[7]。原理的に環境との相互作用がないためコヒーレンス時間は長く，実際に 10 分という報告もある[8]。ただし，ゲート操作が超伝導ビットよりも数十倍程度遅いというデメリットもある。
光量子は例えば光の偏光を量子ビットとして用いる方式であり、室温で動作する（解説記事は[9;10]）。
ゲート方式で必須となる 2 つの量子ビットを操作する制御 NOT ゲートは実現が困難であったが，線形光学素子と単一光子源と光子検出器の組合せによる方法が提案された[11]。しかし，制御 NOT ゲートは確率的に動作するため，ゲートをつなげていくと計算が成功する確率が指数関数的に減少してしまうという問題があり，量子テレポーテーションを利用する方法も試みられている。
ダイヤモンド中の炭素原子の一つを窒素原子(N)に置き換え，それに伴いできた空孔(V)でできた NV中心とよばれる欠陥を利用し，その合成電子スピン状態を量子ビットとする。この方式も室温で動作する。量子ビットの操作はマイクロ波などを用い，エ表 1) 量子ビットの様々な方式のまとめ（ゲート方式）
原理

超伝導

イオントラップ

ジョセフソン接合

イオンのエネルギー 光子の偏光
準位

材料・装置 アルミニウム（超伝導体），酸化アルミ
ニウム（絶縁体）

光量子

NV中心

シリコン

合成電子スピン電子スピン・核スピ
ン・量子ドット

イッテルビウムイオ
ンなど

光子，光学装置

ダイヤモンド中の窒素と空孔の構造シリコン，シリコン中のリンなどの不純物
26(Intel)

ビット数

72(Google)

160(IonQ)

18（6光子の偏光などによる）

6（電子スピン1，核
スピン5）

コヒーレン
ス時間

100マイクロ秒

10分

0.15ミリ秒

1ミリ秒（電子スピン） 25秒
1秒（核スピン）

冷凍機

必要

不要

不要

不要

必要

特徴

ビット数が多いものが実現している。希
釈冷凍機が必要。

コヒーレンス時間が長いが，量子ゲート
操作に時間がかかる。

室温で動作し，そのまま情報通信に使える。確率的な量子ゲート操作がある。

コヒーレンス時間が長いが，NV中心を並べた多ビット化に課題あり。量子中継器など向け。

コヒーレンス時間が長く，シリコン技術が使えると期待され
ている。

主要
プレーヤ

IBM，Google，Intel， IonQ
Rigetti， D-Wave,
東大(中村研)、理研(蔡研)

Xanadu，
PsiQuantum，
東大（古澤研）

横国大（小坂研）

Intel，慶大(伊藤研)，
理研(樽茶研)ラー耐性のあるゲート操作も成功している[12]。現在，NV 中心を複数作成した量子ビットで実現したものは 3 量子ビットであるが[13]，NV 中心の電子ス
ピン 1 個と周囲にある炭素原子 5 個の核スピンを使った 6 量子ビットも作られた[14]。
シリコン量子ビットには，リンなどの不純物を加えそれによってできた局在した電子スピンの状態を量子ビットとするものや，シリコンをナノ加工し電子を 3 次元的に閉じ込めた量子ドットを量子ビットとする方式があり[15]，他にもシリコン基板に埋め込んだリンの核スピンを量子ビットとするもの[16]，純粋なシリコンの核スピンを量子ビットにするもの[17]もある。動作温度は不純物を使うものでは 10Kに到達した[18]。またコヒーレンス時間に関しても，シリコンの同位体の核スピンを使ったもので 25 秒が実現されている[19]。

図 3 は，NEC グループにより 1999 年に世界で最初動作実証された固体素子量子ビットの模式図である[24]。超伝導体中では，伝導電子が対（クーパー対）を作っており，クーパー対箱（Cooper-pair box）と呼ばれる電極内に余剰クーパー対が一つある時を”1”
状態，無い時を”0”状態として，これらの量子重ね合
わせ状態を実現した。このときのコヒーレンス時間
は 1 ns 程度であった。
その後，超伝導量子ビット技術はコヒーレンス時
間[22]やゲート操作忠実度といった性能指数において着実に進歩してきた[25]。その中で，量子ビットの読み出し技術もまた重要な要素技術であり，これま

2. NEC での取り組み
NEC では現在，量子アニーリングの研究開発を進めている。量子アニーリングの最初の理論提案を忠実に再現するためには[20]，高いコヒーレンスをもち集積性に優れた量子ビットが必要となるが，超伝導回路がその有力候補である。その理由は，超伝導現象に由来する強固な量子コヒーレンスと固体素子であるが故の集積性の良さを兼ね備えているからである[3;21;22;23]。

- 18 -

図 3）NEC が実現した世界初固体量子ビット模式図でに様々な方法で実現されてきた。近年では，分散読出しと呼ばれる方法が主流となっている。量子ビットと共振器を分散的に結合させた時に，量子ビットの状態に応じて共振器の共振周波数が変化することを利用する。特に研究初期のころは読出し信号の
信号対雑音比が低かったため，多数回試行による平均化が必要であった[26]。信号対雑音比が低いのは，量子ビットの寿命が短かったことが一因であるが，読出しの信号を増幅するための増幅器のノイズ（典型的にはノイズ温度が～5K 程度）も主要因であった。そこで NEC を含む幾つかのグループが，より低雑音のマイクロ波増幅器を超伝導回路で作ろうと考えた[27;28;29;30]。それがジョセフソンパラメトリッ
ク増幅器 (Josephson parametric amplifier: JPA) である。

び注目を集めることになった。
図 4(a) は，，2008 年に NEC が開発した磁束駆動型
JPA の等価回路を示している．デバイスは SQUID(superconducting quantum interference device:超伝導量子干渉計) で終端されたコプラナー導波路で構成さ
れ，SQUID が共振器の境界条件を決定する。共振周
波数の二倍の周波数をポンプポートに印加すると，その周波数で共振周波数が変調を受ける。この変調が共振器に入射した信号にパラメトリックな作用を与え，増幅された信号が反射される。図 4(b) , (c) は，
この動作をブランコの振幅増幅に例えて説明したものである。人の重心がブランコの周期の 2 倍周期で動くことで変調を与え，ブランコの振幅が時間とともに大きくなる。

3. ジョセフソンパラメトリック増幅器と発振器

3-2 ジョセフソンパラメトリック発振器

3-1 ジョセフソンパラメトリック増幅器
実は JPA は 1960 年代から知られている[31]。応用
先があまりなかったこともあり，JPA は広く使われることはなかったものの，2000 年代に入り，超伝導
量子コンピュータという研究分野の発展と共に，再図４) ジョセフソンパラメトリック増幅器の説明 (a) 等価回路, (b) ブランコを使った動作
説明 (c) 振幅の時間発展
(a)

(b)

一般に JPA の信号増幅率はポンプのパワーと共に増大するが，ポンプパワーには共振器内光子の寿命で決まるある閾値が存在する[32]。その閾値を越えると JPA は発振を起こし，ポンプ周波数の半分の信号を発生する[33]。これをジョセフソンパラメトリ
ック発振器(Josephson parametric oscillator: JPO) と呼ぶ。
JPO の発振出力は，等しい振幅で位相がπずれた二つの状態のうちどちらかを取る。二つの状態は，入力信号がなければ完全にランダムに発生するが，入力信号があると，その振幅や位相によって発生確率を制御することが出来る。これを説明したのが図6 である。これは 1950 年代に日本で発明されデジタ
ル計算機素子として用いられたパラメトロンの動作原理であり[34]，NEC が 2014 年に動作実証したもの
は[35]，これの超伝導回路版と言える。

3-3 ジョセフソンパラメトリック発振器の応用
JPO の応用先として，まず高感度の位相検波器が挙げられる。これは，発振状態（0π/1π）の出現確率
が入力信号の位相に依存することを利用するもの
で，NEC は量子ビットの分散読出しや，マイクロ波
単一光子検出にこの技術を応用した[35;36]。また最近では JPO のネットワークを量子アニーリングマシ
ンとして用いるという提案がなされている[37;38;39]。そこでは JPO の 2 つの発振状態が量子ビ(c)- 19 -

図５）ジョセフソンパラメトリック発振器（JPO）の動作原理

ットとして用いられており，その点ではパラメトロン計算機と似ているが，アナログ（ナチュラル）計算機であるという点で本質的に異なっている。各
JPO を真空状態に初期化し，断熱的にポンプを印加して発振させた時，JPO の0π/1πの発振状態が，JPO間の相互作用に対応したイジングハミルトニアンの基底状態を表している。このような原理に基づき，スケーラブルに JPO 間の全結合を実現する方法も提案されている[40]。NEC では現在，この方式に基づいた量子アニーリングマシンの開発を進めている。
ここで，量子アニーリングの計算性能を決める重要な性能指標の１つがコヒーレンス時間の長さである。NEC は超伝導パラメトロン技術を活用してコヒーレンス時間の低下を防ぎ，結果として実用化で先行する D-wave 社を上回る高性能な量子アニーリン
グマシンを提供できると考えている。

4. まとめ
本論文では，量子コンピュータの心臓部となる量
子ビットの様々な方式を紹介し，特に NEC が開発する量子アニーリングにおいて量子ビットとして用いる，超伝導パラメトロンデバイスについて詳しく紹介した。心臓部である量子ビットだけでなく，希釈冷凍機の外にある制御装置と 10mK に冷却された多数の量子ビットを接続するための，実装・配線技術も同様に重要である。この部分を含め，2018
年に採択された NEDO の研究開発事業において[41]，産総研らとともに取り組んでいる。

5. 参考文献[1] 阿部英介, 伊藤公平, “固体量子情報デバイスの現状と将来展望”, 応用物理 86, 453 (2017).
[2] ”Quantum Computing Report”,
https://quantumcomputingreport.com/scorecards/qubitcount/[3] M. J. Gambetta et al., “Building logical qubits in asuperconducting quantum computing system”, npj
Quantum Information 3, 2 (2017).
[4] IonQ, Inc., https://ionq.com/[5] IonQ, Inc., “IonQ harnesses single-atom qubits to build
the world’s most powerful quantum computer”, 2018,https://ionq.com/news/december-11-2018[6] K. Wright et al., “Benchmarking an 11-qubit quantum
computer”, Nature Commun. 10, 5456 (2019).
[7] N. Friis et al., “Observation of Entangled States of a
Fully Controlled 20-Qubit System”, Phys. Rev. X 8,021012 (2018).
[8] Y. Wang et al., “Single-qubit quantum memory
exceeding ten-minute coherence time”, Nature Photon.
11, 646 (2017).
[9] 竹内繁樹, “線形光学素子を用いた量子コンピュータ” 応用物理学会分科会日本光学会, 光学 33, 284(2004).
[10] P. Kok et al., “Linear optical quantum computing withphotonic qubits”, Rev. Mod. Phys. 79, 135 (2007).
[11] E. Knill et al., “A scheme for efficient quantum
computation with linear optics”, Nature 409, 46 (2001).
[12] K. Nagata, et al., “Universal holonomic quantum
gates over geometric spin qubits with polarised- 20 -

microwaves”, Nature Commun. 9, 3227 (2018).
[13] M. Haruyama et al., “Triple nitrogen-vacancy centre
fabrication by C5N4Hn ion implantation”, Nature
Commun. 10, 2664 (2019).
[14] A. Reiserer, et al., “Robust Quantum-Network
Memory Using Decoherence-Protected Subspaces of
Nuclear Spins”, Phys. Rev. X 6, 021040 (2016).
[15] F. A. Zwanenburg et al., “Silicon quantum
electronics”, Rev. Mod. Phys. 85, 961 (2013).
[16] E. B. Kane, “A silicon-based nuclear spin quantum
computer”, Nature 393, 133 (1998).
[17] T. D. Ladd et al., “All-Silicon Quantum Computer”,
Phys. Rev. Lett. 89, 017901 (2002).
[18] K. Ono, et al., “High-temperature operation of asilicon qubit”, Sci. Rep. 9, 469 (2019).
[19] T. D. Ladd et al., “Coherence time of decouplednuclear spins in silicon”, Phys. Rev. B 71, 014401(2005).
[20] T. Kadowaki and H. Nishimori, “Quantum annealing
in the transverse Ising model”, Phys. Rev. E 58, 5355
(1998).
[21] G. Wendin, “Quantum information processing withsuperconducting circuits: a review”, Rep. Prog. Phys.
80, 106001 (2017).
[22] W. D. Oliver, and P. B. Welander, “Materials insuperconducting quantum bits”, MRS Bulletin 38, 816(2013).
[23] M. H. Devoret and R. J. Schoelkopf,“Superconducting Circuits for Quantum Information:
An Outlook”, Science 339, 1169 (2013).
[24] Y. Nakamura et. al., “Coherent control ofmacroscopic quantum states in a single-Cooper-pairbox”, Nature 398, 786 (1999).
[25] R. Barends et al., “Superconducting quantum circuits
at the surface code threshold for fault tolerance”,
Nature 508, 500 (2014).
[26] A. Wallraff et al., “Strong coupling of a single photon
to a superconducting qubit using circuit quantum
electrodynamics”, Nature 431, 162 (2004).
[27] E. A. Tholén et al., “Nonlinearities and parametricamplification in superconducting coplanar waveguideresonators”, Appl. Phys. Lett. 90, 253509 (2007).
[28] M. A. Castellanos-Beltran and K. W. Lehnert,“Widely tunable parametric amplifier based on asuperconducting quantum interference device arrayresonator”, Appl. Phys. Lett. 91, 083509 (2007).

- 21 -[29] T. Yamamoto et al., “Flux-driven Josephsonparametric amplifier”, Appl. Phys. Lett. 93, 042510(2008).
[30] N. Bergeal et al., “Analog information processing at
the quantum limit with a Josephson ring modulator”,
Nature Phys. 6, 296 (2010).
[31] H.
Zimmer, “Parametric Amplification of
Microwaves in Superconducting Josephson Tunnel
Junctions”, Appl. Phys. Lett. 10, 193 (1967).
[32] T. Yamamoto et. al, in Principles and Methods of Quantum
Information technologies, Eds. Y. Yamamoto and K. Semba(Spinger, Tokyo, 2016) p.495.

[33] C. M. Wilson et al., “Photon Generation in an
Electromagnetic Cavity with a Time-Dependent
Boundary”, Phys. Rev. Lett. 105, 233907 (2010).
[34] E. Goto, Proc. Inst. Radio Engrs. 47, 1304 (1959).
[35] R. Z. Lin et al., “Josephson parametric phase-locked
oscillator and its application to dispersive readout of
superconducting qubits”, Nature Commun. 5, 4480
(2014).
[36] K. Inomata, et al., “Single microwave-photon
detector using an artificial Λ-type three-level system”,
Nature Commun. 7, 12303 (2016).
[37] H. Goto, “Bifurcation-based adiabatic quantum
computation with a nonlinear oscillator network”, Sci.
Rep. 6, 21686 (2016).
[38] S. E. Nigg et. al., “Robust quantum optimizer withfull connectivity”, Sci. Adv. 3, e1602273 (2017).
[39] S. Puri et al., “Quantum annealing with all-to-all
connected nonlinear oscillators”, Nature Commun. 8,15785 (2017).
[40] R. Movshovich et al., “Observation of zero-point
noise squeezing via a Josephson-parametric amplifier”,
Phys. Rev. Lett. 65, 1419 (1990).
[41] 日本電気株式会社, “高効率・高速処理を可能とする量子アニーリングマシンの研究開発に採択”,
2018,
https://jpn.nec.com/press/201810/20181009_04.html

<MCPC 量子コンピュータ推進 WG 2019>

大規模な組合せ最適化問題に向けたスケーラブルな CMOS アニーリングプロセッサ
林 真人*1

竹本 享史*2

吉村 地尋*1

山岡 雅直*1

日立製作所 〒185-8601 東京都国分寺市東恋ヶ窪 1-280*1
日立製作所 〒001-0021 北海道札幌市北区北２１条西１１丁目*2

A Scalable CMOS Annealing Processor for Solving Large-scale
Combinatorial Optimization Problems
Masato Hayashi*1
Hitachi, Ltd.

Takashi Takemoto*2

Chihiro Yoshimura*1

Masanao Yamaoka*1

1-280, Higashi-koigakubo, Kokubunji-shi, Tokyo, 185-8601 Japan *1

Hitachi, Ltd. Nishi-11, Kita-21jyo, Sapporo-shi, Hokkaido, 001-0021 Japan *2
本稿ではイジングモデルの基底状態探索を高速に実行する CMOS アニーリングプロセッサについて述べる。
CMOS アニーリングプロセッサの特長はチップ間接続を通してより大型のチップを構成できる点にある。また，既存の計算機システムと接続可能な名刺サイズの計算ノードをも開発した。この計算ノードは 2 チップを搭載し，61,952 スピンの問題を一度に処理できる。NP 困難な組合せ最適化問題である最小頂点カバー問題
を用いた性能評価により，CPU に対して最大 55 倍の性能向上を得た。さらに，アプリケーション開発の推進に向けて CMOS アニーリングプロセッサを多くのユーザが簡易に利用可能なクラウド環境を整備した。
Keyword: 組合せ最適化，アニーリング，アクセラレータ，イジングモデル

1. 背景
アニーリングプロセッサと呼ばれる新たな計算機
アーキテクチャの実装が利用できるようになりつつある[1][2][3]。これらのプロセッサは NP 困難な組合
せ最適化問題であるイジングモデルの基底状態探索を高速に実行する。種々の組合せ最適化問題をイジ
ングモデルの基底状態探索に帰着すれば，これらのプロセッサを用いて高速に解くことが可能である。
こうした中で，我々は半導体回路を用いた CMOS ア
ニーリングプロセッサ(以下 CMOS-AP)を開発している。これはスケーラビリティと既存システムとの接続性に優れている。
CMOS-AP を用いる際の計算フローを図 1 に示す。
まず，前処理として解くべき組合せ最適化問題をCMOS-AP で処理できる形式であるイジングモデルに変換する。続いて，得られたイジングモデルを
CMOS-AP に転送して，基底状態探索処理を実行する。この結果得られたスピン値をホストから読出し，
元の問題の解として解釈する。
イジングモデルは図 2 に示すように，±1 の 2 値をとるスピンと呼ばれる変数(図中のσ)が隣接するスピンと相互作用する数理モデルであり，図 2 の J- 22 -

Formulation of Ising model
𝐻𝐻 𝝈𝝈 = − �
h1

J14

h4
h7

J47

σ7

h8
J78

𝑁𝑁

𝑖𝑖𝑖𝑖,𝑗𝑗𝑗𝑗=1,𝑖𝑖𝑖𝑖<𝑗𝑗𝑗𝑗

h5
J45

σ4 J
58

σ8

𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖 𝐽𝐽𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝜎𝜎𝜎𝜎𝑗𝑗𝑗𝑗 − �
h
J12 2

σ1 J
25
h9
J89

σ5

h
J56 6
J69

𝑁𝑁

ℎ𝑖𝑖𝑖𝑖 𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖

𝑖𝑖𝑖𝑖=1

h
J23 3

σ2 J
36

Data IO 88 bits(= 8 × 11 bits)

RandomPulses(28 bits)

BufferDummy spin (176 spins)

Data IO 88 bits(= 8 × 11 bits)

Spin array(44 × 176 spins)

図 1. CMOS-AP を用いる計算フロー

16
spins
BUF
16
spins
BUF

Spin array(44 × 176 spins)

基底状態探索(アニーリング)

16
spins
BUF

Word driver &control-signal driver

CMOS
アニーリング
プロセッサ

スピン値

Macro
control

イジングモデル

Ising core: 30k (= 176 × 176) spins

解Spin array(44 × 176 spins)

結果の解釈

Bufferマッピング

Spin array(44 × 176 spins)

組合せ
最適化
問題

176 (=11 × 16) spins

ホスト
(CPU)

28 bits
Random pulse generator

σ3

図 3. CMOS-AP のコア部分のブロック図

σ6Annealing process

σ9Update to lower energy
Thermal fluctuation

図 2. イジングモデルの模式図

EnergyLocal
minimum
Local
minimumLow- 23 -

High

はスピン間の相互作用の強さを表す相互作用係数であり，h は各スピンにかかる磁場の強さを表す外部磁場係数である。イジングモデルは統計物理の分野
で磁性体の性質を記述するために用いられていた[4]。イジングモデルに対して，エネルギーと呼ばれる量が定義されており，図 2 中の数式で算出される。
イジングモデルのエネルギーが最も低くなるスピン値の組合せは基底状態と呼ばれており，これを求めることは NP 困難な最適化問題として知られている。
また，イジングモデルは QUBO(Quadratic Unconstraint
Binary Optimization) も し く は UBQP(Unconstrained
Binary Quadratic Programming)と呼ばれる種類の組合
せ最適化問題と等価であることが知られている。すなわち，イジングモデルの基底状態を求めることで，QUBO 形式の組合せ最適化問題を解くことが可能である。その他 の組合 せ最適化問 題に関し ても，
QUBO/イジングモデルの形式にマッピングできる
例が知られており[5]，イジングモデルの基底状態を高速に求める専用ハードウェアにより種々の組合せ
最適化問題を高速に解くことが可能となる。
本稿では，イジングモデルの基底状態探索を高速に実行する専用ハードウェアである CMOS-AP の概
要および，これを搭載する名刺サイズの計算ノードについて述べる。また，開発した計算ノードを多くのユーザから容易に利用できるようにするためのク
ラウド環境について述べる。

Ground stateSpin configuration (2n pattern)

図 4. スピンの値とエネルギー
2. CMOS アニーリングプロセッサ
CMOS-AP は SRAM メモリセルと演算回路が密接に結びついたインメモリアプローチに基づいて設計されている[3]。図 3 に CMOS-AP の演算を行うコア
部分のブロック図を示す。プロセッサはスピンユニットと呼ぶ基本素子を多数並べた構造となっており，
これはスピンの値と，近隣のスピンとの間の相互作
用係数を記憶するメモリセルと，スピンの次状態を計算する演算回路からなる。さらに，スピンユニッ
トを多数集積したブロックであるスピンアレイを 4つ配置している。スピンユニットに含まれるメモリ
セルは通常の SRAM と同様に，ワード線とビット線を介して読み書きすることができる。ワード線とビット線はスピンアレイに隣接するワード線ドライバとデータ I/O ブロックにより駆動される。一方，ス
ピンユニットには後述するとおり，演算中にランダ

3

0
2

176 spins+ 1 DSPIN
2

3

2

3

1

0

1

0

1

3

2

3

2

3

0

1

0

1

0

1

2

3

2

3

2

3

0

1

0

1

0

1

Dummy spin
(DSPIN)

22
bits

LVDS
I/F
×22

100
Mb/s

LVDS
I/F
×22

TX S/P(176 to 22)

CMOS-AP chip B

SP0[87:0]
SP2[87:0]

RX P/S(22 to 176)

22
bits

×22

100
Mb/s

4.3 mm
LVDS I/F

RX
P/S

TX_CLK

176 spins

2

SP1[87:0]
SP3[87:0]

×22
TX
S/P

Process

40nm

Spin

30,976 (176x176)

2

3

クロック周波数

100MHz

0

1

電源

1.1V

2

3

0

1

2

3

0

1

5.5 mmIsing core

LVDS I/F

CMOS-AP chip A

RX_CLK

図 5. チップ間通信部のブロック図

Compute node of CMOS annealing processor (91 × 55 mm2)
Host
PC

USB 3.0
5 Gb/sControl FPGA

USB 3.0
controller

ムなパルス列を入力する必要がある。このランダム
パルス列は CMOS-AP 全体で共有される 1 セットのランダムパルス発生器で生成されており，演算器のクロックとは非同期に全スピンユニットに分配される。さらに，CMOS-AP 間の接続時に，対向するプロ
セッサ上のスピン値を記憶しておくダミースピンと呼ばれるフリップフロップ群を備えている。プロセッサ間通信の動作については後述する。
まず，CMOS-AP におけるスピンの更新方式について説明する。図 4 に示すように，イジングモデル
はスピン値の組合せに応じて，様々なエネルギー値をとる。こうした中で効率よくエネルギーの低い状態を探索するため，CMOS-AP はシミュレーテッド
アニーリング(以下，SA)法[6]をもとに，半導体回路での実装に適したビット演算を用いて近似した方法を実装している[7]。スピンの値を更新する際，当該のスピンとその隣接スピンの値で決まる局所的なエネルギーを最小化する方向には確実に遷移し，そうでない場合でも温度と呼ばれるパラメータに応じて確率的に遷移することで，局所解に陥ることを避けつつエネルギーの低いスピン値を求める。温度が高い状態では，局所的なエネルギーが上昇するスピン値への遷移を受け入れやすく，温度が下がるほどそうした遷移を受け入れにくくなる。温度はアニーリ
ングの開始直後には高い値に設定し，徐々に低い値となるように制御する。これにより，演算開始直後
は解空間の広い範囲を探索できるようにし，徐々にエネルギーの低いスピン値へと向かいやすくなる。
ここで，温度はランダムパルス発生器の出力によって制御されており，ランダムパルス列に含まれる’1’の割合が高いほど高温の状態となり，’0’の割合が高
いと低温の状態となる。
続いて，CMOS-AP 間接続機能について述べる。
CMOS-AP では，スピンを模擬する演算器であるス
ピンユニットが多数並列に動作することで基底状態探索を高速に行うことができる。このため，より多図 6. CMOS-AP のダイ写真

USB I/F

Systemclock
100 MHz

QSPI
I/F

CMOS-AP
chip A

Clock
controlDatamemoryPhase
adjustment

QSPI (4 bits × 100 Mbps)

RandomPulse
controlTemperature
memoryLVDS
signals
100 Mb/s

CMOS-AP
chip B

91 mm
CMOS-AP
chip A

55 mm

USB 3.0(Control signal andpower are supplied)

Control
FPGA

CMOS-AP
chip B

図 7. 計算ノードのブロック図
くのスピンユニットを並列に動作させることで更なる性能向上を見込める。これを実現する有効な手段
として，チップ面積を大きくすることで 1 チップに搭載できる演算器の数を増やすというものがある。
しかし，チップ面積を大きくしすぎると歩留りが低下し，製造コストが上昇することや，用途に応じて異なるサイズのチップを用意すると手間が大きいといった問題がある。このため，製造しやすいサイズのチップを用意し，複数のチップを接続して大規模なプロセッサを構成することが有用である。そこで，
CMOS-AP は図 5 に示すようにチップ間接続インタ
ーフェースを備えている。CMOS-AP 上では図 5 左側に示すように，各スピンが上下左右および斜め方
向の 8 つのスピンと隣接する King’s Graph と呼ばれる形状で接続されている。このため，2 つのプロセッサを接続する際に，チップ端に位置するスピンの値を送受信すればよい。ここで，スピン値の更新とプロセッサ間のデータ転送をオーバーラップさせる
ことで，転送レイテンシの影響を最小限に抑える工夫を行っている。スピンは互いに隣接していない 4
つのグループに分かれており，図 5 左側に示したイ- 24 -

ジングモデルのスピンの色がこのグループを示している。1 サイクルで同時に更新できるのは 1 つのグ
ループに属するスピンに限られる。これは，隣接するスピン同士を同時に更新してしまうと，互いに隣接スピンの古い値をもとに次の状態を決定するため，
正しい演算結果にならないためである。このため，
4 サイクルかけて全てのスピンを 1 回ずつ更新する動作となっている。これを利用して，あるグループのスピンの値が更新された直後に，隣接チップ上のバッファに転送する。同じグループのスピンが次に更新されるまで 4 サイクルかかるため，この間にデータ転送を行うことで転送に要するレイテンシを隠すことができる。チップ端にあるスピン値は最終的に 100Mbit/ 秒 で 動 作 す る LVDS(Low Voltage
Differential Signaling)を通して対向チップに伝送される。LVDS は 22 レーンあり，チップ境界部に位置す
るスピンの値は 176 スピン分で 176bit となるため，
送信側/受信側のそれぞれでシリアル/パラレル変換を行い，順次伝送を行う。対向チップから受け取ったスピン値はダミースピンと呼ばれる専用のフリップフロップに格納される。チップ端に位置するスピ
ンは，ダミースピンの値を隣接スピンの値とみなして計算を行う。
図 6 に CMOS-AP のダイ写真を示す。40nm のCMOS プロセスを用いて製造しており，4.3mm×5.5mm のチップ上に 176x176=30,976 スピンを集積している。
3. 計算ノード
2 章で述べた CMOS-AP を既存の計算機と接続して利用するためのインターフェースとして図 7 に示
す計算ノードを開発した。この計算ノードは 2 チップの CMOS-AP と，これを制御する FPGA を搭載している。計算ノードはホストとの接続用に USB3.0 イ
ンターフェースを備えている。ホストは FPGA 上のメモリに相互作用係数値を格納したり，結果のスピ
ン値を読み出すことで所望の演算を行う。FPGA は自身のメモリに格納されたデータを CMOS-AP のイ
ンターフェースである QSPI インターフェースのコ
マンドに変換して入出力を行う。さらに，FPGA は
CMOS-AP 上のランダムパルス発生器に入力する温度情報をチップ上の専用ピンに対して出力する。温度の値はメモリに格納した値を使うため，シミュレ
ーテッドアニーリングでしばしば用いられる幾何冷却等に限らず，任意の温度の系列を用いることができる。

- 25 -

この計算ノードは USB3.0 のバスパワー(5V/最大
900mA)で動作しており，それ以外の外部電源を必要としない。ホストから見ると，CMOS-AP の境目を意
識せず使用できるようになっており，352×176 スピンからなる合計 61,952 スピンのイジングモデルの基底状態探索を一度に実行できる。計算ノードの基板
は名刺サイズ(91×55mm)となっており，コンパクト
かつ省電力な実装となっていることで，データセン
タから組み込みシステムに至るまで広範なシステムと接続して利用することが可能である。
4. 性能評価
NP 困難な組合せ最適化問題である最小頂点カバーを用いて CMOS-AP 及び計算ノードの性能評価を行った。最小頂点カバー問題は入力されたグラフに対して，全ての辺の少なくとも一方の頂点が含まれるような頂点の部分集合のうち，頂点数が最小のものを求める問題である。この問題はイジングモデルの基底状態探索にマッピングできることが知られている[5]。マッピングの基本的な考え方を以下に示す。
まずグラフの各頂点が頂点カバーに含まれるかどうかをスピンの値に対応させる。これをもとに構成したエネルギー関数を下式に示す。

H(σ) = � 𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖 + 2 � (1 − 𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖 )(1 − 𝜎𝜎𝜎𝜎𝑗𝑗𝑗𝑗 )𝑖𝑖𝑖𝑖(𝑖𝑖𝑖𝑖,𝑗𝑗𝑗𝑗)∈𝐸𝐸𝐸𝐸

エネルギー関数の第一項は頂点カバーに含まれる頂点が多いほど大きな値をとるため，エネルギーを最小化することで，頂点カバーのサイズを小さくす
る働きをする。一方，第 2 項は頂点カバーとして正しい出力を得るための制約条件に対応する。グラフ
中の一本の辺について着目すると，第 2 項の値は，辺の両端の頂点がカバーに含まれない場合のみ正の値をとり，それ以外の場合は 0 となる。つまり，頂点カバーとして正しくないときのみエネルギー値が大きくなるため，エネルギーを最小化することで，有効な頂点カバーが得られることになる。
性能評価にあたって入力するグラフは CMOS-AP
上で直接取り扱えるようにするため，King’s グラフの部分グラフをランダムに生成したものを用いた。
計算時間と計算精度は最小頂点カバー問題向けのヒューリスティックアルゴリズムである List Right ア
ルゴリズム[8]を比較対象とした。List Right アルゴリ
ズムは CPU 上で実行した。アニーリングの所要時間
はスピンの更新回数により異なり，スピンの更新回数は必要な解精度によって決まる。ここでは，List

12

1.16
1.14

10
計算時間 (msec)

近似比

1.12
1.10
1.08
1.06
1.04
1.02
1.00

0

10,00020,00030,00040,00050,000

List Right

6
4
2
0

60,000

問題サイズ(頂点数)
CMOS-AP8020,00040,00060,000問題のサイズ (頂点数)Optimal

CMOS-AP

図 8. 計算速度の比較結果

List Right

図 9. 解精度の比較結果

Right と同様の演算精度を得るために必要なスピンの更新回数を予備実験により求めた。また，List Right
アルゴリズムの実行環境として，Intel® Core i7®
6700K マシンを用いた。CMOS-AP の計算時間はア
ニーリングの開始から終了までとし，I/O を含まない。
計算時間の比較結果を図 8 に示す。List Right アル
ゴリズムの計算時間オーダーは問題サイズに対して線形であり，実測結果とよく一致している。CMOS
アニーリングアルゴリズムの所要時間は問題サイズによらずほぼ一定である。これは，List Right と同等の精度を得るために必要なスピンの更新が問題サイズによらず同じであったことによる。今回開発した計算ノードで一度に計算できる最大のサイズである
61,952 頂点の問題では，CPU 上の List Right アルゴ
リズム対して最大で 55 倍の速度向上を得られた。
また，図 9 に計算精度の比較結果を示す。各サイズの問題に対して，最適解に対する CMOS-AP および
List Right で得られた頂点カバーのサイズの比率を近似比としてプロットしており，近似比が 1 に近いほど精度が高いことを意味する。なお，最適解は予め数理最適化ソルバを用いて算出した。List Right アル
ゴリズムはいずれの問題サイズに対してもおおむね一定の解精度を得られている。CMOS-AP は事前に
ListRight と同等以上の精度を得られるスピンの更新回数を定めているため，3-7%高い精度を得られているが，それぞれの問題に対して得られた解精度のばらつきが大きい。これは，CMOS-AP の計算結果が乱数のシード値に応じてばらつくことに起因している。
現状の計算ノードでは，I/O に要する時間がボトルネックとなっている。ホストからイジングモデルの相互作用係数を書き込むための所要時間は 22.6msec で計算結果であるスピン値を読みだすための所要時間
は 1.5msec であった。この点に関しては今後，USB

インターフェースの使用効率の向上により高速化をはかる必要がある。
5. クラウド環境
CMOS-AP のユースケースの例としてクラウド環
境について述べる。CMOS-AP は新しい計算機であり，ソフトウェアスタックを新たに整備していく必要がある。とくに，種々の有用な最適化問題をイジ
ングモデルにマッピングする方法を拡充していく必要がある。アニーリングマシンのユーザの裾野を広げ，このような活動に多くの人が容易に参加できるようにするため，計算ノードをインターネット経由で操作できるクラウドインターフェースを公開している[9]。
この環境では，イジングモデルを記述する相互作
用係数および外部磁場係数の値を JSON 形式で表現
し，アニーリングの計算時間と精度を決めるパラメータとともに Web API 経由で投稿することで基底状
態探索の結果を得ることができる。これにより，ユーザはハードウェアを制御する際に必要となるメモ
リマップや制御レジスタの使用方法といった低水準の情報を意識せず CMOS-AP を利用できる。また，
API 自体は特定のハードウェアの仕様に依存していないため，将来的なハードウェアの拡張に対してもソフトウェアの再利用性が高まるメリットがある。
6. まとめ本稿ではイジングモデルの基底状態探索を通じて組合せ最適化問題を高速に解くことを目指す専用目
的の計算機 である CMOS-AP に ついて述 べた。
CMOS-AP はシミュレーテッドアニーリング法を半導体回路で実装しており，2 つの CMOS-AP を接続- 26 -

することでスケーラブルに大規模化を図ることが可能である。さらに，CMOS-AP を搭載し，USB3.0 経
由で既存の計算機と接続可能な計算ノードを開発し，幅広い環境から使用できるようにした。NP 困難な組合せ最適化問題の一つである最小頂点カバー問題を用いた性能評価では，CPU 上のヒューリスティック
アルゴリズムに対して最大 55 倍の計算速度向上を得た。一方，現状では I/O 時間がネックとなっており，今後の改良が必要である。
開発した計算ノードのユースケースとして，クラウド環境の提供を行っており，これを活用してより多くの実用的な組合せ最適化問題を CMOS-AP で高速に解いていく点が今後の課題である。
謝辞
本成果の一部は，国立研究開発法人新エネルギー・
産業技術総合開発機構(NEDO)の委託業務の結果得られたものです。

[1]
[2]

[3]

[4]
[5]

[6]

[7]

参考文献
M. Johnson, et.al., “Quantum annealing with
manufactured spins”, Nature 473, 194-198, 2011
Inagaki, Takahiro, et al. "A coherent Ising machinefor 2000-node optimization problems." Science354.6312 (2016): 603-606.
T. Takemoto, M. Hayashi, C. Yoshimura and M.
Yamaoka, "2.6 A 2 ×30k-Spin Multichip Scalable
Annealing Processor Based on a Processing-InMemory Approach for Solving Large-Scale
Combinatorial Optimization Problems," 2019 IEEE
International Solid- State Circuits Conference (ISSCC), San Francisco, CA, USA, 2019, pp. 52-54
Brush, S. G. History of the Lenz-Ising model. Rev.
Mod. Phys. 39, 883–893 (1967).
Lucas, Andrew. "Ising formulations of many NP
problems." Frontiers in Physics 2 (2014): 5. Lucas,
Andrew. "Ising formulations of many NP problems."
Frontiers in Physics 2 (2014): 5.
Kirkpatrick, Scott, C. Daniel Gelatt, and Mario P.
Vecchi. "Optimization by simulated annealing."
science 220.4598 (1983): 671-680.
T. Okuyama, C. Yoshimura, M. Hayashi and M.
Yamaoka, "Computing architecture to perform
approximated simulated annealing for Ising models,"2016 IEEE International Conference on Rebooting
Computing (ICRC), San Diego, CA, 2016, pp. 1-8.

- 27 -[8] Delbot, François, and Christian Laforest. "A better
list heuristic for vertex cover." (2008).
[9] Annealing Cloud Web, https://annealing-cloud.com/

<MCPC 量子コンピュータ推進 WG 2019>

組合せ最適化問題を高速に解くデジタルアニーラの活用技術
川合 遼 ・ 左尾 将隆 ・ 渡邉 裕之 ・ 武捨 悠一 ・宇都宮 啓宏 ・ 橋本 伸一
富士通株式会社

How combinatorial optimization problems can be efficiently
solved with Digital Annealer
Ryo Kawai, Masataka Sao, Hiroyuki Watanabe, Yuichi Musha, Akihiro Utsunomiya, Shinichi Hashimoto
Fujitsu Limited

論文概要
現在、私たちの社会には配送計画や人員計画、投資ポートフォリオの最適化など、膨大な組合せの中から最適なものを選択する「組合せ最適化問題」が数多く存在します。問題によっては汎用コンピュータでは現実的な時間内で解けないものもあり、このような組合せ最適化問題を高速に解く手段の一つとして、量子コンピュータが期待されています。しかし、現在の量子コンピュータは、安定動作や対応可能な問題の規模に課題があります。そこで、富士通は量子現象に着想を得た新しいアーキテクチャーであるデジタ
ルアニーラを開発し、2018 年より提供を開始しています。本稿では、デジタルアニーラの活用技術について解説します。

とが容易ではなく、ノイズに弱いため安定した動作が難しいこと。もう一つは、量子ビットの数や量子ビット間の結合数が少ないため、適用できる問題の規模がコンピュータは 20 世紀半ばに登場し、急速な進化
小さいことです。[2]を遂げてきたことで私たちの暮らしを豊かにしてきま
一方で、日々増え続ける大量のデータ処理や複雑化した。現在の汎用コンピュータは演算速度をより速くする様々な課題を効率良く処理することは、直近のビするため、「ムーアの法則（半導体の集積密度は 18 か
月で 2 倍になる）」どおりに微細化されてきましたが、 ジネスに必要不可欠であるため、量子コンピュータの
最近ではそれも限界に近づいてきたと言われています。 実用化まで待つことはできません。
そこで、富士通は量子コンピュータと汎用コンピュ[1]そのため、このままでは増え続ける大量のデータ処ータの双方の良さを取り入れた新しいアーキテクチャ
理や複雑化する様々な課題の解決に対して処理能力がーである、デジタルアニーラを開発しました。デジタ
追いつかなくなる可能性があり、単純な演算速度向上
ルアニーラは、アニーリング方式を従来のデジタル回とは異なるアプローチの、全く新しいコンピュータの路で実現したもので、組合せ最適化問題を高速に解く概念が求められています。その有力候補として注目さことに特化しています。[3]れているものの一つが量子コンピュータであり、世界
デジタルアニーラは、上述した量子コンピュータの中で実用化へ向けた取り組みが急速に進んできていま
二つの課題を解決します。一つ目の課題に対しては、す。
デジタル回路で実現しているため、常温で安定した動量子コンピュータ技術には量子ゲート方式とイジ作が保証できます。二つ目の課題に対しては、大規模
ングマシン方式があります。量子ゲート方式の量子コなビット数を全結合したアーキテクチャーであるため、ンピュータはまだ研究段階であり、その実用化には数
現実社会の問題に適用できる仕組みになっています。
十年かかると言われています。また、イジングマシン
本稿では、デジタルアニーラ活用について事例を交方式の一つであるアニーリング方式は商用化されていえて解説します。
るものもありますが、主に二つの課題があると考えられています。一つは、量子ビットの状態を維持するこ
１ はじめに- 28 -

２ デジタルアニーラサービスのアーキテクチャー
デジタルアニーラサービス[4]は、株式会社富士通研究所が開発したハードウェアと 1QB Information
Technologies Inc.（以下、1QBit 社）[5]が開発した
ソフトウェアを組み合わせることによって、組合せ最適化問題に対するソリューションを提供します。[6]富士通研究所が開発したハードウェア[7]は、評価関数の二次制約なし二値最適化（QUBO：Quadratic
Unconstrained Binary Optimization）を解くことに特化しており、最適解を高速に導くために、計算時間を高速化する一括探索手法と、局所解からの脱出確率を高める探索手法を採用しています。これらの手法を使用することで、シミュレーテッドアニーリング[8]などに代表される従来の手法と比べて、最適解を得る確率を高めています。[3]1QBit 社は、定式化した数式を QUBO 形式に変換した
り、イジングマシンに適した形式に変換したりできる
ライブラリを Web API（Application Programming
Interface）として提供しています。
３ イジングモデルと QUBO
イジングモデルとは、強磁性体の相転移を扱うために簡単化されたモデルです。[8]イジングモデルは、+1 と-1 の 2 値を取るスピンσi間の相互作用によりエネルギーが決まり、スピン全体σ=(σ1,σ2,…)の評価関数 E(σ)は以下の式で表されます。
1

𝐸𝐸𝐸𝐸(𝜎𝜎𝜎𝜎) = − ∑𝑖𝑖𝑖𝑖 ∑𝑖𝑖𝑖𝑖 𝐽𝐽𝐽𝐽𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖 𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖 − ∑𝑖𝑖𝑖𝑖 ℎ𝑖𝑖𝑖𝑖 𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖
2…（1）（相互作用項） （静磁場項）
また、スピンの代わりに 0 と 1 の 2 値を取る変数

𝑥𝑥𝑥𝑥𝑖𝑖𝑖𝑖 =𝜎𝜎𝜎𝜎𝑖𝑖𝑖𝑖 +12∈ {0,1} を使い、変数全体 x=(x1,x2,…)の評価関数𝐸𝐸𝐸𝐸(x)を表した場合は QUBO 形式となります。{0,1}で表せるためデジタル回路との親和性が高いことと、数式の次数を下げやすいことから、デジタ
ルアニーラはこの QUBO 形式を採用しています。

図-1 デジタルアニーラサービスの構成(ステップ 1) 実課題の抽出
お客様が抱える課題についてヒアリングを行い、その中から組合せ最適化問題として解きたい課題を抽出する。
(ステップ 2) 組合せ最適化問題への具体化
抽出した課題から組合せ最適化問題として解くことができる問題を抽出する。
(ステップ 3) 定式化
解決すべき問題に対して、一般によく知られている
数十パターンの定式化済みの組合せ最適化問題（巡回セールスマン問題、最大カット問題、ビンパッキング問題、
最小頂点被覆問題など）が適用可能か判断する。
適用できない場合は、新たな組合せ最適化問題として定式化する。ここでは、目的関数、制約条件など、数式で表せるレベルで定義する必要がある。
(ステップ 4) QUBO への変換定式化した数式を QUBO へ変換する。
(ステップ 5) 最適解の算出変換した QUBO は、1QBit 社のソフトウェアによってデジタルアニーラに適した形式に自動的に変換される。
変換された QUBO をデジタルアニーラで解くことにより最適解を算出する。最後に得られた最適な組合せを評価し、問題の解として採用するかを決定する。
次章ではこの各ステップを事例の紹介に沿って具体的に解説していきます。

４ 実問題の数式化技術
５ 適用事例１：作業人員配置
最適解を得るために、組合せ最適化問題として解きたい課題を抽出してからデジタルアニーラで解を算出するまでに五つのステップを踏みます（図-1）。

- 29 -

それでは、ある国内企業で作業人員の配置を最適化した事例を用いて各ステップを解説していきます。
(ステップ 1) 実課題の抽出
お客様は、生産効率を向上させるため、人員の配置を改善したいという悩みを抱えていました。

(ステップ 2) 組合せ最適化問題への具体化
ヒアリングを進めていくと、ある作業において勤務
形態はシフト制を採用しているが、これまでは人が考えて人員を割り当てていたため、その作業に長い時間を費やしていた。また、その割り当ても最適なものとは限らなかった。という「シフト要求を踏まえた上での作業員数を最小化する」という組合せ最適化問題であることが見えてきました。
(ステップ 3) 定式化
今回の事例は前述で紹介した既存パターンではな
いケースなので新たに定式化する必要があります。作
業員 34 名に 1 週間分のシフトを割り当てる際に、人員配置を最適化する組合せ最適化問題として定式化していきます。図-2 は、作業員の時間ごとのシフトの割り当ての有無を表します。a が作業員（0～33：34 名）、
t がシフト（0～3：4 シフト/日）。シフトが割り当てられている場合は 1、割り当てられていない場合は 0 となるようにモデル化していきます。

また、二つ目の制約条件として、各作業員が週に 2日以上休みを取ること（5 日以下の勤務となること）
を加えます｛式(4)｝。
∑𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥𝑥𝑥𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 ≤ 5 （𝑎𝑎𝑎𝑎 = 0,1,2 … ,33）

(ステップ 4) QUBO への変換
次に、式(2)～(4)をデジタルアニーラで解ける形
式にするため QUBO に変換します｛式(5)～(7)｝。
まず式(3)は、
1 日にこなす必要のある作業量𝑆𝑆𝑆𝑆 𝑎𝑎𝑎𝑎 と実際に割り当てる作業量に全く差がない場合に、最小値を取るように変形します｛式(5)｝。
∑𝑎𝑎𝑎𝑎(∑𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑒𝑒𝑒𝑒𝑎𝑎𝑎𝑎 𝑥𝑥𝑥𝑥𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 − 𝑆𝑆𝑆𝑆 𝑎𝑎𝑎𝑎 )図-2 作業人員配置のイメージ
まず、作業員数の割り当てを最小化する式 （勤務が0 日になる作業員を確保する式）を目的関数とします。
これを定式化すると、式(2)のようになります。
作業者数∑𝑎𝑎𝑎𝑎 𝑓𝑓𝑓𝑓(𝑎𝑎𝑎𝑎) → 最小

1 𝑖𝑖𝑖𝑖𝑓𝑓𝑓𝑓 ∑𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥𝑥𝑥𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 > 0,…（2）
0 𝑖𝑖𝑖𝑖𝑓𝑓𝑓𝑓 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑖𝑖𝑖𝑖𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑥𝑥𝑥𝑥𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 は作業割り当ての有無（作業を割り当てない場
合は 0、割り当てる場合は 1）で、d は曜日（0～6：7
日間）です。
更に、本事例を解く際には複数の制約条件が存在しますが、本稿では代表的な二つの制約条件について述
べます。一つ目の制約条件として、作業員全体で 1 日にこなす必要のある作業量（𝑆𝑆𝑆𝑆 𝑎𝑎𝑎𝑎 ）と、実際に作業員へ割り当てる作業量の差が最小化されることを加えます｛式(3)｝。
𝑓𝑓𝑓𝑓(𝑎𝑎𝑎𝑎) = �min�𝑆𝑆𝑆𝑆 𝑎𝑎𝑎𝑎 − ∑𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑒𝑒𝑒𝑒𝑎𝑎𝑎𝑎 𝑥𝑥𝑥𝑥𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 | （𝑑𝑑𝑑𝑑 = 0,1, … ,6）
𝑒𝑒𝑒𝑒𝑎𝑎𝑎𝑎 ：作業員のスキル

…（4）

…（3）

2

…（5）

次に、式(2),(4)を QUBO に変換するためには、二つの補助変数（𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎0, 𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1）を用いる必要があり、式(4)の QUBO への変換では、作業が割り当てられている作業員の勤務日数が 0 日、または 2～5 日の際に最小値を取るようにします。ここでポイントになるのが、日数の範囲を与えられるように、補助変数を用いることです｛式(6)｝。
𝛼𝛼𝛼𝛼 ∑𝑎𝑎𝑎𝑎(∑𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥𝑥𝑥𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 + 2𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎0 + 5𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1 − 4)(∑𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥𝑥𝑥𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 +2𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎0 + 5𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1 − 5)…（6）𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎0 , 𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1は補助変数（0 または 1）で、αは重み（1.0）です。
式(2)の QUBO への変換では、補助変数𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1が 1 となる場合（勤務日数の割り当てが 0 の場合）に最小値を取るようにします（後述で説明）｛式(7)｝。
−𝛼𝛼𝛼𝛼 ∑𝑎𝑎𝑎𝑎 𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1…（7）例として、1 番目の従業員の勤務日数について説明します。勤務日数が 0 のとき、𝑦𝑦𝑦𝑦10=0、𝑦𝑦𝑦𝑦11=1 にすると式(6)は 0 になる。勤務日数が 2 または 3 のとき、
𝑦𝑦𝑦𝑦10=1、𝑦𝑦𝑦𝑦11=0 にすると式(6)は 0 になります。勤務日
数が 4 または 5 のとき、𝑦𝑦𝑦𝑦10 , 𝑦𝑦𝑦𝑦11 =0 にすると式(6)は 0になり、勤務日数が 1、6、7 のとき、式(6)は 0 よりも大きくなります。また、作業員 a の勤務日数が 0のときに𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1は 1 になるため、式（7）は𝑦𝑦𝑦𝑦𝑎𝑎𝑎𝑎1の合計を最大化することで、作業員数の最小化を表現しています。
QUBO は、各変数の値が 0 か 1 になることを考慮した数式を作成する必要があります。本事例では、作業員の勤務日数や割り当て人員の最小化の範囲を表現する際に、補助変数を使用しました。
(ステップ 5) 最適解の算出
数式はクラウド上のデジタルアニーラサービスにJSON（JavaScript Object Notation）形式で記述しジ
ョブを登録します。デジタルアニーラサービスは高速に処理し計算結果を導出します。今回の事例では、これまで 34 名に割り当てていた作業を 29 名で対応可能- 30 -

とする結果が得られました（図-3）。
制約条件を満足する人員割り当て作業の自動化と、作業量に合った人員配置ができました。

図-4 階層的クラスタリングのイメージ

図-3 デジタルアニーラによる作業人員の割り当て結果

６ 適用事例２：倉庫内の部品棚配置最適化
本章では、抽出した課題から組合せ最適化問題として解くことができる問題を抽出するステップ 2 の事
例として、株式会社富士通 IT プロダクツの工場において部品を収納する棚の配置場所および棚のレイアウ
トを最適化する事例を紹介します。
本工場は多品種少量生産を行っています。製品の種類に関わらず、共通した部品を使用することが多い
ため、製品ごとに棚を設けていません。製品を製造する際には、必要な部品のある棚を順に巡って部品を収集します。しかし、効率的に収集するルートは作業者のノウハウであり、必ずしも最適ではありませんでした。また、どの棚にどの部品を配置するかはこれまで
人が判断していたため、その検討に時間を費やしていました。そこで、本工場では、以下の二つの課題に取り組んでいます。
（１）作業者のノウハウに頼らず最適化された部品収集ルートの指示を与えたい。
（２）部品棚に対し最適な配置を容易に導き出したい。
以降では、このうち（２）の課題を組合せ最適化
問題に落とし込む例を紹介します。
棚の配置を最適化する問題は、同時に収集する頻度の高い（相関が強い）部品を近くの棚に集め、同時に収集する頻度の低い（相関が弱い）部品を離れた棚に配置することで解決できます。これには、階層的ク
ラスタリング[9]が適用できます（図-4）。

- 31 -

階層的クラスタリングとは、データ同士の相関を可視化する手法です。階層的クラスタリングには、データが個別の小さなクラスタに分かれている状態から順次クラスタを併合し、クラスタの階層を生成する凝集型と、全体が一つのクラスタになった状態から始めて、再帰的に対象集合の分割を繰り返す分割型の二つの手法があります。この中で、組合せ最適化問題を解くことによって解決できる問題を抽出できる（デジタルアニーラで解きやすい）のは分割型手法です。
分割型手法に沿ったクラスタリングを行うには、部品同士を相関の強いものと弱いものに分割できる組
合せ最適化の手法の一つである「最大カット問題」が適用できます。実際には、部品収集の際に使用している一定期間分の帳票のデータを活用して、重み付き無向グラフ（ノードとエッジにより構成されており、エッジに重みの付いているグラフ）を作成します。
部品をノードとし、同時収集の頻度の高さをエッジの重みとするグラフを考えます。グラフの最大カット問題とは、グラフを二つに分離したときに残ったエッジの重みを最大にすることであり、ここでは同時収集の頻度が高い部品の組をできるだけ残して、部品を二つにグループ分けすることになります（図-5）。グルー
プ分けした部品は、更に二つに分離してグループ分けを行い、部品が最小単位になるまでグループ分けを繰り返します。

図-5 倉庫部品の相関イメージ

その結果、相関の強弱によってクラスタリングすることにより、最適化した部品の配置場所と棚のレイ
アウトを提案できました。実際に部品と棚のレイアウ
トの配置を変更した場合、作業者の１ヵ月あたりの移動距離を 23.6%短縮（総移動距離が 25,001m から
19,080m に短縮）できるという検証結果が得られました。また、（2）の課題とは別に（1）の課題は作業ルートの最適化も行っており、１ヵ月あたりの移動距離を更に 21.7%短縮（総移動距離が 19,080m から
14,926m に短縮）という結果を得ました。
このように、組合せ最適化問題を解くことによって解決できる問題の抽出は、問題を順にモデル化・変形して既知の事例に当てはめていく考え方で実現でき
ます。
７ まとめ
上述の事例の他にも、富士通はこれまでお客様との PoC（Proof of Concept：概念実証）などの実績か
ら前述した五つのステップを実施するノウハウを蓄積してきました。現在デジタルアニーラサービスでは、組合せ最適化問題を高速に処理する「クラウドサービ
ス」および「オンプレミスサービス」、お客様のデジタルアニーラ活用を支援する「テクニカルサービス」の三つのサービスを提供しています。
クラウドサービスは、前述した QUBO 形式の数式、制約条件などを Web-API で入力し探索した解を得る「汎用数式型（QUBO API）」
、業務に応じた情報を入力して探索した解を得る「ソリューション特化型（最適化ソリューション API）」の二つになります（図-6）。

図-7 倉庫内ピッキング API
オンプレミスサービスでは、お客様環境内にハードウェアを設置してクラウドサービス同様に利用できます。
テクニカルサービスは、前述の五つのステップの支援から教育までを含めた人的サービスで、六つのメニューで構成されています（図-8）。
①「定式化検証」：課題が組合せ最適化問題に変換可能であるか、定式化することが可能か検証します。
②「導入支援」：数理モデルの構築から効果評価までビジネスに適用できるか PoC を実施します。
③「構築」：デジタルアニーラを使ったアプリケーシ
ョンの構築を支援します。
④「運用」：運用中の保守や QA サポートを行います。
⑤「教育」：デジタルアニーラの特徴や仕組み、組合せ最適化問題の解き方を学ぶための、利用者向け教育を提供します。
⑥「チューニング支援」：問題にあわせたデジタルア
ニーラのパラメタチューニングに関して技術的な支援をします。
これらのメニューにより、課題の設定から運用に至るビジネス活用から、教育、使い方のフォローまでトータルなサポートを準備しています。[11]図-6 クラウドサービスメニュー
図-8 テクニカルサービスメニュー

現在ソリューション特化型では、倉庫内ピッキン
グ API を提供しています。この API では、倉庫内にある複数の棚などから指定された商品を取り出す（ピッキング）ときに、移動距離が最短となるルートを求めます（図-7）。

- 32 -

参考文献[1] R．Colwell：The Chip Design Game at the Endof Moore's Law．Hot Chips 27，2015．
[2] 野澤哲生："量子コンピュータ"続々 役に立つのはどれか．日経エレクトロニクス，
Vol.1188，p.41-54（2018）．
[3] Digital Annealer．
http://www.fujitsu.com/jp/digitalannealer/[4] 1QB Information Technologies Inc．
https://1qbit.com/[5] 富士通：富士通と 1QBit、量子コンピュータ技術を応用した AI クラウドで協業を開始．
http://pr.fujitsu.com/jp/news/2017/05/162.html[6] 富士通研究所：量子コンピュータを実用性で超える新アーキテクチャーを開発．
http://pr.fujitsu.com/jp/news/2016/10/201.html[7] 西森 秀稔ほか：量子コンピュータが人工知能を加速する，日経 BP 社，2016-2017，p.70-71．
[8] 原田史子ほか：線形代数学に基づくデータ分析
法．共立出版，2016，p.45-57[9] Quantum-inspired hierarchical risk parity.
https://1qbit.com/wpcontent/uploads/2016/11/1QBit-WhitePaper-%e2%80%93-Quantum-Inspired-HierarchicalRisk-Parity.pdf[10] 富士通：デジタルアニーラご紹介資料
http://www.fujitsu.com/jp/documents/digital
annealer/services/da-shoukai.pdf- 33 -

<MCPC 量子コンピュータ推進 WG 2019>

アニーリングマシンを活用した LTE のパラメータ最適化
齋藤和広*1

田中政晃*2

岡本浩尚*2

株式会社 KDDI 総合研究所*1
KDDI 株式会社*2

Parameter Optimization of LTE Using Annealing Machine
Kazuhiro Saito*1

Masaaki Tanaka*2

Hironao Okamoto*2

KDDI Research, Inc.*1
KDDI Corporation*2
論文概要
スマートフォンなどの携帯端末で利用される LTE(Long Term Evolution)は，基地局のパラメータ設定の組合せ数が膨大であり，従来のコンピュータで最適な設定を算出することは困難である。本稿では，量子アニーリングの活用に向けた初期評価として，デジタル回路によるアニーリングマシンを用いて PCI（Physical

Cell ID）と呼ばれる基地局パラメータを最適化することで，SINR (Signal to Interference plus Noise Ratio)の中
央値を 1 dB 改善できることを確認した。
Keyword: LTE, Wireless Communications, Physical Cell ID, Quantum Annealing

1. はじめにLTE (Long Term Evolution) は，携帯電話・ス
マートフォン（以下 携帯端末）などの通信で利用されている無線通信システムである。携帯端末は，様々な場所に設置された基地局と呼ばれる通信設
備と無線接続されることで，音声通話やインター
ネットアクセスなど，様々なサービスを利用することができる。LTE の基地局は日本全国に設置されており，2019 年 12 月現在，周波数ごとに数万
局～数十万局にのぼる[1]。
基地局数の増加により，携帯端末を利用できるエリアが広くなる一方で，基地局に設定するパラメータの最適化が困難になるという問題が生じる。
基地局のパラメータは，設定によっては基地局間で信号の干渉等の原因となり，特に基地局が密集する都市部のエリアではその影響が大きいため，全体で最適化することが必要である。しかしながら，基地局数の増大に伴い，パラメータの設定パ
ターンは指数関数的に増大するため，従来のコンピュータでの最適化は困難であった。
一方で，従来のコンピュータでは計算が困難な問題を解くために，量子コンピュータを活用することに注目が集まっている。近年では特に，特定用途に特化した量子コンピュータのマシン開発が進められている。2011 年に，量子コンピュータの実装の一つとして，量子アニーリングと呼ばれる手法を実装したマシンが発表[2]されたことで，量子コンピュータを実際のビジネス課題に適用できる可能性が出てきた。量子アニーリング
は，極低温で発生する量子力学的な現象により，組合せ最適化問題において最適解に近い準最適解を高速に導出することができる。

- 34 -

本稿では，PCI (Physical Cell ID）と呼ばれる基地局パラメータ最適化に量子アニーリングを活用するための初期評価として，富士通社製のアニーリングマシンであるデジタルアニーラ[3]を用いて取り組んだ事例について紹介する。最適化された基地局パラメータは机上での評価だけでなく，
フィールドトライアルで評価を行い，最適化の効
果を確認した。
セル２

基地局１

セル１
基地局２

3.

アニーリングマシンの活用

3-1. アニーリングマシンを用いた最適化

本 検 討 で は ， ア ニ ー リ ング マ シン を 活 用 して ，MOD3 重複を最小化する PCI の MOD3 値を求める。MOD3 重複を測る指標として，セル間のハンドオ
ーバ数を利用した MOD3 重複率を定義する。ハンド
オーバとは，移動通信において，携帯端末が移動するとき，もともと接続していたセルから通信品質が良いセルに接続先を切り替える動作を指す。
MOD3 重複率は，ハンドオーバの総数に対する
MOD3 重複したセルへのハンドオーバ数の割合である。
図 2 に MOD3 重複率の算出例を示す。図 2 で
MOD3

セル３

0

セルA

ハンドオーバ数 600（MOD3重複なし）

1

セル４

図 1

対象セル

LTE システムの構成例

セルB

2. LTE 基地局のパラメータ設計
本稿で想定する LTE システムの構成図を図 1に示す。LTE システムは複数の基地局と複数の携帯端末から構成され，一つの基地局はセルと呼ばれる 1 つ又は複数の通信エリアに分割される。図1 の例では，基地局 1 が 3 つのセル，基地局 2 が
1 つのセルに分割されている。基地局と携帯端末の間で，音声通話やインターネットサービス等で利用者が送受信するデータのほか，制御用信号や，
無線品質の測定等に用いられる RS (Reference
Signal)等が送受信される。
中でも RS はとりわけ重要な信号で，セルごとに携帯端末に送信されており，隣接するセル間でのRS 同士の干渉は最小限にとどめる必要がある。
RS 同士の干渉を避けるためには，隣接するセル
間で RS を送信する周波数をずらすことが有効である。LTE では PCI (Physical Cell ID)と呼ばれるパラメータが規定されており，PCI は 0～503の 504 通りの値をとる。RS 信号を送信する周波数は，PCI の MOD3 値（PCI を 3 で割った余りで，3 通り）に応じて決定されるため，隣接するセル間で PCI の MOD3 値ができる限り同一にならないように設定する必要がある。以降，PCI のMOD3 値 が 隣 接 セ ル 間 で 等 し く な る こ と をMOD3 重複と呼ぶ。

- 35 -＜ハンドオーバ数＞
総数:
1000
Mod3重複: 400⇒Mod3重複率 40%

ハンドオーバ数 400（MOD重複あり）

図 2 MOD3 重複率

は，対象セルから見て，隣接するセル A は MOD3
重複なし，セル B は MOD3 重複ありとなっており，ハンドオーバ数はそれぞれ 600 と 400 である。対象セルにおけるハンドオーバ総数は 1000
（セル A 600 + セル B400）に対して，MOD3 重複しているセル B へのハンドオーバ数は 400 であり，MOD3 重複率は 40%と計算される。
3-2. 机上評価

本問題の評価には，量子効果に着想を得た富士通社製のデジタルアニーラ[3]を利用した。デジタ
ルアニーラは，量子現象に着想を得た複数の高速化の仕組みをデジタル回路上に実装したもので,従来型の汎用プロセッサを用いたコンピュータより高速に組合せ最適化問題を計算できる[3,4]。また，ビット間の結合を表現するグラフ構造が全結合であり，グラフ変換が不要な点が，活用上及び適用可能な問題の規模の上で優位点となる。
机上評価として，実際に運用中の LTE 基地局のハンドオーバ数のデータを用いて，デジタルア
ニーラによる PCI の MOD3 値の最適化前後の

表 1 評価シナリオ別の計算時間
局数
14 局
100 局
1120 局
設 定 パタ 約 783 億
約 6.5 × 約 3.3 ×
ーン数
1077
10871
計算時間 0.4 秒
58 秒
300 秒

表 1 に示すように最適化する基地局数に応じて，PCI の MOD3 値の設定パターン数は指数関数的に増加する。一方で，デジタルアニーラでの計算時間は 1000 局を超える基地局を最適化対象とした場合でも 5 分以内に計算結果を得ることができる。デジタルアニーラを使うことで実用に耐えうる時間内で計算結果を得られることがわかる。

が、14 局、100 局の計算結果と比較して同等の改善が見られていることから精度の良い計算結果が得られていると判断した。
3-3. フィールドトライアル評価

3-2 節では，机上検討において MOD3 重複率の改善を確認したが，通信品質の改善効果を確認するため，机上検討で用いた基地局 14 局を対象に実際に PCI の変更を行い，通信品質を評価する
フィールドトライアルを行った。本トライアルでは，デジタルアニーラで最適化した MOD3 値をもとに PCI を決定し，この PCI を基地局に設定した。
本トライアルでは，通信品質の評価指標の一つである SINR (Signal to Interference plus Noise Ratio)を用いて，基地局の PCI を設定変更する事前事後において，対象の基地局周辺エリア一帯の SINR
を現地で測定し，その中央値で通信品質を比較した。
11

SINR中央値

MOD3 重複率を比較評価した。ハンドオーバ数のデータを利用した基地局が存在するエリアは，首都圏内の市街地域である。
最適化する基地局数は，最適化対象エリアの広さを変えることで，14 局，100 局，1120 局の三通りとした。なお，MOD3 値の最適化対象とした基地局の周辺にも基地局は存在する。
それらの基地局は最適化対象外であるが，最適化対象基地局との間でのハンドオーバは評価の中で考慮した。

MOD3重複率

25%
20%
15%

10.5
10
9.5
9
最適化前

10%
5%

最適化後

図 4 SINR のフィールド測定結果

0%
14局

100局
最適化前

1120局

最適化後

図 3 MOD3 重複率の机上評価結果

図 3 にデジタルアニーラによる PCI の MOD3値の最適化前後の MOD3 重複率を比較したグラフを示す。最適化前は，14 局，100 局，1120 局でMOD3 重複率がそれぞれ 13.5%，20.3%，17.9%であったが，
デジタルアニーラで最適化した結果，それぞれ 5.7%，10.0%，7.1%となり，大幅な改善が確認できた。最適化対象とする基地局数を 1120
局まで増やした場合は、表 1 に示す通り、設定パ
ターン数は約 3.3×10871 にものぼる巨大数となる

図 4 に測定結果を示す。当該エリアにおいて
SINR の中央値が約 1dB 改善していることがわかる。SINR は，各セルの負荷や伝搬環境の変化で変動する要素はあるが，現地測定結果の 25%ile
値,75%ile 値でも約 1dB の改善を確認したため今回の PCI 変更による改善と判断した。この結果か
ら，デジタルアニーラによって MOD3 重複率を改善することにより，通信品質が改善できることを確認した。
4.

おわりに

本稿では，LTE システムへのアニーリングマシンの適用例として，PCI と呼ばれる LTE 基地局
パラメータの最適化事例を紹介した。机上検討で- 36 -

効果を確認した後，運用状態の 14 局の基地局にデジタルアニーラによる最適化の結果を適用し，フィールドトライアルを実施した。その結果，
SINR の中央値,25%ile 値,75%ile 値のいずれにおいても約 1dB 改善していることを確認した。今後
は，今回の取り組みで得られた知見をもとに，量子アニーリングの活用を進め，LTE のエリア品質を更に向上させるとともに，基地局数が増加する
ことでパラメータ設計作業が LTE よりも複雑になると想定される 5G での活用も検討する。

参考文献[1] 令和元年度 携帯電話及び全国 BWA に係る電波の利用状況調査の意見募集の結果及び評価結果の公表，
総務省総合通信基盤局，
https://www.soumu.go.jp/menu_news/snews/01kiban14_02000001_00003.html[2] M. W. Johnson et al., “Quantum annealing with
manufactured spins,” Nature, vol. 473, no. 7346, pp.
194–198, 2011.
[3] デ
ジ
タ
ル
ア
ニ
ー
ラ
,
https://www.fujitsu.com/jp/digitalannealer/[4] S. Tsukamoto, M. Takatsu, S. Matsubara, and H.
Tamura,“Anaccelerator
architectureforcombinatorial optimization problems,” Fujitsu Sci.
Tech. J., vol. 53, no. 5, pp. 8–13, 2017.

- 37 -

<MCPC 量子コンピュータ推進 WG 2019>

事例紹介：物流センターにおける人員配置最適化の取組
植田 徹史
住友商事株式会社

Challenges for the staff placement optimization
at the distribution center
Tetsushi Ueda
Sumitomo Corporation

代表的な労働集約型産業である物流センターにおいて、作業者が持つスキルを考慮した上で、作業者の作業負荷の均等最小化といった全体が最適になる作業の割振り（人員配置表）を、量子コンピュータ技術の一つであるアニーリング方式で提示した取組を紹介する。より精度の高い人員配置が期待できるばかりか、量子コンピュータ技術が持つ「速さ」により、変化が激しい現場で即座の対応を図ることをも可能とし、様々な働き方の提案に資することも説明する。革新技術の利活用によって、人々が持つ多様な価値観を尊重し、それをも包含した形での「全体最適」された社会の構築に向けた、画期的取組みの第一歩である。
Keyword: Ising model, Annealing, Staff placement optimization

1. 本稿の概要
1-1 物流センターにおける労働上の課題
少子高齢化が進む我が国では、生産年齢人口は近年減少の一途を辿っており、今後更にその傾向は続くものと予測されている。[1]
生産年齢人口が減少する現状において、労働集約型産業はその対策を余儀なくされており、機械化による自動化・省人化に取組む企業も数多い。中には、AI 技術を活用することで熟練工の技術でさえ自動化させることに挑戦している企業もみられ、資本集約型産業への転換が一部では進みつつある。[2]
この流れは様々な形や大きさの「物を動かす・運
ぶ・保管する」といった primitive な機能を提供する物流産業でも例外ではなく、例えば倉庫内作業において棚搬送型 AGV ロボットによるピッキング作
業の自動化や、自動製封函機による梱包作業自動化
等、従来人手で為してきた作業の省人化を図る様々な動きが出てきつつある。
一方で資本集約型産業への転換には多額の設備投資を要するケースが多く、投資余力の乏しい物流現場の多くは自動化がなかなか進まないのが現状である。また、近年の EC 通販事業の拡大による総物量の増加、またそれに伴い貨物の形や大きさのバリエー
ションが豊富になることで、貨物の中継地点である
物流センターの自動化はますます困難なものとなっており、未だに業務の多くを人手に頼っている現場が少なくない。[3]貨物の量・種類とも増加することで物流センター
内の作業は複雑化する一方、輸配送のスピードアッ
プも求められており、働きやすい労働環境を整備す
ることが物流センターの喫緊の課題であり、労働集
約型産業においても解決すべき課題の一つであると言える。
1-2 人員配置最適化の取組み目的
本稿では、筆者が所属する住友商事株式会社の事
業会社の一つである物流センターにおいて、この課
題に取り組んだ事例を紹介する。具体的には、物流- 38 -

センター内作業の一つである「梱包・出荷」作業において、作業者個々人が持つスキルを考慮した上で、全体が最適になる作業の割振り（人員配置表）を、膨大な組み合わせの中から量子コンピュータ技術の一つであるアニーリング方式で提示する取組みである。これにより勘と経験で作成してきたシフト作成の労苦から解放されるだけでなく、状況に応じた最適なシフトの割振りが常に作成できる効果を持つ。
また、作業者側においても個々人が無理なノルマを課されることもなく、自分のスキルに見合った計画が設定され働きやすいものとなり、労働集約型産業における現業作業での働き方改善の効果、また作業の効率化をも期待できる取組みである。
2. 物流センターでの事例
2-1 本物流センターの概要
本稿の物流センターは中部地方にある通信販売事業者専用の出荷センターである。約 1,000 名の従業員が働き、日曜日の休暇日以外は 9 時～17 時を基本として毎日稼働、約 30,000 件/日の商品を最終消費者に向けて出荷している。
業務プロセスは図１）の通り、通信販売事業者からの商品入荷後、自動倉庫を含む保管エリアにて在庫した後、最終消費者からの注文に基づいて保管エリアから商品をピッキング、梱包エリアにて顧客毎に梱包し出荷するという物流センターである。
入荷/ピッキング/梱包・出荷のそれぞれのエリア毎
で作業者は分かれて作業しており、最終工程である梱包・出荷エリア約 100 名の作業員を対象に最適な
人員配置表作成に取組むものである。

2-2 本物流センターでの課題感
通信販売事業者の商品を扱う本物流センターでは、衣料品を中心に小ロット多品種の商品（約 25 万SKU）を扱うため、大規模な設備投資をしないと完
全自動化は難しく、この現場でもピッキングや梱包作業は人手に頼る形をとっている。

- 39 -

物流センターの業務プロセスであっても、工場のライン管理と同様に、最終工程である出荷能力をベースに工程のタクトを振って、前工程にシンクロさせることで全体最適が図れるはずだが、全工程に渡って人が細かな作業を行うため計画通りに工程が進捗しないことが多い。また工程進捗の可視化もなされていないため、状況の変化に応じた配置変換を行うといったライン制御も簡単には実施できない状況である。つまり、常に靄がかかった状況で工程管理を行っているに等しく、その結果、計画では営業時
間通りに終わるはずだった作業が終わらず残業が発生したり、一方では作業員全体で多くの手待ち時間が発生したりと、状況の把握と制御がリアルタイムに行われていないのが現状オペレーションの実態といえる。
2-3 進捗状況を可視化する取組
この状況に対し、人員配置最適化の取組の前に、本物流センターでは個々人の作業スキルと当日の全体目標数から、計画に対する実績シミュレーションが行える、「スマイルボードシステム」を構築した（図2）。これにより目標数に対して計画通り進捗しているか管理者が常にモニタリングでき、予定との乖離に対して即座の対応を可能とした。また、管理者による可視化のみならず、図 2）右の通り、作業現場にもタブレットを配布し、グループ内メンバー個々人の進捗状況をビジュアライズに表示することで、作業員の労働状態をリアルタイムに把握でき、現場での自律的な対応を行える機能も構築した。

この結果、個々作業者の手待ち時間や、管理者の作業進捗管理に関する工数の削減効果が、可視化による効果として顕著に見られた。
次のステップとして、予実管理の元となる人員配置表を作成者の勘と経験で作るのではなくアニーリング方式を用いて最適なものを作るといった、更に高次の段階へ進めた取組を次項で紹介する。
3. 最適な人員配置表の作成
3-1 作成する対象業務
本取組を行う業務として、前述の通り約 100 人の作業者にて行っている「梱包業務」を対象とした。
梱包業務は業務種別が明確に分かれており各個人のスキルが定義し易く、約 100 人という人数が実証において適した規模と判断した。
梱包の業務種別は、図 3）で示した通り四種類あ
り、一つの出荷先に一つの商品を梱包して出荷する「単伝」業務、一つの出荷先に複数の商品を混載してワンパッケージに仕立てる「複伝」業務、そしてその「単伝」「複伝」にギフトラッピングを施す「ギフト単伝」「ギフト複伝」の四種である。（この他にも梱包業務には、段ボール等の資材補充を行う「水すまし」といわれる業務も一般的に存在するが、この業務は特定の方が行う運用となっているため、今回のシフト作成の範囲外とした）。業務種別におけるポイントとしては、「単伝」「複伝」といった業務より、「ギフト」業務はラッピングの技術が必要であり難度が高い、つまり誰もが出来る業務ではないものが存在することである。

3-2 解くべき課題の特定梱包業務における人員配置の最適化を取進めるにあたり、先ず「全体が最適になる」とは何か、解くべき本質的課題は何かを定義する必要がある。
経営側の視点に立つと、その日のノルマを満たす
最少人数の把握、つまりコスト削減に直結する「作業者数の最小化」が解きたい課題といえる。だが、本取組では、当日確定されるノルマを満たす、当日
出勤者の最適な割振りを求めたいものであるため、当日の出勤者が計算上の最少人数を超えた場合、その方々に他の業務を宛がえる保証はない以上、最小化したところで手持ち無沙汰にすることはそもそも働きやすい環境を作るといった狙いとは全く異なるものとなる。
故に、本稿での「全体が最適になる」こととは、当日の朝に確定される四種類の業務のノルマ（目標達成数）を満たしつつ、「全体で最も早く作業を終わらせられる組み合わせ」となる、「作業者の作業負荷の均等最小化」とした。つまり、図 4）で示す通り、個々人の持てる力をフルに発揮することで作業効率を最大化させ、与えられたノルマを満たしつつ、従業員全体での負担軽減・負荷の均等割当に資する「効率の良い配置と作業工数の平等化」に着目した人員
配置表を提示するものである。

3-3 最適化適用技術
本稿では、この全体が最適になる人員配置表をア
ニーリングマシンで求めることを行う。つまり、与えられたそれぞれの作業毎のノルマを満たし、出勤者の作業負荷を均等にしつつ最小化することを、以下のイジングモデルを用いたエネルギー最小化問題
を解くことで求めるものである。

アニーリングマシンの動作モデルとしては、上記
最適化の汎用表式に対し、①解きたい問題に対応するパラメータを入力し、②評価値（コスト）を元に組み合わせ変数がマシンによって調整され、③マシンでの計算完了後に組み合わせ変数を出力するものである。

- 40 -

3-4 目的関数の定義
この解くべき答えとなる、最小化したいエネルギー関数（目的関数）を定義したい。これは前項から、個々人が全力で働いた場合のノルマの達成度合いである「ノルマの充足率を最大化すること」と定義できる。例えば、この「ノルマの充足率が 80%」というのは業務時間の終わりまでに全体でノルマの 80%が達成されていることであり、逆に「ノルマ充足率が 120%」というのは、業務時間の終わりまでにノルマが達成され、かつ 20%の時間的猶予があるということである。
しかし、目的関数をこの「ノルマの充足率を最大化すること」だけで実行すると、四種類の作業の中でノルマの充足率に大きな違いが見られることが分かった。つまり、ノルマは全体で 100%達成しているにも関わらず、各業務の中でノルマを達成し易い業
務は 100%を超えるが、逆にノルマ達成が困難な業務については 100%実施しないといった、結果に対して大きくバラつきが出る傾向が見られたのである。
そこで目的関数として、図 5）の通り、各業務のノルマの充足率に偏りが出ないように均等化することも定義した。

これより本稿での課題を満たすには、「ノルマ充足率の平均を最大化する」こと、及び「ノルマ充足率の分散を最小化する」ことといった、多目的最適化
問題を解くことであり、これらを目的関数として定義するものである。
3-5 パラメータ値の設定
入力パラメータとしては、当日の朝に設定される
各業務の目標数（ノルマ）、その日の出勤者の名簿、そしてその名簿に基づく作業可能量（スキル）の三点である。目標数（ノルマ）は、前日夜間に当日発送分の締処理が為されるので、人員配置表を作成する朝の時点で業務種別毎に数値は確定する。出勤者名簿についても、急な欠勤や個人の出勤シフトの変
更は当日に把握できるレベルであり、通常のオペレ- 41 -

ーションで問題なく入手可能なデータである。ポイントとなるのは、作業者個々人の作業可能量（スキル）の設定である。
本物流センターでは、作業者全員にハンディター
ミナルを持たせ、個々の作業の始まりと終わりに伝票に付されているバーコードを読み取り、WMS に
そのデータが送信される仕組みを持っている。今回の実証においては 2019 年 7 月 1 日～7 月 10 日までの梱包実績データから、この作業を一度でも従事した 238 人の、四種類の作業種別毎の実績数を 30 分毎に集計し、その平均値を各個人のスキル値とした。
スキルの欠損値については、「単伝/複伝」間、「ギ
フト単伝/ギフト複伝」間は、作業特性上似通うものであることから、比例定数により補完した。つまり、
図 6）の通り、例えば単伝のみのデータを持つ作業者
は、複伝についてはスキルを補完したが、ギフト単伝・ギフト複伝については作業スキルがないものとして取り扱った。

3-6 イジングモデルによる定式化
目的関数の一つ「ノルマ充足率の最大化」を定義するにあたり、業務種別 k の充足率 Sk を定義したい。
その準備として、先ず個々の作業員 i が業務種別 k を
単位時間当たりに行える作業量（＝スキル）として、と表す。
（N：作業員数、M：業務種別数）
また、前述の通り「ギフト単伝・ギフト複伝」といった、一部の作業員においては出来ない業務種別があるので、午前中の作業における作業員変数 x に対し、作業員 i に業務種別 k が割り当てられる場合を1、割り当てられない場合を 0 とし、同様に、午後の作業における作業員変数 y に対しても次の通りとした。

この定式をマシンの動作モデルに再定義し、マシンに実際のデータを入力した実行結果として、以下
図 7）の人員配置表が出力された。

これより全体の総作業量は、単位時間当たりの作業
量（スキル）に作業員変数を掛けたものの和であり、（ta：午前の時間数 tb：午後の時間数）
ノルマ充足率 Sk は、ノルマをＷk として以下の通り定義できる。

目的関数は、充足率 Sk を最大化することであり、（左から） '作業員 ID'：(午前作業 ID, 午後作業 ID),
作業 ID ＝ 0:単伝 1:複伝 2:ギフト単伝 3:ギフト複伝…（1）

また、この時のノルマ充足率は以下図 8）の通りであった。

と定義することができる。
また、もう一つの目的関数として、各ノルマは等価値として出来るだけ均一に満たすことが必要であることから、充足率 Sk の分散を最小化するものとして、以下の通り定義する。

…（2）
これに、各作業者にはどれか一つの担当可能な作業を割り当てることができるという、以下の制約関数を与える。

…（3）
以下の通り、（1）を（2）の分散と次元を合わせ、…（1）’（1）’と（2）と（3）を足し合わせてハミルトニア
ンとし最小値を求めることで、最適な人員配置表が得られるものとして定式化を行った。

実データに基づくノルマ充足率がほぼ 100%であったことに対し、図 7）の人員配置を宛がった場
合、四種類の作業のどれもが 30％弱の時間的猶予を持ち得るという結果を表している。また、業務種
別間での充足率の均等化もほぼ認められるものであり、目的関数として定義した人員配置表が作成できたと評価し得る結果であった。
3-7 課題点と実用化に向けた価値
今回の実証で上記結果を得たものの、すぐに実用が果たせるかというと、そこには幾つかの課題を乗り越える必要があり、中でも「作業者スキルの正当な見積もり」は重要な課題と言える。物流センター
では取り扱う貨物によって梱包のスキル値は大きく変動し、精度を求めるためには梱包対象物のデータ化と、それを扱うスキルとの相関測定を必要とする。加えて、その日の作業者の体調等のコンディシ
ョンや、午後は疲れて仕事が捗らないといった時間
帯による変動、或いは作業者同士の好き嫌いといった人間関係が結果に与える影響等といった、スキル
値を左右させる様々な要素の洗い出しと、継続的な- 42 -

データの取得が精度向上に不可欠な取組みであり、機械学習等の AI アプローチも含め数値化させていく取組みが課題解決に必要になってくるといえる。
それでも今回の量子アニーリングマシンを使う価
値はどこにあるのか。この heuristic な解であったとしても、図 9）に示した通り「速さ」が担保され、それによって新しいソリューションを提供できることにその価値がある。つまり、都度変化する状況や不測の事態に対して、最適な配置や必要人員をリア
ルタイムに計算でき、その対応が即座に行えること
は、前述の「常に靄がかかった状況」とは全く異なるマネジメントが行えるのである。
また、今回の実証では、午前/午後のシフト計算のみを行ったが、マシン性能の許す限りにおいては一時間毎の人員配置表の作成も当然に可能であり、午後の二時間だけ働きたいといった希望に対して、
現状のノルマの進捗度合いから「その時点」の最適なシフトが即座に提案できるといった、様々な働き方に資することも可能とする。

重要視してきた。つまり、持続的に事業を行い得る
原点は、全体最適の実現に他ならないということである。[4]
本稿で表した「人員配置の最適化」は、ある一つの局面での全体最適の実現であり、それが重なり合うことで、延いては豊かな社会を形成する礎となり得るものである。これは冒頭で表した、我が国の構造的な課題解決に向かう一つの方策に向かうものでもあると言える。（図 10））「先取の精神」でもって世に生まれる革新技術を適切に活用し、あらゆる連携によって全体最適を図る、これにより、世界中の人々の経済的・精神的な豊かさと夢を実現を目指す、これこそが長きに渡って価値提供し続ける企業が目指す方向性であると考えるものである。

4 今後の展望
本稿は物流センターにおける人員配置最適化の取組であったが、同様の課題は他の労働集約型産業にも存在しており、他の産業への展開も十分に考え得るものである。
更に、本実証を俯瞰すると、社会構造が大きく変化する現代において、技術を活用して価値観の多様化に取り組みつつ、如何に事業を伸張させ得るかといった命題に応える取組みであったとも言える。
筆者が所属する住友商事グループでは、創業以来約四百年に渡り脈々と受け継がれてきた「住友の事業精神」が事業遂行の根幹にあり、中でも「自利利他公私一如」といった、「事業を行うにあたっては自らに価値をもたらすと同時に、取り巻く社会にも価値をもたらし、ともに持続した成長を図る」ことを- 43 -

謝辞
本成果は、MCPC「量子コンピュータの産業応用実装に向けた実証実験」により得られたものであり、実証に参加頂いた㈱フィックスターズ、日本電気㈱、SCSK㈱、早稲田大学に深く感謝の意を表します。
参考文献[1] 国立社会保障・人口問題研究所. National Institute of Populationand Social Security Research 2017. "将来人口推計" p.4-5
http://www.ipss.go.jp/pr-ad/j/soshiki/ipss_j2017.pdf[2]"第 1 部第 1 章 我が国ものづくり産業が直面する課題と展望".
経済産業省 2018 年版ものづくり白書. 経済産業省. 2018, p.82-128
https://www.meti.go.jp/report/whitepaper/mono/2018/honbun_pdf/pdf/honbun01_
01_02.pdf[3]“第ⅱ部 第 6 章 競争力のある経済社会の構築”. 国土交通
省令和元年国土交通省白書. 国土交通省 2019, p.199-201
http://www.mlit.go.jp/hakusyo/mlit/h30/hakusho/r01/pdf/np206100.pdf[4]住友グループ広報委員会. "Sumitomo in History"
https://www.sumitomo.gr.jp/history/

<MCPC 量子コンピュータ推進 WG 2019>

事例紹介：機械学習と最適化の活用に向けた取組
大野 真一朗*1

八代 夕紀子*1

高橋 是清*1

株式会社 野村総合研究所*1

Challenges for utilizing Machine Learning and Optimization
Shinichiro Ohno*1

Yukiko Yashiro*1

Korekiyo Takahashi*1

Nomura Research Institute, Ltd*1
論文概要
機械学習や最適化といった領域はビジネスを大きく変える可能性に満ちている。一方、その適用対象や領域の選定、実施テーマの検討は一般に難易度が高い。著者が経験した「物流業での事例」を題材に、機械学
習や量子コンピュータ含む最適化技術のビジネス適用に向けて必要な取組を、ビジネス、データ、手法の観点から考察する。
Keyword: Machine Learning, Optimization, Logistics, Data Utilization Strategy Planning

1

本稿の概要
1-1 機械学習・最適化を取り巻くビジネス環境
近年、企業におけるデータ活用の背景から、様々な業界・業種の企業において、蓄積したデータを活用して経営指標の予測や経営判断が行われる時代となってきた。
McKinsey Global Institute の調査 [1]によれば、AIを活用した市場の規模は 2030 年までに 13 兆ドルまで広がると予測されており、今後ますます、様々な領域で機械学習や量子コンピューティングを含む最適化技術の活用が進む状況と考える。
技術活用においては、その実現を担う人材が重要である。機械学習や最適化といった技術のビジネス適用を支える人材の不足は長年指摘され続けているが、近年は市民データサイエンティスト(Citizen Data
Scientist) [2]が、多く活躍するようになり、人材面での課題は収束しつつある。
また、彼らを支援するツールとして、DataRobot [3]や H2O.ai [4]といった AutoML と呼ばれる機械学習
モデル構築の自動化製品も普及が進んでいる。

1-2 ビジネス適用での課題と本稿の位置づけ
上述の通り、各種技術を適用すべき市場、それを担う人材、そしてそれらを下支えする製品やツールとすべてが揃う一方で、PoC(Proof of Concept)は実施するが、その先のビジネス現場への技術適用がな
かなか進まない現実も、著者らは多数、目にしてきた。
そういった現象はなぜ発生するのか？について、
本稿では、物流業における事例をケーススタディとして、ビジネス・データ・手法（機械学習や最適化）の３つの観点から考察する。
本稿では、２章にて物流業における事例、当案件での技術適用での課題、解くべき問を見つけるプロ
セスを説明した上で、３章にて機械学習や量子コン
ピューティングを含む最適化技術をビジネス適用するために必要な取組について考察する。
なお、量子コンピューティングの最新技術動向や技術的な議論は本ジャーナルの他稿において、国内
コミュニティーをリードする専門家による議論がある背景から、本稿では、機械学習や最適化技術のビジネス適用を主たる論点としたい。

- 44 -

2 物流業での事例
2-1 顧客とプロジェクトの概要
当案件は、全国十数万の店舗への配送を担い、配送ルート数は、数万に及ぶ物流業の顧客事例である。
近年、多くの企業にて叫ばれている、働き方改革の文脈から、配送員（トラックドライバ）の長時間労務を改善する目的で、機械学習や最適化技術の活用検討を開始した。
2-2 顧客の課題感と目的

2-3 技術適用の方向性
配送ルートの最適化ということで、容量制約付き
配送計画問題(CVRP) [5]として求解し、有るべき配送ルートを検討することとした。
CVRP に対応した最適化ツールは、商用製品であれ
ば Gurobi Optimizer [6]や、オープンソースソフト
ウェアにおいても Google OR-tools [7]等、様々な選択が可能である。
CVRP は組み合わせ最適化問題であり D-Wave を始めとする量子アニーリングマシン及び、国内ベンダのアニーリングマシン活用も選択肢の一つである。
これらのマシンの技術的検討については、本ジャーナルの他稿での議論に譲るとし、本稿では、最適化ツールの「適用のみ」で、目的の「労務の平準化」が実現できるかを議論したい。

顧客へのヒヤリングにて、配送員の労務時間にはムラがあり、配送の完了の為、残業が必要な配送員もいれば、標準業務時間内で配送を完了している配送員もおり、残業が発生している配送員の業務の一部を他の配送員に分配することで、残業時間削減と労務の平準化が図れる見込みであった。
2-4 「現場の観察」と「施策の再考」
具体的には図１のとおり、従業員 C の業務の一
本稿の検証においては、PoC として既存ルートから部を B、D に分配し、労務平準化を実現する。
図 1）業務分配による労務の平準化

A

B

C

D

A

B

C

D

この労務時間のムラの原因を明らかにするために、配送ルートの可視化を行った。管理台帳上の配送順、配送時間制約、配送先住所を地理情報にマッピングし、配送ルートの現状理解を進めた。
結果としては、想定どおり配送員 C の配送ルー
トは他のものに比べ長く、配送ルートの再考による業務平準化が施策として妥当であると判断した。

一部を選定し、CVRP ソルバによるルート最適化、計算機でのシミュレーション及び、実トラックを利用した効果検証を実施した。
トラックでの効果検証においては、著者らもトラックに同乗し、最適化済みルートを走行したところ、走行距離は最適化されたが、走行距離以外にも配送員の労務時間のムラを発生させる要因を発見した。
配送員は１日あたり平均８時間勤務するが、移動時間（図 3 の※1）は６時間であり、CVRP ソルバにより距離が最適化され、移動時間は平準化された。
一方で、店舗におけるトラックの滞留時間（図 3 の※2）に、平均２時間を要しているが、滞留時間は配送ルートと異なり CVRP ソルバでは最適化されない。
滞留時間は、トラックが店舗駐車場に入庫するまでの路上待機時間や、納品作業の所要時間等で構成
され、長時間滞留が必要な店舗への配送を各配送員にいかに分散するか？が重要となる。
図 3）労務時間の要素分解

図 2）配送ルートのイメージ（実線が配送員 C）

１人あたり
労務時間

移動時間
※１

店舗滞留
時間 ※2

倉庫

距離
(最適化)

法定速度

速度

渋滞状況

駐車場入庫
待ち時間

店舗側の
受入状況

納品の
所要時間

配送量
ドライバの
経験・技量

- 45 -

2-8 解“いた”問
これまでの議論をまとめる。
機械学習を用いて、各種説明変数を利用し、分類問題として長時間滞留が発生する店舗を洗い出す。
最適化技術（CVRP ソルバ）を利用し、長時間滞留
店舗のドライバへの均等割当を制約として、配送計画問題としてルート最適化を行う。（図 4）2-5 解く“べき”問改めて「解くべき問」を定義すると下記の通りで
ある。
①
②
③

配送日の条件に基づき店舗滞留時間を推定
推定滞留時間に応じ配送先をドライバに分散
ドライバ毎に回る配送先の経路を最適化

適用技術としては、①は機械学習による推定、②③には CVRP ソルバによる最適化が適用可能である。
機械学習（①）については、上述の要因分解に従い、主にトラック車載器の情報、配送先店舗の情報（所在地、規模、直近売上、その他）、当日の注文情報（配送予定量）、トラックドライバの過去の担当コース、業務歴等をベースに説明変数を設計し、特徴量加工（前処理）した上で、滞留時間推定モデルを作成した。
2-6 機械学習や最適化適用でのトラップ
滞留時間推定モデルの作成・評価では、推定モデ
ルの誤差（=実績-推定）の問題に直面した。
新たなデータソースの検討、特徴量加工、利用するモデルの変更、パラメータチューニング等を試行したが、誤差はビジネスが要求する域にはなかなか収束しない状況であった。解くべき問だとしても、解くことができない問であっては何の意味も無い。
著者らも含め、機械学習や最適化のエンジニアは、作成するモデルが最善の結果を出せるよう、努力を重ねる。それはプロフェッショナルとしてあるべき姿であり、ありたい姿であるが、一方、そこにはトラップがある。
つまり、今行っている改善が最終的な KPI や KGIにつながっているか？出口戦略があるか？である。
今回の施策においては、労務時間を平準化することが目的であり。店舗滞留時間を誤差なく回帰することは手段の１つであり、目的ではない。
2-7 解く“ことができる”問目的に立ち返ると、長時間滞留が発生する店舗を全配送員に分散することさえできれば、労務時間は平準化できるので、最終的に著者らは、本問題を分類問題として求解することとした。

図 4）機械学習と最適化の利用イメージ回帰（滞留は何分？）

25分30秒分類（30分以上か？）True / False
もしくは多値

誤差が大

説明変数

30分以上の店舗が特定ドライバに偏らないようルートを最適化する

この２段階での求解により、「移動時間」と「店舗滞留時間」の両者を配送員間で平準化し、最終的な「労務時間」の平準化の達成の見込みがついた。
現在はこの取組をより広い範囲に適用し、最終的に全国の物流網にて本施策を適用する計画である。
3 事例からの学びと結び
3-1 事例の振り返り
本稿での事例を振り返ると本施策が PoC の域を超えてビジネス適用につながった要因は、下記２点と考える。
 真に解くべき問を見出す
配送労務の平準化ということで、ルートの最適化から開始したが、目的に立ち返ると真に解くべき問は、滞留も考慮したルートの最適化であった。トラックへの同乗で大きな気付きを得ることができた。ビジネス現場の最前線で得る一次情報以上に有益なものは存在しない。いかに現場を知り、データを正しく理解するかが重要である。


具体的には、何分滞留するか？（回帰）ではな
く、30 分以上の滞留が発生するか、否か？（分類）として本件を解くことで、現実的な正解率で長時間滞留の課題に解を出すことができた。

- 46 -

方法を探り,解くことができる問に変換する
ビジネス現場には、先達が挑戦したが、解くことができなかった問が多く存在するのが現実である。その背景から、普通の解き方では解けないことのほうが多い。そのような時にこそ、目的に立ち返り、目的との整合性、出口戦略を意識した手法の選定が重要である。

3-2 機械学習と最適化のビジネス適用に向け解くべきで、解くことができる問を見出すためには、ビジネス・データ・手法を行き来し、三者がうまく重なるように「ビジネス要件を譲歩する」、「不足データを追加採取する」、「解き方・手法を変更する」といった調整が必ず必要となる。
機械学習や最適化のビジネス適用が PoC で止まってしまう大きな要因として、この調整が実施されず、ビジネス側が過大な要件を突きつける、追加データが一切採取できない、エンジニアがある特定の手法にこだわり続ける、といった場面を数多く目にした。
この３者をバランスよくコントロールして、世の中をより良くするユースケースを一つでも多く生み出す事が最適化や機械学習を扱うエンジニアの使命だと考える。

3-4 最後に機械学習や量子コンピューティングを含む最適化の技術は、労働人口減少、排出ガス削減等の社会問
題を解決し、この世界をより良くする為に必要不可欠なものであると信じている。
こういった技術の活用を推進する市民データサイ
エンティストをオンラインで 250 万人以上も輩出し、著者も多大な影響を受けた Stanford University のAndrew Ng 氏の言葉を引用し、本稿の結びとしたい。

“I hope that you find ways to use machinelearning not only to make your life better but
maybe someday to use it to make many otherpeople's life better as well.” [8]4図 5）ビジネス・データ・手法のコントロール

参考文献[1] McKinsey Global Institute,
Notes from the AI frontier: Modeling the impact ofAI on the world economy,” 2018.
https://www.mckinsey.com/featuredinsights/artificial-intelligence/notes-from-the-aifrontier-modeling-the-impact-of-ai-on-the-worldeconomy.
[2] Gartner Research,"Citizen Data Science Augments Data Discovery

3-3 鶏と卵技術のビジネス適用で散見されるもう一つの課題が「鶏と卵」問題である。
機械学習や最適化を適用したくとも、十分なデータが無い、というケースは多い。一方で、データを採取するためには、機械学習や最適化のテーマが必要。といった問題である。
著者の経験では結局、今、何か。を始めなければ鶏と卵の無限ループを抜け出すことはできない。
何を、どのレベル（施策の範囲、レベル、精度）で始めるべきかの鍵は結局、ビジネス現場の最前線にしかない。
労務時間に影響ある滞留時間は概ね 30 分という知識は、物流を担う配送員から得た一次情報に基づいたシミュレーションで算出した結果である。
現場の勘と経験以上に強力な武器は無い。
機械が人から学習し、機械が最適化するのは人の行動であれば、人から謙虚に学ぶ事が最善の策であることは自明である。また、こういった姿勢
がエンジニアには求められる。

- 47 -and Simplifies Data Science,” 2016
https://www.gartner.com/en/documents/3534848.
[3] DataRobot, Inc,https://www.datarobot.com/.
[4] H2O.ai,
https://www.h2o.ai/.
[5] P. a. D. V. Toth,
The vehicle routing problem. Society for Industrial
and Applied Mathematics, 2002.
[6] Gurobi Optimization, LLC.,
https://www.gurobi.com/.
[7] Google,"Google OR-Tools,"
https://developers.google.com/optimization/.
[8] Andrew Ng,"Machine Learning," Stanford University,
https://www.coursera.org/learn/machine-learning.

<MCPC 量子コンピュータ推進 WG 2019>

量子アニーリングで切り拓くモビリティ社会の未来
寺部雅能

株式会社デンソー
MASAYOSHI.TERABE.J6A@jp.denso.com

Our challenges for mobility society by using quantum annealer
Masayoshi Terabe
DENSO CORPORATION
論文概要

デンソーは 2015 年から自動車業界での量子アニーリング技術活用を目指した応用研究を進めている。タイでの交通流最適化をはじめとしたモビリティサービス分野や，工場での無人搬送車の稼働率向上といった工場分野での実証実験の事例を切り口に，今後の量子コンピューティング分野の産業応用の展望を示す。
Keyword: Industry4.0, Society 5.0, CASE, MaaS, Factory IoT, Quantum Annealing, Quantum Computing

1. はじめに自動車業界は今 100 年に一度の変革期にあると言われている。自動運転，電動化，コネクティッド化など技術的な革新が進んでいくが，これらは単純な技術の変化のみではなく，市場がモノからモノ＋サービスへと変化するきっかけを与える。自動運転の例で言えば，誰かが自動運転車を活用した過疎地での搬送サービスを思い付くかもしれない。電動化の例で言えば，街中に大きなバッテリーが動き回っていると考えれば，電力輸送のサービスを思い付く人がいるかもしれない。この分野のインパクトを示す
分かり易い事例としてタクシーの配車サービスを手掛ける UBER Technologies 社が創業たった 5 年半で一部の自動車メーカを超える時価総額になった[1]ことからも，サービス市場の大きな広がりのポテン
シャルを感じることができる。コネクティッドサー
ビスは車のコネクティッド化（IoT 化）を源泉に起こる。

図 1）IoT の進化

図 1 に IoT の進化を示すが，未来の競争力の源泉は最適化であると言われている[2]。IoT の進化にはまずデータ収集のためにセンサを導入する Step1 モ
ニタリングが あり， その次にデ ータを活 用する
Step2 制御がある。車の IoT は得られたデータを何に使うかという Step2 あたりにおり，工場の IoT で言えばセンサを導入していく Step1 あたりにいる。
その先に大量のデータをうまく処理して価値を導出するビッグデータ解析である Step3 最適化がある。
そのため，最適化の真価が発揮されるのはまだこれ- 48 -

からとなるが，ここに最適化を将来超高速に解ける
可能性のある量子アニーリングマシンを導入することによって，今までのコンピュータでは実現できな
かった様なサービスが創出できる可能性がある。この可能性を検証する目的でデンソーでは，車および工場分野で“Optimize the moment”というコンセプ
トで実証実験を行っている。これは，量子アニーリ
ングマシンによる究極の最適化によって，瞬間瞬間を最適化することで新しい価値の創出に挑戦するという目標を示したものである。

適値探索の計算が必要になるため，従来コンピュー
タでは計算に 1 か月以上もかかることもある。これをもし量子アニーリングマシンの導入によって 1 分程度で解くことができれば，これまでは単なるシミュレーションに留まっていた渋滞解消計算が本当に街中の車を制御して渋滞を解消できるシステムへと生まれ変わる可能性がある。
図 3）渋滞を解消する最適化問題

図 2）実証実験のコンセプト動画

車および工場の IoT のどちらの分野もサイバーフィジカルシステムと呼ばれる，モノの世界（フィジカル空間）をデータ化してクラウドの世界（サイバー空間）で最適化することにより，再びモノの世界を制御するシステムを基本にしており，サイバー空間での信号処理に量子アニーリングマシンを活用する。
2. モビリティサービス分野での挑戦
車両台数の増加に伴い，渋滞は大きな社会問題となっている。世界有数の渋滞都市であるバンコクの
例では，運転時間の 57%が停車時間であり，1 年で 21
億時間のロスを生んでいる。更には渋滞によって緊
急車両の到着が遅れることで人命の助かる可能性は大きく減少し，CO2 排出量が年 100 万トン増加するなど，付随する大きな負の影響があるため，渋滞を解消することができれば経済効果だけでなく，命や環境を守ることにも繋がる可能性がある。
街中の車を制御して渋滞をなくすという問題は最適化問題として定義できる[3]。例えば，各車両が 3通りの経路候補を持つ場合に，各車の経路の組み合わせの中で最も重複の少ない，つまりは最も渋滞が少ない組み合わせを求める問題として定義できる。
この例では，車 1 台では 3 通りの組み合わせであるが，車 2 台では 32=9 通り，と指数関数的に組み合わせが増大していき，たった車 30 台で 200 兆通りの最- 49 -

実証実験は豊田通商株式会社と TOYOTA TSUSHONEXTY ELECTRONICS (THAILAND) CO., LTD.が運用する商用の MaaS（Mobility as a Service）アプリケ
ーションである T-SQUARE を用 いている[4]。TSQUARE ではバンコク市内のタクシー，トラックと言った商用車 13 万台に専用の位置情報発信機がついており時刻と位置情報をトレースできる。商用車は24 時間，様々な小道を通るため，プローブデータとしての網羅率が非常に高く，更には T-SQUARE 独自の解析技術によって高精度な渋滞情報を提供している。
また，併せてタクシー会社への配車アプリケーショ
ンや，運送会社への配送計画アプリケーションの提供も行っている。
渋滞解消の例では，入力として過去の移動履歴データから，発車場所と到着場所を取り出して使用する。各車の取り得る複数ルートの組み合わせを最適化することによって経路の重複が少なく，全員が早く到着することができるかというシミュレーションを行うことができる。実際のサービス提供には，各々の車の位置とナビゲーションでセットする目的地情
報を吸い上げ，各車のナビゲーションへ経路情報を伝えるシステムを街中の車に搭載する必要がある。
上述のような未来の交通システムだけでなく，渋滞に関わる目の前の現実的な問題にも取り組んでいる。渋滞を考慮した交通流最適化の一例として図 4に示すような渋滞時刻の過去データから未来の渋滞を予測し，その情報を元に効率的な配送を計画する
問題に取り組み、問題の実装技術の提案を行った。
[5]図 4）渋滞予測情報を鑑みた配送計画問題

滞の起こった回数である。量子アニーリングマシンを活用することにより，従来の排他制御と呼ばれる方法より稼働率が 15%改善することがシミュレーシ
ョン上で確かめられている。
図 6）工場での無人搬送車の稼働率向上実証

その他，早稲田大学田中宗准教授と未来のモビリ
ティサービスを想定した問題の実証を行った[6]。自動車業界では移動の効率化を目指してシェアリング
サービスが広がりを見せている。シェアリング効率を高めていく中で将来は 4 人乗りの小型車から数十人乗りの大型車まで様々な移動手段を活用したシェ
アリングが進展し、それらを乗り継ぐようなマルチ
モーダルライドシェアサービスが考えられる。そう
いった社会を想定し、量子アニーリングで実装，評価を行った。問題は複数の乗客が小型車によって中継地点まで移動し，そこから大型車で次の中継地点に移動，最後にそれぞれの目的地まで小型車で乗客が移動していくという設定で行った（図 5）。小さな問題規模では D-Wave マシンが従来コンピュータより高速に動作することが確かめられた。
図 5）マルチモーダルなライドシェアサービス

3. 工場分野での挑戦
渋滞は街中だけでなく，工場の中でも発生する。
工場の中で走行する無人搬送車（AGV, AutomatedGuided Vehicle）の渋滞解消によって稼働率向上を目指した実証実験を東北大学大関真之准教授と行った[7]。図 6 で黒い線路上に置かれた四角が AGV であり，10 台が走っている。青丸の大きさで示すのが渋4. 課題と展望
以下，ハードウェア，ソフトウェア，アプリケー
ションの 3 階層での課題について説明する。
4-1 ハードウェアの課題
先述した問題の実装規模の向上が第一に挙げられる。その解決の方法として，ハードウェアの観点ではビット数の増大や，量子ビット間の結合数の増大が挙げられる。D-Wave Systems 社によれば，どちらも次世代機で大きく改良予定であると言う。我々はそれらのハードウェアの進化のみでなくソフトウェ
アの進化にも期待している。従来コンピュータでの前処理によって問題を量子アニーリングマシンで解くべき範囲にシュリンクしたり，図 4 で示したように問題を部分問題に分割して量子アニーリングで部
分問題を解きながら後処理で結果を結合するというような従来コンピュータと量子アニーリングマシンのハイブリッドコンピューティング技術にデンソー
は取り組んでいる[8,9]。
4-2 ソフトウェアの課題
量子アニーリングマシンを使うには，解きたい問
題をイジングモデルという一般人には馴染みのないモデルに問題をモデリングする必要がある。これが問題の実装を難解にし，マシンの普及を阻害している要因でもあるため，ハードウェアを意識せずにア
プリケーションを実装できるようなミドルウェアが出てくることが望ましく，世の中では 1QBit 社や Jij社などが取り組んでいる。

- 50 -

4-3 アプリケーションの課題
既存のアプリケーションの多くは既に従来のコンピュータで実装できているため，量子アニーリング
マシンを使って解くべき価値のある，技術的難度の高い未来のアプリケーションを創造する必要がある。
冒頭に述べた UBER Technologies 社の事例のように，異分野との融合で新たなコネクティッドサービスが生まれていくと考えられるため，実証実験のみでな
く積極的な社外発信により量子アニーリング技術をわかりやすく伝えることで，一緒に取り組む仲間を増やしながらアプリケーションを協創する挑戦にデンソーは取り組んでいる[10]。
上述の様な様々な課題解決に向け、MCPC の量子コンピュータ推進 WG をはじめ、量子アニーリング研究
開発コンソーシアム(図 7)など様々な団体が立ち上がり始めており、デンソーはそういった団体を活用しながら量子アニーリング分野の発展を推進していく考えである。
図 7）量子アニーリング研究開発コンソーシアム

5. おわりに
量子アニーリングマシンはハード・ソフトともにまだ未成熟な分野ではあるが，車や製造をはじめとした様々な世界にゲームチェンジを起こす破壊的技術となりえる。今回紹介した渋滞解消は一つの例でしかなく，渋滞解消により環境を良くしたり，多くの人命を救ったり，と社会レベルでの最適化によってこれまで想像もしなかったような価値が生み出すことができる可能性がある。実際に IT 企業や金融など様々な分野での実証実験が始まってきており[11]それらの分野が融合して新しい価値を生み出してい- 51 -

く日も現実的なものになってきたと感じる。この記
事で量子アニーリングを知った方々にぜひ挑戦の一歩を踏み出して頂きたい。
図 8）デンソーの目指す未来像：社会の最適化

6. 参考文献[1] Liyan Chen, Forbes, 2015,
https://www.forbes.com/sites/liyanchen/201
5/12/04/at-68-billion-valuation-uber-willbe-bigger-than-gm-ford-andhonda/#5c3b0e9d32e3[2] Michael E. Porter and Heppelmann, Diamond
Harvard Business Review, 2015,
http://diamond.jp/go/pb/dl/150520_PTC.pdf[3] Florian Neukart et al.,” Traffic Flow
Optimization Using a Quantum Annealer”
frontiers in ICT, 2017https://www.frontiersin.org/articles/10.33
89/fict.2017.00029/full[4] T-SQUARE website
https://www.rticthai.info/tsquare/traffic-application/[5] Hirotaka Irie et al.” Quantum Annealing of
Vehicle Routing Problem with Time, State andCapacity” QTOP, 2019https://link.springer.com/chapter/10.1007/
978-3-030-14082-3_13[6] Akira Miki, “Route Optimization for
Multimodal Transport Systems”, QUBITS
Europe 2019https://www.dwavesys.com/sites/default/fil
es/9_190322_Qubits_AkiraMiki.pdf

[7] Masayuki Ohzeki et al., “Control of
automated guided vehicles without collisionby quantum annealer and digital devices”，
frontiers in computer science, 2019https://www.frontiersin.org/articles/10.33
89/fcomp.2019.00009/abstract[8] Shuntaro Okada et al., “Improvin solutions
by embedding larger subproblems in a D-Wave
quantum annealer”, Sci. Rep. 9, 2098 (2019)https://www.nature.com/articles/s41598018-38388-4[9] Shuntaro
Okada
et
al.,
“Efficientpartition of integer optimization problems
with one-hot encoding”, Sci. Rep. 9, 13036(2019)
https://www.nature.com/articles/s41598019-49539-6[10]デンソー量子コンピューティングチーム
ウェブサイトhttps://www.denso.com/jp/ja/innovation/tec
hnology/quantum/[11]
寺部雅能 大関真之, “量子コンピュータ
が変える未来”, オーム社, 2019https://www.amazon.co.jp/量子コンピュータ
が変える未来-寺部-雅能/dp/4274223728/- 52 -

<MCPC 量子コンピュータ推進 WG 2019>

AI による予測と組み合わせ最適化の業務適用
田中 孝
株式会社グルーヴノーツ

Business application of prediction by AI andcombination optimization by Quantum Computing
Takashi Tanaka
Groovenauts, Inc.
https://www.groovenauts.jp/「来客数の予測」に対して「従業員のシフトを最適化する」のように，AI による予測と量子コンピュータを活用した組み合わせ最適化は，業務課題や社会課題を解決する多くの可能性をもっていると当社は考えている。AI による未来の予測と，量子コンピュータを活用した組み合わせ最適化の社会適用について，一般的な技術背景や業務課題・社会課題を解決するアプローチについて記述する。

Keyword: MAGELLAN BLOCKS, Machine Learning, Deep Learning, AI, Optimization, Data Lake, Consulting,
City as a Service

1． AI とは何か
1）日常にあふれる AI
AI（Artificial Intelligence）は，日本語に直訳すると人工知能，つまり「人工的に作られた知識・知性・知能」となる。これは，「賢い IT（Information
Technology）」を作るための一つの技術として，さま
ざまな領域で使われていることはご存知であろう。
たとえば，スマートフォンの中には，AI を活用したアプリケーション（以下，アプリ）がたくさんインストールされている。多くの人が利用するカメラ
アプリ（顔の自動認識や，明るさの自動調整，ぼかし機能などが搭載されている）もしかり，音声認識や合成音声を使ったアプリ，ウェブの検索（Google
検索など）も，AI が使われたサービスの一つである。
このようにとらえると，私たちは日常生活のさま
ざまなシーンにおいて，AI を利用しているといっても過言ではない。

2）AI が提供するもの
AI を活用したサービスやアプリが身の回りにあふれているのは前述したとおりであるが，では AI- 53 -という技術は，具体的に何の役に立つのであろうか。
結論からいうと，AI はさまざまなものを計算が可能な数値に置き換える，ということを得意とする。
これは，専門用語で「ベクトル化」といわれる。音
声や画像，文字，言語など，さまざまな種類，基準の異なるデータをベクトル，つまり高次元空間上の指標としてとらえて数値化する。これにより，さまざまなものの分類，比較，処理などが実現できるようになる。
たとえば，赤いリンゴと黄色いバナナといった形
状や色も割と異なる 2 種類のものを見分けることは，人間にとっても容易だと考えられる。しかしそれが，これまで見たこともない 10,000 種類の果物を比較して分類するとなると，人間にとっても非常に困難な作業である。この点，AI は 10,000 種類の果物をベクトル化できることで，それぞれの類似度を比較した
り，大きさや色といったさまざまな観点で並べ替えたりすることが可能となる。
すなわち，人間が処理しきれないような膨大な情報をコンピュータが計算可能な形式に変換する技術，
これが AI である。これにより，人間にはできない
大きな問題を解くことが可能とされる。

3）ベクトル化の具体例「ベクトル化」を分かりやすくイメージで掴むとすれば，図図 1 のように表現できる。また，一般公開
されているサービスでは，次のような例が挙
げられる。

図1

画像のベクトル化（1）鳥の声をベクトル化した例 [1]https://experiments.withgoogle.com/ai/bird-sounds/view/（2）写真（インカメラの映像）をベクトル化する
例 [2]
https://teachablemachine.withgoogle.com/（3）単語をベクトル化する例 [3]https://projector.tensorflow.org/

4）AI と BI
AI と BI（Business Intelligence）は似たような文
脈で使われることも多く，一度は耳にした用語であろう。どちらの技術ももっているデータを活用するための技術であるが，大きく異なる点として
次が挙げられる。
⚪

AI：コンピュータで判断する
そのために多くのデータから学習を行う⚪

BI：人間が判断する
そのために人間が理解しやすいように
可視化（ビジュアル化）を行う

世の中の社会課題や業務課題においても，さまざ
まなデータが溢れていると想像される。購買の履歴
や店舗・設備の運営に関わるデータなど，さまざまな形式・粒度のデータがある。こうしたデータを業
務でどのように役立てたいか，その目的と各技術の特徴を鑑みた上で，BI と AI の活用を使い分けられるとよいとされる。

2． 量子コンピュータを活用した組み合わせ最
適化とは何か組み合わせ問題の例示としてよく挙がるのが「巡回セールスマン問題」である。セールスマンが複数都市すべてを一度訪問して出発点に戻るとした場合，その最短経路を導き出せ，というものである。この問題の難しさは，制約条件が設けられていることにある。
つまり，全都市を訪問すること，各都市は一度しか訪問しないこと，移動距離が最小となることといった具合で，世の中の事象はこうした多くの制約条
件によって成り立っている。
組み合わせ問題を業務に置き換えると，シフト最適化（金融業などにおけるコールセンターのオペレ
ーターシフト，運輸業における乗務員シフト，医療業における看護師シフト，大型・多店舗などの小売業における勤務シフトなど）やルート最適化（運輸・小売業の配送に関わる最短ルート）などがある。
たとえば，50 名を対象にしたシフト組みにおいて，各自の労働条件や勤務希望，その日に必要な人員数やスキル条件，さらにはシフト運営上の独自ルール，
各人の相性など，多くの制約条件を加味した上で，すべてのパターンを厳密に計算しようとなると，直ちに数兆通り以上の組み合わせになる。
これをコンピュータで全通り計算すれば，数日から数年かかるような計算量へと膨れ上がり，事実上は不可能となる。これが「組み合わせ爆発」といわれるものである。
現状の通常業務では，現場の知見や経験によって最適であろう組み合わせが選択されていることが多いが，こういった業務は属人化の課題を常に抱える。
かつ，どの程度最適化されたものになっているかを判断することも難しい。そこで，こうした組み合わ
せ爆発の問題を瞬時に解くために研究開発が進んでいる技術が，量子アニーリング方式の量子コンピュータ（Quantum Computing）である（以下は，量子コンピュータと称する）。

3． グルーヴノーツの提供するサービス
1） 先進テクノロジーを駆使した 2 つの事業
株式会社グルーヴノーツ（以下，グルーヴノーツ）- 54 -

では，AI や量子コンピュータを業務に活用できるクラウドプラットフォーム「MAGELLAN BLOCKS（マゼランブロックス）」事業と，学童保育（アフタース
クール「TECH PARK（テックパーク）」）をはじめと
図 2）。
するテクノロジー教育事業を展開している（図図 4 「MAGELLAN BLOCKS」利用企業例（1）データを集める（図図 5）
さまざまなシステムや帳票などに点在するデータを一元管理したり，一箇所に集めたりするための機能である。また，AI で扱えるようにデータを加工する（欠損値の補完など）機能も提供している。

図 2 AI と量子コンピュータの業務活用，そして教育

2）業務の現場で活用できる AI を目指す
「MAGELLAN BLOCKS」「MAGELLAN BLOCKS」では，SaaS（Software
as a Service）型のクラウドプラットフォームとして図図 3 で示すソリューションを提供する。サービ
ス開始以降，累計 3,800 社が利用し，12,500 以上の AI 学習モデルが作られる（2019 年 9 月時点）など，国内有数の実績をもつ。加えて，量子コン
ピュータの商用サービス化は，グルーヴノーツが世界で初めて実現した（2019 年 3 月時点。D-Wave
System, Inc. 調べ）。

図5（2）AI で予測する，分類する（図図 6）
前述のとおり収集した手持ちのデータを AI に学習させることで，未来の予測や事象の分類を行うための AI 機能である。
「MAGELLAN BLOCKS」では，モデルの定義・作成やパラメータのチューニングな
ど，AI 技術を扱う上で難度の高い要素を自動化，もしくはユーザーが意識することなく手軽に AI 予測
モデルを作成できるようにしている。
これにより，Ⅰ）データを作る→Ⅱ）AI 学習モデ
ルを作る→Ⅲ）予測する→Ⅳ）予測精度を確認する→Ⅴ）精度向上のためデータを洗い出す→Ⅵ）最初のⅠ）に戻るといった，AI 活用に欠かせないステップの繰り返しが容易に実現でき，高精度の AI を作ることが可能になる。

図 3 「MAGELLAN BLOCKS」で提供する
ソリューション

- 55 -

図7
図6

4．
「MAGELLAN BLOCKS」による AI 活用事例
（3）最適解を導く（図図 7）
業務の制約条件を，日頃利用する表計算ソフトなどにて整理するだけで，通常のコンピュータでは解くことのできない（現実的な時間内で解けない）問
題を，量子コンピュータを用いて最適解を導くソリューションを提供する。
組み合わせ最適化問題には，次のようなものが挙げられる。これらの最適化問題を掛け合わせること
で，さまざまな社会課題やビジネス上の課題を解くことが可能となる。

グルーヴノーツの「MAGELLAN BLOCKS」を利用して，AI や量子コンピュータで業務課題を解決している事例の概要をいくつか紹介する。

1）株式会社グッデイ：仕入れ予定の花の状態
図 8）を AI が自動判定 [4]（図九州でホームセンターを展開する株式会社グッデ
イは，仕入れ先から送られてくる花の画像を AI で自動的にランク付けする仕組みを実現した。仕入れ基準を統一できるようになったことで，園芸に関する専門知識を持たない社員も仕入れ業務を担うことが可能になった。
また，仕入れ先から送られてくる画像を自動判定するため，現地訪問の必要がなくなり，業務効率も向上した。

⚪ ルート最適化（どの車両・モノ・人が，どの場所を，どのような順番・経路で移動すればよいか）⚪ シフト最適化（よく挙げられるのは「ナーススケジューリング問題」）⚪ ジョブ割当（仕事を人に効率よく割り当てる）など一般的に，量子コンピュータを活用した組み合わせ最適化問題のアプローチには, Ⅰ）問題の定義が難しい，Ⅱ）量子アニーリングマシンに渡す形式（イジングモデルや QUBO（Quadratic
unconstrained binary optimization））に変換するのが難しい，という課題がある。
この点「MAGELLAN BLOCKS」では，実業務に即した分かりやすいユーザーインターフェース設計などによって問題の定義が容易に可能，かつイ
ジングモデル・QUBO の作成を必要とせず，組み合わせ最適化問題の解決が可能である。

図82）株式会社ジェーシービー：コールセンターの入電数を AI で予測，配置計画を最適化[5]日本発唯一の国際カードブランドである株式会社
ジェーシービーは，ユーザーからの相談や質問に応えるため，東京を始めとする全国に複数のコールセ
ンターを設置している。
日や時期によってその入電数は変動するため，それに応じたオペレーターの配置計画を立てる必要が- 56 -

あるが，これまで，その計画の足場と入電数の予測
は特定の従業員が担当しており，知識・ノウハウが属人化する傾向にあった。個人の知見に頼る部分が多く，異動や退職の際のスムーズな引き継ぎが難しいことが課題とされていた。
「MAGELLAN BLOCKS」を利用し，ある拠点の
過去 2 年分の入電データを学習させた実証実験（PoC：Proof of Concept）では，99.8％の精度を獲得。
極めて信頼度の高い配置計画を立てられることと，また，データさえあれば，特定の従業員でなくとも誰もが正確に入電数を予測できることが可能であると思われ，現在，本格的な導入と複数部署・拠点への展開を計画している。

3）三菱地所株式会社：AI と量子コンピュータを活用したルート最適化による CO2 排出量削減（低炭素化）や人手不足の解消 [6]（図図9）の最適化が可能になる。エネルギーの消費量予測から最適なエネルギー・ミックスの選択，移動需要の予測からタクシー配車の最適化，店舗の売上予測とレイアウトの最適配置といった具合に，「MAGELLAN BLOCKS」が，分析・予測・最適化
をシームレスに実現可能なソリューションとして研究開発・進化を重ねる点はここにある。
この AI と量子コンピュータの組み合わせこそ，多くの業務課題や社会課題の解決につながるものと考える。実に，当社にご相談いただく企業・団体様においては，業務効率や成果の最大化に向け，AI による予測または組み合わせ最適化をしたいといった単体の取り組みよりも，Ⅰ）データ統合と可視化，Ⅱ）AI による未来の予測，Ⅲ）組み合わせ最適化の一連のステップに着目し，プロジェクトを一緒に始める
ケースが増えている（図図 10）。

三菱地所株式会社は，丸の内・大手町・有楽町地
区に多くのビルを保有する。この各ビルで発生するゴミの量の把握，未来に発生するゴミの量の予測，
ゴミ収集車ルート最適化により，社会問題となっている CO2（二酸化炭素）排出量の削減をシミュレー
ションするプロジェクトを立ち上げた。
本プロジェクトには，グルーヴノーツがテクノロ
ジーパートナーとして選定されている。
図 10

こうして AI と量子コンピュータの活用事例が広がることで，次には，企業単体ではなく都市全体の最適化の実現を目指す動きが加速する。多業種多企業の連携を図り，都市全体を一つの空間ととらえてサービス化を図る「City as a Service」である（図図 11）。
図9

5．AI と組み合わせ最適化の実現と，グルーヴ
ノーツの考える課題解決コンセプト「City as a Service」「MAGELLAN BLOCKS」の活用事例でお気付きなった方もいると思うが，AI による予測と，予測結果に基づく量子コンピュータによる業務の最適化には一連の流れがある。
むしろ，正しい未来の予測をベースとして，業務- 57 -

図 11「City as a Service」のコンセプト

都市（社会）は，多様なサービスが複雑に混ざりあった空間であると定義することができる。スマー
トシティにて掲げられるエネルギー効率の最適化など，特定の分野・技術の追求による機能的価値に加え，情緒的価値の向上も欠かせない。
それが「豊かな人間性にあふれた街」であり，たとえば人の 1 日の活動において利用されるさまざまなサービスも， AI による予測と量子コンピュータ
による組み合わせ最適化によって，一人ひとりに合った快適な体験として提供されるようになること。
そうした私たちがより豊かに生活できる世界づくりを，当社はさまざまな行政・団体・企業などと協働しながら目指していく。

[6] 三菱地所株式会社: 「丸の内データコンソーシアム」を設立, 2019 年 9 月 12 日,
https://www.mec.co.jp/j/news/archives/mec190912_d
ataconsortium.pdf
株式会社グルーヴノーツ: 三菱地所，グルーヴノーツを事業革新のテクノロジーパートナーに，共同で廃棄物収集ルートの最適化データ解析を開始, 2019 年 9 月 12 日,
https://www.groovenauts.jp/2019/09/12/information43/

6．おわりに
このように AI や組み合わせ最適化によって，今私たちが直面する業務課題を解決できることをご理解いただければ幸いである。また，AI や組み合わせ最適化は，あくまでデータを活用するための道具（ITツール）であって，読者自身や自社内にあるデータなどからどういったことができそうかと，想像してみていただきたい。それを常に意識して業務を俯瞰してみると，さまざまな気付きが生まれてくると思う。
当社としても，日本の企業の一員として，量子コンピュータの活用推進において可能な限りの力を尽くしていきたい所存である。興味をお持ちいただけ
るようなら，ぜひとも一緒に新たなチャレンジに取り組めることを楽しみにしている。

参考文献[1] Google LLC: BIRD SOURND,
https://experiments.withgoogle.com/ai/bird-sounds/view/[2] Google LLC: TEACHABLE MACHINE,
https://teachablemachine.withgoogle.com/[3] Google LLC: TensorFlow,
https://projector.tensorflow.org/[4] 株式会社グルーヴノーツ: 九州でホームセンタ
ーを展開するグッデイによる，店舗運営におけるデータ・AI 活用事例もご紹介, 2019 年 10 月 23日,https://www.groovenauts.jp/2019/10/23/information49/[5] 株式会社グルーヴノーツ「MAGELLANBLOCKS」：利用事例 株式会社ジェーシービー,
https://www.magellanic-clouds.com/blocks/customers/jcb/- 58 -

<MCPC 量子コンピュータ推進 WG 2019>

全体最適とパーソナライズの両立を目指して
菊池 新*1

小田中 育生*1

株式会社 ナビタイムジャパン*1

To Strike a Balance of Total optimization and Personalization
Shin Kikuchi *1

Ikuo Odanaka *1

NAVITIME JAPAN Co.,Ltd.*1

道路交通の渋滞、鉄道の混雑が常態化する都市部では大きな経済損失が発生している。一方, 地方部では
公共交通の維持が困難になるといった課題がある。前者に対しては全ての移動者の移動手段を分散させ全体最適化する, 後者に関しては膨大な移動ログからダイヤ最適化を行う, 検索ログから観光資源を発掘するといった取り組みが考えられる。また, 全体で最適化しながらも個人の嗜好性を加味することが求められる。
これらは大規模なリアルタイムデータを扱うため, 組合せ爆発により古典コンピュータのキャパシティを超えることが予想される。未来の交通があるべき姿を量子コンピュータによって実現する方法を模索する。
Keyword: 交通最適化, パーソナライズ, ナビゲーション, 巡回経路探索

1

日本における交通の課題

1-1 都市交通が抱える課題
全国で年間に発生する渋滞損失を貨幣価値換算す
ると, 約 12 兆円にも上るといわれている。また(株)ナビタイムジャパン独自の試算によると, 満員電車の経済損失は年間 3,240 億円に上る。こういった数
値からもわかるように都市部における交通は混雑・渋滞が常態化しており, 日々経済的な損失を発生させている。(株)ナビタイムジャパンでは, 図 1 にあるような道路交通の渋滞緩和を狙った施策, 図 2 にあるような鉄道混雑の可視化・混雑を回避する経路の提供を行っている。前者については渋滞緩和を狙った施策「ナビタイムマイレージ」利用者の渋滞走
行比率が 10%減少, 後者についても混雑回避ルート
が選択肢に出現した際には数%程度のユーザーが回避ルートを選択した実績が報告されている。

- 59 -

図 1: 渋滞緩和を狙ったインセンティブ付与の例

図 2: (株)ナビタイムジャパン提供の鉄道混雑情報

図 3: 外国人ドライブ観光客の位置情報取得状況

図 5: AI を活用したルート検索のイメージ
図 4:自動運転電動カート対応のルート案内
1-2 地域公共交通が抱える課題
地域公共交通が抱える課題は, 需要集中による課題を抱える都市部とは対照的なものである。都市部
への人口の流出, モータリゼーションによるマイカ
ー社会へのシフトなどが複合的に作用し地域公共交通の衰退を招いている1)。高齢化がこの問題の深刻化に拍車をかけている。公共交通が衰退しているため運転に危険を覚える年齢になっても免許証を手放すことができない, いざ手放してしまうと移動へのハードルが高くなり外出が極端に減ってしまうといった形で問題が顕在化している。その問題を解決するアプローチとしては大きく2種類に分けられる。
1. 域外から域内への誘客を行い, 新たな収益源を創出する
2. 維持コストの低減, 効率化を行い現状の地域生活を大きく変化させずに公共コストを維持する
2017 年に(株)ナビタイムジャパンと北海道開発局が共同で開発したスマートフォン用アプリケーション「DriveHokkaido!」では外国人ドライブ観光客の位置情報データ可視化, 分析を行い 1. の解決にアプローチしている(図 3)。
また、2019 年には永平寺町で行われる自動運転電動カートを用いた実証実験に対してルート案内を提供している(図 4)。この実証実験は 1.の意味合いもあるが, 自動運転を導入することで人件費を削減し地域交通を維持させたいという 2.の視点での実験が日
本各地で行われている。

2 ナビゲーションサービスのユーザー
2-1 ユーザーが求める経路
公共交通利用者向けのサービスとしては乗換案内があり, また自動車を運転するドライバー向けのサービスとしてはカーナビゲーションがある。ユーザ
ーが出発地と目的地を入力すると経路が返却される
こういったサービスでは, ユーザーに対して複数の経路を提示することが一般的である。乗換案内では「時間・運賃・乗換回数」, カーナビゲーションでは「推奨・高速・一般道」のような選択肢が提示される。これは, 最適な経路が一意に定まるものではな
く, ユーザーのニーズによって最適さが異なるため
である2)。(株)ナビタイムジャパンのカーナビゲーションサービスでは更に踏み込んで, AI を活用したルート検索を提供している。これはユーザーごとの走
行データから走行の傾向を分析しその傾向にあわせた経路を提供する機能になる。
2-2 ユーザーはメリットがある経路を選ぶ
2-1 で示したようにユーザーが経路に求めるニーズは様々な種類がある。ユーザーは自分にとってメ
リットがある経路を選択する。都市交通の課題を解決するために全体最適をしよう, ユーザーがどこを走行するかシステム側で分散させようとしてもユーザーがそのとおり行動するとは限らない。実際, カーナビゲーションサービスの移動ログを確認すると提供された経路とは異なる経路を走行しているユーザーが散見される。このことから, 全体最適により- 60 -

図 8: GPU を利用した経路探索改善の例
図 6: パラメータ数と経路組合せ数

図 7: 中長距離での間引き例
混雑や渋滞の緩和を目指すにあたってはマクロ視点
での最適化のみ考慮するのではなく, 個人個人の移動に対する嗜好を考慮する必要があるということがわかる。
3 組合せ爆発する経路
3-1 大規模データと経路探索
経路探索は膨大なデータのうえで実現している。
車向け経路探索のデータを確認してみると, リンク(交差点と交差点をつなぐ一本の道路。経路探索はこの単位で行われる)の数は全国で 2,700 万本程度にも上る。このリンク 1 つ 1 つに旅行時間(リンクを通過するのにかかる時間), 幅員, 接続しているリンク,
道路種別(高速, 国道など)といった情報が付与され,それら情報を総合的に用いて経路を算出している。
乗換検索の場合はこういった空間的ネットワークに加えて時刻表の考慮が必要になる。図 6 が示すように考慮するパラメータの数に対し経路の候補は指数関数的に増加していくことになる。つまり, 検索する距離が長くなったり, 考慮するべき要素が増加したりすると計算時間が増大し経路提供までのレスポ
ンスタイムが悪化してしまうのだ。実際のサービスにおいては長距離の経路探索を行う際には検索の対
象を主要道路のみに絞る, といったデータ面での間引き処理によりレスポンスタイムの急激な悪化を抑- 61 -

図 9: 経路探索の要素えている(図 7)。
3-2 GPU を利用した経路探索
2019年7月, (株)ナビタイムジャパンは GPU を活用
して自転車経路探索の抜本的な改善を行った 3)。前
述のような間引きをほぼ行わず、GPU の並列処理によって長距離での計算量爆発を抑えることに成功した。図8はその一例である。自転車向けナビゲーショ
ンサービスでは遠回りする経路に関する指摘がユーザーから寄せられていたが, 本リリース後はほとん
ど遠回りに関する指摘がなくなった。
3-3 それでも増大する計算量
GPU を利用することで, 現時点ではデータ量増大に伴う計算量爆発を克服することができた。しかし
図 9 が示すように最適な経路探索を算出するための要素は数多く存在する。周辺で開催されるイベント
により発生する混雑や渋滞、その日のユーザーの体調など。また、近年では移動の選択肢自体が増加している。たとえばシェアサイクルは都市部を中心に

図 10: SBM での 10 地点巡回経路探索結果
広がりを見せており, コンビニエンスストアに併設されているカーシェア用の駐車場を見かけることも多くなってきた。MaaS(Mobility as a Service)という概
念が人口に膾炙するようになり, 今後もモビリティの選択肢は増加していくと思われる。一方, 経路探索処理にはリアルタイム性が求められるため, 考慮するべき要素が増加していくことで GPU では捌ききれない計算量になる可能性がある。
3-4 量子コンピュータへの期待
2019 年 10 月 23 日には米 Google 社が量子超越性を実証したというニュースが報じられた。このニュースは様々な論争を巻き起こしているが, 近い将来に
量子コンピュータを用いたソリューションが市場を席巻することを期待させるものである。
交通の分野では独フォルクスワーゲン社が北京において交通最適化の社会実験を行うなど、量子コン
ピュータへの視線は熱い。(株)ナビタイムジャパン
では以下のような応用を検討し, 期待している。
1. 個人の嗜好やその日のコンディションなどを考慮した「その日その時その場所でその人に必要な経路」の計算
2. 全体最適経路計算による混雑・渋滞の解消
3. リアルタイムでのデータ分析・学習とレコメン
ド情報の提供
4. 巡回経路探索、ナップザック問題の厳密解を秒単位のオーダーで算出
3-5 カギは量子ネイティブなエンジニアの育成
量子コンピュータをビジネス利用するためには様々なハードルが存在する。そもそもハードウェア
をどうするのか, 動作させるためにはどのようなソ
フトウェアを作成するとよいのか。この点に関しては実際に動かせるソリューションがいくつか存在する。東芝の SBM(シミュレーテッド分岐マシン)は厳
密には量子コンピュータではないが, AWS 上で稼働するイジングマシンだ。図 10 はこの SBM で算出した巡回経路であり, 10 地点を 20 秒ほどで計算していることがわかる。
このように実際に触れるソリューションが現状でも存在することから, 本格的な普及期にはおそらくクラウドサービスで提供されるのではないかと考えている。そうなるとハードウェアの問題はある程度解決される。最終的には量子コンピュータを自在に操るエンジニア, 量子ネイティブなエンジニアの育成こそが量子コンピュータ時代においてビジネスを飛躍させるキーファクターとなっていくだろう。
(株)ナビタイムジャパンでは社内有志による勉強会や先述の SBM を実際に動かす取り組みなどを通してエンジニアの量子コンピュータへの理解を深めている。またオフィスに併設するセミナーホールを量子コンピュータ関連の勉強会に場所提供するなど,分野が広がりを持つための動きに一役買っていると自負している。
全体最適で渋滞や混雑といった社会の課題を解消しながら, 個人のきめ細やかな要望を満たすようなパーソナライズされたサービスを提供する。地域課
題を解決するためのデータ分析をリアルタイムに行いスピーディな施策を打っていく。昨今, 社会が抱える大きな課題となっている物流を組合せ最適化問
題で支えていく。量子コンピュータ時代にはこういった活動が現時点では想像できないような品質で行えるようになることを期待しているし, 我々自身が量子コンピュータを使いこなし世の中の快適な移動体験に資することを目指している。
参考文献
1)国土交通省（H29）, 「過疎地域における地域公
共交通の現状と課題」,
https://www.soumu.go.jp/main_content/000569916.pdf
2)太田 恒平・渡部 啓太・小竹 輝幸・梶原 康至（2016）, 「カーナビが経路選択を左右する」, 第53 回土木計画学研究発表会,
http://consulting.navitime.biz/pdf/monograph_20160529_01.pdf3)Makoto Yoshihama(2018), "Massively parallel shortest
path finding algorithm using GPU", GTC Japan ポスタ
ーセッション,https://twitter.com/navitime_tech/status/10405347611968
10241/photo/1- 62 -

<MCPC 量子コンピュータ推進 WG 2019>

Malware Cyber-Security への量子コンピューティング応用
可能性に関する考察
柏山 正守*a)
MCPC 量子コンピュータ推進 WG 主査
株式会社ゼネテック/慶應義塾大学 SFC 研究所

Discussion on Quantum Computing Applicability for Malware
Cyber-Security
Masamori Kashiyama*a)
論文概要
Soceity5.0 を支えるビッグデータ処理システムは，Exa Flops スケールの高性能コンピュータシステムの導入を必要としている。しかし，ムーア則が終焉した今，高性能コンピュータが要求するプロセッサは，複雑なエンハンス的アーキテクチャ進化が続く。このようなプロセッサ進化は，巧妙な Cyber 攻撃手法にバリエーションを与え，プロセッサ進化を標的とした進化型 Malware の登場が懸念される。そこで，これら進化型
Malware Cyber 攻撃検出に量子アニーリングの最適化処理を応用する考察を行った。本考察のアルゴリズム
は，量子アニーリングマシンの超高速性を生かし，Malware Cyber-Security に新しい可能性を与える。
Keyword: Malware Cyber-Security, TEE, Pattern Match Accelerator, HLAC, Quantum Annealing

1. はじめに
近年，Cyber-Security のリスクが増大している。
Cyber-Security は，Malware 感染，
不正アクセス，DDoS
攻撃などからシステムを防御することであり，これらの脅威は年々増加傾向にある[1]。このような変化の中で，Cyber 攻撃の増加や巧妙な Malware の出現
は，インフラや金融などのミッションクリティカルシステムに大きな脅威である。
図 1.は，これらミッションクリティカルシステムの Cyber-Security に用いられる防御手段の基本的要素を示したものである。通常はクリティカルデータの暗号化や暗号鍵と認証管理を組み合わせた防御手
a) Correspondence to: Masamori Kashiyama, Ph.D. E-mail:masamory@sfc.keio.ac.jp＊
株式会社ゼネテック/
慶應義塾大学 SFC 研究所上席所員

図 1. 防御手段の基本的要素- 63 -

段をシステム側に装備するのが一般的である。さらに昨今は，ハードウェアセキュリティモジュール(HSM)を組み込むことでより強固なセキュリティを確保して行くことがトレンドになりつつある。
図 2.はクリティカルデータのアクセスを防御する
HSM の代表的なソリューション Trusted Execution
Environment(TEE)の社会実装の概要を示した図である 。 TEE と 同 様 な ソ リ ュ ー シ ョ ン に は ， IntelSGX(Software Guard Extensions) や Apple Secure
Enclave[2]があり，これらは 2018 年後半から Cyber
Security のためにコンピュータシステムへ実装されている。

図 3. 過去 42 年間のプロセッサ性能のトレンド[3]図 2. クリティカルデータ保護の仕組み
他方，ビッグデータや AI の隆盛に伴い，より高性能なデータ処理システムの要求が強くなっており，
高性能プロセッサへの期待が大きい。
しかし，近年，図 3.に示すトレンドが示すように，
単体プロセッサの性能向上は限界に近づいており，
引き続き性能向上が期待されるファクターを生かす
アーキテクチャが提案されている。例えば，集積度を生かす取り組みにはメニーコア・プロセッサによる超並列コンピュータ処理などがある。また単体プ
ロセッサの性能向上では，複雑な命令処理機構を取り入れる方向でアーキテクチャが進化している。例
えば，投機的命令実行方式や平均消費電力調整機能，プロセッサ周波数を上げるパワーブースト機能な
ど，複雑な機構を取り入れて性能向上を達成している。これらアーキテクチャの進化は，互換性の観点からどうしてもパッチワークの意味合いが強くなり，ドラステックな処理方式の革新を取り入れることは難しい。最近の Cyber 攻撃は，これら進化の隙を突き，巧妙な手段を創出してコンピュータシステ
ムからクリティカルデータを盗み出す。

2. 課題と既往の研究
2-1 巧妙化するセキュア領域への攻撃 2019 年 12月，衝撃的なニュースが配信された[4]。前述した Intel-SGX のセキュア領域(Enclave)に格納されている暗号鍵などのクリティカルデータを盗み出す手法(Plundervolt)の論文が発表された[5]。その手法は，プロセッサ内部回路の活性化部位を機械語命令列で操作する。これらの組み合わせの影響からプロセッ
サ動作電圧の低下を誘発させ Enclave に格納されている暗号鍵情報を取り出す手法である。盗み出した
暗号鍵を用いてハッカーは，正式に全系システムへ侵入し，制御をコントロールすることが可能になる。また，それ以前に公表されている手法として，
Meltdown や Spectre といったプロセッサの投機的実行機構に起因する脆弱性に関しても論文が公開されている。これらの Cyber 攻撃手法は，複雑化するプ
ロセッサのマイクロアーキテクチャ(命令実行方式)
やトリッキーな論理や回路の特徴を巧みに突くことを特徴とする進化型 Malware であり，既往の防御手
段で防ぐことは難しく，防御策は喫緊の課題である。
2-2 ポテンシャル既往研究 図 4.は，Edge において自律的にリアルタイムで Malware を識別する手法の概 要 で あ る [6] 。 文 献 [6] で は ， 高 次 局 所 自 己 相 関(HLAC: Higher-order Local Auto Correlation)から得られるマスクパターンを用いて Malware Texture Imageの構造レベル解析を Pattern Match Accelerator で行
い ， パ タ ー ン マ ッ チ ン グ か ら 得 ら れ る Malware
Texture Image 固有のパワースペクトル特徴量(PowerSpectrum Features)を主成分解析するアルゴリズムを用いて Malware の識別を実現している。文献[6]のMalware 検出システムは，80%程度の識別性能を持ち，計算コスト概算では，一つの Malware ファイル- 64 -

図 4. Pattern Match Accelerator を用いた Malware 識別手法[6]の識別処理時間は，数 100μsec オーダー程度を実現する。手法[6]は，現在一般に用いられている Malwareの振る舞いによる動的解析やコード解析による静的解析手法と比較し，未知の異常な状態をどのように検知するかという本質的な課題解決に対してポテン
シャルを持つ。手法[6]のアルゴリズムの特徴は，「ある種の目的を持った処理を行う固有なコア・コードの機械語命令列群」が，局所的なパターンとして
Texture(抽象化後の Malware プログラム)の中に存在するという仮説に立脚しており，これは静的解析による機械語命令列の解析と等価である。また，
Malware 種類の各々に原型となる固有パターンのレ
イアウト (位置)とテクスチャー(パターン)を比較す
れば，Malware の識別が可能であるとしている。
さらに，単純なパターンマッチングと異なり，機械語命令列を HLAC から算出される 3×3 サイズのマ
スクパターン 221 種を用いて，Malware の Texture 全
体をパターンマッチ処理することにより，局所的類
似性と大局的類似性を比較する構造レベルの解析手法を導出している。図 5.は，Malware の Ganiw 種の統 計 量 を ヒ ス ト グ ラ ム と し て 抽 象 化 後 の PowerSpectrum である(一例)。識別は，この波形トレンドの主成分解析による。
3. 量子コンピューティング適用可能性考察
3-1 暗号化領域 Cyber-Security への適用に関して一般に知られている領域は，RSA 暗号や楕円曲線暗号などの解読である。しかし，これら領域は汎用型
量子コンピュータ(Gate 型)の登場を待つ必要がある。他方，Annealing 型の量子コンピュータは，組み合わせの最適化近似解を求める処理速度が注目さ
れ，ルート最適化やシフト計画など社会課題解決に向けた PoC が始まっている[7]。本考察においては，
この Annealing 型マシンのポテンシャルに着目し，進化型 Malware の識別へ応用する。
3-2 モデルと識別アルゴリズム 図 6.は，Computingにおいて Malware 攻撃の要素の位置を示したものである。既往の Malware は，機械語命令を組み合わせた単純なプログラムであったが，文献[5]にあるよう

図 5. Histogram of Pattern Match Frequency of
Malware.

図 6. Computing 階層における Malware 攻撃要素の位置- 65 -

図 8. Computing 階層構造と System 設計思想

図 7. Pattern Generator への Annealing マシン適用な進化型 Malware では，命令実行方式と回路の特徴・性質も考慮したプログラムへ進化している。本考察では，このプログラムのモデルから Malware 固有コ
ードを摘出できるマスクパターンを創出する。しかし，これら機械語命令列群は，命令セットの指数的組み合わせの膨大な数のコードが存在する。その膨大な命令セットの組み合わせに Annealing 型マシンを用いて最適な組み合わせ近似解を求め，それらを機械語命令列群とし，マスクパターンへ抽象化する。
命令セットの組み合わせは，命令を R-R 型，M-M 型，
R-M 型，演算型，コンデション型などに整理し，全体の組み合わせ数を削減後，フォールトツリーと同様の概念を用いて作成する。機械語命令列群によるコードの攻撃効果は，サイドチャネルなどの実験結果との比較で有効性の判断を行い最終的なマスクパ
ターン群を創出する。進化型 Malware の CyberSecurity においては，図 7.に示すような識別システム
が，文献[6]を応用したアルゴリズムにより Cloud 全体のファイルをスクリーニングしていく。
3-3 システム設計の考慮点 これらのシステム実現に際して，考慮すべきシステム設計思想は，量子コンピュータとアクセラレータ，汎用処理プロセッサに対する最適なワークロードの配分とインターコネ
クトのシステムデザインである。図 8.は，各構成要
素の連携を上手く調和させるシステムの設計思想をシンプルに表現したものである。文献[8]に示すデー
タバンド幅やレイテンシーなどの本質的なボトルネ
ック解決は，量子コンピュータ時代においてもシス
テムデザインの基本である。
4. おわりに
汎用型量子コンピュータの実現は，今後 10 年スパ
ンの時間を要する。それまでは，従来方式のプロセッサの改良とアクセラレータの組み合わせによるHeterogeneous Computing 環境がマジョリティとなる。これらの状況と Cyber 空間の進展は，益々巧妙化する Cyber 攻撃との戦いが待ち受ける。本考察で示したソリューションが実現すれば，量子アニーリ
ングマシンの計算能力の進展により Cyber 空間を超高速でスキャンし進化型 Malware のスクリーニングを可能とする革新的ソリューションが実現すると考える。

- 66 -

文

献[１] 国立研究開発法人情報通信研究機構 NICT NEWS：「サイバーセキュリティの研究開発最前線」,
Vol.472, No.6 (2018-11)[２] Apple Inc. : “Apple T2 Security Chip Security
Overview”,
https://www.apple.com/mac/docs/Apple_T2_Security_C
hip_Overview.pdf, (2018-10)[３] Karl Rupp : “42 Years of Microprocessor Trend Data”,
GitHub, 2018.
https://www.karlrupp.net/2018/02/42-years-ofmicroprocessor-trend-data/[４] International Business Times, : “New Intel CPU
Vulnerability Could Break Algorithms, Steal Data,
Reveal Secret”, ( 2019-12)https://www.ibtimes.com/new-intel-cpu-vulnerabilitycould-break-algorithms-steal-data-reveal-secret2884358[５] K. Murdock, D. Oswald, et al.. : “Plundervolt: SoftwareBased Fault Injection Attack against Intel SGX”,
University of Birmingham, UK., (2019-6)
https://plundervolt.com/doc/plundervolt.pdf[６] 柏山正守・柏山礼興・関弘翔・細野裕行，:“Pattern
Match Accelerator を用いた IoT Edge 向け CyberSecurity の 研 究 , ” , 電 気 学 会 論 文 誌 D , IEEJ
Transactions on Industry Applications, Vol.140, No.1,
pp.15-28, (2020-1)[７] IT Leaders, 「: MCPC の量子アニーリング実証実験プ
ロジェクトが始動、NEC、富士通、日立のマシンを使用」，(2019-9)
https://it.impressbm.co.jp/articles/-/18564[８] M. Kashiyama, : “Explanation of Data Bus Technologies
for High Speed Processing”, IPSJ Magazine, Vol.38,
No.6, pp.457-459 (1997-6)

<MCPC 量子コンピュータ推進 WG 2019>

量子アニーリング早わかり
竹井俊文
モバイルコンピューティング推進コンソーシアム

Quick understanding of quantum annealing
Toshifumi Takei
論文概要
本稿では「量子アニーリング」とは何か？ AI の視点から「ディープラーニング」との比較で解説する。
また量子アニーリングによって革新的な解決が期待される「組合せ最適化問題」とは何か？ 日常生活における身近な例で解説する。最後に，量子アニーリングによる課題解決の方法を例え話でやさしく解説する。
Keyword: ディープラーニング, 組合せ最適化問題，イジングモデル，QUBO

1. 「ディープラーニング」との比較から「量子アニーリング」を理解する
1-1 従来のコンピュータが苦手なもの
AI(人工知能)が目指すものは「ヒトの脳は得意だが，従来のコンピュータには苦手な情報処理」である。
「AI の父」と称されるミンスキーが 1961 年に発表した「AI へのステップ」によると，AI が目指す情報処理能力は「アナロジーによる推論」「パターン認識」「ヒューリスティック探索」，ならびにヒトとの意思疎通をゴールとする「自然言語」である。
1-2 アナロジーによる推論
ヒトの脳が日常的に行っている高度な情報処理であり，過去の経験や学習などから物事の因果関係や相関関係を導き出し，未来の結果や過去の原因などを予測する能力である。この推論能力を実現する代表的な AI が数理統計学を駆使した「統計モデル」と呼ばれるものであり，人手によるビッグデータの分析や機械学習などよって構築する。
たとえば「ベイジアンネット」は着陸経路上の気流ビッグデータから着陸難易度の確率推論、「線形回
帰」は曜日時間毎の販売ビッグデータから商品の売上予測といった能力をもつ。
1-3 パターン認識：「ディープラーニング」
同じくヒトの脳が日常的に行っている情報処理ではあるが，論理や思考の必要な推論とは違い，赤ちゃんや子供にも備わる視覚や聴覚などによって特定のヒトやモノを識別する能力である。このパターン- 67 -

認識能力を実現する代表的な AI が脳内ネットワー
ク構造を模倣し，その統計的振る舞いを利用した「ニューラルネット･モデル」と呼ばれるものである。
中でも視覚野の深層ネットワーク構造を模した「ディープラーニング」は，画像認識や手書き文字
認識，初歩的な自然言語処理などが得意である。同モデルに多量の画像データを与えて機械学習させると，ビッグデータに内在するヒトやモノの特徴量を自ら抽出し，認識に必要な「ヒトやモノの概念」をそのネットワーク内部に自動的に構築する。

図 1.入出力によるディープラーニングと量子アニーリングの違い

1-4 ヒューリスティック探索：「量子アニーリング」
前二者のように論理や過去の経験の積み重ねによって解に至るのではなく，直感によって素早く解に到達する発見的方法である。たとえば，配送管理や和を目的関数として，それを最小とする周波数帯域の割り当てを求める。また，周波数の適応変調によって電波干渉を回避できる「動的割り当て方式」に
おいては，同じく呼損による損失と送信電力による損失の加重和を目的関数として，周波数帯域の割り当てを求める。
3) IoT の大規模センサーネットワーク：
多くの装置が稼働する工場などの異常検知には
AI によるデータ分析が欠かせない。そのビッグデー
タを集めるために，数多のセンサーによる IoT（モノのインターネット）が導入される。この IoT エリア
ネットワークで利用されているマルチホップ通信な
どの無線通信方式においては，周波数帯域を複数の
アクセスポイントに割り当てる「組み合わせ最適化問題」がある。たとえば最適な割り当てを行った場
合には，データ収集に要する時間が短縮し，かつ消費電力も低下することが報告されている。
2-3 身近な「組み合わせ最適化問題」例
1) 最短経路問題
出発地から目的地までの最短の経路を求める問題（カーナビのルート検索,電車･バスの乗換案内）
2) 最大流量問題
目的地へ最大の量を流す経路を求める問題（交通網,
通信網, 電気･水道ライフライン, 石油パイプライン）
2. 割と多い身近な「組み合わせ最適化問題」
3) 配送計画問題
トラック等で配送･収集する最も効率的な経路を求
2-1 「組み合わせ最適化問題」とは？
少し難しいが，最適化問題とは，制約条件（x∈S）
める問題（郵便, 宅配，コンビニ商品配送，ゴミ収集）を満たす解の中で，目的関数 f(x) を最小（最大）に
4) 施設配置問題
する解を求める問題である。ただし，変数 x = (xl, x2,
都市施設（役所, 学校, 病院, 消防署, 店舗, 銀行等）
… ,Xn) は n 次元ベクトルであり，S は変数 x がとの利便性と収益性を最大にする配置を求める問題
りうる値の集合である。目的関数は，損失（コスト）5) スケジューリング問題
関数とも呼ばれる。特に変数ｘが整数などの離散値
従業員･乗務員･看護師等の勤務シフト表, スポーツ
をとる場合を「組み合わせ最適化問題」と呼ぶ。
対戦の日程表等, 時間軸上の最適な割り当て問題
2-2 通信における「組み合わせ最適化問題」
2-4 「組み合わせ最適化問題」の解法
通信ネットワークにおいては，「ネットワーク資源」 「組み合わせ最適化問題」には論理的な解法として（通信帯域、電波の周波数帯域）の割り当て問題が，の厳密解法と、困難な問題に対する様々な近似解法
重要な「組み合わせ最適化問題」の一つである。
がある。最近，近似解法ではあるが，より精度の高1) 固定通信（電話）ネットワーク：
いヒューリスティックな探索法の一つとして「シミ
古くから「アーラン B 式」が一般的な近似的解法
ュレーティドアニーリング」さらに「量子アニーリ
ング」が登場してきた。
となっており、呼損（通信回線の輻輳のため不通となる）による損失を目的関数として，それを最小と3. 誰でも分かる量子アニーリングによる課題解決
する通信帯域を求める。
2) 無線通信ネットワーク：
周波数帯域を分割したチャネルの「静的割り当て【ある奉納相撲における課題】
方式」においては，呼損（チャネルの輻輳のため不神社で子供力士の横綱による奉納相撲を行うこと通となる）による損失と電波干渉による損失の加重になった。横綱は東西一人ずつ二人しかいない。とスケジュール管理において，多くの組み合わせの中から一番効率的な配送ルートや勤務シフト表を決定するなど，管理者の直感によって「決断や意思決定に必要な最適解」を求める能力である。
この「組み合わせ最適化問題」の困難さは「巡回セールスマン問題」として知られている。セールス
マンがいくつかの都市を一度ずつ訪問し全ての都市を巡回し終え出発点に戻ってくる際，その移動距離が最小になる経路を求める問題であり，仮に 30 都市の場合の全ての経路を計算し厳密解を求めようとす
ると，スパコンでも百億年以上かかる。
そのため，各種「組み合わせ最適化問題」ごとに考案されたアルゴリズムによる最適解の探索が古典
コンピュータ(従来のコンピュータ)によって行われていたが，新たに量子の振る舞いを利用した量子コンピュータなどが登場しヒューリスティックな探索が行われるようになった。たとえば，量子コンピュータの一種である「量子アニーリング」やその計算過程を古典コンピュータ上で模した「シミュレーティドアニーリング」などは，「ディープラーニング」のようなビッグデータを必要とせず，瞬時に高精度な最適解を探索する能力を持つ。

- 68 -ころが，奉納相撲の主催者であるあなたは、神主からある厳しい要件を与えられた。その要件とは，この神社の祭神は勝負事が大嫌いなので，取り組み結果を「二番勝負による引き分け」にすること。その際，一番ごとにどちらを勝たせるか，星取りを予め決めておいてもよい。但し，その星の組み合わせの決定には，不浄な人間が関わってはいけない。

3-1 課題を「組み合せ最適化問題」として明確化
二番勝負であるから，星の組み合わせは「二勝（〇〇）」「一勝一敗（〇●）」「一勝一敗（●〇）」「二敗（●●）」の四通りしかない。この中から，引き分けにするための最適な組み合わせを探索するまでもな
く，五分の星すなわち「一勝一敗（〇●あるいは●〇）」にすればよいことは、人間ならば誰でもすぐ分かる。しかし，神事であるから，不浄な人間の探索行為は許されない。ならば，どうするか？ そこで，
“自然神”とでも言うべき不思議な自然現象由来の探索能力を持つ「量子アニーリング」様にお伺いを立てて，星取の最適な組み合わせを決定していただ
くことにする。
量子アニーリング様にお伺いを立てる際には，人間の言葉やプログラミング言語が通じない。そこで，量子世界の「イジングモデル」という，量子ビットを変数とする量子力学の数式にしなければならない。
量子とは，物質を形づくっている分子や原子よりも小さい電子などの「粒子」であるが，同時にその運動状態を観測しようと思っても，捉えどころのない「波動」の性質を持つ。それゆえ「+１(スピン↑)」と「-１(スピン↓)」といった，粒子の相反する（自転）運動状態を重ね合わせ持つ「量子ビット（スピン変数）S」として表現する。
この量子ビットは相撲に似ている。相撲の場合，「〇（勝ち）」か「●（負け）」のいずれかであり，
引き分けはない。しかし，それは結果であって，相撲の最中は，たとえば相手を土俵際まで追い詰めたり，逆に追い詰められたりして，勝っている状態（+
１）と負けている状態（-１）が重ね合わされた状態がしばらく続いた後，土俵を割って勝負が決まる。
そこで，相撲の星取を「量子ビット S」の和で表すことにする。但し，S は「+1(〇勝ち)」か「-1(●負け)」- 69 -のいずれかである。これを，S∈{+1, -1}と表す。二番勝負の場合，片方の横綱の一番目の星を S1，二番目の星を S2 とすると，引き分けとするためには，S1と S2 の和が 0 となればよい。つまり「S1+S2=0 となる（S1, S2）の最適な組み合せは何でしょうか？ 但し，S1∈{+1, -1} , S2∈{+1, -1}」という「組み合せ最適化問題」の質問として明確化し，これをイジング
モデル（数式）に変換して，量子アニーリング様にお伺いを立てればよい。
3-2 QUBO による「イジングモデル」の具体化
イジングモデルは，下記のような数式にて表される。右辺の第 1 項は量子ビット（スピン変数）Si とSj 間の相互作用，第 2 項は Si に働く局所磁場の強制力であり，Jij と hi はそれぞれの定数である。左辺のH はハミルトニアンとも呼ばれ，系（辺 E と頂点 Vから成る格子）全体のエネルギーであり，各量子ビットの状態によって変化する。

量子力学を専攻していない限り，上記のような数式とは馴染みが薄い。そのため，量子ビット（S1, S2,…）をバイナリ変数（x1, x2, …）に替えて，量子世界のイジングモデルを人間世界の「QUBO」に落とし込む。バイナリ変数とは，我々にとって馴染みのある
デジタル情報処理の二値（0/1）のことである。QUBO（Quadratic Unconstrained Binary Optimization）とは，
このバイナリ変数の制約が無い場合に限定した比較的扱いやすい高々二次関数の数式を用いることによって，難解なイジングモデルを代替する方法である。
分かりやすく言えば，QUBO とは，人間が組合せ
最適化問題に直面した際，“お伺い書”を持って「量子アニーリング様、最適解を教えてください！」とお伺いを立てさえすれば、即時に量子アニーリング
様から「最適解はこれだ！」とお答えをいただける，
実にありがたい方法なのである。
まず，量子ビット（S1, S2）の質問をバイナリ変数（x1, x2）の質問に替えると，「x1+x2=1 となる（x1, x2）の最適な組み合わせは何でしょうか？ 但し，x1∈{0,1} , x2∈{0, 1}」となる。
次に，この質問をイジングモデルに代わる QUBO
（数式）に変換しなければならない。ところが，量子アニーリング様は，そもそも「方程式 x1+x2=1 の最適解は？」という人間世界の質問を理解できない。

なぜならば「アニーリング」とは元々“焼きなまし法”（少しずつ温度を下げるなど，変化させながら最適解を探索する方法）であり，方程式の解を一意的に求めるような人間やコンピュータが得意とする「演算」ではないからである。それは，投げたボールが必ず計算された放物線を描いて落ちるような決定論的なものではなく，つかみどころのない「波動」
として振る舞う目に見えないボールが，揺らぎながら徐々に最適な穴凹へと落ちるイメージである。
すなわち，量子アニーリング様は「時間とともに、全体としてエネルギーが最小となるような組み合せに落ち着く」という量子の自然現象に拠って，最適解を探索しているわけである。そこで，人間にも分かるようにするために，量子力学の難解な「エネルギー」を人間世界の具体的な「コスト」に読み替える。つまり「時間とともに，コストが最小になるよ
うな組み合せに落ち着く」という汎用的な表現にすることによって，我々が直面する様々な「組み合わせ最適化問題」に応用できる。
3-3 量子アニーリングによる瞬時の課題解決
一般的には，個々の「組み合わせ最適化問題」ごとに，個々の「コスト関数（目的関数）」が定義される。
「コスト関数」とは，最適な価値を生み出すために最小あるいは最大にしたい「目的関数」（関数値）のことであり，この関数値を変化させるのがバイナ
リ変数の組パターンである。
たとえば，宅配業の配送トラックによる「配送最適化問題」においては，文字通り「輸送コスト」というコスト関数（目的関数）を最小にする配送ルー
トの最適な組み合わせを探索する。また，通信事業の「ネットワーク最適化問題」においては，通信ネットワークを流れるデータの「フロー（流量）」というコスト関数（目的関数）を最大にするネットワー
ク（枝･容量）などの最適な組み合わせを探索する。
さて，質問「x1+x2=1 となる（x1, x2）の最適な組み合わせは？」を QUBO（数式）に変換する場合，バ
イナリ変数（x1, x2）の組ごとに求まる“x1+x2”値（2,1, 0）の中から“1”に一致するものを探索すればよい
ので，コスト関数として「誤差関数」を使えばよい。
すなわち，誤差関数を「最小二乗法による“x1+x2”の値と正解値“1”との誤差の二乗」として定義し，コスト関数 Cost が最小になるバイナリ変数（x1, x2）の組
み合わせを求める。
Cost = (1-(x1+x2))2 = 1-2x1-2x2+x12+2 x1x2+x22

ここで，バイナリ変数の細工を施す。x1∈{0, 1}, x2∈{0, 1} ゆえ，x1＝x12 , x2＝x22 であるので、Cost = 1-2x12-2x22+x12+2 x1x2+x22 = 1 + (-x12-x22+2 x1x2)H22
コスト関数 Cost の変数部分 H=-x1 -x2 +2 x1x2 は，二次関数となっているので，以下のような n×n 上三角行列式（対角とその上以外は 0）：QUBO 行列式という，で表すことができる。
H = (x1 x2) �−1 2 x1
�� �
0 − 1 x2

QUBO 行列式＝ �

−1 2
�
0 −1

そこで，この QUBO 行列式が書かれた“お伺い書”
を持って量子アニーリング様にお伺いを立てれば，「x1+x2=1 となる（x1, x2）の最適な組み合わせは何でしょうか？」，すなわち「奉納相撲の二番勝負による引き分けの最適な組み合わせは何でしょうか？」という質問に対する最適な組み合わせを即時に決定していただくことができる。
たとえば「Wildqat」という QUBO のオープンソー
スの Python フレームワークに QUBO 行列式を入力すれば，（x1, x2）=（0, 1）あるいは（1, 0），すなわち「一勝一敗（〇●あるいは●〇）」という答えが瞬時に出力される。
4. （まとめ）量子アニーリング普及の課題
もちろん，前述の「奉納相撲における課題」は人間によって簡単に解決できる「組み合わせ最適化問題」である。しかし、実際には「巡回セールスマン
問題」のように困難なケースが多々ある。それも，我々が日常直面している課題が，実は「組み合わせ最適化問題」であるにもかかわらず，全くそれに気づいていない場合がほとんどかも知れない。
それゆえ，前述したように，業務などにおいて直面する課題を具体化かつ明確化し，それを「組み合せ最適化問題」として認識することが第一歩である。
その上で，厳密解法を採用できるならばそれで良いし，もし近似解法が必要であれば「量子アニーリン
グ」あるいは「シミュレーティドアニーリング」の採用を検討する。
ただ，アニーリングにおいては QUBO によるイジン
グモデル対応が避けられないので、今後，量子アニーリングの普及には，従来のコンピュータにおけるプログラミングに替わる数式（数学）を扱える人材が必要となる。（了）- 70 -

おわりに
我々量子コンピュータ推進 WG は、発足から 3 年半を経過し、皆様のご協力により、理念・目的であった
コミュニケーションハブとして様々な情報のエクスチェンジを行うことができました。関係者の皆様には厚く御礼申し上げます。
国内外の量子コンピュータを取り巻く技術進化のスピードは速く、特にアニーリング方式では社会実装につながる大きな進展が見られました。アニーリング方式のコンピュータは、従来のデジタルコンピューティ
ングの概念と異なり、本質的に物事の振る舞いは何処に収斂していくのかという命題の解法により、最適な近似解を求めて行く新しい概念のコンピューティング・パラダイムシフトです。
今回、このような状況変化の中にあって、アニーリングコンピューティングの応用社会実装を意識し、最近どのような進展が起こったのか、また新しい兆しは何かなど、各社・著者から最新動向のご提供と解説を頂戴し、本解説書を通じて情報共有を行います。 皆様の動向把握や、今後の取り組みにご活用いただければと思っています。
2022 年 3 月 量子コンピュータ推進 WG 主査

柏山 正守（Ph.D.）

MCPC AI& ロボット委員会
量子コンピュータ推進 WG「拡⼤する量⼦コンピューティングその社会実装ポテンシャル」＜企画・編集メンバー＞
AI& ロボット委員会委員長

森山浩幹

株式会社ドコモ CS

量子コンピュータ推進 WG 主査

柏山正守

株式会社ゼネテック /慶應義塾大学 SFC 研究所

量子コンピュータ推進 WG 副主査

白根昌之

日本電気株式会社

橋本

文之

富士通株式会社

編集責任

岡本

利夫

前 AI& ロボット委員会副委員長

事務局

秋山

孝

MCPC

企画・編集メンバーは 2020 年 3 月初版時のメンバーです。
【MCPC について】
ワイヤレスデータ通信とコンピューティングシステム （モバイルシステム） の普及を促進するために、 1997 年にわが国を代表する移動体通信会社、 コンピューターハードウェア / ソフトウェアメーカ、 携帯電話 /PHS メーカ、 システムインテグレータなどにより組織化されました。 現在、 モバイル利活用の M2M/IoT 市場の発展 ・ 拡大実現に向かって活動しており、 そのための技術課題への対応、 運用課題の調査 ・ 研究、 開発の推進、 標準化、 相互接続性検証、 普及啓発活動、 人材育成などの活動を行っています。 さらには、 米国姉妹組織の WTA （Wireless Technologies Association）、 USB-IF、 Bluetooth SIG、 IEEE などと連携を図りながら、 モバイル利活用の M2M/IoT ソリューションの市場の形成拡大と、 利用環境の高度化に努めています。
（2022 年 3 現在 会員会社数 180 社）- 71 -

- 72 -