量子コンピュータとは？万能な並列計算機ではない5つの理由

皆さんは量子コンピュータについてどんなイメージをお持ちでしょうか？普段私たちが使用しているコンピュータの上位互換として考える方もいると思います。しかし、量子コンピュータは何でも解ける魔法の計算機ではありません。

「並列計算」と説明されがちな量子コンピュータですが、「並列計算」という言葉の先入観により誤解が生まれていると私は思います。
本稿では、量子コンピュータの仕組みを現在のコンピュータと比べながら解説した後、量子コンピュータが万能な計算機ではない理由を5つ挙げようと思います。

本稿は量子コンピュータに対する誤解を解き、今までぼやけていた量子コンピュータのイメージの輪郭をつかんでもらうための記事になっているため、ビットコインには触れていません。ビットコインの量子耐性に関する以下の過去記事も合わせて読んで頂けると面白いと思います。

『量子耐性ハードウェアウォレット』の本当の意味｜Trezor発表を正しく理解する

今週、Trezor社が業界初の「量子耐性のあるハードウェアウォレット」を発表しました。私もその場で発表を聞いていたのですが、最初の感想は「どういうこと？？」でした。一般的に言われがちなビットコイン（やアルトコイン）の量子耐性リスクはハードウェアウォレット側で対応できるものではないためです。 しかし、発表をよく聞いてみるとそれとは別にハードウェアウォレットの仕組みにも量子コンピューターによるリスクがあること、そして今回Trezorはそこを手当したことに納得しました。 今日は「量子耐性のあるハードウェアウォレット」が具体的に何を指すのか解説します。 ・ビットコインの「量子耐性リスク」はハードウェアウォレット側で手当てできるものではない ・ハードウェアウォレットの仕組みのどこに「量子耐性」を実現したのか？ ・超長期的には必要だが、いま購入すべきという判断材料にはならない ビットコインの「量子耐性リスク」はハードウェアウォレット側で手当てできるものではない ビットコインが量子コンピューターの時代にどう対応していくのかという問題は定期的に話題に上がります。典型的な内容は、ビットコ

ビットコイン研究所加藤 規新

ビットコインは量子コンピューター耐性をどうやって手に入れるのか

ここ数年、定期的に話題に上がる量子コンピュータのビットコインに対する脅威が今週もツイッターで話題になっていました。確かに量子コンピュータは進歩していますが、現時点で状況が大きく変わったとは言い難いのが実情です。 また、4年近く前に有識者によってSpotlightに投稿された以下の記事もとても参考になるので、お時間のある方は読んでみてください。 ビットコイン vs 量子コンピュータ本記事では結局量子コンピュータはブロックチェーンに対してどのような影響があるのかをなるべく詳細に説明Spotlight😆 この話題が盛り上がるとき、多くの場合話題の中心は「量子コンピュータがどのようにビットコインに対して脅威なのか」「時期的にはいつくらいからリスクがあるのか」「自分が取れる対策は」というテーマになります。しかし重要なのはビットコインがどのようにして量子コンピュータ耐性を獲得するのか、そのプロセスなのではないでしょうか。 今日はビットコインが量子コンピュータ耐性を獲得するプロセスを想像してみましょう。 ・量子耐性のある署名アルゴリズムのBIPドラフトが提案されている ・提案の内容、導

ビットコイン研究所加藤 規新

なお筆者自身は大学でゲート方式量子コンピュータに関する研究に携わっていました。その経験も踏まえつつ本稿では解説をしていきます。

量子コンピュータとは？古典コンピュータとの違い

私たちが普段使用しているPCやスマホのような従来の計算機を、量子の世界では区別し「古典コンピュータ（Classical Computer）」と呼びます。それに対しミクロな世界を記述する量子力学の性質を計算に応用したコンピュータが「量子コンピュータ（Quantum Computer）」です。

量子コンピュータの狙いは「全ての計算を速くする」ことではなく、特定の種類の問題で古典コンピュータより効率の良い解き方（アルゴリズム）があることにあります。一方で、量子計算が得意な構造を持たない問題では、古典コンピュータが依然として強く、量子コンピュータが万能な「上位互換」というわけではありません。

古典コンピュータと量子コンピュータの違いを理解するには、情報の最小単位である「ビット」に注目することが重要です。両者の違いは、このビットの性質の違いに集約されます。

古典コンピュータ（従来）：0か1で計算する

古典コンピュータで使われるビットは、常に0か1のどちらか一方の確定した値を持ちます。トランジスタの電圧が高いか低いか、磁気の向きが上か下か、といった物理的な状態で表現されます。

