古典的な計算：AND、OR、NOT
量子コンピューティングに対処するには、古典的なものの知識を更新する価値があります。 ここで、処理される情報の単位は少しです。 各ビットは、0または1の2つの可能な状態のいずれか1つにしかなれない
情報の処理と変換には、ブール代数からのビット演算が使用されます。 主な操作は、シングルビットのNOTと2ビットのANDおよびORです。 ビット演算は、真理値表を介して説明されます。 入力引数と取得値の対応を示します。
古典的な計算アルゴリズムは、一連のビット操作です。 機能要素の図（SFE）の形式でグラフィカルに再現するのが最も便利で、各操作には独自の指定があります。 次に、2ビットの等価性をチェックするSFEの例を示します。
量子コンピューティング。 物理的基礎
それでは、新しいトピックに移りましょう。 量子コンピューティングは、量子物理学のプロセスに基づいた古典的なアルゴリズムの代替です。 他の粒子と相互作用することなく（つまり、測定の瞬間まで）、電子は原子の軌道に明確な座標を持たず、同時に軌道のすべての点にあると言います。 電子が位置する領域は、電子雲と呼ばれます。 2つのスリットを使用したよく知られた実験では、1つの電子が両方のスリットを同時に通過しますが、同時に干渉します。 この不確実性は測定中にのみ崩壊し、電子の座標は明確になります。
量子コンピューティングに固有の測定の確率的性質は、多くのアルゴリズムの基礎になっています。たとえば、非構造化データベースでの検索です。 このタイプのアルゴリズムは、正しい結果の振幅を徐々に増加させ、最大の確率で出力でそれを取得できるようにします。
キュービット
量子コンピューティングでは、量子オブジェクトの物理的特性は、いわゆるキュービット（qビット）で実装されます。 古典的なビットは、0または1の1つの状態のみになります。測定の前に、キュービットは同時に両方の状態になります。したがって、式a |0⟩+ b |1⟩で表すのが習慣です。 | 2 + | B | 2 = 1。 キュービットの測定は、その状態を基本的なものの1つに即座に「崩壊」させます-0または1。この場合、「クラウド」はある点まで崩壊し、初期状態は破壊され、それに関するすべての情報は回復不能に失われます。
このプロパティのアプリケーションの1つは、真の乱数ジェネレーター
量子および古典的な計算。 最初のラウンド
基本から始めましょう。 長さNのベクトルによってバイナリ形式で表される計算用の入力データのセットがあります。
従来の計算では、2 n個のデータバリアントの1つのみがコンピューターメモリにロードされ、このバリアントの関数値が計算されます。 その結果、2 nの可能なデータセットの1つだけが同時に処理されます。
量子コンピューターのメモリでは、ソースデータの2 n個のすべての組み合わせが同時に表示されます。 変換は、これらすべての組み合わせに一度に適用されます。 その結果、1回の操作で、データセットの2 n個の可能なすべてのバリアントの関数を計算します（最終的な測定では1つの解しか得られませんが、それについては後で詳しく説明します）。
クラシカルコンピューティングと量子コンピューティングの両方で、論理変換ゲートが使用されます。 古典的な計算では、入力値と出力値は異なるビットに格納されます。つまり、ゲートでは入力の数が出力の数と異なる場合があります。
実際の問題を考慮してください。 2ビットが同等かどうかを判断する必要があります。
出力で古典的な計算で1つを取得する場合、それらは同等です。
次に、量子コンピューティングを使用してこの問題を想像してください。 それらでは、すべての変換ゲートに入力と同じ数の出力があります。 これは、変換の結果が新しい値ではなく、現在の状態の変化であるという事実によるものです。
この例では、1番目と2番目のキュービットの値を比較します。 結果はゼロ量子ビット-量子ビットフラグになります。 このアルゴリズムは、基本状態（0または1）にのみ適用できます。これが量子変換の順序です。
- 「Not」ゲートを使用してキュービットフラグを処理し、1に公開します。
- 2キュービットゲート「Controlled Not」を2回使用します。 このゲートは、変換に関与する2番目のキュービットが状態1にある場合にのみ、フラグキュービットの値を反対に変更します。
- ゼロキュービットを測定します。 結果として1を取得した場合、最初のキュービットと2番目のキュービットは両方とも状態1（キュービットフラグの値が2回変更された）または状態0（キュービットフラグは状態1のままです）にあります。 それ以外の場合、キュービットは異なる状態にあります。
次のレベル。 パウリの量子ワンQゲート
もっと深刻な問題で、古典的な計算と量子計算を比較してみましょう。 そのためには、さらに理論的な知識が必要です。
量子コンピューティングでは、処理された情報は量子ビット、いわゆるキュービットでエンコードされます。 最も単純な場合、古典的なビットのようなキュービットは、次の2つの基本状態のいずれかになります。|0⟩（ベクトル1の短い表記|0⟩+ 0 |1⟩）および|1⟩（ベクトル0 |0⟩+ 1の場合） |1⟩）。 量子レジスタは、キュービットベクトルのテンソル積です。 最も単純なケースでは、各キュービットが基底状態の1つにある場合、量子レジスターは古典的なレジスターと同等です。 状態の2つのキュービットのレジスタ| 0>は、次の形式で書き込むことができます。
（1 |0⟩+ 0 |1⟩）*（1 |0⟩+ 0 |1⟩）= 1 |00⟩+ 0 |01⟩+ 0 |10⟩+ 0 |11⟩= |00⟩。
量子アルゴリズムで情報を処理および変換するには、いわゆる量子ゲート（ゲート）が使用されます。 それらはマトリックスの形で提示されます。 ゲートを適用した結果を得るには、キュービットを特徴付けるベクトルにゲートの行列を掛ける必要があります。 ベクトルの最初の座標は|0⟩の前の因子であり、2番目の座標は|1⟩の前の因子です。 主な1キュービットゲートのマトリックスは次のようになります。
Notゲートの使用例を次に示します。
X * |0⟩= X *（1 |0⟩+ 0 |1⟩）= 0 |0⟩+ 1 |1⟩= |1⟩
基本状態の前の因子は振幅と呼ばれ、複素数です。 複素数のモジュラスは、実数部と虚数部の平方和の根に等しくなります。 基本状態の前の振幅係数の2乗は、量子ビットを測定するときにこの基本状態を得る確率に等しいため、振幅係数の2乗の合計は常に1になります。のベクトルは常に1に等しくなければなりません（すべての結果の確率の合計は常に1に等しくなります）、変換はベクトルのノルムを保持する必要があります。 つまり、変換はユニタリでなければならず、対応するマトリックスはユニタリでなければなりません。 ユニタリ変換は可逆的であり、UU † = Iであることを思い出してください。
量子ビットを使用したより視覚的な作業のために、それらはブロッホ球上のベクトルで表されます。 この解釈では、単一キュービットゲートは、軸の1つを中心としたキュービットベクトルの回転を表します。 たとえば、ゲートNot（X）は、X軸に対してPiだけキュービットベクトルを回転させるため、厳密に上向きのベクトルで表される状態| 0>は、厳密に下向きの状態| 1>になります。 ブロッホ球上のキュービットの状態は、式cos（θ/ 2）|0⟩+ e iϕ sin（θ/ 2）|1⟩によって決定されます。
量子2量子ビットゲート
アルゴリズムを構築するには、1キュービットゲートだけでは不十分です。 特定の条件に応じて変換を実行するゲートが必要です。 主なツールは、CNOT 2キュービットゲートです。 このゲートは2つのキュービットに適用され、最初のキュービットが|1⟩状態にある場合にのみ2つ目のキュービットを反転します。 CNOTゲートマトリックスは次のようになります。
そして、これがアプリケーションの例です：
CNOT * |10⟩= CNOT *（0 |00⟩+ 0 |01⟩+ 1 |10⟩+ 0 |11⟩）= 0 |00⟩+ 0 |01⟩+ 1 |11⟩+ 0 |10⟩= |11⟩
CNOTゲートを使用することは、結果を2番目のキュービットに書き込む古典的なXOR演算を実行することと同等です。 実際、XORおよびCNOT演算子の真理値表を見ると、対応がわかります。
| Xor
| CNOT
| |||
| 0
| 0
| 0
| 00
| 00
|
| 0
| 1
| 1
| 01
| 01
|
| 1
| 0
| 1
| 10
| 11
|
| 1
| 1
| 0
| 11
| 10
|
CNOTゲートには興味深い特性があります-その適用後、キュービットは初期状態に応じてもつれたり、もつれが解かれたりします。 これについては、次の記事の量子並列性のセクションで説明します。
アルゴリズム構築-古典的および量子実装
量子ゲートの完全な武器を持つことで、量子アルゴリズムの開発を開始できます。 グラフィカル表現では、キュービットは直線で表されます-ゲートが重ねられた「ストリング」。 パウリのシングルクォートゲートは通常の正方形で示され、その内部に回転軸が表されています。 CNOTゲートはもう少し複雑に見えます。
CNOT Gateの適用例：
アルゴリズムで最も重要なアクションの1つは、結果を測定することです。 通常、測定値は、矢印の付いたアークスケールと、測定が行われる軸についての指定によって示されます。
それでは、引数に3を追加する古典的な量子アルゴリズムを構築してみましょう。
列による通常の数値の合計は、各桁での2つのアクションの実行を意味します。桁自体の合計と、そのような転送があった場合の前の操作からの転送の結果の合計です。
数値のバイナリ表現では、合計操作は同じアクションで構成されます。 Pythonコードは次のとおりです。
arg = [1,1] # result = [0,0,0] # carry1 = arg[1] & 0x1 # 0b11, , = 1 result[2] = arg[1] ^ 0x1 # carry2 = carry1 | arg[0] # 0b11, , = 1 result[1] = arg[0] ^ 0x1 # result[1] ^= carry1 # result[0] ^= carry2 # print(result)
次に、量子コンピューター用の同様のプログラムを開発してみましょう。
このスキームでは、最初の2つのキュービットが引数であり、次の2つがハイフンであり、残りの3つが結果です。 これがアルゴリズムの仕組みです。
- 障壁への最初のステップ、古典的な場合と同じ状態-0b11に引数を置きます。
- CNOT演算子を使用して、最初の転送の値を計算します。arg＆1演算の結果は、argが1の場合にのみ1になります。この場合、2番目のキュービットを反転します。
- 次の2つのゲートは最下位ビットの追加を実装します。量子ビット4を状態|1⟩に入れ、XOR結果を書き込みます。
- 大きな長方形は、CNOTゲートの拡張であるCCNOTゲートを示します。 このゲートでは、最初の2つが状態| 1の場合にのみ、2つの制御キュービットと3つ目のビットが反転します。 2つのCNOTゲートと1つのCCNOTの組み合わせにより、従来の操作carry2 = carry1 | arg [0]。 最初の2つのゲートは、キャリーの1つが1の場合にキャリーを1に設定し、CCNOTゲートは両方とも1に等しい場合を処理します。
- シニアキュービットを追加し、キュービットを転送します。
中間結論
両方の例を実行すると、同じ結果が得られます。 量子コンピューターでは、追加のコンパイルを量子アセンブラーコードに実行し、実行のためにクラウドに送信する必要があるため、これには時間がかかります。 量子演算の使用は、基本操作（ゲート）の実行速度が従来のモデルよりも何倍も遅い場合に意味があります。
専門家の測定によると、1つのゲートの実行には約1ナノ秒かかります。 したがって、量子コンピューターのアルゴリズムは、古典的なアルゴリズムをコピーするのではなく、量子力学の固有の特性を最大限に使用する必要があります。 次の記事では、このような主要な特性の1つである量子並列性を分析し、一般的な量子最適化について説明します。 次に、量子コンピューティングに最適な球体を決定し、その用途について説明します。
Sberbank-TechnologiesのSEC開発部門のITシステム開発部門のシニアマネージャーであるDmitry Sapaevと、Sberbank Technology Innovation CenterのプロジェクトディレクターであるDmitry Bulychkovの資料に基づきます。
UPD ： 記事の第2部を公開しました。ここでは、量子コンピューティングをさらに深く掘り下げ、それらの実際の応用について説明します。