量子情報:ゲームのルールの変更

Carl Miller 、数学者、 Cryptographic Technology Group ;フェロー、 メリーランド大学量子情報およびコンピュータサイエンス合同センター (QuICS)

私は2008年にミシガン大学の数学研究者でしたが、純粋数学の研究から量子情報科学の研究に移行するという狂気の概念(ランダムとさえ言えます)がありました。

当時の私のメンターはこれに混乱していました。 W なぜ、すべてのトレーニングを受けている分野をあきらめて、知らないものに切り替えるのですか?私の短い答えは、数学は芸術であると同時に道具でもあるということです。私は芸術的な側面を見てきましたが、今は数学を使いたいと思っていました。しかし、おそらくもっと重要なのは、量子情報がかっこいいように見えたことです。それは若い分野であり、ポピュラーサイエンスメディアで注目を集めていました。基礎となる数学は本当に興味深いものでした。

これは単なる主題の変化以上のものでした。純粋数学者は、日常の経験の乱雑さと不確実性に悩まされることなく、規則を修正することに慣れています。固定された仮定である「公理」を設定し、次にそれらの仮定から推論する「定理」を構築します。 「証明」は、定理の真理の最終的な、そして不変の証明です。

しかし、情報科学ではそうではありません。そして、それは私たちに毎日影響を与える事実です。

オンラインでクレジットカード取引を行うたびに、特定の暗号化プロトコルが私の情報を十分に隠して、犯罪者が私のクレジットカード番号を盗んで買い物をするのを防ぐことができると思います。このような仮定は、ある意味で「証明」することができますが、そのような証明は、他の分野の発展のために時間の経過とともに修正する必要があるかもしれない基礎に基づいています。これは、情報理論を非常に困難にし、それを非常に楽しくする理由の一部です。

量子論理

20世紀初頭、物理学者は、説明するのが非常に難しい、素粒子レベルで起こっていることを発見しました。 「位置」と「状態」にあることの意味についての基本的な考え方が疑問視されました。

日常生活では、車のキーをキッチンカウンターに置いたり、ポケットに入れたりすることはできますが、両方を行うことはできません。後でどこに置いたか忘れてしまうかもしれませんが、猫の1匹がそこにたどり着かない限り、それはまだどこかにあります。

素粒子スケールでは、物事は…異なります。クォンタムルールに従って動作するキーは、ポケットとカウンターの両方に同時に存在する可能性があります。 そして、それがどこにあるかを確認すると、ランダムにいずれかの場所に行き着きます。これは量子重ね合わせの考え方であり、奇妙なことに、この概念は特定の実験の結果を説明する正しい方法を提供することが最終的に決定されました。

さらに進んで、2つの粒子を重ね合わせた状態でリンクまたは「絡み合わせる」ことができます。つまり、2つの粒子の観測は、それらがどれほど離れていても、常に一致します。

ここで、「量子論理」に注意を払う必要がある理由を説明する例を示します。下に「魔方陣ゲーム」と呼ばれる数学パズルがあります。これは、私が以前行っていた数学のコンテストの初期のラウンドで発生した可能性のある種類の問題です。

ランダムな行が割り当てられているアリスとランダムな列が割り当てられているボブは、それぞれ、指定された3つの条件を満たすグリッド内のボックスに入力する必要があります。最も重要なことは、ゲームの進行中はコミュニケーションが取れないことです。彼らが毎回このゲームに勝つことを可能にする戦略はありますか? (示されている例では、彼らは勝ちましたが、たぶん彼らは幸運に恵まれました。)

アリスとボブが事前にスクリプトを作成しようとしていることを想像できます。試みは次のとおりです:

この戦略は、最後の正方形を正しく埋める方法がないことを除いて、優れています(行は偶数、列は奇数)。また、最初からやり直して別の方法でグリッドに入力しようとすると、常に同様の問題が発生することがわかります。

短い議論で、魔方陣パズルには解決策がないことを確信できます。 どのスクリプトでも、アリスは各行の合計が偶数になる必要があるため、スクリプト全体の合計が偶数になる必要があることに気付きます。一方、ボブの列は合計が奇数になる必要があるため、スクリプト全体の合計が奇数になる必要があります。スクリプトが同意できないため、完璧な戦略がありません。