重要なのは、ビットの状態は常に観測可能で、確定しているということです。メモリに保存された1バイト（8ビット）のデータは、たとえば「01001101」というように、8個の明確な0と1の列として存在しています。

仮に10ビットの古典ビットを用いて情報を処理する場合を考えます。このとき、10ビットの全ての組合せを考えると、1024回の計算が必要になります。nビットでは計算が2ⁿとなり、計算量が爆発的に増え、現実的な時間で解を得ることが困難になることがあることはお分かりいただけると思います。

量子コンピュータの場合はどうでしょうか。

量子コンピュータ：量子ビット（qubit）で計算する

量子コンピュータの量子ビット（qubit）は、根本的に異なる性質を持ちます。量子ビットは、観測されるまで0と1の「重ね合わせ状態」にあります。これは「0でもあり1でもある」という、古典物理学では説明できない量子力学特有の現象です。

厳密には正しい説明とは言えませんが、サイコロを想像してもらうと理解しやすいと思います。6面あるシンプルなサイコロに対して、一度サイコロを振るという場面を考えてみます。

このとき、サイコロを振る前はどの目が出る確率も同じ（6分の1）であり、サイコロは「1でも2でも3でも4でも5でも6でもある」という重ね合わせの状態であると見なすこともできるでしょう。

そして、サイコロ振る（＝観測する）ことで1つの状態に収束するということになります。

量子コンピュータでは10量子ビットを使う場合、1024通りすべての状態の重ね合わせを同時に保持できます。n量子ビットなら、2ⁿ個の状態を保持することができるということです。

この重ね合わせの原理により、すべての状態を同時に保持することができるという説明が、量子コンピュータが「並列計算」を行うことができるというイメージに繋がってしまっているのでしょう。

量子計算が並列計算と異なる5つの理由

並列計算というと、例えば10台のコンピュータが別々の計算をして最後に答えを合わせることで、1台のコンピュータが10回計算を行うより、10倍高速であるみたいなイメージがあると思います。

量子コンピュータも2ⁿ通りの状態を保持できるのだから並列に計算を行うことで、古典コンピュータよりも高速に計算を行うことができるという誤解が広まっているのでしょう。

重要なのは、量子コンピュータは2ⁿ個の計算を並列に実行しているわけではありません。ここでは、5つの理由からその違いを説明します。

理由１：測定すると1つの答えしか取り出せない

もし量子コンピュータが本当に並列計算をしているなら、すべての計算結果を同時に取り出せるはずです。しかし現実は違います。例えで考えてみましょう。

並列計算マシンなら、1000通りの迷路の道を1000台のコンピュータで同時に試して、1000通りすべての結果を報告できます。しかし量子コンピュータは、1000通りを「重ね合わせ」として内部で扱いますが、最後に観測すると「この道でした」と1つの答えしか教えてくれません。残りの999通りの情報は消えてしまうのです。

これは並列計算の定義に反します。並列計算なら、すべての並列プロセスの結果を集められるはずです。

理由２：速くなるのは「干渉（interference）」で当たりを増幅できるときだけ

量子コンピュータが威力を発揮するのは、特定の条件が揃ったときだけです。そのカギは「量子干渉」という現象です。

量子状態の各成分には「振幅」という複素数が割り当てられています。量子アルゴリズムは、この振幅を巧みに操作して、正しい答えに対応する振幅を強め合わせ、間違った答えの振幅を打ち消し合わせることで機能します。なぜこれが並列計算と違うのか。

並列計算では、各プロセスは独立に計算を進め、それぞれの結果を保持します。良い結果も悪い結果もすべて残ります。

量子コンピュータでは、計算の途中で様々な可能性の振幅が互いに干渉し合います。最終的に測定すると、増幅された「当たり」が高確率で観測されるように設計されています。

理由３：ノイズと誤りで、理想通りの並列性が崩れる

もし量子コンピュータが完璧な並列計算マシンなら、2ⁿ個の並列プロセスが独立に動作するはずです。しかし現実の量子コンピュータは、極めて脆弱です。

重ね合わせ状態は、わずかな温度変化、振動、電磁波などで簡単に壊れてしまいます。現在の量子ビットのコヒーレンス時間（量子状態を保持できる時間）は、方式により大きく異なるが、概ね数マイクロ秒から数ミリ秒程度です。

理由４：コピーできない（ノークローン定理）

並列計算では、計算結果のコピーは基本操作です。複数のプロセスが同じデータを読んだり、結果を複製したりすることは当たり前に行われます。

