量子コンピューティングとは何なのか?

高校生の頃だったか。ブルーバックスの「量子コンピュータ」を読んで以降、ずっと、量子コンピュータというものに憧れを抱いてきた。大学・大学院では量子情報光学の研究室にいた。その後、就職により量子コンピュータからは離れたが、不思議な縁があって、今は企業で量子コンピュータの応用研究をしている。そんな私は、量子コンピュータのアーリーアダプタだと自認している。

ハードウェアとしての「量子コンピュータ」、あるいは、量子コンピュータによる計算を表す「量子コンピューティング」とは何なのか? かつては、その意味は明確であったように思う。しかし、今現在、量子コンピューティングとは何か? と問われると、少し困ってしまう。

何故なのか。恐らく、以下のような背景があるのではないか。

• D-Waveの量子アニーリング型量子コンピュータの登場

• NISQ型量子コンピュータの登場

• 量子コンピュータのシミュレーション技術の発展

量子コンピュータとは何であったか?

かつては、量子コンピュータとは何であったか?
量子コンピュータとは、従来のコンピュータよりも本質的に計算が速いコンピュータであった。

計算の速さとは何か?

「本質的に計算が速い」の意味を説明するには、計算の速さとは何かを説明する必要がある。

計算の速さとして、まず初めに思いつくのは、計算にかかる時間を時計で測った時間の長さである。そのような指標は "wall-clock time" とも呼ばれる。
CPUやメモリが高速化したり、CPUのコアが複数に増えると、その分、同じプログラムであっても、その実行にかかる wall-clock time が短縮される。CPUがx倍速くなったり、コアの数がx倍になると、(実際にはそううまくいかないが、理想的には) wall-clock time はx倍速になる。これは非常に嬉しいことだが、見方によっては、この高速化は実はあまり大したことではない。

別の速さの観点として、計算したい問題の大きさがn倍になったとき、問題を解くのにかかる時間が何倍になるか、というものがある。計算量のオーダーと呼ばれている考え方だ。
単純な問題では、問題の大きさがn倍になっても、計算にかかる時間は変わらなかったり、n倍にしかならない。しかし、複雑な問題では、それよりも大きなスケールで、計算にかかる時間が増えていく。
例えば、都市と、都市間をつなぐ道路の情報が与えられている。それを見て、全ての都市をただ一度だけ通るような経路を見つけられるだろうか。都市や道路の数が増えると、そのための手順は増えないだろうか。
あるいは、全ての道路をただ一度だけ通るような経路だと、どうだろうか(実は、全ての道路を通る方の問題は、都市や道路の数が増えてもあまり計算量が増えない)。

計算量のオーダーの考え方では、計算量の大まかな増え方のみを考慮し、CPUがx倍速くなった、などの影響は「高々定数倍」として無視する。単純な問題では計算にかかる時間で困ることはあまりないし、複雑な問題では、問題の大きさが増えたときの計算量の増え方と比べて、数倍増えただけでは焼け石に水だからだ。逆に、どれだけ定数倍の高速化を行っても、計算量のオーダーを落とすことはできない。

量子コンピュータによる高速化

本題に戻ろう。量子コンピュータは、計算量のオーダーを落とすことができる。それにより、定数倍の高速化では不可能だった計算が可能になる。

すべての問題が高速になるわけではないが、量子コンピュータにうまく載せられる問題は、通常のコンピュータのハードウェアやソフトウェアをどれだけ改善しても成し遂げられない、計算量のオーダーの削減ができる。
その問題の一例として、物性や材料に関する計算、素因数分解や離散対数問題、確率過程に関する問題、線形代数の問題などがあり、実用上重要なものも含まれている。

量子コンピュータは、こういった意味で、本質的に従来のコンピュータよりも計算が速い。

「量子アニーリング方式」の登場

2012年に、突如、カナダの無名のベンチャー企業D-Wave社から「量子コンピュータ」と称するものが発表された。これは、従来考えられていた意味での量子コンピュータとは全く異なるものであった。

これまでの量子コンピュータは、従来のコンピュータの延長にあるものとして考えられていたが、D-Wave社の「量子コンピュータ」は、特定の形の問題のみを解くことができるものだった。

焼きなまし法と量子アニーリング

