サイモンの問題

以下の関数は、必要な特性を満たす関数の例です。${\displaystyle n=3}$:

この場合、${\displaystyle s=110}$（つまり、ソリューション）。すべての出力${\displaystyle f}$は 2 回発生し、任意の 1 つの出力に対応する 2 つの入力文字列のビットごとの XOR は、${\displaystyle s=110}$。

例えば、入力文字列${\displaystyle 010}$そして${\displaystyle 100}$両方ともマッピングされています（${\displaystyle f}$同じ出力文字列に${\displaystyle 000}$つまり、${\displaystyle {\displaystyle f(010)=000}}$そして${\displaystyle {\displaystyle f(100)=000}}$010と100にXORを適用すると110が得られます。${\displaystyle {\displaystyle 010\oplus 100=110=s}.}$

${\displaystyle s=110}$入力文字列001と111を使用して検証することもできます。これらは両方とも（fによって）同じ出力文字列010にマッピングされます。001と111にXORを適用すると110が得られます。つまり、${\displaystyle 001\oplus 111=110=s}$これは同じ解決策を与える。${\displaystyle s=110}$以前と同様。

この例では、関数fは確かに 2 対 1 関数であり、${\displaystyle {\displaystyle s\neq 0^{n}}}$。

直感的に言えば、これは「古典的な」方法では解決が難しい問題です。たとえランダム性を用い、小さなエラー確率を受け入れたとしてもです。難しさの背景にある直感は比較的単純です。古典的な方法で問題を解決しようとすると、2つの異なる入力を見つける必要があります。${\displaystyle x}$そして${\displaystyle y}$そのために${\displaystyle f(x)=f(y)}$関数には必ずしも構造があるわけではない。${\displaystyle f}$それは、そのような入力を 2 つ見つけるのに役立ちます。より具体的には、次のようなことを発見できます。${\displaystyle f}$（あるいはそれが何をするのか）は、2つの異なる入力に対して同じ出力が得られる場合にのみ行われます。いずれにせよ、推測する必要があります。${\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}$異なる入力は、ペアを見つける可能性が高い前に、${\displaystyle f}$誕生日問題と同様に、同じ出力が得られます。古典的には、 100%の確実性でsを見つけるには、チェックする必要があります。$\displaystyle \Theta (\sqrt 2^n)$入力値に対して、サイモンの問題は、この古典的な方法よりも少ないクエリを使用してsを見つけようとするものです。

量子回路（図参照）は、サイモンのアルゴリズムの量子部分を実装したものです。このアルゴリズムの量子サブルーチンは、アダマール変換を利用します。$${\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }$$どこ${\displaystyle k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}}$、 どこ${\displaystyle \oplus }$XORを表します。

まず、アルゴリズムは、初期化された 2 つのレジスタから始まります。${\displaystyle |0\rangle ^{\otimes n}|0\rangle ^{\otimes n}}$次に、最初のレジスタにアダマール変換を適用すると、次の状態が得られます。

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.}$

オラクルに問い合わせる${\displaystyle U_{f}}$州を取得する

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle }$。

最初のレジスタに別のハダマール変換を適用します。これにより、次の状態が生成されます。

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].}$

最後に、最初のレジスタを測定します（2番目のレジスタを最初のレジスタより先に測定してもアルゴリズムは機能しますが、これは不要です）。状態を測定する確率${\displaystyle |j\rangle }$は$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}}$$これは、このベクトルの大きさを取って二乗すると、第 2 レジスタのすべての可能な測定値のすべての確率の合計になるという事実によるもので、第 1 レジスタは${\displaystyle |j\rangle }$測定には2つのケースがあります。

1. ${\displaystyle s=0^{n}}$そして${\displaystyle f}$1対1です。
2. ${\displaystyle s\neq 0^{n}}$そして${\displaystyle f}$2対1です。

最初のケースでは、$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}}$$この場合、${\displaystyle f}$は1対1であり、範囲は${\displaystyle f}$は${\displaystyle \{0,1\}^{n}}$つまり、総和はすべての基底ベクトルについて行われるということです。2番目のケースでは、2つの文字列が存在することに注意してください。${\displaystyle x_{1}}$そして${\displaystyle x_{2}}$、したがって${\displaystyle f(x_{1})=f(x_{2})=z}$、 どこ${\displaystyle z\in \mathrm {range} (f)}$。 したがって、$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}}$$さらに、${\displaystyle x_{1}\oplus x_{2}=s}$、${\displaystyle x_{2}=x_{1}\oplus s}$、 など$${\displaystyle {\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}}$$この式は簡単に評価できます。測定しているのは${\displaystyle j}$。 いつ${\displaystyle j\cdot s=1}$すると、この式は次のように評価されます。${\displaystyle 0}$、そして${\displaystyle j\cdot s=0}$すると、この式は次のようになります。${\displaystyle 2^{-n+1}}$。

