大学院生が量子コンピューティングを確認する問題を解決した

ウルミラ・マハデフは、量子コンピューティングの最も基本的な質問の1つに対する答えを求めて、8年間を政務に費やしました。

2017年の春、ウルミラ・マハデフは、ほとんどの大学院生の観点から、良い位置にいました。 彼女は、量子コンピューティングの重要な問題であるコンピューターサイエンスの分野を解決し、量子物理学の奇妙な法則からその能力を引き出しました。 彼女の初期の作品とともに、いわゆるマハデフによる新しい結果 テキサス大学オースティン校のITスペシャリストであるスコットアーロンソンは 、次のように述べています。



当時28歳だったマハデブは、カリフォルニア大学バークレー校の大学院ですでに7年生でした。これは、ほとんどの生徒が忍耐を失い、すでに学校を卒業したい時間よりもはるかに長い時間です。 そして、ついに、彼女はバークレーのキュレーターであるウメシュ・バジラニ氏は、「優れた博士論文」を書くことができたと言いました。



しかし、マハデフはその年の勉強を終えていませんでした。 彼女はこの問題さえ考慮しません。 彼女はまだ終わっていません。



5年以上にわたり、彼女は別の研究課題に取り組み、アーロンソンは「量子コンピューティングの分野で問われる最も基本的な質問の1つ」と呼びました。 つまり、量子コンピューターに計算を依頼した場合、それが指示に従っているかどうかをどのようにして知ることができますか。実際、量子レベルで何かを行うのでしょうか。



この質問はまもなく純粋に学術的でなくなるかもしれません。 研究者は、何年も経たないことを望み、量子コンピューターは、ブラックホールの近くの状況のモデリングから大きなタンパク質の折り畳みのシミュレーションまで、多くの問題を解決する際に指数関数的な加速を提供できるようになります。



しかし、量子コンピューターが古典的なコンピューターでは不可能な計算を実行できるようになったら、それが正しく実行されることをどのようにして知ることができますか？ 普通のコンピューターを信じないなら、理論的には自分で計算の各ステップを注意深く研究することができます。 しかし、量子コンピューターは本質的にそのようなチェックに抵抗します。 そもそも、彼らの仕事は非常に複雑です。数百個の量子ビットまたは量子ビットのみで構成されるコンピューターの内部状態の記述を記録するには、観測された宇宙よりも大きなハードディスクが必要です。



そして、この説明を書く場所があったとしても、それを分解することはできませんでした。 量子コンピューターの内部状態は、通常、量子ではなく多くの古典的な状態（生きている、死んでいるシュレディンガー猫のような）の重ね合わせです。 しかし、量子状態を測定するとすぐに、古典状態の1つにすぐに崩壊します。 300量子ビットの量子コンピューターの内部を見ると、300ビットの古典的なビット（0と1）だけが表示され、見返りに丁寧に微笑んでいます。



「量子コンピューターは強力ですが、神秘的です」とバジラニは言いました。



これらの制限を考慮して、コンピューター科学者は、量子コンピューターがそれが主張することを本当に実行したという絶対に信頼できる保証を提供できるかどうか長い間考えてきました。 「量子世界と古典世界の相互作用は、そのような対話を可能にするのに十分強いのでしょうか？」ヘブライ大学エルサレムのコンピューター科学者、 Dorit Akharonovaに尋ねました。



政権の2年目に、マハデフはこの任務に捕らわれ、その理由を完全には理解していません。 その後、彼女はあるアプローチを使用し、別のアプローチを使用しようとしました。 「私は、すべてを正しく行っているように思えた瞬間が何度もあり、それからすべてが壊れました-非常に迅速に、または1年後に」と彼女は言いました。



しかし、彼女はあきらめることを拒否しました。 マハデフは、バジラニが以前に会ったことのないレベルの不変の決意を示しました。 「この意味で、ウルミラは絶対に並外れている」と彼は言った。







そして今、8年間の大学院研究の後、Mahadevは成功しました。 彼女は、量子能力を持たないユーザーが暗号化を使用して量子コンピューターを抑制し、それをどこにでも向けることができるインタラクティブなプロトコルを作成しました。 Vazirani氏によると、Mahadevのアプローチはユーザーに「コンピューターが取り除くことのできない圧力のてこ」を提供します。



