《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

量子アニーリングやイジングマシンの基礎と応用
慶應義塾大学 理工学部 物理情報工学科
田中 宗

概要
本原稿では，近年，産学両面から注目されている新しい計算技術である量子アニー
リングやイジングマシンの基礎と応用について紹介する．これらの計算技術は組合せ最適化問題（膨大な選択肢から，制約条件を満たし，ベストな選択肢を探索する問題）に対する高効率解法として期待されている．これらの計算技術は物理学の概念を取り込んだアルゴリズムを基盤としており，統計力学による理論構築や，ハードウェア開発，ソフトウェア開発，アプリケーション探索といった幅広い領域の研究開
発が同時進行で進められている．量子アニーリングやイジングマシン分野の研究は，物理学と情報科学・情報工学の境界領域分野の研究に位置づけられ，これからますます幅広い分野の研究者・技術者の参入が必要不可欠である．

1 導入
近年，組合せ最適化問題に特化した新しい計算技術として量子アニーリングやイ
ジングマシンが注目を集めている．組合せ最適化問題は，「膨大な選択肢のうち，与えられた制約を満足した上で，コスト関数を最小化する選択肢を探索する」という問題である．ここで選択肢は組合せ的構造になっていることから，組合せ最適化問
題と呼ばれる（組合せ最適化問題に限らず一般の数理最適化についての新しい教科書として [1] などが挙げられる）．典型的な組合せ最適化問題の例として，巡回セー
ルスマン問題や人員計画問題などが知られている．組合せ最適化問題は要素の個数（人員計画問題における人数など）に対して，解の選択肢が指数関数的に増大することが知られている．これを組合せ爆発と呼ぶ．組合せ最適化問題は，様々な基礎学
術分野だけでなく，多様な産業分野において内在する．量子アニーリングや類似の概念により動作する関連計算技術であるイジングマシンは，組合せ最適化処理を高速かつ高精度に実行できると期待されている．
量子アニーリングは 1998 年，門脇と西森によって提案された計算技術であり [2,3]，
シミュレーテッドアニーリング [4–6] の類似概念である．シミュレーテッドアニー
リングにおいては，温度（熱ゆらぎ）の概念を擬似的に導入し，徐々に温度を下げていくという操作を実行し，最終的に得られる状態を解とする，というアルゴリズムで《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

ある．非常にゆっくり温度を下げれば自然に基底状態を得ることができるという物
理学の感覚と適合したアルゴリズムである．実際，シミュレーテッドアニーリング
は，S. Geman と D. Geman による収束定理 [7] などの理論的側面の研究がなされている．シミュレーテッドアニーリングは，実装の容易さから様々なところで利用されている．それに対し量子アニーリングは，量子ゆらぎの概念を擬似的に導入し，徐々に量子ゆらぎを弱めていくという操作を実行し，最終的に得られる状態を解とする，というアルゴリズムである．
世界初の商用量子アニーリングマシンが 2011 年に発表された [8]．当時は，128個の量子ビットからなる小規模の量子アニーリングマシンであった．門脇，西森による量子アニーリングの提案から商用量子アニーリングマシン登場までの間は，量子アニーリングの収束定理などの理論的研究 [9] や，モンテカルロ法や平均場近似を基礎とした数値計算手法による量子アニーリングとシミュレーテッドアニーリングの解精度比較などの研究がメインであった [10–13]．
量子アニーリングマシンが実現され，量子ゆらぎの導入や量子ゆらぎを徐々に弱めるという操作を，従来型コンピュータによるシミュレーションではなく実際のマシン上で実行することができるようになった．これを契機に，これまでのような理論研究や従来型コンピュータによるシミュレーション研究に加え，量子アニーリン
グマシンと従来型コンピュータ上で動く従来アルゴリズムの比較などの研究が数多く世に出るようになってきた [13]．また量子アニーリングマシンの実現を皮切りに，様々なイジングマシンが開発されてきた [14–20]．
現在，量子アニーリングやイジングマシンが実応用に向かうために必要な三要素
として，ハードウェア開発，ソフトウェア開発，アプリケーション探索が相互に密接に関係し合いながら研究開発が進められているという状況である．

2 イジングモデルの基礎
イジングモデル (Ising model) は統計力学における基本的なモデルの一つである．
ここではまずイジングモデルを定義し，そのうえで，イジングモデルの統計力学的性
質について紹介していく．

2.1 イジングモデルの定義
無向グラフ G = (V, E) を考える．ここで V は無向グラフ G における頂点集
合，E は無向グラフ G における辺集合を表す．無向グラフの「無向」とは辺に向きがないことを表す．図 1 に頂点が 4 つの無向グラフ G = (V, E) の例を示す．図 1 の無向グラフの頂点集合 V は V = {1, 2, 3, 4} であり，辺集合 E は

E = {(1, 2), (1, 3), (2, 3), (3, 4)} である．
イジングモデルは無向グラフ G = (V, E) 上に定義される．無向グラフの頂点に±1 のスピンが配置されている．また局所磁場は無向グラフの頂点上で定義され，相《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

図1

1

2

4

3

無向グラフ G = (V, E) の例．無向グラフの頂点集合 V は V = {1, 2, 3, 4} であり，辺集合 E は E = {(1, 2), (1, 3), (2, 3), (3, 4)} である．

互作用は無向グラフの辺上で定義される．イジングモデルのハミルトニアンは，

H=−


i∈V

hi s i −Ji,j si sj ,si ∈ {+1, −1} (∀i ∈ V ).

(1)(i,j)∈Eで与えられる．ここで hi は頂点 i における局所磁場，Jij は辺 (i, j) における相互作用を表す．また，si は頂点 i のスピンを表す．式 (1) の右辺第一項は頂点集合全体にわたって和を実行し，右辺第二項は辺集合全体にわたって和を実行する．さきほ
ど無向グラフとして例示した図 1 上に定義されたイジングモデルを書き下すと，

H = − h 1 s 1 − h2 s 2 − h3 s 3 − h 4 s 4− J1,2 s1 s2 − J1,3 s1 s3 − J2,3 s2 s3 − J3,4 s3 s4 ,(2)

s1 , s2 , s3 , s4 ∈ {+1, −1}.

(3)

となる．

2.2 イジングモデルの性質
前節でイジングモデルを定義した．続いて，イジングモデルの性質について見ていこう．

2.2.1 局所磁場と相互作用の意味
まずは，最も簡単な場合として 1 スピン系について考える．この場合は単純に 2準位系となる．ハミルトニアンは

H = −h1 s1 ,s1 ∈ {+1, −1}.

(4)である．s1 = +1 のときエネルギーは −h1 となり，s1 = −1 のときエネルギーは

h1 となる．h1 > 0 のとき s1 = +1 が基底状態（エネルギーが最小となる状態）であり，h1 < 0 のとき s1 = −1 が基底状態となる．すなわち，式 (1) で与えられるイ《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