しかし量子力学には「ノークローン定理」という根本的な制約があります。未知の量子状態は完全にコピーできないのです。量子コンピュータでは、重ね合わせ状態にある量子ビットをコピーしようとすると、量子力学の基本法則に違反してしまいます。コピーを試みると、元の状態が破壊されるか、不完全なコピーしか得られません。

この制約は、量子コンピュータが並列計算マシンとして機能できない決定的な理由の一つです。並列計算なら当然できるはずの「データの複製と配布」ができないのですから。

理由５：量子コンピュータでも解けない問題が存在する

最後に、より根本的な視点を提供します。仮に量子コンピュータが完璧な並列計算マシンだったとしても、それだけでは「あらゆる問題を高速に解ける」わけではありません。

計算機科学には「P≠NP予想」という有名な未解決問題があります。簡単に言えば、「答えが正しいか確認するのは速いが、その答えを見つけるのは非常に時間がかかる問題が存在する」という予想です。こちらは、ミレニアム懸賞問題とも言われ1問解くごとに100万ドルの懸賞金を獲得することができます。

The Millennium Prize Problems - Clay Mathematics Institute

In order to celebrate mathematics in the new millennium, The Clay Mathematics Institute of Cambridge, Massachusetts (CMI) established seven Prize Problems. The Prizes were conceived to record some of the most difficult problems with which mathematicians were grappling at the turn of the second millennium; to elevate in the consciousness of the general public the fact […]

Clay Mathematics Institute

重要なのは、量子コンピュータもNP完全問題を効率的に解けるとは考えられていないということです。量子コンピュータが得意なのは、BQP（Bounded-error Quantum Polynomial time）というクラスの問題です。これは古典的な並列計算とも、NP完全問題とも異なる種類の問題なのです。

例えば、ショアのアルゴリズムで解ける「素因数分解」は、BQPに含まれますが、NP完全ではないと考えられています。逆に、多くのNP完全問題は、量子コンピュータでも効率的に解けないと予想されています。

つまり、量子コンピュータは「何でも解ける魔法の機械」ではなく、特定の種類の問題に対して古典コンピュータより効率的という存在なのです。

実際の量子コンピュータの計算方法

量子コンピュータは並列計算マシンではないことを説明しました。では、実際にどう動くのでしょうか。一言で言えば、確率分布を加工して、正解が出やすい状態に持っていく計算機です。

量子ビットのすべての可能な答えが等しい確率で存在する状態を作ったのち、量子ゲートという操作を使って、この確率分布を少しずつ変形させていきます。

何をしているのかというと

• 正解の確率を少しずつ上げる
• 不正解の確率を少しずつ下げる

これを「量子干渉」という波の性質を使って実現します。音波が共鳴して特定の音だけが大きくなるように、正解に対応する量子状態だけが強められていくのです。

最後に量子状態を測定します。すると確率に応じて、1つの答えがランダムに選ばれます。これが実際の量子コンピュータの基本的な計算方法です。

サイコロの例を取ると最初は全ての出る目が同じ確率であったのに対して、サイコロを改造することで特定の値が出やすいようにしているというイメージになります。

量子コンピュータの強みは、この量子特有の計算方法が特定の問題には、高速に問題を解くことに作用するという点にあります。今後は量子コンピュータが高速に問題を解くことができる場合やビットコインの暗号解読についてを記事にしようと思うのでぜひご覧ください。

まとめ：量子コンピューターは並列実行ではなく確率を設計する計算機

量子コンピュータは「すべての可能性を同時に計算する並列マシン」ではありません。その本質は、確率分布を操作して、正解が出やすい状態を作る計算機です。

並列計算なら1000通りを1000台で計算し、1000通りすべての結果を得られます。しかし量子計算は1000通りの重ね合わせを保持するものの、測定すると1つの答えしか得られません。その代わり、量子干渉という現象を使って正解の確率を増幅し、不正解の確率を減少させることで、ランダムに選ぶよりはるかに高い確率で正解を引き当てられるのです。

量子コンピュータが並列計算でない理由は明確です。測定で1つしか取り出せないこと、干渉で確率を操作する独自の原理、ノイズで全体が崩れる脆弱性、量子状態をコピーできないこと、そして並列計算でも解けない問題があるという理論的限界があります。

量子コンピュータは古典コンピュータの「上位互換」でも「超並列版」でもありません。量子干渉により確率分布を巧みに設計する、まったく新しい計算パラダイムです。特定の問題に対してのみ、この独自の仕組みが劇的な高速化をもたらすのです。