バーンスタイン・ヴァジラニアルゴリズム

Bernstein –Vaziraniアルゴリズムは、 Bernstein–Vazirani問題を解く量子アルゴリズムで、1997年にEthan BernsteinとUmesh Vaziraniによって発明されました。 ^{[1]これは、} Deutsch–Jozsaアルゴリズムの制限バージョンであり 、2つの異なる関数クラスを区別する代わりに、関数にエンコードされた文字列を学習しようとします。^[2] Bernstein–Vaziraniアルゴリズムは、複雑性クラス BQPとBPPの間の神託の分離を証明するために設計されました。^[1]

が と秘密の文字列との2を法とするドット積になることが保証される関数を実装するオラクルがある場合、 を見つけます。 ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle s\in \{0,1\}^{n}}$ ${\displaystyle f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}}$${\displaystyle s}$

古典的には、秘密の文字列を見つける最も効率的な方法は、すべての入力値を使って関数を回評価することです。^[2]${\displaystyle n}$${\displaystyle x=2^{i}}$${\displaystyle i\in \{0,1,...,n-1\}}$

${\displaystyle {\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{aligned}}}$

を見つけるために関数のクエリを少なくとも必要とする古典的なソリューションとは対照的に、量子コンピューティングでは1つのクエリのみが必要です。量子アルゴリズムは次のとおりです。^[2]${\displaystyle n}$${\displaystyle s}$

量子ビット状態にアダマール変換を適用すると、 ${\displaystyle n}$${\displaystyle |0\rangle ^{\otimes n}}$

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

次に、を変換するオラクルを適用します。これは、 に適用することでを変換する標準オラクルを通じてシミュレートできます。 (は 2 を法とする加算を表します。) これにより、重ね合わせが次のように変換されます。 ${\displaystyle U_{f}}$${\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle }$${\displaystyle |b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle }$${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle }$${\displaystyle \oplus}$

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

別のアダマール変換が各量子ビットに適用され、 の量子ビットの場合、その状態はからに変換され、 の量子ビットの場合、その状態はからに変換されます。 を取得するには、量子ビットに対して 標準基底( )での測定を実行します。${\displaystyle s_{i}=1}$${\displaystyle |-\rangle}$${\displaystyle |1\rangle }$${\displaystyle s_{i}=0}$${\displaystyle |+\rangle }$${\displaystyle |0\rangle }$${\displaystyle s}$${\displaystyle \{|0\rangle ,|1\rangle \}}$

グラフィカルに、アルゴリズムは次の図で表すことができます。ここで、は量子ビットのアダマール変換を表します。 ${\displaystyle H^{\otimes n}}$${\displaystyle n}$

${\displaystyle |0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}|x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}|y\rangle =|s\rangle }$

最後の状態が である理由は、特定の に対して、 ${\displaystyle |s\rangle }$${\displaystyle y}$

${\displaystyle {\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y)}=1{\text{ if }}s\oplus y={\vec {0}},\,0{\text{ otherwise}}.}$

は の場合にのみ真となるため、これは のみにゼロでない振幅があることを意味します。したがって、計算基底で回路の出力を測定すると、秘密の文字列 が得られます。 ${\displaystyle s\oplus y={\vec {0}}}$${\displaystyle s=y}$${\displaystyle |s\rangle }$${\displaystyle s}$

確率的オラクルを使用して1つ以上の秘密鍵を見つけることを含む、Bernstein-Vazirani問題の一般化が提案されています。 ^[3] これは興味深い問題であり、量子アルゴリズムは確実性または高い信頼度で効率的なソリューションを提供できますが、一般的なケースでは古典的なアルゴリズムでは問題を完全に解決できません。

• 隠れた線形関数の問題