表1

式 (5) のスピンの状態とエネルギーの対応関係．

(s1 , s2 )

エネルギー(+1, +1)−h1 − h2 − J1,2(+1, −1)−h1 + h2 + J1,2(−1, +1)+h1 − h2 + J1,2(−1, −1)+h1 + h2 − J1,2

ジングモデルにおいて局所磁場はスピンに対する「強制力」として働くとみることができる．
次に簡単な場合として 2 スピン系について考える．ハミルトニアンは，

H = −h1 s1 − h2 s2 − J1,2 s1 s2 ,

s1 , s2 ∈ {+1, −1}.

(5)である．このときスピンの状態とエネルギーの対応関係は表 1 のようになる．相互作用の効果を見るために局所磁場がゼロの場合，すなわち，h1 = h2 = 0 の場合について考える．このとき，J1,2 > 0 のとき (s1 , s2 ) = (+1, +1), (−1, −1)，すなわち，

s1 = s2 が基底状態となり，J1,2 < 0 のとき (s1 , s2 ) = (+1, −1), (−1, +1)，すなわち，s1 = −s2 が基底状態となる．このことから J1,2 > 0 の場合を強磁性的相互作用と呼び，J1,2 < 0 の場合を反強磁性的相互作用 と呼ぶ．

2.2.2 フラストレーションと基底状態探索の困難
前節では，相互作用の効果を見るために，式 (5) について h1 = h2 = 0 なる状況を考えた．ここでは式 (5) について別の 2 つの例について検討する．
まず h1 = 1, h2 = −1, J1,2 = 2 の場合について考える．このとき，表 1 より基底状態は (s1 , s2 ) = (+1, +1), (−1, −1) である．これらの状態に共通しているのは，相互作用 J1,2 に対する安定状態（エネルギーが低い状態）ではあるものの，片方の局
所磁場に対する安定状態ではないということである．このように，全ての相互作用，全ての局所磁場に対して安定状態ではないという状況をフラストレーションと呼ぶ．
次に，h1 = 2, h2 = −2, J1,2 = 1 の場合について考える．このとき，表 1 より基底状態は (s1 , s2 ) = (+1, −1) である．この状態もフラストレーションが生じている．なぜなら，両方の局所磁場に対する安定状態ではあるものの，相互作用に対する安定状態ではないからである．
フラストレーションは局所磁場がない場合も生じうる．そのことについて考えるために，3 個のスピンからなる以下のイジングモデルを考える．

H = −J1,2 s1 s2 − J2,3 s2 s3 − J3,1 s3 s1 ,

s1 , s2 , s3 ∈ {+1, −1}.

(6)

これについて J1,2 = J2,3 = J3,1 = J < 0 とした場合を考える．このとき基底状態は (s1 , s2 , s3 ) = (+1, +1, −1), (+1, −1, +1), (−1, +1, +1), (−1, −1, +1),

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)(−1, +1, −1), (+1, −1, −1) である．これらすべての状態について，相互作用のいずれか一つに対して安定状態ではないことが確認できる．
フラストレーションがない場合は，基底状態を簡単に構成することが可能である．
フラストレーションがない場合は，全ての局所磁場，全ての相互作用に対して安定状態となっているため，1 つずつ順番に（逐次的に）スピンの状態を決めていけば基底状態を構成することが可能であるからである．一方，フラストレーションがある場
合には，一般に，基底状態を構成することが困難である．量子アニーリングやイジン
グマシンで基底状態を探索しようとするイジングモデルは一般にフラストレーショ
ンがある．

3 イジングマシンにおける内部アルゴリズム
様々なグループによって開発されているイジングマシンはそれぞれ固有のアルゴ
リズムに基づき，基底状態探索を行う．ここではその中でも基本となる 2 つのアル
ゴリズムについて見ていく．

3.1 シミュレーテッドアニーリングの動作原理
式 (1) で与えられるイジングモデルについて考える．シミュレーテッドアニーリ
ングでは以下のアルゴリズムに従い，スピンの状態を更新する．

Step 1
Step 2
Step 3
Step 4式 (1) のスピン {si } をランダムに設定する．
初期温度 T0 として，十分高い温度を設定する．
スピンをランダムに選択する．
設定した規則に基づき定義される確率によって，Step 3 で選択されたスピンをフリップするかどうか決める．ここで「設定した規則」としてよく用いられる方法として，熱浴法やメトロポリス法が挙げられる．

Step 5 Step 3 と Step 4 を平均的に全てのスピンを 1 回ずつ行う．
Step 6 温度を下げ，Step 3 に戻る．十分に温度が下がったとき，スピンの状態を見る．
これによりシミュレーテッドアニーリングが実現される．

3.2 量子アニーリングの動作原理
量子アニーリングにおいては，組合せ最適化問題を表現するイジングモデルに対し，量子ゆらぎを導入し，その量子ゆらぎを徐々に弱めるという操作を行う．シミュ
レーテッドアニーリングが組合せ最適化問題を表現するイジングモデルに対し，温度（熱ゆらぎ）を導入し，その温度を徐々に下げる（熱ゆらぎを徐々に弱める）ことと類似の関係にあるといえる．

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

量子ゆらぎを導入するために，パウリ行列と呼ばれる以下の行列を定義する．


x

σ =

0
1



1
0


,

z

σ =

1
0

0
−1


(7)

．

式 (1) のスピン変数 si をパウリ行列 σ z で置き換えるという操作を行う．すなわち，

Hc = −

hi σiz −Jij σiz σjz .

(8)(ij)∈Ei∈Vとする．これは σ z が対角行列となる基底を取っていることに相当する．ここで Hc
を古典ハミルトニアンと呼び，2N × 2N の対角行列である．対角行列の各成分は式
σ z の固有値 +1, −1 に対応する固有ベクトルはそれぞれ
 (1)の値に対応する．



1
0

，

0
1

である．式 (1) の基底状態に対応する固有ベクトルが式 (8) の基底状態となる．
次に，量子ゆらぎを表すハミルトニアンを導入する．量子ゆらぎは Hc と非可換なハミルトニアンとして導入する．現存の量子アニーリングマシンでは

Hq = −

N


σix .

(9)

i=1

で与えられるタイプの量子ゆらぎを用いている．ここで Hq を量子ハミルトニアンと呼ぶことにする．最近は新たな量子アニーリングマシンの開発 [21, 22] や，理論的な観点から，上で挙げたタイプとは異なる量子ゆらぎを用いた量子アニーリングの性能に対する考察も進められている [23–27]．
量子アニーリングの動作は以下のような時間に依存するハミルトニアンで表現される．

H(t) = A(t)Hc + B(t)Hq ,0 ≤ t ≤ τ.

(10)

