大学院生が量子コンピューティングの基本的な問題を解決

2017年の春、ウルミラ・マハデフは、ほとんどの大学院生がかなり恵まれた状況と考える立場にいた。量子計算、つまり量子物理学の奇妙な法則から力を引き出すコンピューターの研究における重要な問題を解いたばかりだったのだ。テキサス大学オースティン校のコンピューター科学者、スコット・アーロンソンは、マハデフの「ブラインド計算」と呼ばれる分野における新たな成果と、以前の論文を合わせると、「彼女が将来有望な新星であることは明らかだ」と述べた。

当時28歳だったマハデフさんは、カリフォルニア大学バークレー校大学院の7年目に突入していた。多くの学生が卒業を待ちきれなくなる時期をとうに過ぎていた。そして今、ついに「非常に素晴らしい博士論文」の素地ができたと、バークレー校で彼女の博士課程の指導教官を務めたウメッシュ・ヴァジラニ氏は語る。

しかし、マハデフはその年卒業しませんでした。卒業することなど考えもしませんでした。彼女はまだ終わっていなかったのです。

5年以上もの間、彼女は別の研究課題に着目していた。アーロンソン氏が「量子計算において問える最も基本的な疑問の一つ」と呼ぶものだ。つまり、量子コンピュータに計算を実行させた場合、それが本当に指示に従ったのか、あるいはそもそも量子的な処理を行ったのかをどうやって知るのか、という問題だ。

この問いは、まもなく学問の世界から遠く離れてしまうかもしれない。研究者たちは、量子コンピューターが、ブラックホール周辺の挙動のモデル化から巨大タンパク質の折り畳みのシミュレーションまで、多くの問題を指数関数的に高速化できるようになることを期待している。

しかし、量子コンピュータが古典コンピュータではできない計算を実行できるようになったら、その計算が正しく実行されたかどうかをどうやって確認するのでしょうか？ 通常のコンピュータを信用できないのであれば、理論上は自分で計算のあらゆるステップを精査することができます。しかし、量子システムは根本的にこの種の検証を不可能にしています。まず、その内部の仕組みは非常に複雑です。わずか数百の量子ビット（キュービット）でコンピュータの内部状態を記述するには、目に見える宇宙全体よりも大きなハードディスクが必要になります。

たとえこの説明を書き記すだけのスペースがあったとしても、それに到達する方法はありません。量子コンピュータの内部状態は、一般的に、多くの異なる非量子的な「古典的」状態の重ね合わせです（シュレーディンガーの猫のように、死んでいると同時に生きている状態です）。しかし、量子状態を測定するとすぐに、それはこれらの古典的状態のうちの1つに収束します。300量子ビットの量子コンピュータの内部を覗き込むと、基本的に見えるのは300個の古典的ビット、つまり0と1が、あなたに穏やかに微笑んでいるだけです。

「量子コンピューターは非常に強力だが、非常に秘密主義でもある」とヴァジラニ氏は語った。

こうした制約を踏まえ、コンピュータ科学者たちは長年、量子コンピュータが主張通りの動作を実際に行ったという確固たる保証を提供できるのかどうか疑問に思ってきた。「量子世界と古典世界との相互作用は、対話が可能なほど強いのだろうか？」と、エルサレム・ヘブライ大学のコンピュータ科学者、ドリット・アハロノフ氏は問いかけた。

大学院2年生の頃、マハデフはこの問題にすっかり魅了された。理由は彼女自身も完全には理解していない。その後数年間、彼女は次々とアプローチを試した。「正しいことをしていると思っても、あっという間に、あるいは1年後にはうまくいかなくなることが何度もありました」と彼女は言う。

しかし、彼女は諦めなかった。マハデフは、ヴァジラニがかつて見たこともないほどの、途切れることのない決意を示した。「ウルミラはまさにその意味で並外れた存在です」と彼は言った。

大学院で8年間の学びを経て、マハデフ氏はついに成功を収めた。彼女は、量子力を持たないユーザーでも暗号技術を用いて量子コンピュータにハーネスを装着し、好きな場所に操作できるインタラクティブプロトコルを考案した。しかも、量子コンピュータがユーザーの命令に従っていることは確実だ。マハデフ氏のアプローチは、ユーザーに「コンピュータが決して振り払うことのできない影響力」を与えるとヴァジラニ氏は述べた。

大学院生が独力でこのような成果を達成するのは「本当に驚異的だ」とアーロンソン氏は語った。

