量子コンピュータは真の乱数生成器となる可能性がある

コンピュータ科学者の集まりで「量子超越性」という言葉を口にすれば、おそらく誰もが呆れて呆れるだろう。これは、量子コンピュータが近い将来、古典コンピュータにとって極めて困難なタスクを比較的容易に実行できる閾値を超えるという考えを指している。最近まで、これらのタスクは実世界ではほとんど利用されていないと考えられていたため、呆れて呆れるのも当然だ。

しかし、現在、Google の量子プロセッサがこの目標に近づいているという噂があり、差し迫った量子超越性は、純粋なランダム性を生成するという重要な用途を持つことになるかもしれない。

ランダム性は、私たちが計算や通信インフラを使って行うほぼすべての活動において極めて重要です。特に、データの暗号化に利用され、日常的な会話から金融取引、国家機密に至るまで、あらゆるものを保護しています。

本物の検証可能なランダム性 (一連の数字が持つ、次の数字を予測できない特性と考えてください) を得るのは非常に困難です。

量子コンピュータがその優位性を実証すれば、状況は一変するかもしれない。当初は単に技術の性能を誇示することを目的としていたこれらの最初のタスクは、真の、そして証明されたランダム性を生み出す可能性もある。「私たちは本当に興奮しています」と、カリフォルニア大学サンタバーバラ校の物理学者で、Googleの量子コンピューティング研究を率いるジョン・マルティニス氏は述べた。「これが量子コンピュータの最初の応用例となることを期待しています。」

ランダム性とエントロピー

ランダム性と量子論は、雷鳴と稲妻のように密接に結びついています。どちらの場合も、前者は後者の避けられない帰結です。量子の世界では、システムはしばしば複数の状態の組み合わせ、いわゆる「重ね合わせ」状態にあると言われます。システムを測定すると、システムはそれらの状態のうちの1つに「収束」します。量子論は、測定時に何が起こるかの確率を計算することを可能にしますが、特定の結果は常に根本的にランダムです。

物理学者たちはこの関連性を利用して乱数生成器を開発してきました。これらはすべて、ある種の量子重ね合わせの測定に依存しています。これらのシステムはほとんどの人にとって乱数生成のニーズを十分に満たしますが、扱いが難しい場合もあります。さらに、これらの乱数生成器が本当に乱数生成器であるかどうかを懐疑的な人に証明するのは非常に困難です。そして最後に、検証可能な乱数を生成するための最も効果的な方法の中には、複数のデバイスを遠く離れた場所に設置する、複雑な構成を必要とするものもあります。

単一のデバイス、つまり量子コンピュータからランダム性を引き出す方法として最近提案されたのが、いわゆるサンプリング課題を利用するというものです。これは量子超越性の最初の検証の一つとなるでしょう。この課題を理解するために、タイルが詰まった箱を想像してみてください。それぞれのタイルには、000、010、101といった1と0がいくつか刻まれています。

ビットが3つしかない場合、選択肢は8つあります。しかし、箱の中には各ラベルの付いたタイルが複数枚入っている場合があります。例えば、010のラベルの付いたタイルが50枚、001のラベルの付いたタイルが25枚あるかもしれません。このタイルの分布によって、特定のタイルをランダムに引く確率が決まります。この場合、010のラベルの付いたタイルを引く確率は、001のラベルの付いたタイルを引く確率の2倍になります。

サンプリングタスクは、特定の分布のタイルが入った箱に手を伸ばし、その中からランダムに1つを取り出すのと同等の処理を行うコンピュータアルゴリズムです。分布内のタイルに指定された確率が高いほど、アルゴリズムがそのタイルを出力する可能性が高くなります。

もちろん、アルゴリズムは文字通り袋に手を入れてタイルを取り出すわけではありません。代わりに、例えば50ビット長の2進数をランダムに出力します。その際、各50ビットの出力文字列の望ましい確率を示す分布が与えられます。

古典コンピュータでは、文字列のビット数が大きくなるにつれて、このタスクは指数関数的に困難になります。しかし、量子コンピュータでは、5ビットであろうと50ビットであろうと、このタスクは比較的単純なままであると予想されます。

量子コンピュータは、すべての量子ビット（キュービット）が特定の状態からスタートします。例えば、すべてのキュービットが0からスタートするとします。古典コンピュータがいわゆる論理ゲートを用いて古典ビットを操作するのと同様に、量子コンピュータは量子ゲートと呼ばれる量子に相当するものを用いてキュービットを操作します。