魔方陣ゲームは勝つことができません。それともそうですか?

アリスとボブが絡み合った粒子を共有できるようにすると、シナリオが変わります。量子情報は、実数に基づく通常の確率論ではなく、数値の長方形の配列である線形演算子によって支配されます。線形演算子は加算および乗算できますが、実数とは動作が異なります。

魔方陣グリッドに配置すると、任意の行に沿った積が+1になるように、25個の線形演算子(それぞれが4×4の数値配列)を考え出すことができることがわかりました。つまり、X1X2X3X4X5 * = 1ですが、任意の列に沿った積は-1です。これらの各演算子は、「測定」、つまり、+ 1または-1のいずれかである結果を得るために量子システムを観察する特定の方法を記述します。

アリスとボブが2組の絡み合った粒子を共有し、これらの演算子でそれらを測定してそれぞれの行または列に入力すると、毎回魔方陣ゲームに勝ちます。 (これが魔法のように見える場合、それはそうだからです。それは量子「疑似テレパシー」と呼ばれ、もつれなしでそれを行う方法はありません。)

ここで興味深いのは、スクリプトがないということです。アリスにグリッドに入れる数字を事前に教えてもらうと、彼女はわかりません。彼女とボブが測定を実行して、それらが何であるかを調べるまで、これらのビットは未定の状態のままです。戦略の結果は、プレイヤー自身にとってさえ、本質的に予測不可能です。

このように、数学的な「証明」は、物理的な世界には当てはまらない仮定を行ったため、取り消されました。これは悪いニュースです!情報科学は、コンピューターができること、そして暗号化にとって決定的にできないことについての主張に基づいています。 できません。量子物理学の導入は、ルールを書き直す必要があるゲームチェンジャーです。

しかし、これに落胆するべきではありません。新しいルールを有利に使用する必要があります。ここから量子情報が始まります。

量子ランダム性

2010年、私は量子数学者になるという私の夢が実現できるかどうかを確認する準備ができていたので、ミシガン大学のコンピューターサイエンス学部に移りました。この時点で、私は従来のアカデミックトラックを残し、時には刺激的で、時には非常に困難な即興の道を進んでいました。

(若手研究者へのアドバイス:博士号取得後に分野を切り替えることは可能ですが、非常に難しいので、正当な理由がある場合にのみ行ってください!)

数か月後、同僚のYaoyun Shiは、私たちが勉強するのに魅力的な問題を見つけました。 Roger Colbeckという名前の研究者は、魔方陣ゲームのようなマルチプレイヤーゲームを使用して、認定された乱数を作成できると推測していました。ランダム性は情報科学の重要なリソースです。オンラインで安全に通信するたびに、「秘密鍵」を使用します。これは、他の人が推測できないように十分にランダムでなければならない0と1の文字列です。

コルベックの提案は多かれ少なかれ次のようになりました。完全に信頼されていない 2つの量子デバイスを取り、魔方陣を何度もプレイさせます(最初のデバイスはアリスの役割を果たし、2番目のデバイスはアリスの役割を果たします)。ボブの役割で)、そして彼らが何回勝ったかをチェックしてください。コルベックは、勝利数が十分に多いことがわかった場合、出力を完全にランダムな秘密鍵に変換し、それをコミュニケーションのリソースとして使用できることを証明することを提案しました。

>

これは研究の素晴らしい出発点のように思えました。利用可能な最善の手法に逆らった簡単な質問です。

数学の研究とは何かと聞かれました。私の答えは次のようなものです。汗が多く、涙が少し、血が少し(紙切れが最悪です)、かなりの空想があります。 (空想の重要性を過小評価してはなりません!ここからいくつかの最高のアイデアが始まります。常にそうしないでください。)最終的には勢いが増し、洞察が急速に高まり、すべてを次のように変えます。成功した研究プロジェクト。

Yaoyunと私が遭遇してから約2〜1年半後、認定されたランダム性の問題を解決しました。これは間違いなく、私がこれまでに解決した中で最も難しい数学の問題でした。証明は昨年公開され、インターネットで入手できます。