現在バークレー大学でポスドク研究員を務めるマハデフ氏は、今年パリで開催された理論計算機科学最大の会議の一つである「計算機科学の基礎に関するシンポジウム」で、自身のプロトコルを発表しました。彼女の研究は、同会議の「最優秀論文賞」と「最優秀学生論文賞」を受賞しました。これは理論計算機科学者にとって稀有な栄誉です。

カリフォルニア工科大学のコンピューター科学者で、過去にマハデフ氏と共同研究を行ったトーマス・ヴィディック氏はブログ投稿で、彼女の研究結果を「近年、量子コンピューティングと理論コンピューターサイエンスの接点に現れた最も傑出したアイデアの1つ」と呼んだ。

量子計算の研究者たちは、マハデフ氏のプロトコルが達成した成果だけでなく、彼女がこの問題に持ち込んだ根本的に新しいアプローチにも興奮している。古典的な暗号を量子領域で用いることは「真に斬新なアイデア」だとヴィディック氏は書いている。「これらのアイデアを基に、今後も多くの成果が生まれることを期待しています。」

長い道のり

ロサンゼルスの医師一家に育ったマハデフは、南カリフォルニア大学に進学。大学では様々な分野を転々としながら研究を進め、当初は医師になるつもりはないと確信していました。しかし、有名なRSA暗号アルゴリズムの開発者の一人であるコンピュータ科学者、レナード・エイドルマンの授業をきっかけに、理論計算機科学に興味を持つようになりました。彼女はバークレー大学の大学院に出願し、出願書類の中で、量子計算を除く理論計算機科学のあらゆる側面に興味があると説明しました。

「それは最も異質なもの、私が最も知らないもののように聞こえました」と彼女は語った。

しかし、バークレーに着くと、ヴァジラニの分かりやすい説明にすぐに考えが変わりました。彼は彼女に量子計算を検証するためのプロトコルを見つけるという問題を提示し、その問題は「彼女の想像力を本当にかき立てた」とヴァジラニは言います。

「プロトコルはパズルのようなものです」とマハデフ氏は説明した。「私にとって、プロトコルは他の問題よりも取り組みやすいように思えます。なぜなら、すぐに自分でプロトコルを考え始め、それを破ることで、それがどのように機能するかを理解できるからです。」彼女は博士研究の対象としてこの問題を選び、ヴァジラニ氏が「非常に長い道のり」と呼ぶ道を歩み始めた。

量子コンピュータが古典コンピュータでは解けない問題を解けるからといって、必ずしもその解の検証が困難になるわけではありません。例えば、大きな数の因数分解の問題を考えてみましょう。これは大規模な量子コンピュータなら効率的に解けるものの、古典コンピュータでは到底不可能だと考えられています。古典コンピュータが因数分解できないとしても、量子コンピュータによる因数分解が正しいかどうかは簡単に検証できます。因数を掛け合わせて、正しい答えが得られるかどうかを確認するだけでよいのです。

しかし、コンピュータ科学者たちは、量子コンピュータが解ける問題の多くにはこの特性がないと考えており（そして最近、その証明に向けて一歩前進しました）、言い換えれば、古典コンピュータはこれらの問題を解くことができないだけでなく、提案された解が正しいかどうかさえ認識できないのです。この点を踏まえ、2004年頃、オンタリオ州ウォータールーにあるペリメーター理論物理学研究所の物理学者ダニエル・ゴッテスマンは、量子コンピュータが非量子観測者に対して、自らが主張した通りのことを実際に実行したことを証明できるプロトコルを考案できるかどうかという疑問を提起しました。

4年の歳月を経て、量子コンピュータの研究者たちは部分的な答えを導き出しました。2つの異なる研究チームが、量子コンピュータが計算結果を純粋に古典的な検証者ではなく、自身の非常に小型の量子コンピュータにアクセスできる検証者に対して証明することが可能であることを示しました。その後、研究者たちはこのアプローチを改良し、検証者に必要なのは一度に1つの量子ビットを測定できる能力だけであることを示しました。

2012年には、ヴァジラニ氏を含む研究チームが、相互に通信できない2台の量子コンピュータで実行された量子計算であれば、完全に古典的な検証器で検証できることを示しました。しかし、この論文のアプローチはこの特定のシナリオに合わせて調整されており、問題はそこで行き詰まったように思われたとゴッテスマン氏は述べています。「おそらく、それ以上先に進むことはできないと考える人もいたでしょう。」