ただしここで t は時刻を表し，τ はアニーリング時間と呼ばれる．A(t) は t = 0 で0 であり，t = τ で有限の正の値を取る単調増加関数であり，B(t) は t = 0 で有限の正の値を取り，t = τ で 0 となる単調減少関数である．すなわち，t = 0 で量子ハミルトニアン Hq であり，t = τ で，解きたい組合せ最適化問題を表現する古典ハミル
トニアン Hc に移行する．
初期状態を t = 0 のハミルトニアンの基底状態，すなわちHq の基底状態として用意する．σ z の固有値 +1 に属する固有ベクトルを |↑ :=
属する固有ベクトルを |↓ :=

0
1



1
0

，固有値 −1 にと書くことにする．ここで以下で |→ を定義

する：

1|→ := √ (|↑ + |↓) .
2(11)

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

これは σ x の固有値 +1 に属する固有ベクトルである．|→ を用いて Hq の基底状
態は，|→→ · · · → := |→ ⊗ |→ ⊗ · · · ⊗ |→ .

(12)と表すことができる．
初期状態を Hq の基底状態 |→→ · · · → とし，ハミルトニアンを時間とともに変化させる．量子力学によれば，状態はシュレディンガー方程式：d|Ψ(t) = H(t) |Ψ(t) ,dt|Ψ(0) = |→→ · · · → .
i

(13)
(14)

に従って時間発展する．ただしここで  はプランク定数と呼ばれる定数である．
我々の目的は組合せ最適化問題を処理することであり，t = τ のハミルトニアン

Hc の基底状態を求めることが目的である．量子アニーリングでは，t = 0 のハミル
トニアン Hq の基底状態を初期状態とし，量子力学に従って時間発展させることを考える．そのため仮に，各時刻のハミルトニアン H(t) の基底状態を連続的に（断熱的に）たどることができれば，確実に t = τ のハミルトニアン Hc の基底状態を得る
ことができる．t = 0 のハミルトニアン Hq は実験的に用意しやすい形を取る必要があり，式 (9) はその状況を満たす．
このような理想的状況，すなわち，各時刻のハミルトニアン H(t) の基底状態を連続的に（断熱的に）たどるための条件として，断熱条件が知られている．断熱条件は，

max  Ψ1 (t)| dH(t)
|Ψ
(t)

0
dt
min ΔE(t)2

1.

(15)

で与えられる．ただしここで |Ψ0 (t) 及び |Ψ1 (t) はそれぞれ H(t) の最小固有値

E0 (t) 及び二番目に小さい固有値 E1 (t) に対応する固有ベクトルである．また，ΔE(t) := E1 (t) − E0 (t) である．
上では理想的状況について述べたが，この状況は絶対零度，孤立量子系において成立するものである．一方，実際の量子アニーリングマシンは外部環境との相互作用があるため，孤立量子系ではない．また有限温度下で動作するものであることに注意が必要である．実際の量子アニーリングマシンを使って，温度効果及びアニーリン
グ時間と基底状態占有確率の関係を網羅的に調査した結果が報告されている [28]．

4 組合せ最適化問題とイジングモデル
本章では，イジングモデルないしは QUBO(Quadratic Unconstrained Binary

Optimization：制約なし二値変数二次最適化) で典型的な組合せ最適化問題を表現することをみていく．詳細な例は，文献 [29] や web サイト [30, 31] に掲載されているので，そちらも参照されたい．以下では，文献 [32] に基づいて解説する．

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

4.1 組合せ最適化問題
まず，組合せ最適化問題について簡単に紹介する．組合せ最適化問題は，組合せ的な構造を持つ N 個の決定変数 x ∈ ZN ，目的関数 f (x)，制約条件から成る．組合せ最適化問題は，制約条件を満足する解のうち，目的関数 f (x) を最小にする決定変数の組 x∗ を求めよ，という問題である．
本原稿では，制約条件が等式あるいは不等式で表される場合について考える．数式で表現すると，x∗ = argminx f (x),g (x) = 0, ( = 1, · · · , L),hm (x) ≤ 0, (m = 1, · · · , M ).

(16)
(17)

となる．

4.2 イジングモデルと QUBO
バイナリ変数 xi ∈ {0, 1} を用いて，QUBO は以下の式で与えられる．

H=

Qij xi xj ,xi ∈ {0, 1}.

(18)1≤i≤j≤N

ただしここでバイナリ変数は N 個あるとする．また，xi ∈ {0, 1} であることから

x2i = xi となるため，
H=

N

i=1

ai x i +

bij xi xj .

(19)

1≤i≤j≤Nと書くこともできる．イジングモデルにおけるスピン変数が {+1, −1} であり，

QUBO におけるバイナリ変数が {0, 1} であることから，スピン変数とバイナリ変数の変換は相互に可能であり，式 (1) で表現されるイジングモデルと，式 (19) で表現される QUBO とは等価であることがわかる．

4.3 イジングモデルや QUBO による組合せ最適化問題の定式化
組合せ最適化問題をイジングモデルや QUBO で表現する際，以下の 3 つの分類に基づいて検討するのがよい．

• 制約条件が無い場合• 等式で表現できる制約条件がある場合• 不等式で表現できる制約条件がある場合
以下ではこれら 3 つについて紹介する．

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

4.3.1 制約条件が無い場合
制約条件が無い組合せ最適化問題の例として，以下で与えられる数分割問題を考えよう．N 個の自然数の集合 S = {n1 , n2 , · · · , nN } が与えられ，これを互いに素な（つまり，共通要素を持たない）2 つの部分集合 S1 , S2 に分割する際，それぞれの部分集合に属する自然数の和の差が最小になるような分割方法を見つけよ，という問題である．すなわち，目的関数：






 


.
n
−
n
i
i


ni ∈S1ni ∈S2(20)が小さくなるような互いに素な 2 つの部分集合 S1 , S2（ただし，S1 ∩ S2 = ∅）を見つけよ，という問題である．
これをイジングモデルを用いて表現することを考える．整数 ni ∈ S を S1 に属させる場合 si = +1 とし，S2 に属させる場合 si = −1 とする．このようにスピン変数 {si } を導入し，以下のハミルトニアンを考える．

H=

N


2
n i si

.

(21)

i=1

式 (20) で与えられる目的関数が最小となるとき，式 (21) も最小となる．式 (21) は数分割問題を表現するイジングモデルのハミルトニアンであることが確認できた．

4.3.2 等式で表現される制約条件が存在する場合
イジングマシンを用いて組合せ最適化問題を処理する際，等式で表現される制約条件が存在する場合があり，これは大きく分けて二通りある．第一に，もともとの組合せ最適化問題に課された等式で表現される制約条件が存在する場合がある．第二に，イジングマシンを使用するため，整数値を複数のバイナリ変数で表現することに起因する等式で表現される制約条件が存在する場合がある．以下，2 つの場合について見ていく．
まずはじめに，等式で表現される制約条件が存在する組合せ最適化問題の例として，以下で与えられるグラフ分割問題を考えよう．グラフ G = (V, E) を考える．
ここで V と E はグラフ G の頂点集合，辺集合である．いま，頂点数 G の頂点数

