この文章の目的
量子計算機に対する期待が高まる一方、虚実入り混じった情報がインターネット等に溢れており、長期的に量子計算機に対する信頼を揺るがしかねないと感じています。
ある程度理解されている方はそういった情報に惑わされないかもしれませんが、一般の方にとっては何が正しいのか分からないのが現状です。
そこで、量子計算機の話題に触れる際に前提として知っておいた方が良いことを、いくつか挙げました。
一般の方が量子計算機に関する話を見かけたときに、おかしな話に惑わされる頻度が減れば幸いです。
内容に誤りなどがあれば、ご連絡頂けると助かります。
1.計算可能性は、古典計算機も量子計算機も同じ
計算リソース(メモリや計算時間)を無限に利用できれば、「古典計算機で計算できる問題＝量子計算機で計算できる問題」です。
量子計算は、指数関数的に巨大なユニタリ行列のかけ算なので、古典計算機で行列計算すれば原理的にはシミュレートできます。
そのため、指数関数個の古典計算機を並列化したり、天文学的な時間をかけて良いのであれば、古典計算機で量子計算機をシミュレートできます。
しかし、現実的には、そういうことはできません。
(それができるのであれば、指数時間かかる古典アルゴリズムに困ったりしていないですよね)
2.すべての計算が高速化になる訳ではない
古典計算機には、スパコン、GPU、FPGAなど、様々な種類があり、得意なことが違います。
それぞれの計算機は得意な分野で活躍しています。
一方で、量子計算機によって高速化できるのは、効率的な量子アルゴリズムが発見された問題です。
得意なことが違うため、すべての計算が高速になる訳ではありません。
そのため、量子計算機が実用化しても、スパコンなどの古典計算機は必要です。
スパコンのニュースが出るたびに「これからは量子計算機の時代なのに、スパコンにお金をかけるなんて～」みたいな言説を見かけますが、スパコンは必要です。
3.一部の量子計算は、古典計算機で効率的にシミュレートできる
標語的な言い方になりますが、量子計算の能力をフルに使った計算を、「ユニバーサルな量子計算」と呼びます。
ユニバーサルな量子計算ではなく、量子計算の能力の一部しか使っていないケースでは、古典計算で効率的にシミュレートできることがあります。
たとえば、Cliffordゲート(H,S,X,Y,Z,CNOTゲート)とX,Y,Z測定のみを使った量子計算は、古典計算機で効率的にシミュレートできることが知られています(Gottesman–Knillの定理)。
どんな条件なら古典計算機で効率的にシミュレートできる(できない)かの研究は、量子計算機を適用すべき範囲に関わるため、重要だと思います。
(テンソルネットワークとか、面白そうですよね)
4.ユニバーサルな量子計算は、古典計算機で効率的にシミュレートできない(と考えられている)
理論的に証明はされてはいませんが、計算理論的な背景により、ユニバーサルな量子計算は古典計算機で効率的にシミュレートできないと考えられています。そのため、効率的にシミュレートできない前提で話を進めます。
万が一、効率的にシミュレートできることが証明されたら、おそらく大ニュースとして世界を駆け巡ると思います。
(チューリング賞とか受賞できるのではないでしょうか)
量子ビット数を増やしていくと、古典計算機でシミュレートするのに必要なリソースが指数関数的に増加します。
そのため、「GPUを使えば～」とか「並列化すれば～」とか「テンソルネットワークを使えば～」とか、そういう手段では指数関数的な増加について行けず、現実的にはシミュレートできなくなります。
(それができるのであれば、指数時間かかる古典アルゴリズムに困ったりしていないですよね)
また、特に断りがない限り、単に「量子計算」と書いた場合は、ユニバーサルな量子計算のことを指します。
5.計算量理論的な性質は、漸近的なもの
この文章で挙げたような計算量理論的な性質は、ランダウの記号$O(f(n))$の定義に登場する「$n \rightarrow \infty$」での話です。
2022年時点の量子計算機のように、$n$が小さいと成り立たなかったりします。
なので、実際の計算時間が「古典計算機 < 量子計算機」から「古典計算機 > 量子計算機」に変わる閾値を目指して、実用的な量子計算機を研究・開発する必要があります。
この閾値がいくつなのかは問題によっても違いますし、それぞれの計算機の発展によって今後変わりますが、100万量子ビットとか1000万量子ビットを目指して量子計算機は研究・開発されています(誤り耐性量子計算機)。
とは言っても、100万量子ビットとかが実現するのは当分先と考えられているので、それまで待てないですよね。
そのため、量子ビット数が2-3桁くらいの「NISQ」と呼ばれる量子計算機で計算時間が逆転する実用的な問題やアルゴリズムを探す研究も進められています。
6.2022年時点で、量子計算機は商用化しているが、実用化していない
「実社会に役立つ計算に使われ、古典計算機より高速に計算できて、精度も十分」を「実用化」と定義すると、2022年時点で量子計算機は実用化していません。
2019年に「スパコンで1万年かかる見込みの計算を、量子計算機で200秒で計算した」という論文をGoogleが発表し、話題になりました。すごいことではありますが、この論文で比較したのは実用的な計算ではないため、「実用化」とは言えません。
また、「古典計算機より高速」と言うからには、謎の古典アルゴリズムと比較して「当社比xx%アップ」みたいなズルはダメで、その時点で知られている最速の古典アルゴリズムを使ったものより高速であるべきでしょう。
一方、実用的でない量子計算機でも、研究などの目的で利用するには意義があります。
「量子計算機の利用料をもらうビジネスが存在する」を「商用化」と定義すると、量子計算機は既に商用化しています。
量子計算機を商用化した企業が上場するくらい、ビジネスとして進められています(IonQ社、Rigetti社など)。
「商用化しているが、実用化していない」という状況は、量子計算機が実用化するまで続きます。
そのため、「商用化」と「実用化」を区別しないと、おかしなことになります(混乱している記事を見かけます)。
7.量子計算機は指数関数的に成長する
標語的な言い方になりますが、1量子ビット増えると古典計算機でシミュレートするのに必要なリソースが2倍になるイメージです。$n$量子ビットの量子計算機をシミュレートするのに必要なリソースが$2^n$になるイメージです。
しかも、「量子ビット数が$m$年で2倍になるペースで量子計算機が発展する」と仮定すると、$t$年後に量子計算機をシミュレートするのに必要なリソースが$2^{2^{t/m}}$くらいになるため、二重指数関数的に成長することになります。(この仮定は、ここ数年の量子計算機の発展にはフィットしますが、今後どうなるかは不明です)
8.古典計算機も成長している
古典計算機はこれからも現役ですし、当然ハード、ソフト共に発展しています。
指数関数的に高速化した古典アルゴリズムが見つかった問題は、量子計算機を使っても高速化できないかもしれません。
また、2019年に「スパコンで1万年かかる見込みの計算を、量子計算機で200秒で計算した」という論文をGoogleが発表しましたが、その後古典計算機の発展があり、2021年にはスパコンで304秒で計算できるようになっています。
ただし、量子計算機は指数関数的に成長するため、Googleの論文のように「量子計算機が得意な計算」については、しばらくすると古典計算機ではシミュレートできなくなります。
古典計算と量子計算の境界を知るためにも、古典計算機の発展は必要なことだと思います。
9.量子計算機が実現しても、暗号システムは崩壊しない(ように今後アップデートされる予定)
「量子計算機が実現したら公開鍵暗号が一瞬で解読されてしまう」という話を見かけますが、さすがに「一瞬」は言い過ぎです。
たとえば、この論文では、量子計算機にひいき目な条件でも「2048ビットのRSA暗号を解読するのに、2000万量子ビットの量子計算機で8時間」と試算されています。
このような試算は計算機の発展によって今後変わりますが、「一瞬」(数秒とか)は無理じゃないでしょうか。
また、「耐量子暗号」(Post-Quantum Cryptography)という、量子計算機でも現実的には解読できない(と考えられている)公開鍵暗号が研究され、標準化が進んでいます。耐量子暗号は古典計算機上で動く暗号です。
何年もかかるでしょうが、公開鍵暗号のインフラは耐量子暗号に置き換えられる予定です。
量子計算機の実用化は当分先と考えられているため、それまでには耐量子暗号に置き換えられるはずです。
そのため、余程のことがない限り、暗号システムは崩壊しないと思います。
ちなみに、「量子暗号」(Quantum Cryptography)はよく似た名前ですが、別の技術です。
10.量子計算機で組合せ最適化問題を～
次のリンク先がまとまっていますので、そちらをご覧ください。
最後に
他にも
- 誤り耐性がない量子計算機はスケールしない
- Grover検索はクエリ計算量
- 指数時間かかるものが2次の高速化しても、計算量的には計算できないまま
- 誤り訂正による計算量の増加を踏まえても、量子計算機は速いのか
- 共通鍵暗号の解読はどうなのか
- …
など、列挙しはじめるとキリがなさそうですが、まずは本文に挙げたようなことが共通認識になればと思います。