マハデフ氏が検証問題に遭遇したのは、ちょうどこの頃だった。当初、彼女は量子コンピュータの性能について何の仮定も置かない「無条件」な結果を導き出そうとした。しかし、しばらくこの問題に取り組んでも進展がなかったため、ヴァジラニ氏は代わりに「耐量子」暗号の利用を提案した。耐量子暗号とは、研究者たちが量子コンピュータでさえ解読不可能だと考えているものの、確実なことは分かっていない暗号のことである。（オンライン取引などの暗号化に用いられるRSAアルゴリズムなどは耐量子ではない。これらの暗号のセキュリティは、大きな数の因数分解の困難さに依存しているため、大型の量子コンピュータであれば解読可能である。）

2016年、マハデフとヴァジラニは別の問題に取り組んでいた際、後に決定的な進歩を遂げた。サンフランシスコの企業OpenAIに所属するコンピューター科学者、ポール・クリスティアーノと共同で、暗号技術を用いて量子コンピューターに「秘密状態」と呼ばれる状態を構築させる方法を開発した。秘密状態とは、従来の検証者にはその記述が知られているものの、量子コンピューター自身には知られていない状態である。

彼らの手順は、「落とし戸」関数と呼ばれるものに依存しています。これは実行は簡単ですが、秘密の暗号鍵を持っていない限り、解読が困難な関数です。（研究者たちは、適切な落とし戸関数を実際に構築する方法をまだ知りませんでした。それは後ほど明らかになります。）また、この関数は「2対1」であることも求められます。つまり、すべての出力が2つの異なる入力に対応するということです。例えば、数を2乗する関数を考えてみましょう。0という数字を除いて、各出力（例えば9）には2つの対応する入力（3と-3）があります。

このような関数を利用すれば、量子コンピュータは次のようにして秘密の状態を作り出すことができます。まず、関数へのあらゆる入力の重ね合わせをコンピュータに構築させます（コンピュータにとって複雑な処理のように聞こえるかもしれませんが、実際には簡単です）。次に、この巨大な重ね合わせに関数を適用し、関数のあらゆる出力の重ね合わせである新しい状態を作成します。入力と出力の重ね合わせはエンタングルメント状態になり、一方の測定値が他方に即座に影響を及ぼします。

次に、コンピュータに出力状態を測定し、結果を返すように指示します。この測定により、出力状態は可能な出力の1つに絞り込まれ、入力状態もそれに合わせて瞬時に絞り込まれます。なぜなら、入力状態と出力状態は互いに絡み合っているからです。例えば、2乗関数を使うと、出力が9の状態であれば、入力は3と-3の状態の重ね合わせに絞り込まれます。

しかし、落とし戸関数を使っていることを忘れないでください。落とし戸の秘密鍵を持っているので、入力の重ね合わせを構成する2つの状態を簡単に解明できます。しかし、量子コンピュータはそうできません。また、入力の重ね合わせを単純に測定して、それが何で構成されているかを解明することもできません。なぜなら、測定すると重ね合わせがさらに崩れてしまい、コンピュータは2つの入力のうちの1つしか取得できず、もう1つを解明する方法がなくなるからです。

2017年、マハデフ氏は、エラー学習（LWE）と呼ばれる暗号技術を用いて、シークレットステート方式の中核となるトラップドア関数の構築方法を解明しました。このトラップドア関数を用いることで、彼女は量子版の「ブラインド」計算を実現しました。クラウドコンピューティングのユーザーは、クラウドコンピューターが計算中でもデータを読み取れないようにデータをマスクすることができます。その後まもなく、マハデフ氏、ヴァジラニ氏、クリスティアーノ氏は、ヴィディック氏とズヴィカ・ブラケルスキ氏（イスラエル、ワイツマン科学研究所）と共同で、これらのトラップドア関数をさらに改良し、シークレットステート方式を用いて量子コンピューターが証明可能な乱数を生成する確実な方法を開発しました。

マハデフさんはこれらの結果で卒業できたはずだったが、検証問題を解くまで研究を続けると決意していた。「卒業のことなど考えたこともありませんでした。卒業が目標だったわけではないからです」と彼女は言った。

解けるかどうかわからないことが、時々ストレスになることもありました。でも、「興味のあることを学ぶことに時間を費やしていたので、決して無駄な時間ではなかったと思います」と彼女は言いました。

石に刻まれた