したがって、どちらの場合も${\displaystyle s=0^{n}}$そして、${\displaystyle s\neq 0^{n}}$我々の測定値${\displaystyle j}$満たす${\displaystyle j\cdot s=0}$。

線形独立なビット列のリストが得られるまで、アルゴリズムの量子部分を実行します。${\displaystyle y_{1},\ldots ,y_{n-1}}$、そしてそれぞれ${\displaystyle y_{k}}$満たす${\displaystyle y_{k}\cdot s=0}$したがって、この連立方程式を古典的な方法で効率的に解くことで、${\displaystyle s}$。

確率${\displaystyle y_{1},y_{2},\dots ,y_{n-1}}$線形独立であるのは少なくとも$${\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots }$$連立方程式を解いて解を導き出すと${\displaystyle s'}$そうすればテストできます${\displaystyle f(0^{n})=f(s')}$これが本当なら、私たちは次のことがわかる${\displaystyle s'=s}$、 以来${\displaystyle f(0^{n})=f(0^{n}\oplus s)=f(s)}$もし${\displaystyle f(0^{n})\neq f(s')}$つまり、${\displaystyle s=0^{n}}$、 そして${\displaystyle f(0^{n})\neq f(s')}$以来${\displaystyle f}$1対1です。

サイモンのアルゴリズムを定数回繰り返すことで、時間計算量は変わらないまま、成功確率を任意に高めることができる。

アルゴリズムの最も単純な例を考えてみましょう。${\displaystyle n=1}$この場合、入力状態をアダマールゲートとオラクルを通して進化させると、（再正規化を除いて）次の状態が得られます。

${\displaystyle |0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .}$

もし${\displaystyle s=1}$つまり、${\displaystyle f(0)=f(1)}$すると、2 番目のレジスターを測定すると、常に次の結果が得られます。${\displaystyle |f(0)\rangle }$、そして常に最初のレジスタが（再正規化を除いて）次の状態に縮退する結果となる。

${\displaystyle |0\rangle +|1\rangle .}$

したがって、アダマールを適用して最初のレジスターを測定すると、常に次の結果が得られます。${\displaystyle |0\rangle }$一方、${\displaystyle f}$1対1、つまり、${\displaystyle s=0}$すると、2 番目のアダマールの後の最初のレジスターを測定すると、両方の結果が得られる可能性がある。${\displaystyle |0\rangle }$そして${\displaystyle |1\rangle }$同じ確率で。

回復する${\displaystyle s}$測定結果から、常に測定していたかどうかを調べる${\displaystyle |0\rangle }$その場合${\displaystyle s=1}$あるいは両方を測定した${\displaystyle |0\rangle }$そして${\displaystyle |1\rangle }$等しい確率で、その場合、我々は次のように推論する。${\displaystyle s=0}$この計画は、以下の場合には失敗します。${\displaystyle s=0}$しかし、それでも私たちは常に結果を見つけました${\displaystyle |0\rangle }$しかし、この事象の確率は${\displaystyle 2^{-N}}$と${\displaystyle N}$実施された測定の回数であり、統計量を増やすことで指数関数的に小さくすることができる。

次に、${\displaystyle n=2}$アルゴリズムの初期部分では、（正規化を除いて）次の状態が得られます。$${\displaystyle |00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .}$$もし${\displaystyle s=(00)}$、 意味${\displaystyle f}$単射である場合、${\displaystyle |f(x)\rangle }$2 番目のレジスタでは、常に最初のレジスタが縮退します。${\displaystyle |x\rangle }$すべての${\displaystyle x\in \{0,1\}^{2}}$言い換えれば、アダマールゲートを適用し、最初のレジスターを測定すると、4 つの結果が得られます。${\displaystyle 00,01,10,11}$したがって、それらは等しい確率で発見される。

一方、${\displaystyle s\neq (00)}$、 例えば、${\displaystyle s=(01)}$測定${\displaystyle |f(00)\rangle }$2 番目のレジスタでは、最初のレジスタが状態に縮約されます${\displaystyle |00\rangle +|10\rangle }$より一般的には、測定する${\displaystyle |f(xy)\rangle }$与える${\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}$最初のレジスタで。ハダマールゲートを適用し、最初のレジスタで測定すると、次の結果が得られます。${\displaystyle 00}$そして${\displaystyle 10}$等しい確率で。

他のケースにも同様の推論が適用されます。${\displaystyle s=(10)}$すると、考えられる結果は次のとおりです。${\displaystyle 00}$そして${\displaystyle 01}$、もし${\displaystyle s=(11)}$考えられる結果は${\displaystyle 00}$そして${\displaystyle 11}$と互換性があり、${\displaystyle j\cdot s=0}$一般的な場合で議論された規則。

回復するために${\displaystyle s}$したがって、我々はこれら4つのケースを区別するだけでよく、ある結果の確率分布を別の結果の確率分布と誤認する確率が十分に小さいことを保証するために十分な統計データを収集すればよい。