|V | が偶数と仮定する．このとき，互いに素な 2 つの部分グラフ G1 = (V1 , E1 ),G2 = (V2 , E2 ) に分割する際，|V1 | = |V2 | の条件のもと（つまり，2 つの部分グラフの頂点数は等しい），2 つの部分グラフをつなぐ辺の本数を最小にする分割方法を見つけよ，という問題である．

2 つの部分グラフをつなぐ辺の本数をイジングモデルで表現するために，以下のようにスピン変数を導入する．頂点 i が部分グラフ G1 に属するとき，すなわち，i ∈ G1 のとき，si = +1 とする．一方で，頂点 i が部分グラフ G2 に属するとき，

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

すなわち，i ∈ G2 のとき，si = −1 とする．このようにスピン変数を導入すると，2つの部分グラフをつなぐ辺の本数は，

Hcost =

 1 − si sj
.
2

(22)

(i,j)∈Eと表される．頂点 i と頂点 j が同じ部分グラフに属するとき，式 (22) の (1 − si sj )/2
は 0 となる．一方，異なる部分グラフに属するときこれは 1 となる．
次に，制約条件 |V1 | = |V2 | をイジングモデルで表現すると，


Hconstraint =



2
si

.

(23)

i∈V

となる．実際，|V1 | = |V2 | のとき，式 (23) の右辺は 0 となり最小値をとる．この定式化のポイントは，制約条件を満たすとき，イジングモデルの基底状態となるように
イジングモデルを設計するという点である．
目的関数（2 つの部分グラフをつなぐ辺の本数）と制約条件（|V1 | = |V2 |）のイジ
ングモデルを用いて，この問題のイジングモデルは
2 1 − si sj
H = Hcost + μHconstraint =
si
.
+μ
2
i∈V

(24)

(i,j)∈Eとなることがわかる．ただしここで μ はハイパーパラメータである．制約条件を満たす解が式 (24) で表現されるイジングモデルの基底状態となるためには，ハイパー
パラメータ μ の下限値 μ∗ が存在する．
次に，イジングマシンを使用するため，整数値を複数のバイナリ変数で表現することに起因する等式で表現される制約条件が存在する場合について見てみよう．典型的な問題として，巡回セールスマン問題を考える．巡回セールスマン問題はグラフ

G = (V, E) 上で定義される問題である．簡単のため，G は無向グラフと仮定し，また全結合グラフであると仮定しよう．全結合グラフとは，任意の頂点から別の任意の頂点への辺が存在するグラフである．
巡回セールスマン問題ではグラフ G における頂点を場所と見立て，辺を道と見立てることにより，以下のように定義される．全ての場所を 1 度ずつ訪問し，全ての場
所を訪問したのち最初の場所に戻るという条件のもと，総経路長を最も短くする場
所の訪問の仕方を見つけよ，という問題である．場所 i と場所 j の距離を i,j とし，

t 番目に訪問する場所を v(t) と表すことにすると，総経路長はL=N

v(t),v(t+1) ,v(N + 1) = v(1),(25)v(i) = v(j), ∀i = j.

(26)

t=1

と表現される．ただし，N は場所数である (N = |V |)．

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

これを QUBO を用いて表現することを考える．バイナリ変数を xi,t ∈ {0, 1} と設定する (1 ≤ i, t ≤ N )．ただしここで，t 番目に場所 i を訪問することを xi,t = 1と表す．このとき，総経路長 L を QUBO の Hamiltonian として表すと，Hcost =

N
N 
N 


xi,N +1 = xi,1 ∀i.

i,j xi,t xi,t+1 ,(27)

t=1 j=1 i=1となる．ただし，以下の制約条件を満足する必要がある．
N

xi,t = 1, ∀t,(28)

xi,t = 1, ∀i.

(29)

i=1
N

t=1

式 (28) は，各ステップ t において 1 箇所の場所にいることを表し，式 (29) は，各場
所に 1 回ずつ訪問することを表す．グラフ分割問題を考えたときと同様，これらの制約条件を満たすときにエネルギーが低くなるようなハミルトニアンを設計すればよい．すなわち，

Hconstraint−1 =Hconstraint−2 =

N
N


t=1

i=1

i=1

t=1

N
N



2
xi,t − 1

,

(30)

.

(31)

2
xi,t − 1とすれば，これらが最小エネルギー 0 のとき，式 (28)，(29) を満足する．
したがって，巡回セールスマン問題の QUBO 表現は，

H = Hcost + μ1 Hconstraint−1 + μ2 Hconstraint−2
=

N 
N 
N


i,j xi,t xi,t+1

t=1 j=1 i=1

+ μ1

N
N


t=1

(32)

i=1

2
xi,t − 1

+ μ2

N
N


i=1

2
xi,t − 1

.

(33)

t=1

となる．ここで μ1 ならびに μ2 はハイパーパラメータである．グラフ分割問題と同様，これらのハイパーパラメータには下限値が存在する．

4.3.3 不等式で表現される制約条件がある場合
イジングマシンを用いて組合せ最適化問題を処理する際，不等式で表現される制約条件が存在する場合がある．不等式等式で表現される制約条件が存在する組合せ最適化問題の例として，以下で与えられるナップサック問題を考えよう．ナップサッ
ク問題においては，N 個のアイテムがあり，それぞれのアイテムには価値と重さが《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

定義されている．また，重さ W まで詰め込めるナップサックが定義されている．このとき，ナップサックの重さ制約を満たし，かつ，価値が最大となるようなアイテムの選び方はどうなるか，を探索するのがナップサック問題である．ここで，アイテム

i の価値を pi ，重さを wi とする．
これを QUBO を用いて表すことを考える．バイナリ変数を xi ∈ {0, 1} と設定する (1 ≤ i ≤ N )．ただしここでアイテム i をナップサックに入れる場合を xi = 1 と表す．このとき，ナップサックに入れるアイテムの総価値 P と総重み W はそれぞれ
P =

N


p i xi ,

(34)

i=1
N


W =

wi xi .

(35)i=1と表される．イジングマシンを用いる際には「最小化問題」として定式化する必要がある．そのため，

Hcost = −N

p i xi .

(36)

i=1

として，ナップサックの目的関数を QUBO で表現することができる．次に，不等式で表現される制約条件，すなわち，W ≤ W を QUBO を用いて表現することを考えよう．いま，yj ∈ {0, 1} (1 ≤ j ≤ W) なるバイナリ変数を導入する．これを用いる
ことで，W ≤ W を満たすときに最小値 0 を取る QUBO を構成することができる．


Hconstraint =

1−

W


2
yj

j=1

+

W


jyj −

j=1

N


2
w i xi

.

(37)

i=1

以上より，ナップサック問題の QUBO 表現は，

