量子コンピュータって難しい

調べてみたのですがよく分からなかったので勉強の記録として載せておきます（正確性は全く保証できません）。

そもそも量子コンピュータって何ですか

量子コンピュータ、量子アニーリング、量子鍵配送という設定も目的も全く別の技術を区別して整理するところから始めます。

量子コンピュータ

古典的な電子回路の代わりに量子ビット(qubit)と量子ゲートを並べて、普段我々が使っているコンピュータと同等以上の計算能力を得ることを目的とした計算機です。万能量子コンピュータとも言われます。理論研究が先行しており、理論通りに完成すると既存の公開鍵暗号を無力化します。この記事で扱うのは主にこの万能量子コンピュータです。ビットコインの要素のうち影響を受けるのは、署名に関する部分と、楕円曲線に特徴的な性質を使った応用部分であり、ハッシュ関数やマイニング、スクリプトの安全性自体は直接の影響を受けません。

量子アニーリング

特定の問題（組み合わせ最適化問題など）に特化した計算機で、公開鍵暗号への脅威となることはありません。万能量子コンピュータとの共通点は未だに実用的ではないということくらいでしょうか。

(量子鍵配送)

あるデータを交換するときに、そのデータが中間で傍受されたことを、量子の性質を用いて検証できる技術です。例えば通常の回線の間に傍受のための機械を設置しても通信にタイムラグが出るかもしれないといった程度でしか影響はありませんが、量子鍵配送では読み取ると状態が変化するためにバレないように傍受することが不可能になります。 これは計算機でもなんでも無いのですが、「暗号」と「量子の性質」を利用するものです。量子耐性暗号とも全く異なります。 コストの面から商用化されてはいませんが、理論的にも現実的にもすでに完成に近づいており、やりたいことはできる状態です。 量子鍵配送は暗号通貨とは直接の関係はありませんが、公開鍵暗号の鍵交換の確実性を高めるという意味でむしろ既存の暗号技術を強化するものと言えるでしょう。

量子コンピュータの現状の計算能力

万能量子コンピュータの現状の計算能力を説明する分かりやすい資料として

量子計算機の到来を正しく恐れたい https://www2.nict.go.jp/csri/plan/H31-symposium/pdf/kunihiro.pdf

があります。理論研究が先行しているものの、実際の物理系をどのように設定すればいいのかは試行錯誤が続いています。それらの物理系全てが補完しあうということはなく、ほとんどの提案された手法は全く無意味であり、新しい量子ビットをシミュレートできる物理系が提案されてそのバリエーションが増えても完成へは近づかないと示唆しています。

量子コンピュータと言われても具体的に何が計算に対応しているのか分かりづらいので、具体的な物理系を解説してみます。 Nature紙に2001年に初めて掲載された具体的な量子コンピュータの設計です。

Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (2001)
https://arxiv.org/pdf/quant-ph/0112176.pdf

この物理系(NMR量子コンピュータ)では「ペルフルオロブタジエニル鉄錯体」という物質が使われました。この分子内の炭素とフッ素の原子の位置の違いから来る非対称性で、それぞれの原子を特定して別々に操作することができるようになります。特定の分子を操作するわけではなく、特定の周波数の電磁波を照射して溶液中にたくさんある分子内の特定の位置の原子の振る舞いを一斉に操作するという手法が用いられました。この分子１つずつが量子コンピュータです。最後に溶液内に存在する分子の統計的な情報を得ることで計算結果を取得します。

この系では7量子ビットが使われました。原子の状態（核スピン）が量子ビットにあたり、電磁波を照射する操作が量子ゲートにあたります。

このNMR量子コンピュータでは3ｘ5=15の因数分解に成功したと言われていますが、実際は3ｘ5=15という数式が先に存在し、それを量子コンピュータの理論に従ってシミュレートするために系を作ったという方が正しいでしょう。

ソフトウェア

理論上の計算量において量子コンピュータが有利になる問題が知られています。公開鍵暗号の基盤になっている素因数分解と離散対数問題は、量子コンピュータで簡単に解ける問題クラスに属しています。したがって、十分な数の量子ビットと量子ゲートを備えた計算機が完成すると公開鍵暗号は解読されてしまいます。

