量子アニーリングの現状と展望

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

東北大学
大学院情報科学研究科

西森 秀稔

出来ることゲート模型（回路方式）

量子アニーリング

原理的には任意の計算組み合わせ最適化問題，サンプリング，量子シミュレーション

強み

指数的な高速化が保証されてい ノイズに強い。最適化問題は，機るアルゴリズムがいくつかある。 械学習（人工知能）など社会的影
素因数分解，量子シミュレーショ 響が大きい問題を含む。
ン，機械学習など

弱み

ノイズに弱く、ノイズに強くするに 高速化が保証されている重要なは膨大な規模が必要で大規模アルゴリズムがまだない。
化が困難。

現状

数十量子ビット

2000量子ビット

見通し

小規模なら5，6年で実現か。
「ハイブリッド」モデル「ハイブリッド」モデルでの試用が始まっている。

量子コンピュータの主な使い道
 最適化（主にアニーリング）
配送，ポートフォリオ，仕事の割り当て，機器の配置，故障診断など
流通，運輸，自動車，金融，鉄鋼，電機，通信，IT，

 量子シミュレーション（主にゲート）
創薬，肥料合成，燃料電池設計など
 機械学習（ゲート，アニーリング）
量子ボルツマン（サンプリング），量子機械学習など• 量子アニーリングによりこれらのタスクが高速に実行できるかどうかは、厳密には保証（証明）されていない。
• ゲート方式は｢汎用｣ゆえこれら以外にも使えるが，一般の用途には速くない。
実質的には専用機。

量子ビットの基礎-- 超伝導リング --1と0が同時に存在

Johnson et al.
(Nature 2011)

4

2つの数

4=2x2つの数

0,100, 01, 10, 110000, 0001, 0010, 0011
0100, 0101, 0110, 0111
1000, 1001, 1010, 1011
1100, 1101, 1110, 1111

16=24個の数

00000, 00001, 00010, 00011
00100, 00101, 00110, 00111
01000, 01001, 01010, 01011
01100, 01101, 01110, 01111
10000, 10001, 10010, 10011
10100, 10101, 10110, 10111
11000, 11001, 11010, 11011
11100, 11101, 11110, 11111

32=25個の数

8=2x2x2つの数
000, 001, 010, 011
100, 101, 110, 111

000000, 000001, 000010, 000011
000100, 000101, 000110, 000111
001000, 001001, 001010, 001011
001100, 001101, 001110, 001111
010000, 010001, 010010, 010011
010100, 010101, 010110, 010111
011000, 011001, 011010, 011011
011100, 011101, 011110, 011111
100000, 100001, 100010, 100011
100100, 100101, 100110, 100111
101000, 101001, 101010, 101011
101100, 101101, 101110, 101111
110000, 110001, 110010, 110011
110100, 110101, 110110, 110111
111000, 111001, 111010, 111011
111100, 111101, 111110, 111111

64=26個の数
5

巡回セールスマン問題
経路をビット列で表現
1000000100010000001000001
この数に応じた長さd

経路をビット列で表現
1000001000001000001000001
この数に応じた長さd量子アニーリングによる最適解探索•

ビット列が決まると経路長が決まる。

•

最初は量子力学的な重ね合わせですべての経路が同じ確率で同時に存在。

•

次第に量子力学効果を弱めていくと，経路長が短い経路の確率が大きくなる。

Qubit by superconducting circuit− h(Φ1 )σ z − Γ(Φ 2 )σ x
1 0 
01−
 1 0  1 1  = +1 
 0 − 1 0 
 0
 1 0  0 
 0
  = −1 
 0 − 1 1 
1

Johnson et al.
(Nature 473, 194, 2011)

σ z = ⇑a
1  0  = a  + b b 0 1

⇑Interaction⇓⇓

Superposition of two states− σ iz J ijσ zj
0 1

10


 0 1  1   0   =  10
 0   1 
 0 1  0   1   =  10 1   0 

σ x = ⇑ to ⇓⇓ to ⇑

Harris et al.
Phys. Rev. B 80, 052506 (2009)

量子アニーリングの定式化
目的 : 組み合わせ最適化問題

イジング模型の基底状態

相互作用{Jij} (と局所磁場 {hi})が与えられたとき Hclassicalを最小にする{σiz} を探す

H classical = −∑ J ijσ izσ zj

状態探索に量子ゆらぎを使う

H (t ) = H classical + H quantum = −∑ J ijσ izσ zj − Γ(t )∑ σ ix最初の例
シミュレーテッド・アニーリングとの比較
小規模なスピングラス問題 (8 spins)

