Googleの「量子超越性」実証とは何なのか？

(2019年10月15日)

　量子コンピューターは量子力学の原理を利用して計算する次世代コンピューターです。大手IT企業の開発競争や無数のスタートアップの誕生、そして米中貿易摩擦の舞台となるなど、世界的な関心が高まっています。最近の注目トピックスは、Financial Times誌が9月21日付けで掲載した、Googleの研究チームが量子コンピューターの「量子超越性」を実証したとするニュースでしょう[1]。

　この文章を書いている時点で、これに関する正式な論文発表はまだありません。本当であればとても画期的な成果で、物理学や計算機科学の歴史に刻まれるような、重要なマイルストーンですが、専門性の高い内容のため憶測や誤解も生じています。ここではGoogleの研究者チームが挑戦したと考えられることと、その結果の重要性についてご紹介します。

１．量子超越性とは？

　「量子超越性」（Quantum Supremacy）とは、スパコンを始めとする現在の計算機ではとても長い時間かかる何らかの計算を、量子コンピューターが圧倒的に高速に実行できることを指します。重要なポイントは、高速であることを示せる計算であれば、何の役にも立たない問題設定でもよいということです。そもそも何かの問題を「解く」必要さえありません。単にスパコンではとても長い時間かかる特殊な計算タスクについて、量子コンピューターなら現実的な時間で計算可能であることを示せれば十分です。

２．上手い問題設定

　どのような計算なら量子コンピューターの高速性を検証できるでしょう？　対戦相手であるスパコンの計算能力はとても優れているので、量子コンピューターに勝ち目のある都合の良い問題設定が必要です[3]。

　経験的に難しいとされている問題のうち、量子コンピューターによる高速解法がすでに知られている「素因数分解」という計算タスクはどうでしょう。大きな数の素因数分解は暗号の安全性の基盤になるほど難しい問題であるにもかかわらず、量子コンピューターで高速に解く方法（Shorのアルゴリズム）が知られています。答え合わせが簡単（大きな２つの数の掛け算をするだけ）なのも、検証に都合がよさそうです。

　問題は、いま開発可能な50量子ビット程度の小規模量子コンピューターでは、スパコンとの差が示せるような巨大な数の素因数分解ができず、実験検証できないことです。

　ですから、（１）理論的・経験的に「難しい」と言える問題で、（２）スパコンで高速に計算する方法はなさそうだと理論的に保証されており、（３）すぐに用いることができる現実的なサイズの小規模量子コンピューターでも計算でき、さらに（４）量子コンピューターの計算結果が正しいことを検証可能、であるような上手い問題を考える必要があります。

３．量子コンピューターのシミュレーション

　量子コンピューターに有利なのは、当たり前かもしれませんが（そして、ちょっとズルい気もしますが）量子コンピューターの動作のシミュレーションです。

　量子コンピューターは量子力学の原理に従って動作します。量子力学の基礎方程式はよく分かっており、量子コンピューターの動作を通常のコンピューターでシミュレーションすることは可能です。例えば、基本素子である量子ビットを10個持つ量子コンピューターが2の10乗（＝1024）通りにわたる並列計算を行う様子は、手元のノートPCでもシミュレーションできます。

　ところが、少しサイズの大きい量子コンピューター（例えば量子ビット数が50）になると、とたんに手に負えなくなります。何も工夫をしなければ、数ペタバイトのメモリを持つようなスパコンが必要になってしまいます。もちろん、一部のデータをメモリに保持し繰り返し使うなどしてメモリを節約することもできますが、今度は計算に膨大な時間がかかってしまいます。何れにせよ、量子コンピューターの動作のシミュレーションは、スパコンにとって難しい問題なのです。