「本当に驚くべきことです」と、大学院生が単独でこの結果を達成できることをアーロンソンは言いました。



現在バークレーの研究ポスドクであるマハデフは、2018年10月に、今年パリで開催された最大のコンピューター会議の1つであるコンピューターサイエンスに関する年次シンポジウムでプロトコルを発表しました。 聴衆は彼女の作品に賞「最高の作品」と「最高の学生の作品」を授与しました。これは理論計算機科学の専門家にとって珍しい賞です。



ブログ記事で、カリフォルニア工科大学のITスペシャリストであるThomas Widickは、過去にMahadevと協力しており、「近年の量子コンピューティングと理論情報学の交差点で生まれた最も優れたアイデアの1つ」と説明しています。



コンピューターサイエンスの分野の研究者は、Mahadevプロトコルが可能なことだけでなく、この問題に対処するのに役立つ根本的に新しいアプローチも喜んでいます。 量子分野での古典的な暗号化の使用は「真に革新的なアイデア」であるとVidikは書いています。 「他の多くの結果がこれらのアイデアで成長すると思います。」

長い道のり

マハデフはロサンゼルスの医師一家で育ち、南カリフォルニア大学で学び、ある地域から別の地域に移り、最初は自分が医者になりたくないと確信しました。 それから彼女は、有名なRSA暗号化アルゴリズムの作成者の1人であるレナード・エイドルマンによって教えられた理論的なコンピューターサイエンスのコースに非常に興味を持ちました。 彼女はバークレーの大学院に入学し、量子コンピューターを除く理論コンピューター科学のすべての側面に興味があることを説明文で示しました。



「それは、私が考えていなかった完全に異質なものでした」と彼女は言いました。



しかし、一度バークレーに来て、彼女はワジラーニの利用可能な説明の影響ですぐに心を変えました。 彼は量子コンピューティングを確認するためのプロトコルの検索に彼女を紹介し、このタスクは「本当に彼女の想像力を働かせた」とバジラニは言った。



「プロトコルはパズルのようなものです」とマハデフは説明しました。 「他の質問よりも簡単です。ここでは、すぐにプロトコルについて考え始め、それらを細かく分割して、それらがどのように機能するかを見ることができます。」 バジラニが言ったように、彼女は博士号のためにこの仕事を選び、「非常に長い旅」に乗り出しました。



量子コンピューターが古典的なコンピューターでは不可能な問題を解決できる場合、これは解の検証が困難であることを自動的には意味しません。 例えば、多数を因子に分解するタスクを考えてみましょう-大型の量子コンピューターは効率的にそれを解くことができると信じられていますが、同時にそれは古典的なコンピューターの能力を超えています。 しかし、古典的なコンピューターが数値を因数分解できない場合でも、量子結果が正しいかどうかを簡単に確認できます。すべての因子を乗算し、それらが正しい答えを与えるかどうかを確認するだけです。



ただし、コンピューター科学者は、量子コンピューターが解決できる多くのタスクにはそのような機能がないと信じています（そして最近、証明に向けた一歩を踏み出しました）。 言い換えれば、古典的なコンピューターはそれらを単に解決することはできず、提案された解決策が正しいかどうかさえ認識できません。 その結果、2004年、Waterloo Perimeter Instituteの理論物理学者であるDaniel Gottsmanは、量子コンピューターが非量子オブザーバーに、彼が主張していることを実際に達成したことを証明できるプロトコルを考え出すことが可能かどうかを尋ねました。







4年間、量子コンピューティングの研究者は部分的な答えを見つけました。 2つの異なるチームは 、量子コンピューターがその計算を証明できるが、純粋に古典的な検証者ではなく、別の非常に小さな量子コンピューターにアクセスできる検証者に証明できることを示しました。 後に、研究者はテスターが一度に1キュービットの状態を測定する能力のみを必要とすることを示すことにより、このアプローチを改善しました。