マハデフ氏は、秘密状態法から検証プロトコルへと至る様々な方法を試みたが、しばらくの間、行き詰まっていた。そこで彼女はある考えを思いついた。研究者たちは既に、検証者が量子ビットを測定できる能力があれば、量子コンピュータを検証できることを示していた。従来の検証者には、定義上、この能力が欠けている。しかし、従来の検証者が何らかの方法で量子コンピュータに測定を強制し、その結果を正直に報告させることができたらどうなるだろうか？

マハデフ氏は、検証者がどのような測定を要求するかを知る前に、量子コンピュータに測定しようとしている状態を事前に決めさせることが難しい点だと気づいた。そうでなければ、コンピュータが検証者を騙すのは容易だ。そこで秘密状態法が登場する。マハデフ氏のプロトコルでは、量子コンピュータはまず秘密状態を生成し、次にそれを測定すべき状態とエンタングルさせる。こうして初めて、コンピュータはどのような測定を実行すべきかを知ることができる。

コンピュータは秘密状態の構成を知らないが、検証者は知っているため、マハデフ氏は量子コンピュータが、その偽造の明白な痕跡を残さずに重大な不正行為を行うことは不可能であることを示した。ヴィディック氏によると、コンピュータが測定する量子ビットは本質的に「暗号の石に埋め込まれている」という。そのため、測定結果が正しい証明のように見える場合、検証者はそれが本当に正しいと確信できる。

「本当に素晴らしいアイデアですね！」とヴィディックさんは書いている。「ウルミラが説明するたびに、本当に驚かされます。」

マハデフ氏の検証プロトコルは、乱数生成器やブラインド暗号化方式と同様に、量子コンピュータがLWEを解読できないという仮定に基づいています。現在、LWEは耐量子暗号の有力候補として広く認識されており、近いうちに米国国立標準技術研究所（NIST）が量子コンピュータが解読可能な暗号に代わる新たな暗号標準として採用する可能性があります。しかし、ゴッテスマン氏は、それが量子コンピュータに対して本当に安全であることを保証するものではないと警告しました。「しかし、今のところLWEは堅固です」と彼は述べ、「解読可能であるという証拠は誰も見つかっていないのです」と続けました。

いずれにせよ、このプロトコルがLWEに依存していることで、マハデフ氏の研究はWin-Winの関係にあるとヴィディック氏は書いている。量子コンピュータがこのプロトコルを欺く唯一の方法は、量子コンピューティング業界の誰かがLWEを破る方法を発見することであり、それ自体が驚くべき成果となるだろう。

マハデフ氏のプロトコルが近い将来、実際の量子コンピュータに実装される可能性は低い。当面は、このプロトコルは実用化するにはあまりにも多くの計算能力を必要とする。しかし、量子コンピュータが大型化し、研究者がプロトコルを合理化していくにつれて、今後数年で状況は変化する可能性がある。

マハデフ氏のプロトコルは、おそらく今後5年以内には実現不可能だろうが、「完全に空想の世界の話というわけでもない」とアーロンソン氏は述べた。「すべてがうまくいけば、量子コンピューターの進化の次の段階で検討を始められる可能性はある」

そして、この分野の現在の急速な発展を考えると、その段階は遅かれ早かれ到来する可能性がある。ヴィディック氏によると、わずか5年前までは、研究者たちは量子コンピュータが古典コンピュータでは解けない問題を解けるようになるまでには何年もかかると考えていたという。「今では、1、2年で実現すると考えている人もいる」と彼は述べた。

マハデフさんは、お気に入りの問題を解いたことで、少し途方に暮れた気持ちになっている。その問題のどこが自分にとって正解だったのか、理解できればいいのに、と彼女は言う。「今は新しい疑問を見つけなければならないので、それがわかれば嬉しいです。」

しかし、理論計算機科学者たちは、マハデフ氏による量子計算と暗号の統合を、物語の終わりというよりも、豊かなアイデアの鉱脈となるであろうものの最初の探究であると見ている。

「今後、多くの追加研究が行われるだろうと感じています」とアハロノフ氏は述べた。「ウルミラからのさらなる成果を楽しみにしています。」

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

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

• 遺伝子検査はたくさんあるのに、説明してくれる人はほとんどいない
• テクノロジーがあなたよりもあなたのことをよく知っているとき
• この魔法のサングラスはあなたの周りのすべてのスクリーンをブロックします
• ネット上の陰謀論について知っておくべきこと
• 過去25年間の25のお気に入り機能
• もっと知りたいですか？毎日のニュースレターに登録して、最新の素晴らしい記事を見逃さないでください。