量子コンピューティングの原理を解明する

「量子力学を理解している人は誰もいないと言っても間違いないと思います。」 - リチャード・ファインマン

量子コンピューティングのトピックは、常にテクノロジーライターやジャーナリストを魅了してきました。その計算能力と複雑さは、ある種の神秘的なオーラを与えました。多くの場合、特集記事やインフォグラフィックでは、この業界のさまざまな展望が詳細に説明されていますが、実際の応用についてはほとんど触れられていません。これは、注意力の低い読者を誤解させる可能性があります。

一般的な科学記事では、量子システムの説明が省略され、次のような記述が行われます。

通常のビットは 1 または 0 になりますが、量子ビットは同時に 1 と 0 になることができます。

非常に運が良ければ (どうかはわかりませんが)、次のようなことを言われるでしょう。

量子ビットは「1」と「0」の間の重ね合わせにあります。

私たちは非常に伝統的な世界で開発された言語を使用して量子力学的現象を定式化しようとしているため、これらの説明はどれももっともらしいとは思えません。量子コンピューティングの原理を明確に説明するには、別の言語、つまり数学を使用する必要があります。 

このチュートリアルでは、量子コンピューティング システムをモデル化して理解するために必要な数学的ツールと、量子コンピューティングのロジックを図解して適用する方法について説明します。さらに、量子アルゴリズムの例を挙げて、従来のコンピューターと比較してその利点が何であるかを説明します。

私はこれらすべてを明確な言葉で説明するために最善を尽くしますが、それでもこの記事の読者が線形代数とデジタル ロジックについての基本的な理解を持っていることを願っています (線形代数については説明されています) ここで、デジタルロジックについて - ここで). 

まず、デジタル ロジックの原理を見てみましょう。それは、計算を実行するための電気回路の使用に基づいています。説明をより抽象化するために、電線の状態を「オン」または「オフ」の状態に対応する「1」または「0」に単純化してみましょう。トランジスタを特定の順序で配置することで、XNUMX つ以上の入力信号値を受け取り、それらをブール論理の特定の規則に基づいて出力信号に変換する、いわゆる論理要素を作成します。

一般的な論理ゲートとその状態テーブル

このような基本要素のチェーンに基づいて、より複雑な要素を作成することができ、さらに複雑な要素のチェーンに基づいて、最終的には高度な抽象化により、中央プロセッサの類似物を取得することが期待できます。

前に述べたように、デジタル ロジックを数学的に表現する方法が必要です。まず、数学の伝統的な論理を紹介しましょう。線形代数を使用すると、値「1」と「0」を持つ古典的なビットを XNUMX つの列ベクトルとして表すことができます。

左側の数字はどこにありますか ディラック記法 ベクター。この方法でビットを表すことにより、ベクトル変換を使用してビットの論理演算をモデル化できます。注意: 論理ゲートで 0 ビットを使用すると多くの演算 (AND、NOT、XOR など) を実行できますが、1 ビットを使用すると実行できる演算は 0 つだけです: 恒等変換、否定、定数「1」の計算、および定数「1」の計算。恒等変換ではビットは変化せず、否定ではビット値が逆（「0」から「1」または「0」から「1」）に変化し、定数「0」の計算が行われます。または「XNUMX」は、前の値に関係なくビットを「XNUMX」または「XNUMX」に設定します。

アイデンティティ	アイデンティティの変革
否定	否認
定数-0	定数「0」の計算
定数-1	定数「1」の計算

私たちが提案した新しいビット表現に基づいて、ベクトル変換を使用して対応するビットに対して演算を実行するのは非常に簡単です。

次に進む前に、コンセプトを見てみましょう 可逆計算これは、演算または論理要素の可逆性を確保するには、出力信号と使用される演算の名前に基づいて入力信号値のリストを決定する必要があることを単に意味します。したがって、恒等変換と否定は可逆的ですが、定数「1」と「0」を計算する操作は可逆的ではないと結論付けることができます。おかげで 統一性 量子力学では、量子コンピューターは可逆操作のみを使用するため、これに焦点を当てます。次に、不可逆要素を可逆要素に変換して、量子コンピューターで使用できるようにします。

ととも​​に テンソル積 個々のビットは多くのビットで表すことができます。