しかし、量子ゲートは量子ビットを奇妙な状態にすることができます。例えば、ある種のゲートは、初期値0から始まる量子ビットを0と1の重ね合わせ状態にすることができます。その後、量子ビットの状態を測定すると、0か1のどちらかに等確率でランダムに崩壊します。

さらに奇妙なことに、2つ以上の量子ビットに同時に作用する量子ゲートは、量子ビット同士を「エンタングルメント（絡み合う）」状態にすることがあります。この場合、量子ビットの状態は互いに絡み合い、単一の量子状態を用いてのみ量子ビットを記述できるようになります。

多数の量子ゲートを組み合わせ、それらを特定の順序で量子ビットの集合に作用させると、量子回路が構築されます。今回の場合、50ビットの文字列をランダムに出力するために、50個の量子ビットをまとめて、再現したい分布を捉える状態の重ね合わせ状態とする量子回路を構築できます。

量子ビットを測定すると、重ね合わせ全体がランダムに崩壊し、50ビットの文字列が1つになります。特定の文字列に崩壊する確率は、量子回路によって規定される分布によって決まります。量子ビットの測定は、目隠しをした状態で箱の中に手を伸ばし、分布からランダムに文字列を1つ抽出するようなものです。

では、どのようにして乱数が得られるのでしょうか？重要なのは、量子コンピュータによってサンプリングされる50ビットの文字列には、無秩序性や予測不可能性、ひいてはランダム性の尺度であるエントロピーが非常に多く含まれるということです。「これは実際にはかなり大きな意味を持つかもしれません」と、この新しいプロトコルを考案したテキサス大学オースティン校のコンピューター科学者、スコット・アーロンソン氏は述べています。「これが量子コンピュータの最も重要な応用だからというわけではありません。私はそうは思いません。むしろ、これがおそらく技術的に実装可能な最初の量子コンピュータの応用になると思われるからです。」

アーロンソンの乱数生成プロトコルは非常に単純です。古典コンピュータはまず、信頼できる情報源から数ビットの乱数を集め、この「シード乱数」を用いて量子回路の記述を生成します。この乱数ビットは、量子ゲートの種類と、それらが量子ビットに作用する順序を決定します。古典コンピュータはこの記述を量子コンピュータに送信し、量子コンピュータは量子回路を実装し、量子ビットを測定し、50ビットの出力ビット列を返します。この処理によって、回路によって指定された分布からランダムにサンプリングが行われます。

このプロセスを何度も繰り返します。例えば、各量子回路について10回ずつです。古典コンピュータは、出力文字列が十分なエントロピーを持つことを確認するために統計的検定を用います。アーロンソンは、リージエ・チェンと共同で発表した論文と、まだ発表されていない論文の両方で、このような問題は計算上困難であるという一定の妥当な仮定の下では、量子コンピュータが分布からランダムにサンプルを採取するのにかかる時間に近い時間で、そのようなエントロピーを生成する古典コンピュータは存在しないことを示しました。これらのチェックの後、古典コンピュータは50ビットの出力文字列をすべて貼り付け、よく知られた古典アルゴリズムに入力します。「ほぼ完全にランダムな長い文字列を生成します」とアーロンソンは述べています。

量子トラップドア

アーロンソンのプロトコルは、約50～100量子ビットの量子コンピュータに最適です。量子コンピュータの量子ビット数がこの閾値を超えると、このプロトコルは従来のスーパーコンピュータでさえ計算的に手に負えなくなります。ここで、量子コンピュータを用いて検証可能な乱数を生成する別の手法が登場します。この手法は、「トラップドア・クローフリー関数」という難解な名前を持つ既存の数学的手法を使用します。「聞こえは悪いですが、実際はもっとひどいです」と、カリフォルニア大学バークレー校のコンピュータ科学者であるウメシュ・ヴァジラニ氏は述べています。ヴァジラニ氏は、ズビカ・ブラケルスキ氏、ポール・クリスティアーノ氏、ウルミラ・マハデフ氏、トーマス・ヴィディック氏と共にこの新しい戦略を考案しました。