何かの関数 f(x) があったとして、その値を最小にするような x を求める問題を考えたい。こういった問題を「最適化」と呼ぶ。f(x) がどういったものかが全く分からなければ、xを総当たりで求めるしかない。しかし、 x を少しだけ変えた x' について、 f(x) と f(x') が近い値を取るのであれば、x を少しずつ変えていくことで、総当たりをしなくても最も良い x が求まるかもしれない。しかし、そのような方法では「局所最適」に陥ってしまう。

このような問題をうまくかわす方法として、焼きなまし法 (シミュレーテッド・アニーリング) がある。これは、x を少しずつ変えて、より良い x を作る過程で、一時的により悪い x になるのを許容することで局所最適ではない最適解を得るというものだ。最初は比較的高い確率で x が悪くなるのを許容し、徐々に、良くなるもののみを許容するように変えていく、という手順で x を求める。

この方法は、金属の「焼きなまし」処理から着想を得たようだ。金属の温度を上げて徐々に冷却することで、金属内部のひずみを取る。金属は結晶構造をとっているが、エネルギーが「局所最適」になるように結晶化してひずんでいたものを、一旦温度を上げて「局所最適」を崩して徐々に冷やしながら再結晶化させることで、ひずみのない最適な状態となる。

量子アニーリングは、焼きなまし法を元にしたアルゴリズムで、イジングモデルという磁性体を表す量子力学的な物理モデルに磁場をかけたときの時間発展の過程を用いて最適化を行う。この方法は1998年に門脇氏・西森氏により発明された。通常のコンピュータで行う最適化アルゴリズムとして提案され、量子コンピュータとは無関係な手法であった。

「量子アニーリング」を行うハードウェア

D-Waveは、超伝導技術を用いて「量子アニーリング」を実際の物理的な系で作り、実際に時間発展をさせて最適化を行う。通常のコンピュータで行う「量子アニーリング」は比較的重い計算が必要だが、物理的な系で行うとより計算が速い。

では、D-Waveは通常のコンピュータでは解けない問題を、量子力学的な物理モデルを用いたハードウェアで、本質的に速く解いているか。そこが一つの論点であった。

結論から言うと、D-Waveが通常のコンピュータよりもどれくらい速いのかは未だに答えが出ていない。D-Waveが速いという十分な証拠が揃っていないのである。

そのような理由に、焼きなまし法や量子アニーリングが発見的手法であることが挙げられる。焼きなまし法を行っても、最適化問題が必ず解けるとは限らない。実用上は広い場面で答えが出ることが経験的には分かっているのだが、理論的には最適解にたどり着く保証はなく、また、実際に最適解にたどり着かない問題もある。こういった性質のため、どのアルゴリズムがいいか、という比較がしづらい。よって、仮に「量子アニーリング」を用いた最適化計算の手法としては従来のコンピュータよりもD-Waveの方が速かったとしても、最適化計算の手法として、通常の焼きなまし法や、その他のアルゴリズム (タブーサーチなどが有名) と比べ、従来のコンピュータに勝っているとは言えない。

そして、実際に、D-Waveに投入できる問題と同じ形式の問題を、FPGAやGPUなどの従来のコンピュータ技術を用いて解く技術が多数出ている。富士通のデジタルアニーラ、東芝のSQBM+、日立のCMOSアニーリングなどが挙げられる。具体的な性能の評価は上述の通り難しいので個人的な感想だが、控えめに言ってD-Waveは苦戦しているように見える。

ハードウェアの面でも、D-Waveはまだまだ課題を抱えている。重ね合わせ状態や量子もつれ状態などの量子力学的な性質は寿命が短いが、D-Waveでは計算のどの段階までそれらの性質を保てているのか、という議論は前からある。また、ハードウェアの構造により問題を埋め込む方法が制約され、そのために変換をかける必要があったり、ハードウェアに載せられる問題が小さいために問題を分割する必要があったりという課題もある。従来のコンピュータで問題を分割できるのなら、最後まで解くこともできるのではないか、と考えたら負けである。

量子コンピュータとは何であるか ver.2

D-Waveの方式は、従来の量子コンピュータとは全く異なるもので、また、量子力学的な性質を利用して本質的に高速に問題を解けているかは不明である。かつてはD-Waveは本物の量子コンピュータではないという意見もあったが、今はそのような意見はあまり見かけなくなった。
しかし、異なるものであることは明らかなので、D-Waveの方式を「量子アニーリング方式」や「イジングマシン方式」と呼んで、これまでの意味での量子コンピュータを「量子ゲート方式」と呼ぶことが定着した。

