16,994 文字
多くの一般科学メディアは、量子コンピューティングについて、ほぼ確実に誤解を招くような説明をしています。その説明はだいたいこんな感じです。古典的なコンピュータではデータがビット、つまり1と0の配列として保存されますが、量子コンピュータでは、ある固定された長さのビット列のあらゆる可能な組み合わせを、「重ね合わせ」と呼ばれる一つの大きなものの中に同時に表現できます。
そして、こうした説明からは、量子コンピュータが古典的なコンピュータのやることを基本的にすべての配列に対して並列に処理することで高速化できるという印象を受けることがあります。これは何か本当のことを指し示してはいますが、誤解を招くと思いますので、クイズを使ってそれを証明してみましょう。
説明のために、ある謎の関数があるとします。0からn-1までのすべての数字の中に、その関数に入力すると「真」を返す特定の秘密の数字が一つだけあり、他のどの値を入力しても「偽」を返すとします。関数の内部を見ることはできず、できるのは数字を入力して試してみることだけだとしましょう。
ウォームアップの質問です。この謎の秘密の鍵を見つけるために、平均して何回この謎の関数を適用する必要があるでしょうか？通常の古典的なコンピュータの場合、推測と確認以外の方法はありません。すべての数字を試していき、運が良ければ早く見つかりますし、運が悪ければ後の方まで見つからないでしょうが、平均すると、n個の可能性のあるリストでは、鍵を見つけるのにn/2回の試行が必要になります。
コンピュータサイエンスでは、実行時間がどのようにスケールするかが重要です。リストが10倍大きくなったら、どれだけ時間がかかるでしょうか？コンピュータサイエンティストには実行時間を分類する方法があります。これはO(n)と呼ばれ、「ビッグO」は1/2のような定数や、nより遅く成長する要素があるかもしれませんが、nが大きくなるにつれてどれだけ速くスケールするかを説明するのはn因子だということを表しています。nが10倍になると、実行時間も10倍になります。
さて、あなたへのクイズです。量子コンピュータでの同等のセットアップの場合、秘密の鍵を見つけるための最適な実行時間は何でしょうか？選択肢は、O(√n)、O(log n)、O(log log n)、O(1)です。ここでO(1)とは、実行時間がnの成長に伴って増加しない単なる定数であることを意味します。
確かに、私はまだ量子コンピューティングを定義していません。実際、それをゼロから説明することがこのビデオの目標です。そのため、この謎の関数が量子の設定でどのように見えるかを示さずに、この質問は少し筋が通っていないかもしれません。しかし、これは採点するためのクイズではなく、本格的な説明に入る前の直感のチェックとして意図されています。
原則として、タスクは同じです。干し草の山から針を見つけるように、多くの選択肢の中から一つの関数を一意にトリガーする値を発見したいのです。私は先月YouTubeの投稿でこれを尋ね、親切にも10万人の方々が回答してくれました。最近、スタンフォード大学の学生グループに生で出題したこともあります。
国際数学オリンピアドの参加者にもこれを提示しました。そして、これらすべてと他の多くの場合で、回答の分布は非常に似ています。最も一般的な回答は常にO(1)です。そしてこれは間違いで、おそらくその誤解を招く要約からきています。その要約は、検索する必要のあるn個の値をすべてこの謎の重ね合わせに入れ、それらをすべて並列に処理し、何らかの方法で答えが明らかになるということを暗示しています。
二番目に一般的な回答は通常O(log n)で、これも間違いです。これは指数関数的な高速化と呼ばれます。例えば、リストのサイズを10倍ずつ増やすと、O(log n)の実行時間は毎回同じ量だけ加算的に増加するだけです。この誤った回答は、量子コンピュータが一般的にどれほど優れているかについての誤解から来ていると思います。
指数関数的な高速化を達成できる特定の特殊な問題があります。おそらく最も有名な例は、大きな数字を因数分解するためのショアのアルゴリズムでしょう。しかし、ほとんどの問題はそうではありません。この場合、正解はO(√n)です。そしてこれは、量子コンピュータで得られる典型的な高速化をはるかに代表しています。
1994年、量子コンピュータがこのタスクでO(√n)より優れることは不可能であると証明されました。そして2年後、ラブ・グローバーはその実行時間を実際に達成する特定の手順を見つけました。したがって、100万個のオプションの袋を検索するには、1000ステップ程度かかります。1兆個のオプションの袋は100万程度のステップです。このビッグOは、実際には正確な実行時間にπ/4という定数が隠されており、そのπには語るべき面白い物語があります。
特定の値によってトリガーされる謎の関数を持つこのパズルは、非常に人為的なものだと思うかもしれません。しかし、これは、解決策を素早く検証する方法は知っていても、最初にその解決策を見つける方法は知らないという、あらゆる問題の一般的な代表と考えてください。これはコンピュータサイエンスでNP問題として知られる膨大なクラスの問題を表しています。ですから、√nの高速化は率直に言って指数関数的な高速化ほど地球を揺るがすものではなく、ビッグOの実行時間は他の実用的な考慮事項よりもしばしばはるかに重要ではありませんが、グローバーのアルゴリズムのようなものが可能であること自体が考えさせられます。あらゆるNP問題を高速化するための万能の方法を提供しているのです。
この授業の目標は、そのアルゴリズムがどのように機能するかをステップバイステップで解説することです。それは非常に幾何学的で美しいものです。しかし、そこに到達するためには多くの背景知識を構築する必要があります。
このビデオの最初の2/3程度は、量子コンピューティングの基礎を構築するのに費やされます。誤解を招く可能性のある一連のアナロジーではなく、数学の一部として、その分野のより正直な描写を見ることができる眼鏡を提供します。
これは、最初は少し奇妙に感じる前提がいくつかあるトピックの一つで、慣れるのに少し時間がかかることを警告しておきます。現在の計画では、この授業の後に、基礎となる物理学についての別の授業を行い、ここで見ることになる奇妙に見えるルールのいくつかを動機づけるのに役立つことを願っています。
しかし今日の目標は、本物の量子アルゴリズムを見るための最小限の実行可能な道筋を提供することです。古典的なコンピューティングと量子コンピューティングの対比をもう一度取り上げ、より代表的なメンタルモデルを構築できるかどうか見てみましょう。
確かに、古典的なコンピュータのデータは1と0の連続として表されており、より高い抽象化レベルでは整数やテキストなどの実際のデータ型を表し、より低い抽象化レベルでは、これらの1と0はコンデンサの電圧などの物理的な世界の実際のものを表します。
これらの抽象化の同じ層は、量子コンピューティングについて議論する際にも役立つフレーミングを提供します。そこでも何らかの基礎となる物理的測定があり、その測定の結果を一連の1と0で表し、これも数字などの実際のデータ型を実装する可能性があります。
ちなみに、私が示しているこの記号は「ケット」と呼ばれます。数分後に適切に説明しますが、今のところ、それが量子コンピュータからのものであることを伝えているものとして考えてください。
中間層の抽象化のレンズを通して量子コンピューティングの説明から始めましょう。つまり、今はすべての基礎となる物理学を後回しにします。これは、ハードウェアについて議論せずにコンピュータサイエンスを教えるようなものです。
古典的なコンピュータでは、メモリの状態とメモリから読み出すものを区別する必要はなく、どちらも同じビット列のように見えますが、量子コンピュータでは非常に異なります。今日の私たちの主な仕事は、状態ベクトルと呼ばれるものを理解することです。これは連続的なもので、コンピュータが実際に操作するものですが、実際に読み出す値、つまり離散的なビット列との関係は非常に異常です。
この状態ベクトルを定義する前に、もう一つ古典的なコンピュータとの重要な違いを知る必要があります。読み出される値は、1と0の連続のように見えますが、ランダムです。より正確に言うと、通常はランダムだと言うべきでしょう。
考え方としては、量子コンピュータでプログラムを実行すると、そのプログラムは特定の出力を必ずしも決定するわけではなく、代わりにすべての可能な出力にわたる確率分布を決定するということです。
画面に表示している例では、読み出されるものが4ビットの非常に小さな量子コンピュータで、つまり2の4乗、つまり16の可能な出力があり、実行する特定のプログラムがそれらの可能な出力全体にわたる何らかの分布を決定します。一部のプログラムは1つの出力に対して確率をより集中させるかもしれませんが、他のプログラムはすべてにわたってより均等な分布を与えるかもしれません。
ちなみに、読み出されるものが4ビットのこの例は、4量子ビット量子コンピュータと呼ばれます。より一般的には、k量子ビット量子コンピュータがある場合、2のk乗の異なる可能な出力があり、任意のプログラムがそれらすべてにわたる分布を与え、読み出されるものにはk個の異なるビットがあることを意味します。
ちなみに、量子ビットという言葉も、数分以内にもっと正確に定義するものです。この分布は暗黙的であることを強調したいと思います。直接見ることはなく、実行するプログラムに基づいてどのようなものでなければならないかを推測します。すべてのビット文字列が何らかの形で一度に共存しているのを見ることはありません。
この分布に従ってランダムに引き出された1つだけを見ます。より低い抽象化レベルでは、私がメモリからの読み出しとして説明しているものは物理的な測定のように見え、ランダム性は量子力学の法則から生じています。物理学に興味があれば、より低い抽象化レベル、それが次のビデオのテーマです。
このレベルでは、すべての可能なビット文字列にわたる確率分布について考えるだけです。ここでもう一つの面白いルールがあり、それは基礎となる量子力学から浮かび上がってきますが、メモリから読み出した後、特定の値を見ると、コンピュータの基礎となる状態が変化し、すべての確率が読み出した値に集中するようになります。
そのため、メモリから繰り返し読み出すと、同じ値を見続けることになります。これらのプログラムは、非常に繊細で敏感な確率分布を作り出し、それを見た瞬間、その分布からサンプリングすると、全体が一つの値に崩壊すると想像できるでしょう。
さて、この分布はどこから来るのかと疑問に思うかもしれません。これが最も重要で最も混乱する部分です。コンピュータの状態は大きなベクトルによって記述されると考えてください。今、ベクトルという言葉を使うとき、数の大きなリストとして考えることができますが、後で見るように、これを超高次元空間の方向として考えると役立つことがあります。
このベクトルの各成分は、読み出される可能性のある値の1つ、つまり異なるビット文字列の1つに対応します。したがって、読み出されるものが4ビットのこの例では、状態ベクトルには16の異なる成分があります。状態ベクトルは、すべての可能な出力にわたる確率分布と同じではありませんが、非常に密接に関連しています。
基本的なルールは、最初は非常に奇妙に見えることを認めますが、その状態ベクトルの各成分の大きさを取り、それを二乗すると、対応する出力、対応するビット文字列を見る確率が得られるというものです。
最初に言っておきますが、量子コンピューティングを学ぶ多くの人々はこの状態ベクトルを少し奇妙だと感じます。それは実際には何であり、なぜ確率を得るために物事を二乗するのでしょうか？単純化のために、ビデオの終わりまで隠している重要な詳細があります。
これには慣れが必要だと言っておきます。ここでの基本的なルールについて超明確にするために、このプログラムがこのベクトルを処理した後、おそらく0011のような特定のビット文字列に関連する成分が0.5になったとしましょう。
その値を二乗すると、0.5の二乗は0.25なので、これの観察可能な意味は、メモリから読み出すとき、そのビット文字列0011を見る確率が25%あるということです。
強調したいのは、この状態ベクトルの値が負になる可能性があることです。最初は、符号を反転しても二乗が変わらないため、したがってすべての確率は同じままであるため、これは実際には影響がないと思うかもしれません。
確率が同じままであるのは事実ですが、これを別の状態と考えることは絶対に正しく、後で見るように、符号を反転させるという考えはグローバーのアルゴリズムで非常に中心的な役割を果たします。
この4量子ビットの例では、画面上にかなり多くのものがあり、それをバックアップする可視化があまりありません。そこで、コンピュータが0と1で表される2つの可能な出力しか持たない最も小さな可能なケースに話を縮小しましょう。
この最も単純な場合、状態ベクトルは2次元のみなので、実際に2D空間内の矢印として幾何学的に表現できます。この場合、x座標は出力0に対応します。その座標の二乗はコンピュータから読み出すときに0を読み出す確率を教えてくれるという意味です。
おそらく、その確率を示す小さなバーを追加すると役立つでしょう。ベクトルがより水平方向を指すほど、確率質量がより0に集中していることに気付くでしょう。同様に、y座標は同じ方法で1に対応します。より垂直な状態ベクトルは、コンピュータから読み出すときに1を見る可能性が高いことを意味します。
さて、2つの確率は1に加算されるべきであることに注意してください。結局、何かが起こるわけですから、x二乗+y二乗は1に等しいはずです。幾何学的には、これは状態ベクトルの長さが1であることを意味するので、単位円に限定されていると考えることができます。より一般的には、量子コンピュータの状態ベクトルは常に長さ1を持ち、非常に高次元の単位球面上に存在すると考えることができます。
この2次元の例には、すでに言及した特別な名前があります。量子ビット（量子ビット）と呼ばれ、量子ビットの略です。古典的なビットとのアナロジーは、コンピュータから読み出すとき、0か1のどちらかを見るということですが、それ以外は完全に異なるものです。
数学的には、量子ビットは2次元空間内の単位ベクトルであり、これらの2つの垂直なx方向とy方向が測定時に読み出される可能性のある2つの値に対応する座標系が一緒になっています。
私が先送りにしている複雑さがあることを知っておくべきですが、これは正しい考え方の90%です。そして繰り返しますが、量子ビットを測定して0か1のどちらかを見るとき、ベクトルはその対応する方向に崩壊するという奇妙なルールがあります。そのため、その量子ビットを対角方向に戻すための何かが行われない限り、その後の観測は常に同じ結果を示すことになります。
この時点で、「わかった、グラント、これは非常に奇妙な前提のセットを受け入れるように求めているんだね」と考えている可能性があります。そしてそうであれば、あなたは一人ではありません。私が説明しているのは、おそらくわかると思いますが、基本的に量子力学の公理です。
物理学全体にわたる多くのシステム、例えば電子のスピンや光子の偏光などが、測定の結果がランダムであるというこの特性を持っており、私たちの最良の物理法則では、そのシステムの状態を、ここで説明しているようなベクトルを使ってモデル化し、そのベクトルの成分の大きさの二乗がさまざまな可能な結果を見る確率を与えます。
これには実際に特別な名前があり、ボルンの規則と呼ばれています。量子ビットのこの考え方は、基本的にはこのような多くの可能なシステムにわたる抽象化であり、ちょうどビットが二つの方向の間で切り替えることができる多くの可能な物理システムにわたる抽象化であるのと同じです。
ちなみに、私が示している記号は、量子という単語を含む任意の主題で使用され、この状態空間内の単位ベクトルを指します。そのケットの中に入れるものは、多くの場合、そのベクトルが表すものに何らかの読み取り可能な意味を与えます。
したがって、量子ビットの例では、右側の単位ベクトルは多くの場合、ケットの中にゼロが入っているように示されます。なぜなら、それが状態ベクトルであれば、コンピュータから決定論的にゼロを読み出すということを意味するからです。
同様に、垂直方向の単位ベクトルは、中に1が入ったケットで表されます。そして、これについてもっと読むと、非常によく見られるのは、列ベクトルで一般的な量子ビットを書き下す代わりに、多くの人が二つの座標方向の二つの単位ベクトルの明示的な重み付き和として書くのを好むということです。
これは非常に物理学者的な慣習です。さて、古典的なコンピューティングには論理ゲートという考え方があり、AND、OR、NOTなどの特定の基本的な操作を使用してビットを処理し、それらを組み合わせて任意に複雑な関数を作成できます。
同様に、量子ゲートと呼ばれるものがあり、それらは量子ビットやまたは複数の量子ビットのシステムに適用できる特定の基本的な操作です。そして、それらは常に状態ベクトルをなんらかの方法で反転または回転させるように見えます。
すべての異なる量子ゲートの詳細にはあまり深入りしませんが、興味があれば、そのうちの一つがどのように見えるかの例を示します。これはアダマールゲートとして知られる非常に標準的なものです。
それが行うことは、水平方向のゼロ方向のその単位ベクトルを対角線の北東方向にマッピングし、垂直方向の1方向の単位ベクトルを一種の対角線の南東方向にマッピングすることです。
これは非常に一般的に、決定論的な状態、つまりゼロまたは1のどちらかを取り、それを50-50の等しいバランスのあるものに変えるために使用されます。また、その逆も同様です。
これは一つの例ですが、量子コンピューティングの構成要素を形成する他のいくつかもあり、この設定でアルゴリズムを書く芸術は、量子ベクトルがほぼ完全に一つの特定の座標方向を指すまで、異なる量子ゲートをたくさん組み合わせて、ベクトルを段階的に操作し、反転し、マッサージすることです。おそらく、あなたが気にかけている質問に実際に答える方向です。
さて、量子ビットの最も単純な例では、扱うことができる座標方向は2つだけなので、単純なイエス・ノーの質問に答えることに限られます。また、3次元以上の幾何学的なベクトルを私が描くことはできませんが、原則として、k量子ビットを持つシステムは2のk乗の異なる座標方向を持ち、それぞれがビット文字列に対応します。
したがって、何らかの方法でこのベクトルをちょうど一つの方向に向かせることができれば、潜在的に、より多くの情報を運ぶ、より興味深い質問に答えることができるかもしれません。おそらく、そのうちの一つは、因数分解しようとしている非常に大きな数の素因数を表すか、あるいはこのビデオの冒頭のパズルからの秘密の鍵値を表します。
量子コンピュータの潜在的な力が大幅に誇張されてきた長い伝統がありますが、そこに実際により多くの力がある限り、その主な理由の一つは、状態ベクトルのサイズが指数関数的に成長することです。わずか100量子ビットでも、すでに途方もなく巨大な状態ベクトルを意味します。
しかし、ここでの注意点は、このベクトル内の値に直接アクセスする方法がないということです。それは効果的にあなたには見えません。それが役立つ唯一の方法は、すべての確率、または少なくともそのほとんどを一つの成分に集中させるような方法でそれを操作し、その成分があなたが気にする質問の答えに対応する場合です。
グローバーのアルゴリズムは、これがどのように見えるかを実際に見るための素晴らしい例を提供しています。そして、その段階に到達する時が来ました。このアルゴリズムの非常に高レベルのプレビューを提供します。これらすべてを詳細に説明することを約束しますが、鳥瞰図は次のとおりです。
このアルゴリズムは、状態ベクトルをすべての可能な結果にわたって等しいバランスがあるように初期化します。それらの結果の一つが、あなたが探している秘密の鍵になります。そして、あなたが利用できるツール、これは後で動機づけることを約束しますが、その座標で状態ベクトルの符号を反転させることです。
これはすぐには確率に影響しませんが、これを他の特定の操作と交互に行い、これら二つの間を行ったり来たりすると、確率質量がゆっくりとその秘密の鍵値に集中し始め、ある時点でほぼすべてがそこにあるようになるため、コンピュータから読み出すとき、探している秘密の鍵をほぼ確実に見ることになります。
それが高レベルですが、もう少し詳細に説明しましょう。最初に対処すべきことは、秘密の鍵に関連付けられた成分の符号を反転させるというこの考えです。それは少し変に感じるかもしれません。
なぜそのような操作が可能だと仮定するのでしょうか？話を戻しますと、グローバーのアルゴリズムは、最初に解決策を見つけることが難しくても、解決策を迅速に検証できる問題に適用することを意図しています。
例としては、数独を解くこと、国境地域が同じ色を共有しない地図の有効な塗り方を見つけること、または暗号技術全体の数え切れないタスクがあります。そこでのセキュリティは、特定の値を見つけることが難しいという事実に依存していますが、実用的な理由から簡単に検証できなければなりません。
このビデオを始めたときに、これらすべての問題の一般的な代表として、0からn-1までの任意の数値を受け取り、それらのうちの一つだけでtrueを返す関数を想像しました。原則として、そのような関数は一連の古典的な論理原則として、そのような関数は一連の古典的な論理ゲートから構築されていると考えます。これらの論理ゲートは入力のバイナリ表現に作用し、最終的な出力は0または1です。
ここで重要なのは、グローバーはこのような論理ゲートのアンサンブルが与えられると、それを量子ゲートのシステムに変換できることを知っていたということです。古典的な場合で関数が何らかのバイナリ入力を取り込んで1（真を意味する）を返す場合、量子の場合ではこれらすべてのゲートの効果は、同じビット列に関連付けられた状態の符号を反転させることです。
同様に、古典的な場合で関数が何らかのバイナリ入力を0（偽を意味する）にマッピングする場合、この量子翻訳では対応する状態への効果は変更しないことです。より一般的に、これらすべての量子操作が線形であるため、状態が複数の純粋な座標方向の組み合わせである場合、その効果は古典関数をトリガーするビット列に関連する成分の符号を単に反転させることです。
これは、NP問題、つまり解決策を迅速に検証できる問題があれば、量子コンピュータ上でその問題の解決策に対応する位置で状態ベクトルの符号を反転させる操作を作成できることを意味します。これは最初は一種の無意味に感じるかもしれません。結局のところ、符号を反転させても確率には影響しません。
しかし、グローバーはこれを、その鍵の値の確率を徐々に増幅する別のステップと組み合わせて使用できることに気づきました。彼のアルゴリズムを視覚化する本当に素晴らしい方法があります。それを設定するために、状態ベクトルが3次元だけを持っていると想像してみましょう。明らかに原則としてはるかに大きいでしょうが、これで最初の絵を描くことができます。
ここでの3つの方向は値0、1、2に対応し、この問題の全体のステートメントは、それらの値の一つが私たちが探している秘密の鍵であるということです。多くの異なる量子アルゴリズムは、すべての成分が同じ値を持つ一種の等しいバランスに状態ベクトルを置くことから始まります。
そのバランスの取れたベクトルに名前を付けましょう。Bと呼びましょう。この基礎となる量子ゲートがそれを可能にする方法に深く立ち入らずに、これが可能であると単に宣言することに、あまり異議を唱えないことを願っています。この場合、基本的にはアダマールゲートの大きな山に見えますが、知る必要があるのは、この等しいバランスの方向が豊富にアクセス可能であるということだけです。
ここから始めて、このベクトルをその秘密の鍵の方向に向けることが目標です。そして、ここでの視覚化の目的にとって非常に役立つことは、グローバーのアルゴリズム全体を通して、ベクトルはこれら二つのベクトルによって張られる2次元平面内でのみ移動するということです。
ですから、私がやろうとしているのは、その二次元のスライスにすべてを描くことです。そして、これは実際の次元が私が文字通りに描くには大きすぎる場合でも、忠実な表現を与えてくれます。ここでそのスライスを描く際に使用する規則は、秘密の鍵の方向（それが何であれ）をこのy軸に沿って配置し、x軸は非鍵状態、つまり鍵でないすべての状態の等しいバランスを表すものとします。
ですから、私たちの非常に小さな3次元の例では、その秘密の鍵がz方向の2状態だった場合、それは垂直方向がz軸に対して垂直なxy平面上に位置する0と1の等しいバランスであることを意味します。完全に等しくバランスの取れた状態bには、秘密の鍵の方向にいくらかの成分があることに注意してください。定義によりその中にその秘密の鍵が少し含まれているからです。
3次元からこのスライスを描く代わりに、より大きな次元数から取られた場合はどのように見えるでしょうか。ほぼ同じですが、主な違いは、その等しくバランスの取れた状態ベクトルが秘密の鍵の方向に対してほぼ垂直になることです。
しかし、重要なことに、この角度は決して完全に90度ではありません。そのバランスの取れた状態は常にその中にその秘密の鍵の値を少し含んでいるからです。実際、この角度を計算することは、グローバーのアルゴリズムの実行時間を理解するために不可欠です。これが実際にやらなければならない主な数学です。
バランス状態と鍵方向の間のドット積を取ることでこの角度を見つけることができます。そのバランス状態ベクトルの成分はすべて、1をnの平方根で割ったようなものになります。これらすべての二乗を加えると1になるはずだからです。
鍵ベクトルはほとんどの場所で0ですが成分の一つで1であるため、これら二つの間のドット積はnの平方根で割った1になります。ドット積について少し知っていれば、これもこれら二つのベクトル間の角度のコサインであることがわかります。この事実を少し翻訳して、後で使いやすくしましょう。
これは、こちらの下の補角のサインが、nの平方根で割った1と同じであると言うのと同じです。その角度をシータと呼びましょう。非常に小さな角度では、シータのサインとシータはほぼ同じなので、nが非常に大きい場合、ラジアンで測定される限り、この角度は約nの平方根で割った1であると安全に言えます。
シータのこの値は、最終的に実行時間における平方根が来る場所です。覚えておきましょう。ここに角に置いておきます。さて、実際の図の設定に時間を費やしましたので、ここでの手順を示しましょう。驚くほど簡単です。
以前に見ていたキー操作を覚えていますか？解決しようとしているNP問題の検証関数を取り、それを量子ゲートに変換し、その効果はその鍵値に関連する符号を反転させるというものです。これは私たちの図の中でどのように見えるでしょうか？
この図では、鍵値に関連する成分の符号を反転させるが、他のすべての成分は同じままの場合、それはx軸について反転するように見えます。そして、必要な最後の要素は、この等しいバランスの方向を中心にこの状態ベクトルを反転させることも可能であるということです。
特定の操作が利用可能であると宣言し続けることが少し不満かもしれないことは理解していますが、一般的に知っておくべきことは、これらの状態ベクトルの一つを明確に記述してアクセスできる場合、それを中心に反射することも完全に可能だということです。いくつかの量子ゲートがあり、それらはこのバランス方向を中心に反転させることができますが、それらがどのように見えるかの詳細に立ち入っても、アルゴリズム全体の明確さや直感をあまり追加しないと信じてください。
洞察は本当に幾何学からやってきます。まずx軸の周りで反転し、次にこの対角線からはずれた方向の周りで反転すると、状態が垂直方向にわずかに傾くことに注意してください。今メモリから読み出すとしたら、秘密の鍵値を見る確率が他のすべてよりもわずかに大きくなるでしょう。
ここで、実際の座標を示すと役立つかもしれません。この場合nは100で、それらの座標の二乗に基づくいくつかの確率バーがあります。x軸の周りで反転し、次にこの対角線からはずれた軸の周りで反転するたびに、その秘密の鍵に関連する成分が少し大きくなることに注意してください。
したがって、グローバーのアルゴリズムは驚くほど単純です。ベクトルが秘密の鍵の方向にできるだけ近くなるまで、これを何度も繰り返すだけです。やらなければならない最後の推論は、それが何回の反復であるべきかを理解することです。
幾何学からの素晴らしい事実は、このようにして二つの異なる線について連続して反転させると、全体的な効果は回転と同じであり、より具体的には二つの線の間の角度の二倍の回転であるということです。
ですから、私たちの場合、利用可能な二つの操作を連続して適用すると、純効果は状態ベクトルを二倍のシータだけ回転させることです。ここでもシータは、私たちが先ほど計算した小さな角度で、約nの平方根で割った1です。
最終的な目標は、初期状態を90度（またはπ/2ラジアン）弱回転させることです。これは、最適な反復回数が二倍のシータで割ったπ/2のように見えることを意味し、それはシータで割ったπ/4であり、重要なことに、シータはnの平方根で割った1程度であるため、ステップの総数はnの平方根にπ/4を掛けたものになります。
したがって、グローバーのアルゴリズムが言うことは、最初にこの値に最も近い整数を見つけ、次に利用可能な二つの反転をその特定の回数だけ繰り返すということです。
具体例として、nが2の20乗だったとしましょう。つまり、約100万のオプションから秘密の鍵を探しているということです。少なくとも20量子ビットを持つコンピュータで実行することになり、アルゴリズムが言うことは、最初にπ/4にこの数の平方根を掛けて計算すると、それは約804になります。つまり、利用可能な二つの操作、鍵状態の符号を反転させるものとバランス方向を中心に反転させるものを804回繰り返すということです。
ここで覚えておいてください、この状態ベクトルはあなたには見えません。それが持つ値を読み出すことができることは何もありません。代わりに、推論を通して、そしてこの場合は幾何学的な推論を通して、それがどこになければならないかを推測する必要があり、この特定の回数の後、ベクトルはほぼ完全にその秘密の鍵の方向を指すはずだと結論付けることができます。
したがって、コンピュータから読み出すとき、その秘密の鍵値をほぼ確実に見ることになります。はっきりさせておくと、それを見ることが保証されているわけではありません。読み出した後に、秘密の鍵ではないものを見る小さな確率があります。
確実を期すために、答えを素早く検証することができます。結局のところ、この状況の前提全体は、答えを素早く検証する方法があるということです。古典的なコンピュータでそれを行うことができます。最悪の場合、運が悪く別の数字をサンプリングしたら、全体をもう一度実行します。そして、これを数回以上実行する必要があることはほとんどありえないでしょう。
最後に、私があなたに言ってきた嘘について正直になり、また、この高速化がどこから来たのかについても少し考え、そして驚くべきアナロジーを強調したいと思います。
その前に、パトレオンのチャンネルサポーターのコミュニティに感謝を言うのにこれ以上に良い時はないかもしれません。このような視覚化されたレッスンを組み立てるには膨大な時間がかかります。ご存知のように、ほとんどのYouTuberはビデオ内のスポンサーシップでコンテンツを収益化していますが、長年にわたってそれを断ることを選んできました。
それが動画をより良くすると思いますし、それが非常にコストのかかる決断ではない唯一の理由は、それに同意する視聴者の多くがパトレオンを通じて直接チャンネルをサポートしているからです。その対価として、サポーターには新しいコンテンツの先行視聴を提供しており、これは実際にそれを開発するのに非常に役立ちます。そして他の特典もあります。
一般的に、このコンテンツが気に入ったら、参加を検討してくれると嬉しいです。しかし、プレッシャーはありません。大きな価値の一つはコンテンツが無料であることです。
さて、その3つの終了点に戻りましょう。嘘は省略による嘘です。私はこれらの状態ベクトルを正と負の実数値で示してきましたが、より一般的には、これらの成分は複素数になる可能性があります。
私の望みは、物理学についてのフォローアップビデオでそれが必要な理由を説明することです。一般的な考え方は、波を扱うときはいつでも振幅と位相の両方を気にするということです。そして複素数は振幅と位相を一緒にエンコードする非常にエレガントな方法です。
したがって、状態ベクトル内の成分の一つを見ると、それについて考える完全な図は、それがいくつかの大きさといくつかの位相を持っているということです。大きさは確率を得るために二乗するものであり、位相は基本的に正と負の値についての私たちの全議論のより一般的なバージョンです。
位相を変更しても、すぐには確率に影響しませんが、状態に影響し、それが処理される方法と世界と相互作用する方法に影響します。言うまでもなく、複素数を投入することで、すでに複雑なトピックに多くの潜在的な混乱が加わります。だから私はそれを避けました。
しかし、グローバーのアルゴリズムの目的のために複素数値を無視しても安全でした。非常に慈悲深いことに、そのアルゴリズム中には正と負の値しか見られないからです。しかし、この複素数値の可用性が、因数分解のためのショアのアルゴリズムなど、他の量子アルゴリズムで重要な役割を果たすことを知っておいてください。
次に、このアルゴリズム全体について説明したすべてを理解したとしても、高速化がどこからきたのかを要約するのは簡単ではありません。このバランスの取れた状態に特定の操作を適用することから始めるという事実は、高速化がすべての可能な入力にわたって操作を並列化することから来ているという誘惑を非常に強くします。
しかし、私が最初に言及したように、その要約は、少なくとも私にとっては、本当に正しくは感じられず、それは確かに誤解を招きます。ご存知のように、そのステップだけでは鍵の値を明らかにするのに何もなりません。
この最初のステップを多くの入力に関数を並列に適用すると説明するか、バランス状態はそれ自体で新しいものであり、持っている関数は常に一度に個々の入力に適用され、複数の入力に一度に適用されることはないと言う方が良いかどうかはあなたの解釈に任せます。ただ、それらの入力は現在、新しい種類のものです。
私の見解では、このアルゴリズムについて、高速化がどこから来たのかを一言で要約するなら、より良い選択はおそらくピタゴラスでしょう。緩やかなアナロジーとして、単位正方形の一つの角から反対側に行きたい場合、xとyの方向にしか移動できないなら、2単位歩かなければなりません。
しかし、対角線上に移動できる場合、√2で到達できます。そしてより一般的に、n次元では、辺に沿ってしか移動できない場合、立方体の一つの角から反対側に行くにはn単位歩かなければなりませんが、対角線に行けば、√nで到達できます。
量子力学の世界観では、異なる観測可能な状態はすべて、ある状態空間内の垂直方向を表します。したがって、このフレームワークから見ると、古典的な決定論的な世界が見えるのは、これらの純粋な座標方向にのみアクセスできる場合です。
考えてみれば、計算をするときはいつでも、コンピュータはある意味で利用可能なさまざまな状態を通して歩いており、アルゴリズムの実行時間はすべて、すべての可能な状態の空間でどれだけのステップを歩かなければならないかを理解することに関するものです。
したがって、古典的な状態が純粋な座標方向のように見えるこの量子的世界観から、量子コンピューティングの主な違いは、作業できる追加の対角方向が多数あるということです。明確に言えば、アナロジーはあまり文字通りではなく、注意して受け取るべきです。
実行時間がこの特定の状態空間を通る距離のように見えるわけではありません。しかし、グローバーのアルゴリズム全体の状態ベクトルを追跡すると、それが行っているのは、初期条件から目標条件まで四分円の弧に沿ってゆっくりと歩いていることであり、純粋な座標方向にのみ移動することに限られている場合には完全に利用できない経路をたどっています。
そして、その効果は平方根サイズのショートカットを提供することです。そして、あなたを去らせる前の最後のポイントとして、定期的な視聴者は、このトピックをカバーする理由の一つが、πを計算できる衝突するブロックについての前回のビデオで約束されたアナロジーであることを知っているでしょう。
そのビデオでは、円の周りにバウンスする特定の二次元状態空間内の点も研究しており、実際、それが行ったバウンスのシリーズは基本的に私たちがここでグローバーのアルゴリズムで見たものと同じです。
ここでの話は、アダム・ブラウンという私の物理学者の友人がそのビデオの最初のバージョンを見たとき、彼は最近グローバーのアルゴリズムについて読んでいて、両方のプロセスが同一であることにすぐに気づいたということです。
私はこのビデオのために、そのアナロジーの文脈で量子コンピューティングとグローバーのアルゴリズムを説明するという計画がありましたが、それはただひどいアイデアであることが判明しました。その全体は、すでにグローバーのアルゴリズムを理解している場合にのみ本当に意味をなしました。
そこで、両方のトピックを個別に見たところで、アナロジーがどのように見えるかの大まかな概要を残します。これを、宿題のパズルとして考えてください。タスクは自分自身で接続を描くことです。
一種の回答キーとして、アダム・ブラウンによる非常に素晴らしい論文へのリンクを提供します。そこでは、そのアナロジーがどのように見えるかを正確に概説しています。量子コンピューティングの基礎についてもっと学びたい場合、数年前に私の非常に賢い友人であるアンディ・マツシャクとマイケル・ニールセンが、このトピックを学ぶための本当に素晴らしいリソースをまとめました。それは長期的にそれを確実に覚えるための非常にユニークなアプローチを提供しています。
基本的な量子力学について学ぶには、Looking Glass Universeチャンネルのミシナ・ヨガナサンが、そのトピックについて非常に初心者に優しいコースをまとめています。彼女は実際に何年も前にグローバーのアルゴリズムの仕組みを私に教えてくれた人であり、正直に言って、このビデオの内容の多くは彼女との多くの役立つ会話に負っています。
そして、最後の注意点として、このビデオを作る際に行った会話の一つは、このトピックについて非常に広く尊敬される研究者で、全く素晴らしい著者であるスコット・アーロンソンとのものでした。私はノート用にZoom通話を録音しましたが、あなたと共有したい小さな部分があります。
「私は科学小説を書く夢を持っていて、クライマックスのシーンになるだろうとわかっています。主人公たちはこの暗号鍵を見つけるためにロンとグローバーのアルゴリズムを実行することになるでしょう。世界の運命がそれを見つけられるかどうかにかかっているのです。悪者たちは彼らの基地を取り囲み、壁を叩き壊しています。
しかし、グローバーのアルゴリズムはまだ実行中で、もし測定すれば解決策を提供する確率は30%しかありません。だから質問は、今測定するか、もう1分実行させるかです。今測定して、それを得られなかったら、すべてを失います。
最初からやり直さなければなりません。これは古典的なアルゴリズムでは持てないプロットです。」
コメント