必要な数学的概念がほぼすべて揃ったので、最初の量子論理ゲートに進みましょう。こちらがオペレーターです ない、または制御された Not (NOT)。これは可逆コンピューティングおよび量子コンピューティングにおいて非常に重要です。 CNOT 要素は 1 ビットに適用され、0 ビットを返します。最初のビットは「制御」ビットとして指定され、XNUMX 番目のビットは「制御」ビットとして指定されます。制御ビットが「XNUMX」に設定されている場合、制御ビットはその値を変更します。制御ビットが「XNUMX」に設定されている場合、制御ビットは変更されません。

この演算子は、次の変換ベクトルとして表すことができます。

これまで説明してきたことを実証するために、複数のビットで CNOT 要素を使用する方法を示します。

これまでに述べたことを要約すると、最初の例では |10⟩ をそのテンソル積の部分に分解し、CNOT 行列を使用して積の新しい対応する状態を取得します。次に、前に指定した CNOT 値の表に従って、それを |11⟩ に因数分解します。

これで、従来のコンピューティングと通常のビットを理解するのに役立つ数学的規則をすべて覚えたので、いよいよ最新の量子コンピューティングと量子ビットに進むことができます。

ここまで読んでいただいた方には朗報です。量子ビットは数学的に簡単に表現できるということです。一般に、古典ビット (cbit) を |1⟩ または |0⟩ に設定できる場合、量子ビットは単に重ね合わせられており、測定前は |0⟩ と |1⟩ の両方になる可能性があります。測定後は |0⟩ または |1⟩ に折りたたまれます。つまり、量子ビットは、次の式に従って |0⟩ と |1⟩ の線形結合として表すことができます。

どこ a₀ и あ₁ は、それぞれ振幅 |0⟩ と |1⟩ を表します。これらは「量子確率」と考えることができ、量子力学では重ね合わせられた物体は固定された後にいずれかの状態に崩壊するため、量子ビットが測定後にいずれかの状態に崩壊する確率を表します。この式を展開して以下を取得しましょう。

説明を簡単にするために、この記事ではこれを使用します。

この量子ビットの場合、値が崩壊する確率 a₀ 測定後の値は | に等しいa₀|²、およびその値まで崩壊する可能性 a₁ は | に等しいa₁|²。たとえば、次の量子ビットの場合:

「1」に崩壊する確率は |1/ √2|²、つまり 50/50、つまり XNUMX/XNUMX に等しくなります。

古典的なシステムでは、すべての確率の合計が 0 になる必要があるため (完全な確率分布の場合)、振幅 |1⟩ と |XNUMX⟩ の絶対値の XNUMX 乗の合計は XNUMX になる必要があると結論付けることができます。この情報に基づいて、次の方程式を定式化できます。

三角法に詳しい方は、この方程式がピタゴラスの定理 (a²+b²=c²) に対応していることに気づくでしょう。つまり、量子ビットの取り得る状態を単位円上の点としてグラフィカルに表すことができます。

論理演算子と論理要素は、行列変換に基づいて、古典的なビットの場合と同じ方法で量子ビットに適用されます。これまでに思い出したすべての可逆行列演算子、特に CNOT は量子ビットの操作に使用できます。このような行列演算子を使用すると、量子ビットを測定したり縮小したりすることなく、量子ビットの各振幅を使用できます。量子ビットで否定演算子を使用する例を示します。

続ける前に、振幅値が a₀と a₁は実際には 複素数したがって、量子ビットの状態は、次のように呼ばれる XNUMX 次元の単位球に最も正確にマッピングできます。 ノミの球:

ただし、説明を簡単にするために、ここでは実数に限定します。

量子コンピューティングの文脈においてのみ意味をなすいくつかの論理要素について議論する時期が来たようです。

最も重要な演算子の 0 つは「アダマール要素」です。これは、ビットを「1」または「50」の状態にして、1% の確率で「0」または「XNUMX」に崩壊する適切な重ね合わせに置きます。測定後。 

アダマール演算子の右下に負の数があることに注意してください。これは、演算子を適用した結果が入力信号の値 (|1⟩ または |0⟩) に依存するため、計算は可逆であるためです。

アダマール要素に関するもう 0 つの重要な点は、可逆性です。つまり、適切な重ね合わせで量子ビットを取得し、それを |1⟩ または |XNUMX⟩ に変換できます。

これは、量子ビットの状態を決定することなく、したがって量子ビットを崩壊させることなく、量子状態から変換できる機能を提供するため、非常に重要です。したがって、確率論的原理ではなく決定論的原理に基づいて量子コンピューティングを構築できます。