3
Γ(t ) =t
量子アニーリング

3T (t ) =t
シミュレーテッド（古典）アニーリング

Kadowaki and Nishimori, Phys. Rev. E 58, 5355 (1998)

1億倍速いというのは本当か

DW2X is 100 million times faster than SA andQMC on single core.
Denchev et al,Phys Rev. X 6, 031015 (2016)最近のベンチマークテスト
16x16のスピングラス問題
キメラをユニットとする埋め込み (8 physical qubits = single logical qubit)

直接表現 (a physical qubit = a logical qubit)

Albash and Lidar, “Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing”
Phys. Rev. X8, 031016 (2018)

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

単一量子ビットのコヒーレンス時間: 10-100 ns
計算時間 : μs to ms133次元量子スピングラスのシミュレーション
Harris et al, Science 361, 162 (2018)

トポロジカル相転移（Kosterlitz-Thouless転移）のシミュレーション

King et al, Nature 560, 456 (2018)

最近の理論の進展
新しい量子効果制御方式

 非疑似古典 (non-stoquastic) ハミルトニアン
 非一様 inhomogeneous な横磁場制御
 リバース・アニーリング(reverse annealing) 計算途中での一時停止 pausingNon-stoquasticハミルトニアン• 負符号問題のために古典的にシミュレート困難な（強い量子効果の）項を入れる。
• これにより，従来の量子アニーリングより指数関数的に計算が高速化される例が見つかっている。
• 高速化されるだけでなく，汎用になることも分かっている。
• D-WaveやIARPA QEO（米国国家プロジェクト）で，この効果を取り入れる回路の研究が急速に進んでいる。
Frontiers in ICT, 4, 2 (2017), PRE 85, 051112 (2012), J. Phys. A 48, 335301 (2015)

Non-stoquastic ハミルトニアン
2Impossible to simulate classically (sign problem). “Strong” quantum effects.

1st order transition(Exponential time)
2nd order transitionPolynomial time

Conventional method

Non-stoquasticity leads to an exponential speedup (not just impossibility of simulation).
Frontiers in ICT, 4, 2 (2017), PRE 85, 051112 (2012), J. Phys. A 48, 335301 (2015)

横磁場の非一様制御

Random-longitudinal-field Ising model, for which non-stoquastic method doesn’t work

解析結果

Final
1次相転移の消失
Conventional

指数的な高速化（一様制御との比較）

IntialJ. Phys. Soc. Jpn. 87, 023002 (2018), arXiv:1808.01582

有効性の実機での検証

量子ビットごとに横磁場を弱めるタイミングをずらせる。

因数分解に要する時間が短縮

リバース・アニーリング
他の方法で解の候補が分かっている場合，そこから出発してより良い解を見つける。
通常の量子アニーリング
量子性を弱める

量子性が強い状態から始める

解

リバース アニーリング
一度量子性を強める

解候補から始める

混じった状態

量子性を弱める

より良い解

解析結果

Start from the classical state εi and thenincrease quantum fluctuations by HTF

Bad initial state
c=0.7

Moderate initial state
c=0.74

Good initial statec=0.8

1st order
Conventional method

1st order disappears
Phys. Rev. A 98, 022314 (2018)計算途中での一時停止 Pausing

通常は、上の図のように古典項の係数を単純に上げるが、下の図のように途中で一度止めてみる。

一時停止のタイミングを適切に選ぶと、正解率が大きく上がる。
Marshall et al, Phys. Rev. Appl. 11, 044083 (2019)

Topics of Qubits Europe 2019
• 空港でのゲート割り当て DLR• 多モード交通流における最適化: DENSO• 資産運用: GE Research• スケジューリング最適化: BAE Systems• 工場ロボットの動きの最適化: BMW• 生産現場の最適化のハイブリッドアルゴリズム: Volkswagen• 量子化学計算: OTI Lumionics

要約部分の日本語訳

課題と展望理論
 量子アニーリングが高速であることの理論的根拠を確立
 高速化のための拡張機能 非疑似古典効果，非一様横磁場制御，リバース・アニーリング, Pausing,…
 誤り訂正方式

実機開発
 高度な制御方式の実装
 集積化・大規模化への技術的な課題克服（コヒーレンス，素子の均一性，ノイズ，） 超伝導以外の素子（イオン，中性原子など）

展望 当面は古典とのハイブリッドで比較的小規模の問題解決に適用されるだろう。
 大規模な実用問題を解くには理論・実験両面でさらなる研究が必要
 大規模ハード開発には大きなブレークスルーが必要、特にゲート模型では。