それにより、「量子コンピュータとは何か?」と聞かれた際には「量子コンピュータには量子アニーリング方式と量子ゲート方式の2種類があって」と答えないといけなくなった。また、量子アニーリング方式に投入できる形式の最適化問題は、FPGAやGPUを用いた従来の計算技術によっても解くことができる。この時点で既に説明が大変なのではないか。

FTQCとNISQ: 2つの量子ゲート方式

ここからは「量子ゲート方式」に話を戻そう。量子ゲート方式は、計算量のオーダーの意味で従来のコンピュータと比べて高速化することが理論的に示されているのだった。
しかし、そのハードウェア開発は難しい。現在は量子ゲート方式のハードウェアも商用化されているが、それらはノイズによる計算の誤りの影響を強く受けている。結果、今ある量子コンピュータは、計算量のオーダーの意味での高速化を成し遂げられていない。

「誤り」と量子誤り訂正符号

非常にミクロな現象を扱う量子コンピュータは、環境中のノイズに敏感で、微弱なノイズであっても内部の状態に影響が及ぶ。その結果、計算に「誤り」が生じる。計算を誤ったまま計算を進めることで、誤りは伝播し、最終的に得られた答えはデタラメなものになる。誤りが多いと、高速化するかしないか以前に、そもそも問題が解けないのである。

実は、誤りを克服するための理論は既にある。量子コンピュータの内部状態に対し、「量子誤り訂正符号」をかけて、誤りを取り除きながら計算を進めていく。量子誤り訂正符号とは、多数の誤りの多い量子ビットをいくつも使って、少数の誤りのほとんどない量子ビットを作る方法だ。そして、量子誤り訂正符号で量子状態をノイズから保護しながら計算を進める方式を「誤り耐性量子計算 (FTQC: Fault-Tolerant Quantum Computing)」と呼ぶ。

FTQCを行うには、膨大な数の量子ビットが必要となる。必要な量子ビット数は、ハードウェアのエラーレートやアプリケーションで許容できるエラーによって異なる。しかし、文献を見ると、誤りの少ない量子ビットを1つ作るために、物理的な量子ビットを1000前後使っているようだ。これらを多数並べ、計算に必要な補助量子ビットやモジュールも合わせて配置すると、トータルで数10万〜数100万量子ビットが必要という途方もない結果が出る。

現時点で作られている量子ビット数は、IBMの433量子ビットが最大だ。また、量子誤り訂正符号は、49量子ビットを用いた小規模な誤り訂正をGoogleが行った。FTQCへの道は近づいては来ているが、まだ遠い。

NISQの時代とその苦難

一方で、量子ゲート方式のハードウェアが出来てきたのだから、現状作れるハードウェアで動作する、新しい量子アルゴリズムやアプリケーションの研究がされ始めた。そういった試みは、NISQ (ニスク, Noisy Intermediate-Scale Quantum)と呼ばれている。特に、量子化学計算、最適化計算、機械学習などの用途で、現状のハードウェアに合わせたNISQアルゴリズムが作られた。しかし、元々量子ゲート方式のモチベーションであった、本質的な高速化ができていることは未だ示されていない。さらに、NISQアルゴリズムは誤差がそれなりにあり、また、wall-clock timeの意味でも非常に低速だ。NISQの実用上のキラーユースケースはまだ見つかっていない。

量子コンピュータとは何か ver.3

量子コンピュータは量子ゲート方式と量子アニーリング方式に分かれるが、量子ゲート方式もさらに2つの方式に分かれる。1つが、量子コンピュータの元々のモチベーションであった本質的な高速化を目指す「FTQC」で、ノイズの影響を克服する必要があり、まだ先の技術である。もう1つが、現状作れる量子コンピュータを、ノイズの影響を受けながらも意味のある計算を目指す「NISQ」で、何に使えるのかはまさに研究途上である。

量子ゲート方式のシミュレーション技術

量子ゲート方式の量子コンピュータの計算を、従来のコンピュータでシミュレーションすることを考える。
実は、どれほど時間をかけてもいいのなら、シミュレーションは可能である。一方で、高速なシミュレーション方法はないと考えられている。もし仮に高速にシミュレーションができるのであれば、量子アルゴリズムを従来のコンピュータでシミュレーションすれば高速に計算ができ、量子コンピュータは不要である。

状態ベクトルによるシミュレーション