H = Hcost + μHconstraint
2  W

2
N
W
N




=−
p i xi + μ 1 −
yj
+
jyj −
w i xi
.
i=1

j=1

j=1

(38)
(39)

i=1

となる．

5 イジングマシンを用いた応用探索事例紹介
本章では，量子アニーリングマシンやイジングマシンの応用探索がどのように進められているかについて紹介する．これらの応用探索の主領域は大きく分けて 3 つあり，組合せ最適化問題，機械学習，物理・化学モデルシミュレーションである．

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

5.1 組合せ最適化問題における応用探索事例
4 章では，各種の組合せ最適化問題の目的関数並びに制約条件をイジングモデルやQUBO で表現することを見てきた．ここで述べた知見を用いて，様々な組合せ最適化問題についてのイジングマシン応用探索が進められている．具体的な例として，イ
ジングマシンの応用探索が行われ始めた時期に報告されたポートフォリオ最適化に対するイジングマシン適用に関する研究について見ていく．
ポートフォリオとは，株や債券などの資産に対する資産配分のことである．経済学者 Markowitz による平均・分散モデル [33] を皮切りに，資産配分比率を決定する
ポートフォリオ選択モデルの研究が行われている [34]．資産配分を行う場合，なるべく期待収益が高く，なるべくリスクが低くなるように行いたい．その際，期待収益とリスクのトレードオフを考慮して最適なポートフォリオを選択する必要がある．