2012年、Vaziraniを含む研究者チームは、完全に古典的な検証者が相互に通信しない一対の量子コンピューターによって実行された場合、量子計算を検証できることを示しました。 しかし、彼らのアプローチはそのようなシナリオのために特別に設計されており、タスクは行き止まりに陥ったように見えた、とゴッツマンは言った。 「おそらく、これ以上先に進む方法はないと考えている人がいたと思います。」



この頃、マハデフは確認の問題に直面していました。 最初は、量子コンピューターができることとできないことを指定せずに、「無条件の」結果を生成しようとしました。 しかし、彼女がしばらく成功せずにタスクに取り組んだ後、バジラニは代わりに「ポスト量子」暗号を使用する可能性を提案しました-つまり、研究者によると、その破壊は量子コンピューターの能力を超えています彼らは知りません （オンライン転送の暗号化に使用されるRSAアルゴリズムなどの方法は、ポスト量子ではありません。セキュリティが大きな数値の因数分解に基づいているため、大型の量子コンピューターはそれらを解読できます）。



2016年、マハデフとバジラーニは別のタスクに取り組んでいる間に突破口を開きました。 サンフランシスコに本拠を置くOpenAIのITスペシャリストであるPaul Cristianoと共同で、暗号を使用して量子コンピューターを「秘密状態」にする方法を考案しました。この状態は、古典的な検証者には知られていますが、量子コンピューター自体には知られていません。



それらの手順は、「トラップ」機能に基づいています。これは、簡単に実行できますが、秘密の暗号キーがない限り、元に戻すことは困難です。 （その瞬間、研究者たちは適切なtrapの作り方をまだ知らなかった-これは後になってきた）。 この関数には、「2対1」プロパティも必要です。つまり、出力データの各セットには、入力データの2つの異なるセットがあります。 たとえば、数値の2乗を想像できます。数値0に加えて、各結果（たとえば9）に対応する2つの入力数値（3と-3）があります。



同様の機能を備えた次のように、量子コンピューターを秘密の状態にすることができます。 最初に、関数に対して考えられるすべての入力データの重ね合わせを作成するタスクをコンピューターに依頼します（これはコンピューターにとっては難しいタスクのように思えるかもしれませんが、実際は単純です）。 次に、この巨大な重ね合わせに関数を適用するようにコンピューターに指示し、関数のすべての可能な出力の重ね合わせである新しい状態を作成します。 入力と出力の重ね合わせは混乱します。つまり、それらの一方を測定すると、すぐに他方に影響します。



次に、コンピューターに注文して最終状態を測定し、結果を報告します。 測定により、状態が出力データの可能なセットの1つに折りたたまれ、入力状態はそれに対応するために折りたたまれます。たとえば、平方関数を使用する場合、出力状態が9の場合、入力は重ね合わせ3に折りたたまれます。 -3。



ただし、トラップ関数を使用することを忘れないでください。 トラップの秘密鍵があるため、入力の重ね合わせを構成する2つの状態を簡単に見つけることができます。 量子コンピューターはできません。 そして、彼は単純に入力の重ね合わせを測定してそれが何であるかを見つけることはできません。そのような測定はさらにそれを崩壊させ、コンピューターを他の計算能力なしに2つの選択肢の1つに残すからです。



2017年に、Mahadevは、エラーを伴う学習 （LWE）と呼ばれる暗号化を使用して、秘密状態法のベースとなるトラップ関数を作成する方法を理解しました。 これらのトラップ機能を使用して、彼女は、クラウドコンピューティングシステムのユーザーがデータを隠して、クラウドコンピューターが計算を実行してもデータを読み取れないようにする「ブラインド」コンピューティングの量子バージョンを作成できました。 その後まもなく、Mahadev、Wazirani、およびCristianoはVidikおよびZwika Brackerski （イスラエルのワイツマン研究所）と協力して、これらの機能の品質をさらに向上させ、秘密状態法を使用して、量子コンピューターが証明可能な乱数を生成できる保証された方法を開発しました。



マハデフはそのような結果に基づいてすでに学位を取得できたかもしれませんが、彼女は確認の問題を解決するまで仕事を続けるつもりでした。 「私の目標はリリースではなかったので、リリースについては考えませんでした」と彼女は言いました。



この問題を解決する能力の不確実性が彼女に圧力をかけることがあります。 しかし、彼女は言った、「私は自分に興味のあることを学ぶことに時間を費やしたので、この娯楽は無駄とは言えない」。