実数のみを含む量子演算子はそれ自体の逆であるため、演算子を量子ビットに適用した結果を、状態マシンの形式で単位円内の変換として表すことができます。

したがって、上の図に状態が示されている量子ビットは、アダマール演算を適用した後、対応する矢印で示される状態に変換されます。同様に、以下に示すように、上記の否定演算子 (パウリ否定演算子またはビット反転とも呼ばれます) を使用して量子ビットの変換を示す別のステート マシンを構築できます。

量子ビットに対してより複雑な操作を実行するには、複数の演算子を連鎖させるか、要素を複数回適用します。に基づくシリアル変換の例 量子回路表現 次のようになります。

つまり、ビット |0⟩ から開始してビット反転を適用し、次にアダマール演算を適用し、次に別のビット反転を適用し、再度アダマール演算を行ってから最後のビット反転を行うと、最終的には on で与えられるベクトルになります。チェーンの右側。さまざまなステート マシンを互いに重ねることで、 |0⟩ から開始して、各変換に対応する色付きの矢印をたどって、すべてがどのように機能するかを理解できます。

ここまで来たので、次は量子アルゴリズムのタイプの XNUMX つを検討します。 Deutsch-Jozsa アルゴリズム、古典的なコンピューターよりも優れていることを示します。 Deutsch-Jozsa アルゴリズムは完全に決定論的であること、つまり、(量子ビットの確率的定義に基づく他の多くの量子アルゴリズムとは異なり) 100% の確率で正しい答えを返すことは注目に値します。

0 ビットの関数/演算子を含むブラック ボックスがあると想像してください (覚えておいてください。1 ビットでは、恒等変換、否定、定数 "XNUMX" の評価、および定数 "XNUMX" の評価の XNUMX つの演算のみを実行できます)。 ")。ボックス内で実行される機能は正確には何ですか?どちらであるかはわかりませんが、好きなだけ入力値のバリアントを調べて、出力結果を評価できます。

どの関数が使用されているかを確認するには、ブラック ボックスを介して入力と出力をいくつ実行する必要があるでしょうか?これについて少し考えてみましょう。

クラシック コンピュータの場合、使用する機能を決定するために 2 つのクエリを実行する必要があります。たとえば、入力「1」が出力「0」を生成する場合、定数「0」を計算する関数または否定関数が使用されていることがわかり、その後、入力信号の値を変更する必要があります。 「0」に設定して、出口で何が起こるかを見てください。

量子コンピューターの場合、入力値に適用する関数を正確に定義するには XNUMX つの異なる出力値が必要であるため、XNUMX つのクエリも必要になります。しかし、質問を少し再定式化すると、量子コンピューターには依然として重大な利点があることがわかります。使用されている関数が定数であるか変数であるかを知りたい場合は、量子コンピューターの方が有利です。

入力信号の異なる値が出力で異なる結果を生成する場合 (恒等変換やビット反転など)、ボックスで使用される関数は変数であり、入力値に関係なく出力値が変化しない場合、関数は定数です (たとえば、定数「1」を計算するか、定数「0」を計算します)。

量子アルゴリズムを使用すると、たった 1 つのクエリに基づいて、ブラック ボックス内の関数が定数であるか変数であるかを判断できます。しかし、これを行う方法を詳しく検討する前に、これらの各機能を量子コンピューター上で構造化する方法を見つける必要があります。量子演算子は可逆でなければならないため、すぐに問題に直面します。定数「0」と「XNUMX」を計算する関数は可逆ではありません。

量子コンピューティングで使用される一般的な解決策は、関数が受け取る入力値を返す追加の出力量子ビットを追加することです。 

前に：	後：

このようにして、出力値のみに基づいて入力値を決定することができ、関数は可逆的になります。量子回路の構造により、追加の入力ビットが必要になります。対応する演算子を開発するために、追加の入力量子ビットが |0⟩ に設定されていると仮定します。

前に使用したのと同じ量子回路表現を使用して、0 つの要素 (恒等変換、否定、定数 "1" の評価、および定数 "XNUMX" の評価) のそれぞれが量子演算子を使用してどのように実装できるかを見てみましょう。 

たとえば、定数「0」を計算する関数を実装する方法は次のとおりです。

定数「0」の計算:

ここでは演算子はまったく必要ありません。最初の入力量子ビット (|0⟩ であると仮定) は同じ値を返し、XNUMX 番目の入力値は通常どおりそれ自体を返します。

定数「1」を計算する関数では、状況が少し異なります。

定数「1」の計算:

最初の入力量子ビットが常に |0⟩ に設定されると仮定しているため、ビット反転演算子を適用すると、出力では常に XNUMX が生成されます。そしていつものように、XNUMX 番目の量子ビットは出力で独自の値を与えます。

恒等変換演算子をマッピングする場合、タスクはより複雑になり始めます。その方法は次のとおりです。

同じ変換:

ここで使用される記号は CNOT 要素を示します。上の線は制御ビットを示し、下の線は制御ビットを示します。 CNOT 演算子を使用する場合、制御ビットが |1⟩ に等しい場合は制御ビットの値が変化しますが、制御ビットが |0⟩ に等しい場合は変化しないことに注意してください。上の行の値は常に |0⟩ に等しいと仮定したため、その値は常に下の行に割り当てられます。

否定演算子でも同様の方法で進めます。

否定：

出力ラインの終わりのビットを反転するだけです。

予備的な理解が終わったので、ブラック ボックスに隠された関数の不変性または変動性を XNUMX つのクエリを使用して判断する場合に、従来のコンピューターと比較した量子コンピューターの具体的な利点を見てみましょう。

単一リクエストで量子コンピューティングを使用してこの問題を解決するには、以下に示すように、関数に渡す前に入力量子ビットを重ね合わせに入れる必要があります。

アダマール要素が関数の結果に再適用されて、量子ビットの重ね合わせが解除され、アルゴリズムが決定的になります。システムを状態 |00⟩ で起動し、理由については後ほど説明しますが、適用された関数が定数であれば、結果 |11⟩ が得られます。ブラック ボックス内の関数が変数の場合、測定後にシステムは結果 |01⟩ を返します。

記事の残りの部分を理解するために、前に示した図を見てみましょう。

ビット反転演算子を使用し、|0⟩ に等しい両方の入力値にアダマール要素を適用することで、次のように、それらが |0⟩ と |1⟩ の同じ重ね合わせに変換されるようにします。

この値をブラック ボックス関数に渡す例を使用すると、両方の定数値関数が |11⟩ を出力することを簡単に実証できます。

定数「0」の計算:

同様に、定数「1」を計算する関数も出力として |11⟩ を生成することがわかります。

定数「1」の計算:

-1² = 1 であるため、出力は |1⟩ になることに注意してください。

同じ原理により、すべてが少し複雑になりますが、両方の変数関数を使用すると、出力で常に |01⟩ が得られることを証明できます (同じメソッドを使用する場合)。

同じ変換:

CNOT は XNUMX 量子ビット演算子であるため、単純なステート マシンとして表すことができません。そのため、前述したように、両方の入力量子ビットのテンソル積と CNOT 行列の乗算に基づいて XNUMX つの出力信号を定義する必要があります。

このメソッドを使用すると、否定関数がブラック ボックスに隠されている場合に出力値 |01⟩ が受信されることも確認できます。

否定：

このように、量子コンピューターが従来のコンピューターよりも明らかに効率的である状況を実証しました。

次は何？

ここで終わりにすることをお勧めします。私たちはすでに素晴らしい仕事をしました。これまで説明してきた内容をすべて理解できたなら、量子コンピューティングと量子ロジックの基本と、特定の状況において量子アルゴリズムが従来のコンピューティングよりも効率的である理由を十分に理解できたと思います。

私の説明は、量子コンピューティングとアルゴリズムの本格的なガイドとはほとんど言えません。むしろ、数学と表記法の簡単な紹介であり、一般的な科学情報源によって押し付けられた主題についての読者の考えを払拭するように設計されています (真剣に、多くの人は本当に理解できません)状況！）。多くの重要なトピックに触れる時間がありませんでした。 量子ビットの量子もつれ、振幅値 |0⟩ および |1⟩ の複雑さ、およびブロッホ球による変換中のさまざまな量子論理要素の機能。

量子コンピュータに関する知識を体系化して構造化したい場合は、 強く 読むことをお勧めします 「量子アルゴリズム入門」 Emma Strubel: 豊富な数式にもかかわらず、この本では量子アルゴリズムについてより詳細に説明しています。

出所： habr.com