具体的には、量子ビットを初期化して、量子フーリエ変換という操作を高速に実行して、その確率的な結果を適切に観測することで元の量子ビット間の関係に関する情報を高速に得ることが出来るというのが、素因数分解を高速に解く肝になります。高速化されるのは量子フーリエ変換の部分だけだと理解すべきです。このアルゴリズムを取り入れて素因数分解を行うアルゴリズムがショアのアルゴリズムと呼ばれています。量子フーリエ変換については以下を参照してください。

量子フーリエ変換 (Quantum Fourier Transform) とは
https://whyitsso.net/physics/quantum_mechanics/QFT.html

計算理論から「ある問題を解くために、どのくらいの規模の量子ビットと量子ゲートを用意すればいいのか」ということは知られています。あくまでも純粋な、理論的な数字であって量子ビット同士を自由に相互作用させられる形での下限です。 およその目安としては量子ビットと量子ゲートがそれぞれ数千個ずつ必要であるとされていますが、実際にはエンジニアリングが必要でこの何十倍も必要になるかもしれません。 なお、難しさを表現する分かりやすいイメージとして例えば10量子ビットを扱える量子コンピュータを考えた時、2倍の20量子ビットに拡張するのは、それぞれの量子ビットが全ての既存の別の量子ビットと綺麗に相互作用してノイズが入り込まないようにしないといけないことから、技術的な難しさは2倍ではなく、10^2=100倍くらいだと考えるといいと思います。

なお量子コンピュータは基本的には確率的な答えを返すので、何回か試行して精度を上げるアルゴリズムを使うことになります。

ハードウェア

こちらの記事が参考になります。量子コンピュータと一口に言っても、その実装は水溶液中の分子だったり半導体だったり様々です。

• 量子コンピュータを実現するハードウェア（前編）
  https://www.qmedia.jp/making-quantum-hardware-1/
• 量子コンピュータを実現するハードウェア（後編）
  https://www.qmedia.jp/making-quantum-hardware-2/

以下、仮想機械としての「さざなみコンピュータ」は直感的に理解しやすいです。

• ２－４　量子コンピューターの威力は人間側の最終防衛ラインを突破するか http://pathfind.motion.ne.jp/aivshuman2-4.html

なお理論上のブレイクスルーが無くエンジニアリングのゴリ押しで256ビットのECDSAを解読できたとしても、その場合は単純にビットコインで使える公開鍵暗号の鍵長を増やせばいいので、具体的な数値よりもハードウェアがどのくらいスケーラブルな物理系なのかということに着目した方がよいと思います。

関連して、グーグルが量子超越性を持つ量子コンピュータを開発したという報道が数年前にありました。量子超越性の達成とは、古典コンピュータよりも、量子コンピュータの方が高速に解ける問題が少なくとも１つ見つかったということです。

高速に計算できたのは、量子ゲートを並べて作った回路への入力からランダムな数字を出力する、乱数生成の問題の一種と理解しています。これを古典計算機で愚直にシミュレートしようとすると非常に時間がかかり、量子コンピュータならばより高速に計算できるということのようです。 基本的にはビットコインで問題になる署名や公開鍵暗号とは全く別設定の問題です。正確さよりもわかりやすさを重視して例を挙げると、こちらのように、ピンボールを考えて、様々に釘や障害物を台の上に配置して、同時に大量のボールを流した時、色々な穴にランダムに落ちるようなゲームを考えると良いでしょう。このゲームの目的は、どの穴に一番多くボールが落ちるのかを当てることです。これは、正確に古典計算機でシミュレートするのはかなり大変です。なぜなら、釘の微妙な位置のズレなどから現実世界ではボールは様々な軌跡を流れるからです。物理的な世界でそのようなゲームを１つ作って、実際にボールを流して計算ができることを確認し、その上でその装置を問題に見立てて古典計算機でシミュレートするのが難しいと主張していると理解しています。

参考
Scott’s Supreme Quantum Supremacy FAQ!
https://www.scottaaronson.com/blog/?p=4317