　この困難さを足がかりにGoogleの研究チームが考えた巧妙な問題設定は「ランダム量子回路サンプリング」と呼ばれる特殊な計算タスクです[4]。ここでは詳細に立ち入りませんが、実験では「スパコンのシミュレーションでは何千年という長い時間かかる問題でも量子コンピューターならほんの数100秒程度しかかからない」というような結果が示されることになるでしょう（もちろん、この「何千年も」などという計算時間は、実際にスパコンを稼働させてみるのではなく、あくまでも見積もりです）。この結果は、少なくともこの特定の計算タスクについて、量子コンピューターの方がスパコンよりも圧倒的に高速であることを証明していると言ってよいでしょう。

４量子超越性の実証には何の意味がある？

　量子超越性の実証は、量子コンピューター研究の重要なマイルストーンのひとつです。長年にわたる量子コンピューター研究は、特定の計算タスクでは量子コンピューターのほうが現代の最も強力なスパコンよりも圧倒的に高速だとする理論的な考察を動機としてきました。量子コンピューターがスパコンを凌駕することは理論的にはほぼ確実な状況ですが、今回、その根拠をようやく実験で検証できるというところまできたわけです。

　もしGoogleの研究チームの検証実験が本当に成功しているのであれば、単に世界初というだけでなく、量子力学という自然法則から強力な計算能力を引き出すすべを人類史上初めて手にしたことになります。

　もちろん、ここで用いられた計算タスクには実用的な価値はなさそうに見えます。しかし、最近になって暗号プロトコルや仮想通貨取引の承認などに応用できる可能性も指摘され[5]、もしかしたら、他にも有益な使い道があるかもしれません。

　注意したいのは、この53量子ビットの量子コンピューターは、現代の暗号システムに直接的な脅威を及ぼすものではないということです。この程度の演算能力では、インターネットで広く使われているRSA暗号や、ビットコインなどの仮想通貨で用いられているSHA-256などのハッシュ関数を破るようなことはできないと考えられています[6]。

５．次のステップ

　まず必要なのは、基本的な構図はこのままに、理論的・実験的な抜け穴を塞いで量子超越性の証拠をより強力にしてゆくことでしょう。

　例えば「ランダム量子回路サンプリング」のタスクを高速に計算する方法が新しく見つかるという可能性はないでしょうか？　これがあるかないかは理論計算機科学上の未解決問題である「多項式階層の崩壊」に密接に関わっており、「そんなことは起こりそうにない」と強く信じられていることの一つではあるものの、証明は難しそうです[7]。従って、実験と照らしながらなるべく良い条件つき証明をして、理論的な確からしさを向上させることは重要なステップでしょう。

　次のマイルストーンとしては、超伝導体や磁石などの物質の量子力学的な性質を、50～100量子ビットの規模の量子コンピューターによって高速にシミュレーションできることの実証が挙げられます。この計算タスクは、遙かに高度な制御技術が要求されるものの、明らかに有用です。

　また、これと並行して、量子誤り訂正の実験実証も重要なマイルストーンです。そして、量子誤り訂正が可能であることを示すだけでなく量子超越性と量子誤り訂正を同じ実験系で実証することは、今後の量子コンピューター開発を元気づける非常に重要な意味をもつものとなるでしょう。

参考資料

[1] Financial Times (2019.9.21) “Google claims to have reached quantum supremacy”

https://www.ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17

[2] Quanta Magazine (2019.10.2) “Why I Called It ‘Quantum Supremacy’”

https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/

[3] Qmedia (2018.2.9) “量子コンピュータの挑戦： スーパーコンピュータに勝てるだろうか？”

https://www.qmedia.jp/quantum-beat-super-computer/

[4] Google AI Blog (2018.5.4) “The Question of Quantum Supremacy”

https://ai.googleblog.com/2018/05/the-question-of-quantum-supremacy.html

[5] Shtetl-Optimized (2019.9.23) “Scott’s Supreme Quantum Supremacy FAQ!”

https://www.scottaaronson.com/blog/?p=4317

[6] 高木剛「暗号と量子コンピュータ -耐量子計算機暗号入門-」, オーム社 (2019).

[7] 森前智行「量子計算理論　量子コンピュータの原理」, 森北出版 (2017).

 

 

科学技術振興機構
研究開発戦略センターシステム・情報科学技術ユニット　
フェロー嶋田 義皓