石に刻まれた

Mahadevは、秘密状態の手法にさまざまなアプローチを使用して確認プロトコルを編成しようとしましたが、しばらくの間、これは何にもつながりませんでした。 そして、彼女にアイデアが浮かびました。研究者は、量子ビットを測定する能力があればテスターが量子コンピューターをチェックできることをすでに示していました。 定義上、古典的な検証者にはそのような機会はありません。 しかし、古典的なテスターが量子コンピューターに何らかの方法で測定を行わせ、その結果を正直に報告できるとしたらどうでしょうか？



検査官が彼に尋ねる測定値を見つける前に、マハデフが量子コンピューターに特定の測定を約束することを理解する方法が困難になります-さもなければ、コンピューターが彼を欺くのは非常に簡単になります。 ここで、秘密状態の方法が役立ちます。 Mahadevプロトコルでは、量子コンピューターが最初に秘密の状態を作成し、次にそれを測定すべき状態と混同する必要があります。 そして、コンピューターはどの測定を行う必要があるかを知っています。



コンピューターは検査官に知られている秘密の状態の内部詳細を知らないので、Mahadevは量子コンピューターがいかなる方法でもチートできず、それについて疑いの余地がないことを示しました。 実際、コンピューターが測定する必要があるキュービットは「暗号石に刻まれています」とVidikは書いています。 したがって、測定結果が正しい証明のように見える場合、検査官はそれが正しいことを確認できます。



「これは素晴らしいアイデアです！ -Vidikを書きました。 「彼女はウルミラが彼女を説明するたびに私を襲う。」



Mahadevの確認プロトコルは、乱数ジェネレーターとブラインド暗号化とともに、量子コンピューターがLWEを解読できないという前提に依存しています。 これまでのところ、LWEは一般にポスト量子暗号の主要な候補と考えられており、米国標準技術局はすぐにそれを新しい暗号標準として承認し、クラッキングを起こしやすいものを量子コンピューターに置き換えることができます。 しかし、これは量子コンピューターに対して実際に安全であることを保証するものではない、とゴッツマンは警告した。 「しかし、これまでのところすべてが明確です」と彼は言います。 「誰もそれを破る可能性の証拠を発見していません。」



いずれにせよ、LWEのプロトコルの信頼性は、いずれにせよMahadevを受賞作品にしている、とVidikは書いています。 量子コンピューターがプロトコルをだますことができる唯一の方法は、量子コンピューティングの世界の誰かがLWEをクラックする方法を思いついた場合です。



Mahadevプロトコルは、近い将来、実際の量子コンピューターに実装される可能性は低くなります。 これまでのところ、彼は実用的な観点からあまりにも多くの計算能力を必要としています。 しかし、将来、これは量子コンピューターの成長に伴い変化する可能性があり、研究者はこのプロトコルを合理化します。



このプロトコルは、たとえば今後5年以内に登場する可能性は低いが、「そんなSFではない」とアーロンソンは語った。 「このトピックについては、量子コンピューターの開発の次の段階で、すべてがうまくいくなら、すでに考え始めることができます。」



そして、この分野がどれほど急速に発展しているかを考えると、この段階は予想よりも早く始まるかもしれません。 実際、わずか5年前に、量子コンピューターが古典的なコンピューターができない問題を解決できなくなるまで、さらに多くの年が経つと研究者たちは信じていたとVidikは言った。 「そして今、」と彼は言った、「人々はこれが1、2年後に起こると信じています。」



お気に入りの問題を解決したマハデフは、やや当惑した状態のままでした。 マハデフは、この問題が彼女にとって非常に適している理由を正確に理解したいと言います。 「今、私は他の質問を探す必要があるので、それを見つけるのは良いことです。」 しかし、理論情報学の専門家は、マハデフが歴史の終わりに成功した量子コンピューティングと暗号法の組み合わせを考慮せず、新しいアイデアの豊富なソースになるかもしれないものの研究の始まりにすぎません。



「多くの派生的なアイデアが続くように思えます」とアーロンソンは言いました。 「ウルミラの新しい結果を楽しみにしています。」