量子アニーリングによる量子コンピューティング
東京工業大学
科学技術創成研究院
量子コンピューティング研究ユニット

西森 秀稔
1/31

量子アニーリングの当初の目的
組合せ最適化問題
離散多変数の1価関数を最小化（最大化）する問題
 イジング模型の基底状態を探す問題に帰着
 多くの社会的に重要な課題が組み合わせ最適化問題として定式化できる。
• 交通流の最適化• 仕事のシフト最適化• 投資ポートフォリオの設計• ペイントショップ問題

2/31

組合せ最適化問題のイジング表現
実用的に重要な問題群が最適化問題として表現される。
最適経路探索, ジョブスケジューリング（仕事の割当）, ポートフォリオ作成など

離散多変数関数の最小化（最大化）𝐻𝐻(𝜎𝜎1 , 𝜎𝜎2 , ⋯ , 𝜎𝜎𝑁𝑁 ) , 𝜎𝜎𝑖𝑖 = ±1

イジング模型の基底状態を求める問題

多体長距離相互作用

H = −∑ hiσ i − ∑ J ijσ iσ j − ∑ J ijkσ iσ jσ k − 
ハードの構造に合わせた埋め込み

近接相互作用イジング模型の基底状態
H = −∑ J ijσ iσ j − ∑ hiσ i
3/31

2値ペイントショップ問題•••

ベルトコンベヤー上を多種類の車(ABCDEF)が各種類２台ずつ流れて来る。
各車種を2つの色（赤と青）に塗り分ける。
色の交代はコストがかかるため、交代回数を最小化する。
車の数が増えたり、色の種類が増えると大変難しくなるが、実用上重要な問題。

ADEBAFCBCDEFADEBAFCBCDEFADEBAFCBCDEF

4 回交代
4 回交代
2 回交代

4/31

A D E B A F C B C D E F をIsing模型で表現
隣接する2つの車がともに1回目か、ともに2回目なら同じ色（ ↑ ↑or ↓ ↓ ）になるように揃える相互作用（強磁性相互作用 、
Jij=1）を入れ、1回目と2回目に分かれていれば違う色(↑ ↓or ↓ ↑)になるような反強磁性的相互作用 （Jij=− 1）を入れる。
AADEBAFCBCDEF

A1 D1 E1 B1 A2 F1 C1 B2 C2 D2 E2 F2BF

基底状態で↑なら最初に赤で塗り、↓なら最初に青で塗る。

CED• VolkswagenがD-Waveの量子アニーリング装置で実証実験。従来法で288回の色変化が57回に。
• ただし、古典コンピュータ（通常のコンピュータ）で出来ない計算かどうかは不明© Volkswagen
5/31

量子アニーリングの定式化
𝐻𝐻classical = − � 𝐽𝐽𝑖𝑖𝑖𝑖 𝜎𝜎𝑖𝑖𝑧𝑧 𝜎𝜎𝑗𝑗𝑧𝑧

最適化問題のイジング表現

𝐻𝐻 𝑡𝑡 = 𝐴𝐴 𝑡𝑡 𝐻𝐻quantum + 𝐵𝐵 𝑡𝑡 𝐻𝐻classical = −𝐴𝐴(𝑡𝑡) � 𝜎𝜎𝑖𝑖𝑥𝑥 − 𝐵𝐵(𝑡𝑡) � 𝐽𝐽𝑖𝑖𝑖𝑖 𝜎𝜎𝑖𝑖𝑧𝑧 𝜎𝜎𝑗𝑗𝑧𝑧

量子項は古典的な状態の重ね合わせを作る。

量子項の基底状態から始める 𝐻𝐻quantum→ 1 ⊗ → 2 ⊗ ⋯ ⊗ → 𝑁𝑁= ↑ 1 + ↓ 1 ⊗ ↑ 2 + ↓ 2 ⊗ ⋯ ⊗ ↑ 𝑁𝑁 + ↓ 𝑁𝑁= ↑1 ↑2 ↑3 ⋯ ↑𝑁𝑁 + ↑1 ↑2 ↑3 ⋯ ↓𝑁𝑁 + ⋯ + ↓1 ↓2 ↓3 ⋯ ↓𝑁𝑁
自然な時間発展(Schrödinger)↑↓↓↑↑ ⋯ ↑↓𝐻𝐻classical 古典項の基底状態＝解6/31

実デバイスとしての実現

7/31

導入企業や研究機関（来年導入予定）

他にも米企業、米国家機関、多数のクラウドユーザー
8/31

量子アニーリングの提案
スピングラスの基底状態探索の手段として、純粋に学問的な興味だけから考え出した。

9/31

基底状態の確率の時間変化
量子アニーリングが古典的な方法（シミュレーテッドアニーリング）より高い確率で正解に到達する。
量子アニーリング

古典的なシミュレーテッドアニーリング

Kadowaki and Nishimori, PR E 58, 5355 (1998)
10/31

量子アニーリング論文の引用数
発表してから約15年間は、ほぼ無視されていた。
1998年の論文の引用数の年次変化（Google Scholar）
300
250200150