もう一度箱を想像してみてください。箱の中に手を入れて文字列を取り出す代わりに、今度はnビットの文字列（xと呼ぶ）を投入すると、別のnビットの文字列が出てきます。箱は何らかの方法で入力文字列を出力文字列にマッピングしています。しかし、箱には特別な性質があります。つまり、xごとに、同じ出力文字列を生成する別の入力文字列yが存在するのです。

言い換えれば、xとyという2つの固有の入力文字列があり、それらに対してボックスは同じ出力文字列zを返します。このx、y、zの3つ組はクローと呼ばれます。コンピュータサイエンス用語では、ボックスは関数です。この関数は計算が容易で、つまりxまたはyが与えられればzを計算するのは簡単です。しかし、xとzしか与えられていない場合、y、ひいてはクローを見つけることは、量子コンピュータであっても不可能です。

爪にたどり着く唯一の方法は、いわゆる落とし戸と呼ばれる内部情報を持っている場合です。

ヴァジラニ氏と彼の同僚は、このような関数を使って量子コンピューターにランダム性を生成させるだけでなく、そのランダム性を信頼するために不可欠な、量子コンピューターが量子力学的に動作しているかどうかを検証したいと考えている。

このプロトコルは、量子コンピュータがn個の量子ビットをnビット列の重ね合わせに用いることから始まります。次に、古典コンピュータが、重ね合わせに適用する関数（トラップドアクローフリー関数）を規定する量子回路の記述を送信します。量子コンピュータは、トラップドアについては一切情報を持たないまま、この回路を実装します。

この段階で、量子コンピュータは、一方の量子ビットセットがすべてのnビット列の重ね合わせ状態にあり、もう一方の量子ビットセットがこの重ね合わせに関数を適用した結果を保持している状態になります。2つの量子ビットセットは互いにエンタングルメント（絡み合った状態）になっています。

次に量子コンピュータは2番目の量子ビットセットを測定し、重ね合わせをランダムに崩壊させて出力zを生成します。しかし、最初の量子ビットセットは、どちらもzを導く関数への入力として機能した可能性があるため、2つのnビット文字列xとyの等しい重ね合わせに崩壊します。

古典コンピュータは出力zを受け取り、2つのことのうちどちらかを行います。ほとんどの場合、量子コンピュータに残りの量子ビットを測定するよう指示します。これにより、重ね合わせ状態は50/50の確率でxまたはyに縮まります。これは、ランダムに0または1を取得することと同じです。

量子コンピュータの量子性を確認するため、古典コンピュータは時折、特別な測定を要求します。この測定と結果は、古典コンピュータだけがアクセスできる落とし戸の助けを借りて、質問に答えるデバイスが実際に量子であることを確認できるように設計されています。ヴァジラニ氏とその同僚は、デバイスが崩壊量子ビットを使用せずに特別な測定に正しい答えを出す場合、それは落とし戸を使用せずにクローを解読することと同等であることを示しました。もちろん、これは不可能です。つまり、デバイス内部には少なくとも1つの崩壊量子ビット（ランダムに0または1を提供する）が存在する必要があります。「[このプロトコル]は、信頼できない量子コンピュータ内に改ざん防止量子ビットを作成しています」とヴァジラニ氏は述べています。

この方式はアーロンソン氏の量子サンプリングプロトコルよりも高速かもしれないが、明確な欠点がある。「50量子ビットや70量子ビットでは実用的ではないだろう」とアーロンソン氏は述べた。

アーロンソン氏は今のところ、グーグルのシステムを待っている。「彼らが導入しようとしているものが、実際に量子超越性を達成するのに十分な性能を持つかどうかは大きな疑問だ」と彼は述べた。

もしそうなら、単一の量子デバイスから検証可能な量子ランダム性を実現できる日は近い。「これは有用であり、潜在的な市場だと考えています。人々に提供することを検討したいと考えています」とマルティニス氏は述べた。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事

• Backpage.comと連邦政府の激しい戦いの内幕
• Googleフォトで写真の過剰摂取を抑える方法
• 最も美味しい食べ物も気候変動の犠牲になる
• 気候科学を氷から引き離した冷戦プロジェクト
• ロボコールを止める方法、あるいは少なくとも遅くする方法
• 🏃🏽‍♀️ 健康になるための最高のツールをお探しですか？ギアチームが選んだ最高のフィットネストラッカー、ランニングギア（シューズとソックスを含む）、最高のヘッドフォンをご覧ください。
• 📩 毎週配信されるBackchannelニュースレターで、さらに多くの内部情報を入手しましょう