Markowitz は資産 i(1 ≤ i ≤ n，ただしここで n は投資対象資産数) の期待収益を
過去の収益 Ri の平均 E(Ri )，リスクを過去の収益の分散 V (Ri ) という簡潔な指標で表現した．これらの指標のトレードオフを考慮して投資家の効用を最大化するよ
うに各資産への資産配分 w = (w1 , · · · , wn )（ただしここで wi (1 ≤ i ≤ n）は非負整数）を決定する問題は，資産の合計を K ，投資家のリスク選好を表すパラメータを γ として以下の指標を最大化するような問題として定義できる：

maximize Ew (R) −Ew (R) =Vw (R) =nγ
Vw (R)
2subject towi E(Ri ),

i=1
n 
n


n


wi = K,

i=1(40)

wi wj C(Ri , Rj ).

i=1 j=1

ただしここで C(Ri , Rj ) は資産 i, j の収益率の共分散である．実際の資産運用での投資単位や取引コストに関する制約条件を考慮し，かつ資産数が多い場合にはこの問題は最適解を得ることが難しい．
このようなポートフォリオ選択問題に対して，Rosenberg ら [35] は量子アニーリ
ングを用いる方法を提案している．一般に量子アニーリングで解を得るためには問題形式を QUBO として表現する必要がある．そのため式 (40) における整数変数を

2 値変数へ変換する必要があり，また，制約条件を QUBO を用いて表現しなければならない．整数変数 w を 2 値変数で表すための 1 つの方法は，例えば D 次元の 2値ベクトルを x として，以下のように表現することである：
w=D
2d−1 xd .

(41)

d=1

また，制約条件については制約条件を違反することに対する，以下のようなペナル

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

ティ関数を作成する．

P (w) = n2wi − K

.

(42)

i=1

これらを用いて，式 (40) は以下の QUBO で表現できる：

x∗ = argmax Ew (R) −xγ
Vw (R) − μP (w) .
2

ここで μ は正の実数である．これは制約条件を違反しないようにするためのハイパーパラメータであり，4 章で紹介した制約条件を取り扱うときに出てくるものである．また，文献 [32] は上で述べた平均・分散モデルを広告配信の選択での効用最大化に応用しており，広告配信にて安定的に収益を得ることのできる可能性を示している．
他にも組合せ最適化問題に対するイジングマシンの応用探索として，渋滞回避を目指した経路探索問題に対する取り組み [36] や，工場内の無人搬送車の経路最適化 [37]，矩形パッキング問題 [38], スロット配置問題 [39], 誘導部分グラフ同型問
題 [40], アミューズメントパーク経路最適化 [41] などが挙げられる．

5.2 機械学習における応用探索事例
機械学習に対するイジングマシン適用可能性についても進められている．機械学
習において何らかの関数を最大化あるいは最小化する部分について，イジングモデル
や QUBO で置き換えることによりイジングマシンの適用を図るというものである．
機械学習は「学習」と「推論」からなり，それぞれに対するイジングマシンの適用について以下で述べる．

5.2.1 機械学習の「学習」部分に対する適用
機械学習の「学習」部分に対する適用の草分け的研究として，QBoost について紹介する．QBoost は Neven らによって提案されたアンサンブル機械学習の方法である [42]．アンサンブル機械学習とは，精度の低い学習器（弱学習器）を複数組み合わせて精度の高い学習器（強学習器）を作ることを指す．ここで，入力 x ∈ RM に対する
弱学習器 i(1 ≤ i ≤ N ) の出力を hi (x) ∈ {−1, 1} とする．また，弱学習器 i の使用の有無を表現するバイナリ変数 wi ∈ {0, 1} を導入し，H(x) = sign(N
i=1 wi hi (x))

で与えられる学習器を生成することを考える．できるだけ少ない弱学習器を用いてより良い性能を得るためにはどの弱学習器を選択すべきかを考える．
正しい入出力の組，すなわち教師データとして，(xs , ys ) を用意する．ただし

s = 1, · · · , S であり，入力は xs ，出力は ys である．この教師データを再現するよ
うに {wi }N
i=1 を決定する．つまり，学習データに対する二乗誤差と正則化項の線形

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

和で与えられる以下のハミルトニアンを最小化する問題とみなすことができる．

H(w) =

S

s=1



1 
wi hi (xs ) − ys
N i=1
N

2

+ λ||w||0(43)

ただしここで ||w||0 は w の L0 ノルムであり，wi ∈ {0, 1} であることから，||w||0 = N
i=1 wi と表せる．また λ は正則化項の強さを決めるパラメータである．
L0 ノルムは従来の最適化手法で効率的に取り扱うことが難しかったが，上の式はQUBO の形式になっていることから，量子アニーリングマシンで処理することが可能である．
他にも機械学習の「学習」部分に対する適用を検討した例として，非負二値行列因
子分解について，量子アニーリングマシンを用いた研究結果についても報告されている [43]．

5.2.2 機械学習の「推論」部分に対する適用
次に，機械学習の「推論」部分に対するイジングマシンの適用事例として，マテ
リアルズインフォマティクスにおけるブラックボックス最適化に対するデモンスト
レーション研究について紹介する [44]．マテリアルズインフォマティクスにおいては，機械学習を駆使することにより，所望の性能を持つ材料の探索を高速化することを目的とした研究が数多くなされている．論文 [44] では，マテリアルズインフォマ
ティクスのある問題に対して，イジングマシンの適用可能性が検討されている．波長選択性を持つ熱放射物質をマイクロメートルオーダーの非均一構造を持つメタマ
テリアルで設計することを目的とし，どのような構造の場合により効率の良い熱放射物質となるかを高速に探索する新しい方法を提案した．
数値計算による材料探索におけるボトルネックは大きく分けて二種類ある．第一に，構造を特定した場合においても，単一のシミュレーション自体に長い時間を要してしまう場合，第二に，単一のシミュレーション自体はそれほど長い時間を要しない
が，構造のバリエーションが非常に多いため，全ての構造についてシミュレーションを実行し，目的とする性能を持つ物質を探索するという戦略を取ると，総時間として長い時間を要してしまう場合に分類することができる．第一の場合については，シミュレーション方法自体を工夫する必要がある．一方で第二の場合については，既存シミュレーション方法自体はそのまま用い，入力する構造を機械学習により適切に選ぶことで，目的とする物質を探索するために要する総計算時間を短縮するという方法を取ることができる．本研究はこの第二の場合について検討しており，既存
シミュレーション方法はそのまま用いて，入力する構造だけを量子アニーリングで選択するというスキームのため，プログラムを大幅に書き換える必要がないという実用的な利点がある．
手続きとしては以下の通りである．第一に，ランダムに構造を生成し，それぞれについてシミュレーションを実行する．ただしここで構造は 0-1 変数の組 {xi }Ni=1で表現できるとする．生成した構造を入力とし，シミュレーションから得られた
物性値を y(x) とする．予測モデルとして，以下の式で定義される Factorization

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

machine [45] を使う：
y(x) =

N

wi xi +

i=1

N 
N 
K


vik vjk xi xj .

(44)

i=1 j=1 k=1

あらかじめ事前準備として，全通りの構造組み合わせ数に比べて十分小さい S 個の構造についてシミュレーションを行い，上記の Factorization machine を学習する．ここで論文 [44] では，wi や vik を得るために Adam(Adaptive moment estimation)を用いた．次のようにして，これらのパラメータ wi や vik を用いることで QUBOが生成できる．

H(x) =NN 
Qij xi xj ,xi = {0, 1},(45)

i=1 j=1



Qij = K
k=1 vik vjk
Qii = wi(i = j)(46)

これを量子アニーリングマシンで処理することにより，準最適な構造 {xi }N
i=1 が出力される．量子アニーリングマシンから出力された新たな構造について，更にシミュレーションを実行し，先ほどと同様，Factorization machine を学習し直し，次の構造選択に利用する．これにより，従来の機械学習手法を用いた方法より短時間で，より効率の良い熱放射物質の構造を発見することが可能になった．

5.3 物理・化学モデルシミュレーションにおける応用探索事例
物質シミュレーションへの適用が挙げられる．これについては，現在の量子アニー
リングマシンで取り扱うことが可能なハミルトニアンを用いた量子化学計算 [46, 47]や，ランダムイジングモデルのシミュレーション（スピングラス相転移）の観測 [48]や，トポロジカル相転移である Berezinskii–Kosterlitz–Thouless 転移 (BKT 転移)の観測 [49]，フラストレーション系のシミュレーション [50] など，様々な研究が進んでいる．

5.4 補足以上，本稿では，量子アニーリングの計算処理方法の概要，組合せ最適化問題における応用探索，機械学習における応用探索について紹介した．紙数の関係から，量子アニーリングの応用探索事例を網羅的に紹介するには至らなかった．様々な応用探索事例については，D-Wave ユーザカンファレンスでの講演動画が掲載されている

web サイト [51] を参照されたい．

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

6 ソフトウェア開発環境
組合せ最適化問題をイジングマシンで処理する際には，様々な工程を経る必要がある．これらの工程に多くの手間を掛けなければならないという状況では，イジン
グマシンに対する参入障壁が高くなってしまい，結果としてイジングマシン分野の発展が促進されなくなってしまう．5 章で述べたような様々な応用探索事例が出てきている中，ソフトウェア開発環境の構築の重要性は高まってきている．最近，オープ
ンソースソフトウェアあるいは研究用途においては無料で利用できるソフトウェア
開発環境がいくつか世に出ている．ここではそのいくつかについて紹介したい．
まず，量子アニーリングマシンを開発している D-Wave Systems による D-Wave

Ocean SDK について見ていく．web サイト [52, 53] などに詳細な解説が記載されているが，D-Wave Ocean SDK は，量子アニーリングマシン D-Wave を利用するためのソフトウェアがまとめられている開発キットである．Python でコーディング
することができ，

pip install dwave-ocean-sdk
でインストール可能である．イジングモデルや QUBO を所定の形式で記載すること
で，簡単に量子アニーリングマシン D-Wave で問題を処理することが可能になる．
web サイト [52] でも紹介されている PyQUBO と呼ばれるオープンソースソフト
ウェアも有用である．PyQUBO はイジングモデルや QUBO の係数行列を表現する
ことを容易にするソフトウェアである [32, 54, 55]．他にも PyQUBO には，制約条件を満たしているかをチェックする機能，整数・バイナリ変数の各種変換機能，論理変数の使用機能，量子アニーリングマシン D-Wave 以外の各種イジングマシンとの接続機能などが含まれている．これも Python でコーディングすることができ，

pip install pyqubo
でインストール可能である．
また，イジングモデルや QUBO のヒューリスティック最適化ライブラリとして提供されている代表的なものの一つにオープンソースソフトウェア OpenJij が挙げられる [56]．量子アニーリングマシンやイジングマシンで組合せ最適化問題を処理している様々な先行研究において行われているベンチマーキングの際に用いる指標についての取り扱いが容易である．また，Graphics Processing Unit（GPU）を用いたシミュレーションも可能であるという点も特徴として挙げられる．これも Python
でコーディングすることができ，

pip install openjij
でインストール可能である．
最近，量子アニーリングクラウドとして Fixstars Amplify が公開された [57]．3
章で，様々なグループによって開発されているイジングマシンはそれぞれ異なる内部アルゴリズムで動作していることを述べた．そのため，それぞれのマシンのポテ
ンシャルを引き出すチューニング方法はそれぞれのマシンで異なる．マシン間の違《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

いを可能な限り吸収し，ユーザが本来行いたかったソフトウェア開発に専念するミ
ドルウェアとして開発された．これも Python でコーディングすることができ，

pip install amplify
でインストール可能である．
以上見てきたように，現在，様々なソフトウェア開発環境が構築されつつある．こ
れによりこれからますますより多くの分野・業種におけるイジングマシンの適用が進むと期待される．

7 まとめ
本原稿では，組合せ最適化問題に対する新しい計算技術である量子アニーリング
やイジングマシンの基礎並びに応用事例を紹介した．量子アニーリングマシンやイ
ジングマシンが次々に開発，改善されている現在においてもなお，解決すべき課題は山積している．より優れた量子アニーリングマシンやイジングマシンを開発する下支えとなる理論研究は現在も活発に進められており，また現在ある量子アニーリン
グマシンやイジングマシンのポテンシャルを引き出す使い方を提案する研究も盛んである．また，応用探索の研究についてもまだまだ発展途上である．物理学と情報科学ならびに情報工学の交差点に位置づけられるこの分野へ，様々なバックグラウ
ンドを持つ研究者や技術者の参入が待ち望まれている．

謝辞
本原稿の作成にあたっては，これまで共同研究をしてくださった方々を始め，議論をしてくださった方々から得た知見に基づきます．この場を借りて感謝申し上げます．また，歴史と伝統の深い物性若手夏の学校において，講義の機会を与えてくださった岩田健寛氏に大変感謝致します．

参考文献[1] 梅谷俊治. しっかり学ぶ数理最適化 モデルからアルゴリズムまで. 講談社サイエンティフィク, 2020.
[2] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in thetransverse Ising model. Phys. Rev. E, Vol. 58, pp. 5355–5363, Nov 1998.
[3] Tadashi Kadowaki. Study of optimization problems by quantum annealing. Ph.D. thesis, Department of Physics, Tokyo Institute of Technology,
1998.
[4] Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization bysimulated annealing. science, Vol. 220, No. 4598, pp. 671–680, 1983.
[5] David S Johnson, Cecilia R Aragon, Lyle A McGeoch, and Catherine

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

Schevon. Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Operations research, Vol. 37, No. 6, pp.
865–892, 1989.
[6] David S Johnson, Cecilia R Aragon, Lyle A McGeoch, and Catherine
Schevon. Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Operations research,
Vol. 39, No. 3, pp. 378–406, 1991.
[7] Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on
pattern analysis and machine intelligence, No. 6, pp. 721–741, 1984.
[8] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, and et al. Quantum
annealing with manufactured spins. Nature, Vol. 473, No. 7346, pp. 194–
198, 2011.
[9] Satoshi Morita and Hidetoshi Nishimori. Convergence theorems for quantum annealing. Journal of Physics A: Mathematical and General, Vol. 39,
No. 45, p. 13903, 2006.
[10] Arnab Das and Bikas K Chakrabarti. Quantum annealing and related
optimization methods, Vol. 679. Springer Science & Business Media, 2005.
[11] Arnab Das and Bikas K Chakrabarti. Colloquium: Quantum annealing
and analog quantum computation. Reviews of Modern Physics, Vol. 80,
No. 3, p. 1061, 2008.
[12] Shu Tanaka, Ryo Tamura, and Bikas K Chakrabarti. Quantum spinglasses, annealing and computation. Cambridge University Press, 2017.
[13] 西森秀稔, 大関真之. 量子アニーリングの基礎. 共立出版, 2018.
[14] Masanao Yamaoka, Chihiro Yoshimura, Masato Hayashi, Takuya
Okuyama, Hidetaka Aoki, and Hiroyuki Mizuno. A 20k-spin Ising chip tosolve combinatorial optimization problems with CMOS annealing. IEEE
Journal of Solid-State Circuits, Vol. 51, No. 1, pp. 303–309, 2016.
[15] Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi, Tomohiro Sonobe,
Shuhei Tamate, Toshimori Honjo, Alireza Marandi, Peter L. McMahon, Takeshi Umeki, Koji Enbutsu, Osamu Tadanaga, Hirokazu Takenouchi, Kazuyuki Aihara, Ken-ichi Kawarabayashi, Kyo Inoue, Shoko Utsunomiya, and Hiroki Takesue. A coherent Ising machine for 2000-node
optimization problems. Science, Vol. 354, No. 6312, pp. 603–606, 2016.
[16] Takuya Okuyama, Masato Hayashi, and Masanao Yamaoka. An Ising
computer based on simulated quantum annealing by path integral Monte
Carlo method. 2017 IEEE International Conference on Rebooting Computing, ICRC 2017 - Proceedings, Vol. 2017-Janua, pp. 1–6, 2017.
[17] Chihiro Yoshimura, Masato Hayashi, Takuya Okuyama, and Masanao Ya-

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

maoka. Implementation and Evaluation of FPGA-based Annealing Processor for Ising Model by use of Resource Sharing. International Journalof Networking and Computing, Vol. 7, No. 2, pp. 154–172, 2017.
[18] Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante, Toshiyuki
Miyazawa, Hirotaka Tamura, and Helmut G. Katzgraber. Physics-inspired
optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics, Vol. 7, No. 48, pp. 1–14, 2019.
[19] Hayato Goto, Kosuke Tatsumura, and Alexander R. Dixon. Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems. Science Advances, Vol. 5, No. 4, pp. 1–9, 2019.
[20] Fixstars Amplify Annealing Engine: Fixstars Amplify. https://amplify.
fixstars.com.
[21] M Maezawa, K Imafuku, M Hidaka, H Koike, and S Kawabata. Designof quantum annealing machine for prime factoring. In 2017 16th International Superconductive Electronics Conference (ISEC), pp. 1–3. IEEE,
2017.
[22] Masaaki Maezawa, Go Fujii, Mutsuo Hidaka, Kentaro Imafuku, Katsuya
Kikuchi, Hanpei Koike, Kazumasa Makise, Shuichi Nagasawa, Hiroshi
Nakagawa, Masahiro Ukibe, et al. Toward practical-scale quantum annealing machine for prime factoring. Journal of the Physical Society ofJapan, Vol. 88, No. 6, p. 061012, 2019.
[23] Yuya Seki and Hidetoshi Nishimori. Quantum annealing with antiferromagnetic ﬂuctuations. Physical Review E, Vol. 85, No. 5, p. 051112, 2012.
[24] Yuya Seki and Hidetoshi Nishimori. Quantum annealing with antiferromagnetic transverse interactions for the hopﬁeld model. Journal of Physics
A: Mathematical and Theoretical, Vol. 48, No. 33, p. 335301, 2015.
[25] Yuki Susa, Johann F Jadebeck, and Hidetoshi Nishimori. Relation between quantum ﬂuctuations and the performance enhancement of quantum annealing in a nonstoquastic hamiltonian. Physical Review A, Vol. 95,
No. 4, p. 042321, 2017.
[26] Layla Hormozi, Ethan W Brown, Giuseppe Carleo, and Matthias Troyer.
Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass.
Physical review B, Vol. 95, No. 18, p. 184416, 2017.
[27] Yuya Seki, Shu Tanaka, and Shiro Kawabata. Quantum phase transitionin fully connected quantum Wajnﬂasz–Pick model. Journal of the PhysicalSociety of Japan, Vol. 88, No. 5, p. 054006, 2019.
[28] Neil G Dickson, MW Johnson, MH Amin, R Harris, F Altomare,
AJ Berkley, P Bunyk, J Cai, EM Chapple, P Chavez, et al. Thermally assisted quantum annealing of a 16-qubit problem. Nature communications,Vol. 4, No. 1, pp. 1–6, 2013.

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)[29] Andrew Lucas. Ising formulations of many np problems. Frontiers in
Physics, Vol. 2, p. 5, 2014.
[30] 組合せ最適化問題のイジング模型定式化. https://quantum.fixstars.com/
techresources/research/ising-model-formulation/.
[31] T-Wave. https://qard.is.tohoku.ac.jp/T-Wave/.
[32] Kotaro Tanahashi, Shinichi Takayanagi, Tomomitsu Motohashi, and Shu
Tanaka. Application of Ising machines and a software development for
Ising machines. Journal of the Physical Society of Japan, Vol. 88, No. 6,
p. 061010, 2019.
[33] Harry Markowitz. Portfolio selection. Journal of Finance, Vol. 7, pp.
77–91, 1952.
[34] 今野浩. 理財工学〈1〉―平均・分散モデルとその拡張. 日科技連出版社, 1995.
[35] Gili Rosenberg, Poya Haghnegahdar, Phil Goddard, Peter Carr, KeshengWu, and Marcos López De Prado. Solving the optimal trading trajectory
problem using a quantum annealer. IEEE Journal of Selected Topics in
Signal Processing, Vol. 10, No. 6, pp. 1053–1060, 2016.
[36] Florian Neukart, Gabriele Compostella, Christian Seidel, David
Von Dollen, Sheir Yarkoni, and Bob Parney. Traﬃc ﬂow optimization
using a quantum annealer. Frontiers in ICT, Vol. 4, p. 29, 2017.
[37] Masayuki Ohzeki, Akira Miki, Masamichi J Miyama, and Masayoshi Terabe. Control of automated guided vehicles without collision by quantum
annealer and digital devices. Frontiers in Computer Science, Vol. 1, p. 9,
2019.
[38] Kotaro Terada, Daisuke Oku, Sho Kanamaru, Shu Tanaka, Masato
Hayashi, Masanao Yamaoka, Masao Yanagisawa, and Nozomu Togawa.
An Ising model mapping to solve rectangle packing problem. In 2018
International Symposium on VLSI Design, Automation and Test (VLSIDAT), pp. 1–4, 2018.
[39] Sho Kanamaru, Daisuke Oku, Masashi Tawada, Shu Tanaka, Masato
Hayashi, Masanao Yamaoka, Masao Yanagisawa, and Nozomu Togawa.
Eﬃcient Ising model mapping to solving slot placement problem. In 2019
IEEE International Conference on Consumer Electronics (ICCE), pp. 1–
6, 2019.
[40] Natsuhito Yoshimura, Masashi Tawada, Shu Tanaka, Junya Arai, Satoshi
Yagi, Hiroyuki Uchiyama, and Nozomu Togawa. Eﬃcient Ising model
mapping for induced subgraph isomorphism problems using Ising machines. In 2019 IEEE 9th International Conference on Consumer Electronics (ICCE-Berlin), pp. 227–232, 2019.
[41] Yosuke Mukasa, Tomoya Wakaizumi, Shu Tanaka, and Nozomu Togawa.
Visiting-route recommendation in amusement parks and its evaluations by《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)