日本国家プロジェクト開始

アメリカ国家プロジェクト開始
GoogleとNASA がD-Wave マシン導入
D-Wave マシン市販

1005002000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020

私の論文は、発表してから長い間、世間受けしないものが結構ありますほとんどです。

2020年は11月までの実績からの予測値

11/31

最近の研究の方向性
1. 量子シミュレーション
量子アニーリング装置を物理実験装置として使う。

2. 非断熱量子アニーリング（高速性、汎用性、古典シミュレーション不可能性）
断熱量子計算の枠組みを脱して、積極的に励起状態を使う。

3. 非疑似古典効果（高速性、汎用性）
古典シミュレーション不可能な効果による量子加速

4. 高度な量子効果（横磁場）制御
非一様横磁場、逆（リバース）アニーリング、一時停止による熱平衡化
2, 3, 4 のレビュー arXiv:2008.09913
12/31

量子シミュレーションへの展開
物理実験装置としての利用、物質科学への応用

13/31

量子アニーリングによる量子シミュレーションの例
平衡状態の性質••••••

3次元スピングラス
Kosterlitz-Thouless転移
スピンアイスShastry-Sutherland模型
場の理論
量子Griffiths特異性

Harris et al., Science (2018)
King et al., Nature (2018)
King et al., arXiv:2007.10555
Kairys et al., arXiv:2003.01019
Abel et al., arXiv:2003.07374
Nishimura et al., Phys. Rev. A (2020)

非平衡（動的）状態の性質• Kibble-Zurek機構• 拡張Kibble-Zurek機構

Gardas et al., Sci. Rep. (2018)
Weinberg et al., Phys. Rev. Lett. (2020)
Bando et al., Phys. Rev. Res. (2020)
14/31

Kosterlitz-Thouless転移の量子シミュレーション
A. D. King et al., Nature 560, 456 (2018)Z6 模型を、フラストレートしたイジング模型
としてD-Wave上のキメラグラフに表現

渦・反渦の対を観測

相関関数のべき減衰を検証（KT転移の特徴）

15/31

Shastry-Sutherland模型

P. Kairys et al., arXiv:2003.01019

2次元正方格子上のフラストレートしたイジング模型の基底状態の相図• 磁化のプラトーの兆候を観測• 相図が理論とコンシステント

16/31

拡張Kibble-Zurek機構の量子シミュレーション

Y. Bando, Y. Susa, H. Oshiyama, N. Shibata, M. Ohzeki, F. Gómez-Ruiz,
D. A. Lidar, S. Suzuki, A. del Campo, and H. Nishimori, Phys. Rev. Res. 2, 033369 (2020)
17/31

Kibble-Zurek機構の問題意識

Kibble (1976), Zurek (1985)

1次元横磁場イジング模型の量子相転移

01Γ/J↑1 ↑ 2 ↑3  ↑ L + ↑1 ↑ 2 ↑3  ↓ L +  + ↓1 ↓ 2 ↓3  ↓ L

欠陥 (キンク)

横磁場の強さ Γ を有限の速度で変えると、非平衡状態になり、
Γ =0 の最終状態に欠陥が生じる。

問題
アニーリングの時間(ta)を変えると、欠陥数(n) はどう変わるか。n の taについての関数形を明らかに。
18/31

Kibble-Zurek機構の予言𝑑𝑑𝜈𝜈
𝑛𝑛−= 𝜌𝜌 ∝ 𝑡𝑡𝑎𝑎 1+𝜈𝜈𝜈𝜈𝐿𝐿

d: 系の次元n: 平均欠陥数
L: 系の大きさ
ta: 駆動時間 =1/ (パラメータの変化速度)

1次元横磁場イジング模型
𝜌𝜌 ∝ 𝑡𝑡𝑎𝑎− 0 .5

𝜌𝜌 ∝ 𝑡𝑡𝑎𝑎− 0 .28

𝜉𝜉 ∼ Γ − Γ𝑐𝑐 −𝜈𝜈𝜏𝜏 ∼ Γ − Γ𝑐𝑐 −𝜈𝜈𝜈𝜈

孤立系（完全な量子ビット） ν = z = 1環境の影響を受けた系（不完全な量子ビット）ν = 0.63, z = 1.98 (Werner et al., 2005)19/31

1次元鎖上の欠陥数を実験的に数える

20/31

欠陥数（平均値）に関する理論の検証
NASAマシン : 減少率0.20

平均欠陥数の減少率
完全でない量子ビット

理論値0.28

完全な量子ビット

理論値0.5Burnabyマシン : 減少率0.34

実験値 0.20(NASA), 0.34(Burnaby)
21/31

欠陥数の統計に関する理論の検証
完全な量子ビットでの理論値（横線）

0.59
0.13

分布の広がりや非対称性を検証？

実験値▲,●
完全でない量子ビットでの理論値はまだない

量子コンピュータが、理論がまだ確立されていない事柄を予測した（おそらく）初めての例。
22/31