証明を実行するための洞察の例を2つ挙げます。 1つは、「部分的に信頼された」量子デバイスのアイデアでした。 「完全に信頼されていない」デバイスは、使用されるたびに必要な処理を実行しますが、「部分的に信頼されている」デバイスの場合、使用するたびに、想定どおりに動作する確率が一定になります。 (信頼されていないクロックは決して正しくないかもしれませんが、停止したクロックは少なくとも1日に2回は正しいです。)完全に信頼されていないデバイスは、部分的に信頼されているデバイスをシミュレートするように強制できることを証明しました。この「強制」は便利です。デバイスが適切に動作する場合、完全な量子重ね合わせによって示されるランダムなコインフリップ効果が得られます。残念ながら、デバイスが適切に動作している場合とそうでない場合はわかりませんが、この部分的な信頼の考え方により、証明を開始できます。

後で関係するもう1つの洞察は、デバイスのパフォーマンスをさまざまに測定するというアイデアです。デバイスから固定数のシークレットビットを取得しようとするのではなく、プロトコルの実行時にこの数を変更しました。デバイスが魔方陣ゲームに勝つたびに、収集する予定の秘密ビットの数を増やします。負けるたびに数を減らします。 (これは「最初は成功しなかったら、期待を下げる」という哲学と呼ぶことができます。楽観主義者である私は、「最初に成功した場合は、期待を上げる」と呼んでいます。)これは、デバイスのパフォーマンスレベルは時間の経過とともに変化する可能性があります。

コルベックのプロトコルが完全に秘密の鍵を生成すること、そしてそれらの鍵を希望する限り作成できることを証明しました。 (キーが長いほどセキュリティが向上します。)私たちの結果は、この分野の他の結果と同様に、「認定されたランダム性」が本物であることを意味します。それだけでなく、今日のテクノロジーでそれを作成できます。信頼できる安全な通信が必要な人にとって、これは朗報です。

未来

クォンタムのゲームを変える効果は私たちの利点に使用できますが、それは非常に両刃の剣です。 1994年、Peter Shorは、数を因数分解するための高速量子アルゴリズムを発明しました。因数分解数の硬さは、暗号化における多くの既存のスキームの基礎です。このアルゴリズムがいつの日か大規模な量子コンピューターに実装された場合(そして、良くも悪くも、まだそれを持っているとは言えません)、情報を保護する多くの方法が完全に安全ではなくなります。

>

現在、私はNISTのCryptographicTechnologiesグループで働いています。ここでは、情報を保護するための継続的な取り組みにおいて、一般の人々がゲームの先を行くのを支援するためのサービスと標準を作成します。私たちは、量子コンピューターに耐性のある次世代暗号化標準を設計し、パブリックランダム性サービスであるNISTランダム性ビーコンを管理することを目標とするポストクォンタム暗号化プロジェクトを主導しています。私はまた、量子情報とコンピューターサイエンスの合同センターのフェローであり、メリーランド大学の数学科の関連教員でもあります。

最近、大企業は量子コンピューターの構築を競い合っており、量子暗号ソリューションが一般に公開されています。これはすべて、解決すべき量子数学の問題がもっとたくさんあることを意味します。

応用数学者になるのはエキサイティングな時期です。

*編集者注: Mediumは下付き文字をサポートしていません。ここでの数字は下付き文字を意味します。

この投稿は元々 Taking Measure National Institute of Standards and Technology(NIST)の公式ブログに掲載されていました / em> 2017年8月2日。

NISTからのブログ投稿やその他のニュースを見逃さないようにするには、 メールアラート に登録してください。

著者について

Carl A. Miller は、NISTコンピュータセキュリティ部門の数学者であり、メリーランド大学の量子情報およびコンピュータサイエンス合同センターのフェローです。カールはメリーランド州、ノースカロライナ州、カリフォルニア州、ミシガン州に住んでおり、高校に通った場所から3マイル以内に戻ってきて幸せです。彼は、パートナーのアンドレアとその猫のオータムとペペと一緒にメリーランド州シルバースプリングに住んでおり、レナードコーエンが恋しいです。