量子ゲート方式の計算のシミュレーションを行う最も単純な方法は、量子コンピュータが取りうる内部状態を全て配列で用意し、量子ゲートひとつひとつに対してそれを計算することである。それは可能であるが、シミュレーションを行いたい量子ビットの数が1つ増えるごとに、必要なCPUとメモリの量が2倍になる。結果、この方法には時間的・メモリ的な制約がある。

2022年3月の富士通の論文で、HPCを用いて36量子ビットのシミュレーションを行ったこと、40量子ビットのシミュレーションにも取り組んでいることが記されている。HPCを利用しても、40量子ビット前後のシミュレーションしか行うことができない。

しかし、状態ベクトルでのシミュレーションは本当によく用いられる。量子ビット数が少ない場合は高速に動作するし、量子ビット数以外の制約がなくて非常に使いやすい。また、SIMDやGPUでの並列化、複数のゲートを融合するなどの、より高速な実装も多数出てきている。

テンソルネットワークによるシミュレーション

より技巧的な方法のシミュレーションもある。どの量子ビット同士が接続しているかに着目すると、内部状態を全て列挙しなくてもシミュレーションを行える。また、少しの近似計算を行って精度と引き換えに計算を効率化したり、計算過程を外部ストレージに保存することで時間と引き換えに計算を大規模化できる。テンソルネットワークという、物理学で使われていた道具を、量子ゲート方式の計算のシミュレーションに応用すると、量子ビットが多数あっても量子ビット間の相互作用が実はそれほど大きくない場合に、効率的に計算ができる。

Googleは2019年、従来のコンピュータでは1万年かかる計算をNISQの量子コンピュータを使って200秒で計算をしたと発表した。最も議論を呼んだポイントは、本当に従来のコンピュータで1万年かかるのか、であった。

IBMはすぐに、現実的な時間で同じ問題が解けることを発表し、また、2021年には中国の研究者らがテンソルネットワークを使って、HPCで同じ問題を304秒で解いている。それでもなお、量子コンピュータの方が速いが、このような数倍の高速化ではなく、より本質的な高速化を目指していたはずだ。量子コンピュータは従来のコンピュータよりも本当に速いのだろうか?

古くから知られていたスタビライザ型シミュレータ

量子コンピュータの速さの秘密は、重ね合わせ状態や量子もつれ状態だ、といった説明は非常によく見かける。端的に言うと、それだけでは足りていない。重ね合わせ状態や量子もつれ状態があっても、多数の量子ビットを効率的にシミュレーションする方法があるからだ。量子誤り訂正符号の理論では、スタビライザという考え方が多用される。量子コンピュータの内部状態を追跡するかわりに、内部状態に対して何も作用が起こらない演算(これをスタビライザと呼ぶ)を追跡する。その計算は、状態ベクトルの計算よりも遥かに容易で、スタビライザの追跡ができる範囲の演算に限れば、シミュレーションはより多くの量子ビットで行える。
スタビライザの追跡ができる範囲の演算には、重ね合わせや量子もつれを作る演算も含まれるから驚きだ。

スタビライザで追跡できない演算はNISQにもFTQCにも非常によく出てくる。少数であればスタビライザで追跡できない演算も力技でシミュレーションが行えるという研究もある。また、そのようなシミュレーションの結果をデータセットに用いて機械学習を行い、ノイズのある量子コンピュータからノイズのない場合の結果を推定するという研究もある。

量子コンピューティングとは何なのか?

量子コンピュータの意味は、まだ理論しかなかった頃には明確であった。実際にハードウェアが出来始めると、理論通りのものを作ることの難しさに直面しながらも、実用化への期待も高まり、近年は研究開発が大きく進展している。その過程で、量子コンピュータとは何かを語るのが非常に困難になった。

量子コンピュータには量子ゲート方式と量子アニーリング方式があり、また、量子ゲート方式はFTQCとNISQに分かれる。そして、いずれの方式も、従来のコンピュータで量子コンピュータと同じことをする試みがあり、それらはかなり上手くいっている。

量子コンピュータのどの方式も、また、シミュレーションも含め、全ての量子コンピューティングの関連技術に共通する軸がひとつある。それは、物理に制約されたこの世界で、いかにして計算を限界まで効率化するか、である。量子コンピューティングとは、現実世界で可能な計算の極限を目指す取り組みだ。その先にある、計算の捉え方の変革こそが、量子コンピューティングの起こすイノベーションの最も重要なものとなるだろう。