スワップテスト

スワップテストは量子計算において2つの量子状態がどれだけ異なるかを調べるために使用される手順であり、最初にバレンコらの研究で登場しました。^[1] その後、ハリー・バーマン、リチャード・クリーブ、ジョン・ワトラス、ロナルド・デ・ウルフによって再発見されました。^[2]これは量子機械学習でよく見られ、量子コンピュータの実装の概念実証に使用される回路です。^{[3] [4]}

形式的には、スワップテストは2つの入力状態とを受け取り、確率1のベルヌーイ乱数変数を出力します（ここでの式は括弧記法を使用します）。これにより、たとえば、スワップテストの実行の平均を取ることで、2つの状態間の内積の2乗を加法誤差で推定できます。 ^[5]これには入力状態のコピーが必要です。内積の2乗は、2つの状態間の「重なり」を大まかに測定するもので、量子状態のクラスタリングを含む線形代数アプリケーションで使用できます。^[6]${\displaystyle |\phi \rangle }$${\displaystyle |\psi \rangle }$${\displaystyle \textstyle {\frac {1}{2}}-{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}}$${\displaystyle {|\langle \psi |\phi \rangle |}^{2}}$${\displaystyle \epsilon }$${\displaystyle O(\textstyle {\frac {1}{\varepsilon ^{2}}})}$${\displaystyle O(\textstyle {\frac {1}{\varepsilon ^{2}}})}$

2つの状態、およびを考えます。プロトコルの開始時のシステムの状態は です。アダマールゲートの後、システムの状態は です。制御されたSWAPゲートは状態を に変換します。2番目のアダマールゲートの結果は次のようになります。 ${\displaystyle |\phi \rangle }$${\displaystyle |\psi \rangle }$${\displaystyle |0,\phi ,\psi \rangle }$${\displaystyle {\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle )}$${\displaystyle {\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\psi ,\phi \rangle )}$$${\displaystyle {\frac {1}{2}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle +|0,\psi ,\phi \rangle -|1,\psi ,\phi \rangle )={\frac {1}{2}}|0\rangle (|\phi ,\psi \rangle +|\psi ,\phi \rangle )+{\frac {1}{2}}|1\rangle (|\phi ,\psi \rangle -|\psi ,\phi \rangle )}$$

最初の量子ビットの測定ゲートは、次の確率で0になることを保証します。

$${\displaystyle P({\text{First qubit}}=0)={\frac {1}{2}}{\Big (}\langle \phi |\langle \psi |+\langle \psi |\langle \phi |{\Big )}{\frac {1}{2}}{\Big (}|\phi \rangle |\psi \rangle +|\psi \rangle |\phi \rangle {\Big )}={\frac {1}{2}}+{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}}$$

測定されたとき。とが直交する場合、0が測定される確率はです。状態が等しい場合、0が測定される確率は1です。^[2]${\displaystyle \psi }$${\displaystyle \phi }$ ${\displaystyle ({|\langle \psi |\phi \rangle |}^{2}=0)}$${\displaystyle {\frac {1}{2}}}$${\displaystyle ({|\langle \psi |\phi \rangle |}^{2}=1)}$

一般に、のコピーと のコピーを使用したスワップ テストの試行では、ゼロとなる測定値の割合は であるため、 を取ることで、この値の任意の精度を得ることができます。 ${\displaystyle P}$${\displaystyle P}$${\displaystyle |\phi \rangle }$${\displaystyle P}$${\displaystyle |\psi \rangle }$${\displaystyle 1-\textstyle {\frac {1}{P}}\textstyle \sum _{i=1}^{P}M_{i}}$${\displaystyle P\rightarrow \infty }$

以下は、およびのP 個のコピーを使用しての値を推定する疑似コードです。 ${\displaystyle |\langle \psi |\phi \rangle |^{2}}$${\displaystyle |\psi \rangle }$${\displaystyle |\phi \rangle }$

入力 Pはn個の量子ビットの量子状態をそれぞれコピーし、出力は推定値${\displaystyle |\psi \rangle }$${\displaystyle |\phi \rangle }$
${\displaystyle |\langle \psi |\phi \rangle |^{2}}$

 jは1からPまでの範囲です。
    補助量子ビットAを状態 で初期化し、補助量子ビットAに1からnまでのiに対して
    アダマールゲートを適用する。${\displaystyle |0\rangle }$
     
        CSWAPをおよび（およびのj番目のコピーのi番目の量子ビット）に適用し、Aを制御量子ビットとする${\displaystyle \psi _{i}}$${\displaystyle \phi _{i}}$${\displaystyle |\psi \rangle }$${\displaystyle |\phi \rangle }$
    補助量子ビットAにアダマールゲートを適用し、基底のAを
    測定し、測定値M jを0または1として記録し
、計算します。
推定値として返します。${\displaystyle Z}$${\displaystyle s=1-\textstyle {\frac {2}{P}}\textstyle \sum _{i=1}^{P}M_{i}}$ ${\displaystyle s}$${\displaystyle |\langle \psi |\phi \rangle |^{2}}$