この成果の意義• 完全な量子ビットを想定して展開された理論の結果が、完全でない量子ビットを使った実験（量子エミュレーション？）でも（実験誤差の範囲で）成立していることが分かった。
• 完全でない量子ビットを想定した理論はまだない。本研究はその展開を促している。
• 実験で未知の現象が見つかって、それが理論の展開を促すという物理学の王道。
• ごく短い時間の範囲については古典コンピュータでも検証できるが、ほとんどの範囲では非常に困難。古典コンピュータでは大変困難な計算（実験）を量子コンピュータが行った。
• 物質の性質を量子デバイス上で解明する量子シミュレーションが、量子アニーリングマシンについても重要な方向性であることを示した。今後、さらに発展の可能性。
23/31

現状と近未来
量子アニーリング• （高速性） D-Waveデバイスで、古典コンピュータでは実行が困難なタスクを実行した例は、（Kibble-Zurek機構の話を除いて）多分まだない。まだまだ基礎研究が必要。
• （社会課題の解決）社会課題を組合せ最適化問題としてとらえて、イジング模型で表現することにより、その課題固有の伝統的な手法より迅速に解ける可能性に多くの人が（量子アニーリングをきっかけに）気付き始めている。
• （システムサイズ）実社会の課題をそのまま乗せられるサイズのシステムには現状ではなっていない。量子・古典ハイブリッドが現実的。そのためのユーザーインターフェースがD-Waveから提供されている。
• （基礎研究）量子アニーリングが最適化問題解決の主要な手段として社会的に定着するまでには、基礎理論から実機開発まで幅広い分野での進歩が必要。

（参考）ゲート方式• （量子シミュレーション）NISQデバイスが、古典コンピュータでは扱えない量子化学シミュレーションを実行できるかどうかはまだ分かっていない。そのギャップを埋めるためには大きな飛躍が必要だろう。
Google Quantum AI Laboratory, arXiv:2004.04174 (April,2020)
24/31

まとめ
•

現行のシステムで実証実験が進んでいる。

•

量子シミュレーションにも使われ始めている。

•

大規模な実用化に至るまでには、まだ相当の基礎研究（特に理論）が必要。

•

現行の量子アニーリング装置が古典コンピュータを大幅に上回る計算速度を出せるという一般的な理論的根拠は見つかっていない。基礎的な理論研究が必須。

•

古典コンピュータとの組み合わせ（ハイブリッド）による実用化が当面の目標。

•

本格的な実用化が社会に定着するまでには長い時間がかかる（特にゲート方式）。

25/31

社会的な側面について少し
最大の課題は人材と基礎科学の研究• 日本の最大の弱点は研究者層の薄さ。米国と決定的な開きがある。
• 国内大学で当分野を専門とする研究室は限られている。一部の大学の一部の研究室。
• 大学での組織的な人材育成への財政資源投入が、研究自体への予算配分より中長期的には有効かつ重要。
• この分野は基礎研究、デバイス作成、実証実験などあらゆるレベルの研究開発が同時進行している。
• 基礎研究が終わってから商品開発を進める通常の研究開発と全く異なっている。

26/31

日本政府の戦略

量子技術によるイノベーション
27/31

量子情報科学・技術
quantum information science and technology

米国政府（議会）の戦略方針

米国 国家量子イニシアティブ法「量子情報科学・技術」
28/31

日本政府の戦略

人材育成の優先順位は最下位
29/31

米国政府（議会）の戦略方針

人材育成が最優先課題

米国 国家量子イニシアティブ法

本法律は、次の施策を実施することにより、量子情報科学とその技術面での応用において、米国がリーダーシップを取り続けられる体制を保証することを目的とする。
(A) 量子情報科学技術に通じた研究者、教育者、学生の数を増やし、人材の供給体制を確立する。
(B) 学部、大学院、ポスドクの各レベルにおいて、量子情報科学に関わる学際的なカリキュラムや研究推進の機会の開発を進める。
30/31

基礎科学と教育への投資を！

31/31

本当に量子力学で動いているのか
エネルギースペクトルと量子もつれ
Lanting et al, Phys. Rev. X 4, 021041 (2014)

単一量子ビットのコヒーレンス時間: 10-100 ns、計算時間 : μs to ms

個々の量子ビットが孤立しているときのデコヒーレンスと、量子アニーリングの動作中に多くの量子ビットが結合して多体系を構成しているときのデコヒーレンスはメカニズムが違う。Energy eigenbasisの間のデコヒーレンス。
Albash and Lidar, Phys. Rev. A 91, 062320 (2015)
32/31

量子アニーリングは量子コンピューティングか

量子コンピューティングの現状と展望に関する米国科学・工学・医学アカデミーの膨大な報告書 (2018)33/31

34/31

ゲート模型量子チップによる計算例
Google Sycamore chip
性能（上ほどよい）

完全な正解
近似を考慮した理論値
簡単な問題では、エネルギー値が正解の半分くらいの値に行きつく。

一番難しい問題では１７量子ビットまで量子ビット数

実用（大きな社会課題の解決）に至るまでには飛躍的な進歩が必要
35/31