量子耐性暗号の現状と展望

格子暗号などが量子コンピュータ耐性のある暗号として提案されていますが、暗号は様々な面から検証され、さらに実際に重要な用途で使って何十年か経たないと安全とはいえないというのが共通認識になっています。量子コンピュータが出現するまでに時間がかかるだろうということで、その間に検証する時間が取れれば実用的な暗号として採択される可能性はあります。現状は新しすぎること、本当に解読できないのか分からないことで、もし今突然量子コンピュータが出現したとしたら格子暗号に直ちに移行するというわけにはいかないのです。

もし量子コンピュータが完成した場合ビットコインはどうなるでしょうか。ビットコインがクリティカルに公開鍵暗号を使う場面は署名検証だけですが、その署名検証は効率化に最適化を重ねたエンジニアリングの産物です。格子暗号が同等の速度で計算できるのかは不明です。署名さえできれば生き残ることはできるかもしれませんが、ブロックサイズを今以上に制限したり、grinのようにインタラクティブな操作が必要になる可能性もあります。

例えば量子コンピュータが仮に20年後に完成したとして、それまでに研究が進み、署名に関する暗号も強化されたとします。そのため将来的に発生するTXに関しては安全で、昔作られたTXやアドレスが問題になるとします。その場合どのような解決策があるでしょうか。

• アドレスを重複使用している場合(一度署名した秘密鍵を使いまわした場合)、すでに公開鍵ハッシュに対応する公開鍵と署名が公開されてしまっているため、公開鍵と署名から秘密鍵を復号することでコイン使用に必要な情報は全てが公開情報扱いになるので、コインは盗られてしまいます。

• 一方で重複使用していない場合を考えてみます。古い秘密鍵s1についてs1の古いtxではもはやコインを使用できないというルールに変え（ハードフォーク）、その後コミットメントhash(s1)と新しい公開鍵p2を同一のトランザクションに入れて新署名方式で署名してブロードキャストし（スパムを避けるために、同時に多めにbtcをバーンする必要があるかもしれない）、ブロックに取り込まれるのを待ちます。さらに十分時間が経過したらs1を平文でトランザクションに入れて公開します。そして、元々s1に入っていたコインは最も古い（＝ブロック番号が若い）コミットメントhash(s1)と同時にブロードキャストされたp2に対応する秘密鍵p1で使用できるというルールを適用すれば、原理的には新しい署名方式への移行は可能になるはずです。ただし、実際にやろうとするとかなり大変になります（計算量、トランザクションのデータサイズ、未知の脆弱性、ハードフォークなど）。何にせよ今のうちからアドレスを再利用しないということは心がけた方が良さそうです。

格子暗号では楕円曲線暗号のような署名バッチ化や秘匿トランザクションのためのテクニックが十分発達していないので、第一世代のナカモトサトシが作った基本的なものに立ち返ることが必要になりそうです。なお、これはビットコインだけでなく全ての暗号通貨について言えることです。

何が量子耐性暗号の標準になるのかはまだ策定中であり、理論上安全な量子耐性暗号が存在するのかどうかはよく分かっていません（そもそも理論上安全な公開鍵暗号が存在するのかはよく分かっていませんが）。米国立標準技術研究所（NIST）や私企業の各デジタル認証局などが協力して、現在標準を策定するためにアルゴリズムの候補を募集している段階です。

結論

• 大衆向けメディアで量子コンピュータとして宣伝されるもののうち、暗号通貨の基盤である公開鍵暗号の脅威になるものは万能量子コンピュータのみであり、ビットコインではマイニングやスクリプトではなく電子署名部分にのみ影響がある
• 万能量子コンピュータの現状の計算能力は十分な鍵長の公開鍵暗号への脅威ではなく、理論を応用できる物理系の設定を色々試しているというのが現状
• もし今日突然十分に強力な万能量子コンピュータが完成した場合、量子耐性暗号の候補は十分な検証が出来ていないため公開鍵暗号自体の安全性が失われ、暗号通貨全体が崩壊すると考えられる