1．は じ め に
気象予測やタンパク質の構造解析，複雑な量子多体系 の解析など，私達の生活を取り巻く多くの問題は組合せ 最適化問題と呼ばれ，問題数の増加に対して計算量が指 数的に増加してしまうため，スーパーコンピュータを用 いても厳密解の解析が困難となる．そこで，より大きな 問題サイズの厳密解を正確に求めることができること， 最適化問題の近似解を古典計算機（量子計算機に対比し てフォンノイマン型の計算機のことを総称する）よりも 効率良く求めることができること，という二つの観点か ら，量子コンピュータの実現が期待されている．2013 年， NASA，Google，大学宇宙研究協会（USRA）が共同で 量子人工知能研究所を設立し，カナダのベンチャー企業D-Wave Systemsによる D-Wave Ⅱという計算機を導入
した．D-Wave Ⅱは 512 個の量子ビットを搭載しており 「新たな動作原理による量子コンピュータ」といわれ話 題になっている．果たして D-Wave は量子系を用いた新 たな原理で，どんなに優秀な古典計算機でも実現し得な いようなコンピュータを実現したのだろうか． 1982年に Feynman らは，量子系のような複雑系を シミュレートするには，古典計算機よりも量子系を用い た計算機のほうがより優れている，と量子コンピュータ の存在を予想した [Feynman 82]．1992 年には Deutsch と Jozsa による最初の量子アルゴリズム [Deutsch 92]， 1994年には Shor の因数分解アルゴリズム [Shor 94]， 1996年には Grover の検索アルゴリズム [Grover 96] な ど，代表的な量子アルゴリズムが発見され，その実装の ために，イオントラップや超伝導回路，冷却原子，光子 など，さまざまな物理系を用いて研究が行われてきた． 2012年にノーベル物理学賞を受賞したアメリカ NIST のWinelandとフランスENSのHarocheは，ともに「個々 の量子系の計測と操作を可能にした画期的な手法の開 発」について，量子コンピュータ研究の発展における大 いなる功績を讃えられた．また，量子コンピュータのみ ならず量子乱数発生器や量子シミュレーションなど，量 子性を用いて古典計算機を凌駕する情報処理を行おうと する研究も，活発に進められている．
2．実現が難しい量子コンピュータ
2･1 量子コンピュータの解ける問題とその性能 量子コンピュータのアルゴリズムは，量子力学的な 重ね合わせと干渉効果を効率的に用いて，確率的に解 を求めるものである．通常の計算機では古典 1 ビット が一度に表すことのできる情報は 0 か 1 のどちらか一 通りであるが，1 量子ビットが一度に表現できる情報は ｜ψ〉＝α｜0 〉＋β｜1 〉といったように任意の複素振幅 α, βによる｜0 〉と｜1 〉の状態の重ね合わせで記述され る．そのため量子ビットの場合，n 個の量子ビットを用 いて一度に表すことのできる状態の数は，実に 2n通り と豊かな表現ができる．ただし古典の並列計算とは異な り，量子並列計算では一度の計算の読出しの結果，2n通 りの計算結果の中から一通りの解だけが読み出される． また，量子コンピュータは汎用計算機ではなく，因数 分解のように量子アルゴリズムが発見されている特定の 問題についてのみ解くことができる．NP 完全問題に対 する量子アルゴリズムは未だ見つかっておらず，量子計 算によってすべての計算問題が P 問題へ帰着させること ができるかという答えは今のところ定かではない．量子 コンピュータが多項式で解くことができる問題は，BQP （Bounded-error Quantum Polynomial time）という計 算クラスに分類され，因数分解などを含んでおりクラスPよりは広く難しいが，NP 完全や NP 困難は含んでい
ないであろうと予想されている．
量子コンピュータの新潮流：
量子アニーリングと D-Wave
The New Trend of Quantum Computing:
Quantum Annealing and D-Wave
宇都宮 聖子
国立情報学研究所情報学プリンシプル研究系Shoko Utsunomiya Principles of Informatics Research Division, National Institute of Informatics.
[email protected], http://www.nii.ac.jp/faculty/informatics/utsunomiya_shoko/
Keywords:
quantum computer, quantum information, quantum annealing, adiabatic quantum computation,2･2 量子コンピュータに必要なリソース 量子コンピュータを実現するにはどのくらいのリソー スを必要とするのだろうか．量子コンピュータの実装が 極めて難しい理由は，外界との相互作用により，量子ビッ トの豊かな重ね合わせ状態がすぐに崩壊してしまい（コ ヒーレンス時間が短いという），量子アルゴリズムの実 行に必要となる正確な量子ビット演算を現実の物理系で 実装することは非常に困難となるためである．これまで に実験的に成功した量子コンピュータの実装例は，7 量 子ビットの核磁気共鳴などを用いた 15＝3×5 の因数分 解 [Vandersypen 01] という規模に留まっている．実際 に量子計算を行うには量子ビットのデコヒーレンス（系 が外界との相互作用により壊れてしまうこと）を修正 するための量子誤り訂正機構が必要となる [Shor 95]． スーパーコンピュータでも解くことができない演算を量 子誤り訂正機構まで含めて量子コンピュータで行った 場合に必要なリソースを見積もった結果がある [Jones 12].それによると，1 024 ビットの因数分解（RSA 暗 号が 1 024 ビットの素因数分解により安全性を保証され ているため）を行うためには実に 108もの量子ビットを 99.9％の精度で個別に制御する必要があるとされ，今の 量子制御技術では実現がとてつもなく難しいと考えられ ている．
3．量子アニーリング
本章では D-Wave の計算機の動作原理となってい る量子アニーリングについて紹介する．最適化問題 に対するアルゴリズムでは，局所解に留まってしま い真の最適解に到達できないことがしばしば問題と なる．Kirtktpatrick らによって提案された焼鈍し法 （simulated annealing：SA）は，金属の焼鈍しという物 理現象にヒントを得たもので，熱的な励起により局所解 から抜け出すことができる．このため，さまざまな問題 に適用できる汎用的近似解法として知られている．ある 問題が，場合の組合せ（この場合は後述のスピン配列） に対して，エネルギーランドスケープとして与えられた 場合を考えてみる．図 1（A）で示す SA は，局所解に陥っ てしまった場合に，その状態から熱的な励起により局所 解から抜け出し，最低基底状態を探索する手法である． 初期状態では，状態をある程度の高温に保ち，徐々に温 度を下げていけば，最終的に基底状態へと到達できると いうものである． 西森らは，局所解から抜け出し最適解を探す方法と して，熱揺らぎの代わりに量子力学的な揺らぎを導入 し，よりエネルギーの低い解を探す方法を，量子アニー リ ン グ（quantum annealing: QA） と し て 提 案 し た [Kadowaki 98]．図 1（B）のように，量子揺らぎによっ て起こるトンネリング効果を用いることでポテンシャル 障壁を通り抜けることができ，徐々にトンネル効果を弱 めていくことによって基底状態を探索する手法である． SA・QA の場合，焼鈍しスケジュールを調整することに より，長時間極限において，確率 1 で基底状態に到達で きることがわかっている． 量子コンピュータにより解くことができる問題は因数 分解などの特定の問題のみに限られているのに対して， QAは下記に述べるように NP 完全・困難問題であるイ ジングモデルを対象として構築されているため，他の NP問題を多項式時間でイジングモデルにマッピングす れば，いかなる NP 問題にも適用できるという点で非常 に魅力的である． 3･1 量子アニーリングの原理 ここで，量子アニーリングの計算原理を紹介する．統 計力学の分野で組合せ最適化問題として，スピングラス と呼ばれる磁性体の問題がよく知られている．この問題 のエネルギー関数（ハミルトニアン）は次式で与えられる． （1） イジング問題はσz i＝±1 の二つの配位をとるイジング スピンが二次元または三次元空間に配列され，スピン間 の相互作用 Ji, jが与えられたとき，一番低いエネルギー をとる各イジングスピン成分の組合せを求める問題であ る．このモデルは三次元の場合，また二次元でかつ各ス ピン成分にλiで表されるポテンシャル勾配がある場合 に，NP 困難であることが知られている [Barahona 82]． このイジングハミルトニアンの基底状態を求めるため に，QA では量子揺らぎを用いて状態探索を行う．式（2） のように，初期状態として，基底状態にシステムを準備 できる初期ハミルトニアン Hiniを準備する．そこから解 きたい問題（上記のイジング問題）Hfinへと断熱的にゆっ くり時間 T をかけ，システム H（t）を変化させていく． （2） 量子力学の断熱定理より，T が十分に大きければ，シ ステムの状態はゆっくりと変化しながらも常に基底状態 に保たれているため，解きたい問題 Hfinの基底状態を 時間 T 後に求めることができる．時間 T が十分長くな く，状態間のクロストークの大きさが基底状態と第一励 起状態のエネルギー差よりも大きいと，状態変化の際に 励起状態に遷移してしまう．図 2 に示すように，ある 時刻において，基底状態と第一励起状態の間のエネル 図 1 焼鈍し法と量子焼鈍し法の違い λ ini fin （A）焼鈍し法 （B）量子焼鈍し法ギーギャップの狭いところでは，断熱の条件を満たすよ うにゆっくりと時間発展をさせれば，状態は最低基底 状態に留まることができる．システムサイズ N によっ てこのエネルギーギャップは指数的に減少する（gmin∝ exp（－cN）（c は正の定数））ので，QA により最適解を 求めるのには，システムサイズに対して指数的な時間が かかってしまう． 3･2 量子アニーリングと量子コンピュータの計算量 QAの考案とほぼ同時期に，量子断熱計算（quantum
adiabatic evolution: QAE）という手法が Farhi らによっ て理論的に示された [Farhi 01]．基底状態が簡単に準備 できるハミルトニアンから出発して，計算したい問題の 答えが基底状態となる別のハミルトニアンへと，断熱的 に状態を変化させていくことで，所望の基底状態を得る ものである．先に示したように QA と QAE は基本的に は同じ計算原理をもつ手法であるが，計算量の問題サイ ズ依存性などを議論するのに QAE はより適している． Aharanovらは，QAE に必要な計算量のクラスは，冒頭 で述べた量子計算機で実現できる計算量のクラス BQP と等価であることを理論的に示した [Aharonov 08]．す なわち，量子計算機と同等の計算パワーは，量子アニー リングマシンによっても実現できるということになる．
4．D-Wave について
D-Waveは 1999 年にブリティッシュコロンビア大学 出身の Rose らによって，QA を実装した量子コンピュー タを商品として開発するベンチャー企業として設立され た．2009 年には Neural Information Processing Systems conference（NIPS）において，Google の Neven らが D-Waveの QA を用いて機械学習の最適化（画像認識に おける識別関数の最適化）を行ったという報告をした． QAは計算機の上で量子効果を取り入れる計算モデル として提案されたものであったが，D-Wave は 2011 年 に QA を超伝導量子ビットで実装した実験結果を発表し た [Johnson 11]．同年，世界初の商用量子コンピュー タとして 128 量子ビットの D-Wave One を売り出し， ロッキード・マーティンと契約したことでも注目を集め た．同製品はその後南カリフォルニア大学に設置され， Miyazawa-Jerniganモデルとして知られる格子タンパ ク質フォールディングモデルの事例を解くなどの計算が 示され，現在もさまざまな研究者達がその性能のベンチ マークにあたっている．QA マシンである D-Wave を量 子コンピュータと定義するかどうかについては，量子性 が効率良く使われているか，量子もつれ状態が計算に効 果を発揮しているか，などのさまざまな論点から現在も 論争が続いている． 4･1 超伝導量子ビットによるプロセッサここでは，D-Wave マシン（D-Wave One,Ⅱを総称する） に使われているプロセッサについて紹介する．D-Wave マ シ ン は 超 伝 導 磁 束 量 子 ビ ッ ト（Superconducting QUantum Interference Device : SQUID）を搭載する計 算機である．SQUID を安定に動作させるためには，外 部からの電磁波をシールドし，20 mK の極低温まで冷 却する必要がある．このため，1 ブロックが 3 m 四方と なる比較的大型の装置となっている． D-Waveマシンは組合せ最適化問題として，イジング スピングラスモデル（式（1））を実装している．イジン グスピンσizは，SQUID の量子化された磁束量子ビット （磁束量子の向きにより固有状態を｜↑〉，｜↓〉を表す） によって実装される．SQUID は強い横磁場をかけると， ｜↑〉と｜↓〉の二つの状態の重ね合わせ状態となり， N個の量子ビットで構成されるシステムの全体の基底状 態は式（3）で表される線形重ね合わせ状態となる． （3） 量子揺らぎによるトンネル効果が非常に大きく，図 1（B） の横軸に表されるようなすべてのスピン配列（N 個のス ピンそれぞれが｜↑〉または｜↓〉である 2N通りの組合せ） に同時に存在している状態に対応する．これをシステム の初期状態として準備する． イジング結合は，量子ビット間に配置された結合用 の別の SQUID を介して実装されている．相互結合の大 きさは，SQUID 間の相互結合インダクタンスの大きさ により正から負へと連続的に変化させることができる． Single Flux Quantum（SFQ）回路により SQUID のイ ンダクタンスへ流す電流値を制御することができ，多 数の局所磁場を独立にコントロールしている．これによ り，イジング結合やゼーマン項の大きさから，個々の 量子ビットの製作段階で生じてしまった微小誤差までを 精密に決定することができる [Harris 10]．このように， D-Waveマシンは極めて制御性の高い装置といえる． D-Waveのプロセッサは 8 個の量子ビットからなる基 本ユニットで構成され，各ユニットから左右上下に最大 12本の結合回路が接続されている．結合回路の配置は 単純な規則に従う，比較的シンプルな構成となっている． NP完全問題を解くために完全グラフを構成するには， 自分以外のすべての量子ビットにサイト数 N の 2 乗の 図 2 エネルギー固有値の時間発展 〉 〉
数の結合をつくる必要があるが，D-Wave では相互結合 回路の煩雑化を防ぐため，マイナーエンベッディングと いう手法を用いている [Choi 10]．この手法を用いると 実装サイズ N に対して√－N の完全グラフを実装できるた め，512 量子ビットを搭載する D-Wave Ⅱでは 20 サイ ト程度の組合せ最適化問題を扱っていることになる． イジングハミルトニアン以外の問題を D-Wave Ⅱで解 く場合は，任意の問題をイジングハミルトニアンの形式 にマッピングするためのブラックボックスが用意されて いる．イジング問題に多項式時間でマッピングできる問 題であればどんな問題でも D-Wave マシンで解くことが できるという点で，量子コンピュータよりも汎用性が極 めて高いといえる．また，D-Wave マシンには量子コン ピュータで重要となる量子誤り訂正機構がない．そのこ とが D-Wave マシンの計算の性能にどう影響するのかは 今のところはっきりとはわかっていない． 4･2 D-Wave に量子性はあるのか D-Waveマシンを量子コンピュータと位置付けてよい のか，その計算機構に量子性はあるのか，Aaronson ら を中心に D-Wave の信憑性に関してさまざまな論争が続 いている [Aaronson]．そんな中，D-Wave が本当に QA を実装できているのか，Troyer らは 108 量子ビットの D-Wave One（DW）と，計算機による量子アニーリン グ（SQA），焼鈍し法（SA），スピンダイナミクス（SD） を用いてイジングスピングラスモデルを解いた解の特性 を比較し，その性能評価を行った [Boixo 13]． イジングモデルのさまざまなインスタンスを実装し， その成功確率のヒストグラムをプロットすると，DW と SQA，SD はやさしい問題（成功確率が 1 に近い問題） と難しい問題（成功確率が 0 に近い問題）に高い確率分 布が集中する二峰性の特徴を示した．一方，SA の場合 は 0.5 付近の成功確率（普通の問題）に最も多く確率分 布が集中し，そこを中心に簡単な問題と難しい問題の方 向へ確率が減少する（単峰性）異なる特徴を示している． それぞれ四つの手法で同じ問題を解いてその成功確率を 比較した結果を見ると，DW と SQA は同じ問題に対す る成功確率が似通っており，DW と SD では，同じ問題 に対して DW のほうが高い成功確率を出している．DW と SA の比較に関しては，SA の繰返しの回数が多くなる ほど SA のほうが成功確率が高くなる傾向を示している． また，QA の計算を有限時間τの間に計算を終わらせ る際に得られた答えが，最適解にどのくらい近いか（残 留エネルギーという）を見積もることが，現実的な計算 では重要な評価手法となる．各インスタンスについて， その成功確率と残留エネルギーの分布を比較したとこ ろ，DW と SQA ではその分布が似通っていて，DW と SA，SD とは異なる分布形状を示しているとの結果が示 されている． また，DW，SA，SQA に対して問題サイズ √－N に対 するアニーリング時間のスケーリングが示されている． 厳密解法のスケーリングは exp（c√－N）（cは定数）より は悪くならないことが知られており，SQA の場合も同 様な結果が示されている．DW の場合は，同じ問題につ いて何度か試行を行い，正しい解を見つけるのにかかっ た試行回数とアニーリング時間の積から計算時間のス ケーリングを求めている．99％の確率で正解を求める場 合は問題サイズに対する計算時間の発散が見られるが， 50％程度の成功確率だと SA，SQA と同等のスケーリン グを示している．これらの結果から，D-Wave の特性は 他の手法に比べてかなり QA に近い特徴を示していると 結論付けられている． 一方で量子ビットの基本的な特性として評価される量 子もつれ（エンタングルメント）などの実験的証拠が十 分に示されていないことから，D-Wave マシンではきち んと量子性が使われているのかという懐疑的な指摘があ る．また，SQUID のコヒーレンス時間はせいぜい 1 ～ 10 nsであり，アニーリングに必要な時間よりも短いこ とから十分な量子効果が使われているのかを疑問視する 声もある．それにもかかわらず，先に述べたように DW の特性として QA に近い結果が出されていることは興味 深い．また，実際には D-Wave を稼働する際は有限の温 度揺らぎや位相揺らぎなどのシステムノイズが存在する ため，それが理想的な QA を実装した場合に比べてどの ように作用しているのか，などの問題は検討されるべく 残されている． 4･3 D-Wave のベンチマーク
D-Wave社の相談役である McGeoch らは，D-Wave
が古典計算機に比べてどのくらい早く計算できるかと いうベンチマークテストを行った [McGeoch 13]．比較 対象とした古典計算機のアルゴリズムは CPLEX，AK という厳密解法，TABU search というメタヒューリス ティック解法の三つであり，これらと 512 量子ビット の D-Wave Ⅱを比較している．比較に用いた計算問題 は，W2SAT，QUBO，QAP という三つの NP 困難問題 で，これらを解いた際の計算時間を比較している．古 典計算機として使用したマシンは七つの Lenovo Think Station S30 0568 workstation で，それぞれが Intel Xeon E5-2609 /2.4GHz Quad-Core with 16GB RAM を 搭載している（OS は Ubuntu 64-bit 12.04 LTS）．
計算時間を固定して問題サイズを変化させたときに， 各アルゴリズムが求めることのできる解の良さが比較さ れている．QUBO 問題を解いた場合，D-Wave Ⅱのア ニーリング時間 491 ms に合わせて同じ時間後に他のプ ログラムが最適解を発見する確率を比較したところ，N＝ 400まで問題サイズを増やしていくと，四つの手法を比 較すると，ほぼ 100％の確率で QA が最も良い解を求め ることに成功している．また，問題サイズを N＝439 に 固定し，100％近い確率で最適解を求めるのに必要な時
間を比較したところ，DW は CPLEX の 3 600 倍速い 0.5 sの時間で最適解を求めている．これらの結果により， ある特定の条件下で DW は古典計算機の性能を上回るこ とが実験的に示された．SA と QA ではそれぞれに得意 な問題，不得意な問題が違うように，いくら優れた計算 機でも汎用性をもたせると，特定の問題を解くことに特 化したデバイスよりも性能が劣ってしまう．そのため上 記の比較は必ずしも DW と古典計算機の正当な比較とは いえない，という指摘もある．
5．ま と め
D-Waveマシンに対する見解はさまざまであり，現在 も計算機科学の理論研究者らを中心として論争が続いて いる．D-Wave 社の最も目を見張るべき点は，量子コン ピュータのアルゴリズムが発見されて以降，世界中の 研究者がハードウェアの実現に苦戦してきた中，早い段 階で QA という別の量子計算機の実現方向に舵を切り， 500量子ビットという従来の 30 倍以上も大きな規模の 量子ビット演算を製品という形で実現させた点であろ う．D-Wave 社の扱う超伝導量子ビットの技術は，専門 家の間でも高く評価されており，その計算機としての真 偽性は，現在も慎重に議論され続けている． 量子コンピュータの実現における最大の敵であるデ コヒーレンスを克服する手段として，量子誤り訂正表面 コードなど，ユニバーサル量子計算を実装技術に近づけ る手法が考案されている一方で，QA のように新たな量 子計算の概念が注目され始めた．量子計算に本当に必要 なのはエンタングルメントなのか，それとも全く異なる 量子効果なのか．大規模なシステムサイズで動作できる 量子計算機を実現するためには，実世界の物理系と相性 の良い量子効果を効率的に利用することが鍵となるであ ろう．量子計算の基本原理が再び議論の中心となる大き な転換期に差し掛かり，量子計算によって開かれる計算 のパラダイムは，さらなる可能性が期待されている． 謝 辞 本稿の執筆に際しご協力をいただきました東京大学 中村泰信氏，国立情報学研究所 山本喜久氏，理化学研究 所 玉手修平氏，東京大学 高田健太氏に，心より感謝申 し上げます．◇ 参 考 文 献 ◇
[Aaronson] The Blog of Scott Aaronson: D-Wave: Truth finally starts to emerge, http://www.scottaaronson.com/ blog/?p=1400
[Aharonov 08] Aharonov, D., et al.: Adiabatic quantum computation is equivalent to standard quantum computation,
SIAM Review, Vol. 50, No. 4, pp. 755-787（2008）
[Barahona 82] Barahona, F.: On the computational complexity of Ising spin glass models, J. Phys. A: Math. Gen., Vol. 15, pp. 3241-3253（1982）
[Boixo 13] Boixo, S., et al.: Quantum annealing with more than one hundred qubits, arXiv, quant-ph, 1304.4595（2013） [Choi 10] Choi, V.: Minor-embedding in adiabatic quantum
computation:Ⅱ．Minor-universal graph design, arXiv: 1001. 3116（2010）
[Deutsch 92] Deutsch, D. and Jozsa, R.: Rapid solutions of problems by quantum computation, Proc. Royal Society of
London, A, Vol. 439, p. 553（1992）
[Farhi 01] Farhi, E., et al.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science, Vol. 292, pp. 472-475（2001）
[Grover 96] Grover, L. K.: A fast quantum mechanical algorithm for database search, STOC’96, pp.212-219（1996）
[Harris 10] Harris, R., et al.: Experimental demonstration of a robust and scalable flux qubit, Phys. Rev. B, Vol. 81, p. 134510 （2010）
[Johnson 11] Johnson, M. W., et al.: Quantum annealing with manufactured spins, Nature, Vol. 194, p. 473（2011）
[Jones 12] Jones, N. C., et al.: Layered architecture for quantum computing, Phys. Rev. X, Vol. 2, p. 031007（2012）
[Kadowaki 98] Kadowaki, T. and Nishimori, H.: Quantum annealing in the transverse Ising model, Phys. Rev. E, Vol. 58, p. 5355（1998）
[McGeoch 13] McGeoch, C. C., et al.: Experimental Evaluation of an Adiabatic Quantum System for Combinatorial Optimization, Proc. ACM Int. Conf. on Computing Frontiers
Article, No. 23（2013）
[Richard 82] Richard, F. and Peter, W. S.: Simulating physics with computers, SIAM J. Computing, Vol. 374, p. 1（1982） [Shor 94] Shor, P. W. : Algorithms for Quantum Computation:
Discrete logarithms and factoring, Proc. 35th IEEE FOCS, pp. 124-134（1994）
[Shor 95] Shor, P. W.: Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A, Vol. 52, pp. R2493-R2496（1995）
[Vandersypen 01] Vandersypen, L. M. K.: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature, Vol. 414, pp. 883-887 （2001） 2013年 12 月 25 日 受理 宇都宮 聖子 国立情報学研究所，情報学プリンシプル研究系，特 任准教授．2008 年東京大学大学院情報理工学系研 究科博士課程修了．光半導体の物性やレーザを用い た新しいタイプの量子コンピュータの開発研究に従 事．