an Ising machine. In 2021 IEEE International Conference on Consumer
Electronics (ICCE), pp. 1–6, 2021.
[42] Harmut Neven, Vasil S Denchev, Marshall Drew-Brook, Jiayong Zhang,
William G Macready, and Geordie Rose. Nips 2009 demonstration: Binary classiﬁcation using hardware implementation of quantum annealing.
Quantum, pp. 1–17, 2009.
[43] Daniel O’Malley, Velimir V Vesselinov, Boian S Alexandrov, and Ludmil B Alexandrov. Nonnegative/binary matrix factorization with a DWave quantum annealer. PloS one, Vol. 13, No. 12, p. e0206653, 2018.
[44] Koki Kitai, Jiang Guo, Shenghong Ju, Shu Tanaka, Koji Tsuda, Junichiro
Shiomi, and Ryo Tamura. Designing metamaterials with quantum annealing and factorization machines. Physical Review Research, Vol. 2, No. 1,
p. 013319, 2020.
[45] Steﬀen Rendle. Factorization machines. In 2010 IEEE International Conference on Data Mining, pp. 995–1000. IEEE, 2010.
[46] Rongxin Xia, Teng Bian, and Sabre Kais. Electronic structure calculations
and the Ising Hamiltonian. The Journal of Physical Chemistry B, Vol. 122,
No. 13, pp. 3384–3395, 2017.
[47] Michael Streif, Florian Neukart, and Martin Leib. Solving quantum chemistry problems with a D-Wave quantum annealer. In International Workshop on Quantum Technology and Optimization Problems, pp. 111–122.
Springer, 2019.
[48] R Harris, Y Sato, AJ Berkley, M Reis, F Altomare, MH Amin, K Boothby,
P Bunyk, C Deng, C Enderud, et al. Phase transitions in a programmablequantum spin glass simulator. Science, Vol. 361, No. 6398, pp. 162–165,
2018.
[49] Andrew D King, Juan Carrasquilla, Jack Raymond, Isil Ozﬁdan, Evgeny
Andriyash, Andrew Berkley, Mauricio Reis, Trevor Lanting, Richard Harris, Fabio Altomare, et al. Observation of topological phenomena in a
programmable lattice of 1,800 qubits. Nature, Vol. 560, No. 7719, pp.
456–460, 2018.
[50] Andrew D King, Jack Raymond, Trevor Lanting, Sergei V Isakov, Masoud
Mohseni, Gabriel Poulin-Lamarre, Sara Ejtemaee, William Bernoudy, IsilOzﬁdan, Anatoly Yu Smirnov, et al. Scaling advantage over path-integral
monte carlo in quantum simulation of geometrically frustrated magnets.
Nature communications, Vol. 12, No. 1, pp. 1–6, 2021.
[51] YouTube Channel (D-Wave Systems). https://www.youtube.com/user/
dwavesystems.
[52] D-Wave Ocean Software Documentation.
https://docs.ocean.
dwavesys.com/en/stable/.

《講義ノート》

物性研究・電子版 Vol. 10, No. 1, 101206(2022年3月号)[53] OpenJij Tutorial 0.3.0 documentation. https://openjij.github.io/
OpenJijTutorial/build/html/ja/004-DWaveOceanSDK.html.
[54] PyQUBO. https://pyqubo.readthedocs.io/en/latest/.
[55] Mashiyat Zaman, Kotaro Tanahashi, and Shu Tanaka. PyQUBO: Python
library for QUBO creation. IEEE Transactions on Computers, pp. 1–1,
2021.
[56] OpenJij. https://openjij.github.io/OpenJijTutorial/build/html/
index.html.
[57] Fixstars Amplify. https://amplify.fixstars.com/.