バーンスタイン・ヴァジラニとサイモン

ドイチュ–ジョザの次に来る2つの分離

ドイチュ–ジョザ は「量子が古典を上回れる」ことを誤りゼロで示しましたが、判定は定数か均衡かの1ビットの答えにすぎず、しかも古典でも乱択なら少数回で高確率に解けてしまいます。ここで扱うバーンスタイン・ヴァジラニ（BV）とサイモンは、その物足りなさを埋める2つの前進です。BV は「n ビットの秘密列を丸ごと1回で抜く」ことで並列性の威力を可視化し、サイモンは「乱択を許しても古典は指数回かかる」という証明可能な指数分離を初めて与えました。そしてサイモンの構造こそが、後の ショア の周期発見の設計図になります。

バーンスタイン・ヴァジラニ：秘密列を1回で抜く

問題設定はこうです。n ビットの隠れた秘密列 s（s ∈ {0,1}^n）があり、オラクルは入力 x に対して s との**内積（mod 2）**を返します。

f(x) = s·x = (s_1·x_1 ⊕ s_2·x_2 ⊕ … ⊕ s_n·x_n)   （すべて mod 2）

s の中身は見えず、f への問い合わせだけで s を当てよ、というのが問題です。古典では s の各ビットを1本ずつ抜くしかありません。x = 100…0 を入れれば f = s_1、x = 010…0 なら f = s_2 ……と、n ビットを知るのに n 回の問い合わせが要ります。情報理論的にも、1回の問い合わせで得られる答えは1ビットなので、n ビットの s を確定するには n 回が古典の下限です。

量子アルゴリズムは、道具立てがドイチュ–ジョザと完全に同じです。補助ビットを |−> に用意して位相キックバックを効かせ、入力側にアダマール変換をかけて干渉させます。手順は3段です。

1. |0>^n にアダマール H^⊗n をかけ、全 x の均等な重ね合わせを作る。
2. 出力ビットを |−> にして U_f を1回適用（位相キックバック）。
   → 各基底状態に (−1)^(s·x) の符号が刻まれる：
      (1/√2^n) Σ_x (−1)^(s·x) |x>
3. 入力側に再び H^⊗n をかけて測定する。

決め手はステップ3の干渉です。アダマール変換 H^⊗n は |x> を (1/√2^n) Σ_y (−1)^(x·y) |y> へ写すので、位相 (−1)^(s·x) が乗った状態全体にかけると、状態 |y> の振幅は次の和になります。

|y> の振幅 = (1/2^n) Σ_x (−1)^(s·x) · (−1)^(x·y)
          = (1/2^n) Σ_x (−1)^((s⊕y)·x)

この和は、s⊕y = 0（つまり y = s）のときだけ全項が +1 で揃って 1 になり、それ以外の y では +1 と −1 が半々で完全に打ち消し合って 0 になります。したがって測定すると確率1で y = s が得られ、n ビットの秘密列が1回の問い合わせで丸ごと確定します。

サイモン：隠れた周期と指数分離

サイモンの問題は、BV より一段深い構造を突きます。関数 f: {0,1}^n → {0,1}^n が、ある未知の秘密列 s（s ≠ 0）について次の**約束（promise）**を満たすとします。

f(x) = f(y)  ⇔  x = y  または  x ⊕ y = s

言い換えると f は2対1で、x と x⊕s という対だけが同じ値に写ります（この s を関数の「周期」と呼びます）。目標は f への問い合わせだけで s を求めることです。

量子アルゴリズムは、1回の実行で s を直接は出しません。代わりに s に直交する式を1本取り出します。回路は入力レジスタ・出力レジスタの2本で、手順は次の通りです。

1. 入力 n 量子ビットに H^⊗n をかけ、全 x の重ね合わせを作る：
      (1/√2^n) Σ_x |x>|0>
2. オラクル U_f を適用して出力レジスタに f(x) を書く：
      (1/√2^n) Σ_x |x>|f(x)>
3. 出力レジスタを測定する（値 f(x0) が1つ確定）。
   すると入力側は衝突対だけが残り、次の状態に射影される：
      (1/√2) (|x0> + |x0 ⊕ s>)
4. 入力側に再び H^⊗n をかけて測定する。

ステップ4の干渉が肝です。(|x0> + |x0⊕s>) にアダマールをかけると、状態 |y> の振幅は (−1)^(x0·y) · (1 + (−1)^(s·y)) に比例します。ここで (1 + (−1)^(s·y)) は、s·y = 1（mod 2）なら 0、s·y = 0 なら 2 になります。つまり測定で得られる y は必ず y·s = 0（mod 2）を満たすものだけで、しかも該当する y の中では一様ランダムに出ます。

測定結果 y は必ず   y·s ≡ 0 (mod 2)   を満たす。

1回の実行は s を未知数とする一次方程式 y·s = 0 を1本与えるだけです。これを繰り返して線形独立な式を n−1 本集めると、GF(2)（2元体）上の連立一次方程式になり、ガウス消去で解けます。非自明な解がちょうど s です（自明解 0 は約束で除外済み）。線形独立な式が n−1 本揃う確率は高く、期待でも O(n) 回の実行で足ります。

Shorへの橋渡し ── 周期発見という共通骨格

サイモンとショアは、表面上は別物（GF(2) の隠れた周期 対 整数の位数）ですが、設計の骨格が同じです。どちらも「関数に隠れた周期構造」を突き止める問題で、量子の役割は周期に紐づく制約を干渉で浮かび上がらせることに尽き、最終的な数の復元は古典後処理に任せます。

橋渡しの核心は「アダマール変換は (Z/2)^n 上のフーリエ変換にほかならない」という視点です。サイモンの周期は XOR（(Z/2)^n の群演算）に対する周期で、その周期を暴くのが同じ群のフーリエ変換＝アダマールでした。ショアはこの枠組みを、周期が整数の加法群 Z に載る場合へ一般化し、(Z/2)^n のフーリエ変換の代わりに 量子フーリエ変換 を使ったもの——というのが正確な関係です。実際ショア自身が、サイモンのアルゴリズムから着想を得たと述べています。両者はまとめて「隠れた部分群問題（Hidden Subgroup Problem, HSP）」の可換群の場合として統一的に理解できます。

3つのアルゴリズムの計算量まとめ

同じ「並列性＋位相／フーリエ干渉」を使っても、古典との差は問題構造で大きく変わります。

BV は「1回で n ビット」というインパクトで並列性を見せますが、古典下限も多項式なので線形の分離です。対してサイモンは、乱択を許しても古典が指数回を要する点で質的に強く、これが「量子は本当に速い」と胸を張れる最初の指数分離になりました。詳しい分離の意味と限界は 量子計算量クラス（BQP） で扱っています。

まとめ

• バーンスタイン・ヴァジラニは、内積オラクルに隠れた n ビットの秘密列 s を、位相キックバックで (−1)^(s·x) を刻みアダマール干渉で y=s に確率1を集中させることで、1回の問い合わせで丸ごと読み出す。古典下限は n 回で、これは線形の分離。
• サイモンは、f(x)=f(x⊕s) という隠れた周期 s を、衝突対への射影とアダマール干渉で y·s=0 の式に変え、n−1 本集めて GF(2) の連立方程式を解いて復元する。古典は乱択でも約 2^(n/2) 回を要し、証明可能な指数分離を与えた最初の例。
• 両者は「量子で周期に紐づく制約を集め、古典で数を解く」という役割分担を共有し、これがそのまま ショア の周期発見（QPE＋連分数展開）の設計図になった。統一視点は可換群の隠れた部分群問題で、既知の指数加速の骨格を成す。