この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

量子情報・量子計算の問題

難易度 2大学院の講義の演習問題レベル大学院物理量子情報・量子計算

$4$ 量子ビットの計算基底 ${∣ x ⟩}_{x = 0}^{15}$ （ $N = 16$ ）に対してグローバーのアルゴリズムを考える。関数 $f : {0, 1, \dots, 15} \to {0, 1}$ は、ただ $1$ つの $x = w$ に対してだけ $f (w) = 1$ となり、それ以外では $f (x) = 0$ とする。

初期状態は、 $∣0000 ⟩$ の各量子ビットにアダマール変換をほどこした一様な重ね合わせ
$∣ s ⟩ = \frac{1}{4} x = 0 \sum 15 ∣ x ⟩$
とする。オラクルを $O ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ 、グローバー反復を $G = (2∣ s ⟩ ⟨ s ∣ - I) O$ と定める。 $∣ s ⟩$ に $G$ を $k$ 回作用させた後、計算基底で測定して $w$ を得る確率を $P_{k}$ とする。ここで $k$ は $1 \leq k \leq 5$ の整数とし、すべての操作は誤りなく行われるものとする。

$P_{k}$ を最大にする $k$ と、そのときの $P_{k}$ の値（既約分数）を、 $(k, P_{k})$ の順に組で求めよ。

この問題で使うもの

グローバーの探索アルゴリズム（説明と入口の問題）

この問題を解けるようになるまで（111 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

グローバー反復 $G$ は、 $∣ w ⟩$ と印のない状態の一様な重ね合わせ $∣ w^{⊥} ⟩$ が張る 2 次元平面内の回転として表せます。

ヒント 2

$sin θ = ⟨ w ∣ s ⟩ = 1/4$ とおくと $P_{k} = sin^{2} ((2 k + 1) θ)$ です。あるいは振幅を「オラクルで符号反転 → 平均の周りで反転」と順に計算しても求められます。

ヒント 3

$(2 k + 1) θ$ が $π /2$ に最も近い $k$ を探してください。振幅の計算では、1 回目の後 $a = 11/16$ 、2 回目の後 $a = 61/64$ になります。

答えと解説

答えを見る

(3, \frac{63001}{65536})

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

2次元部分空間での回転 印の付いた状態 $∣ w ⟩$ と、それ以外の $15$ 個の状態の一様な重ね合わせ $∣ w^{⊥} ⟩ = \frac{1}{15} \sum_{x \neq = w} ∣ x ⟩$ が張る平面を考える。 $sin θ = ⟨ w ∣ s ⟩ = \frac{1}{4}$ となる角 $θ$ をとると、
$∣ s ⟩ = sin θ ∣ w ⟩ + cos θ ∣ w^{⊥} ⟩$
と書ける。 $O$ はこの平面内で $∣ w^{⊥} ⟩$ 軸に関する鏡映、 $2∣ s ⟩ ⟨ s ∣ - I$ は $∣ s ⟩$ 軸に関する鏡映である。2 つの鏡映の合成なので、 $G$ は角 $2 θ$ の回転になる。よって
$G^{k} ∣ s ⟩ = sin ((2 k + 1) θ) ∣ w ⟩ + cos ((2 k + 1) θ) ∣ w^{⊥} ⟩, P_{k} = sin^{2} ((2 k + 1) θ)$
である。

どの $k$ で最大か $θ = arcsin \frac{1}{4} \approx 0.2527$ なので、 $(2 k + 1) θ$ は $k = 1, \dots, 5$ に対しておよそ $0.758, 1.263, 1.769, 2.274, 2.780$ となる。このうち $π /2 \approx 1.571$ に最も近いのは $k = 2$ の $1.263$ （差 $0.308$ ）と $k = 3$ の $1.769$ （差 $0.198$ ）で、 $k = 3$ のほうが近い。 $sin^{2}$ は $π /2$ からのずれが小さいほど大きいので、 $P_{k}$ は $k = 3$ で最大になる。 $k = 1, 2, 3, 4, 5$ に対して $P_{k}$ は順に約 $0.473, 0.908, 0.961, 0.582, 0.126$ である。

$P_{3}$ の正確な値（振幅の漸化式による計算） 印の付いた状態の振幅を $a$ 、印のない各状態の振幅を $b$ とする。初めは $a = b = \frac{1}{4}$ である。1 回の反復は次の 2 段階からなる。
- $O$ によって $a \to - a$ となる。
- $2∣ s ⟩ ⟨ s ∣ - I$ は「平均の周りの反転」である。平均を $m = \frac{a ^{'} + 15 b}{16}$ （ $a^{'} = - a$ ）とすると、各振幅は $c \to 2 m - c$ と変わる。

1 回目: $m = \frac{- 1/4 + 15/4}{16} = \frac{7}{32}$ より、 $a = \frac{7}{16} + \frac{1}{4} = \frac{11}{16}$ 、 $b = \frac{7}{16} - \frac{1}{4} = \frac{3}{16}$ 。

2 回目: $m = \frac{- 11 + 45}{256} = \frac{17}{128}$ より、 $a = \frac{17}{64} + \frac{11}{16} = \frac{61}{64}$ 、 $b = \frac{17}{64} - \frac{3}{16} = \frac{5}{64}$ 。

3 回目: $m = \frac{- 61 + 75}{1024} = \frac{7}{512}$ より、 $a = \frac{7}{256} + \frac{61}{64} = \frac{251}{256}$ 、 $b = \frac{7}{256} - \frac{5}{64} = - \frac{13}{256}$ 。

規格化の確認: $25 1^{2} + 15 \cdot 1 3^{2} = 63001 + 2535 = 65536 = 25 6^{2}$ となり成り立っている。

倍角公式 $sin 7 θ = 7 s - 56 s^{3} + 112 s^{5} - 64 s^{7}$ （ $s = sin θ = \frac{1}{4}$ ）からも
$sin 7 θ = \frac{7}{4} - \frac{7}{8} + \frac{7}{64} - \frac{1}{256} = \frac{251}{256}$
となり、振幅の計算と一致する。

したがって
$P_{3} = (\frac{251}{256})^{2} = \frac{63001}{65536} \approx 0.961$
であり、答えは $(k, P_{k}) = (3, \frac{63001}{65536})$ である。

別解

一様状態 $∣ s ⟩$ は $∣ w ⟩$ と $sin θ = ⟨ w ∣ s ⟩ = 1/ N = 1/4$ をなす。グローバー反復 $G$ は、 $∣ w ⟩$ と $∣ s ⟩$ が張る平面内で角度 $2 θ$ の回転になる。したがって $P_{k} = sin^{2} ((2 k + 1) θ)$ である。

$θ = arcsin (1/4) \approx 0.25268$ なので、 $(2 k + 1) θ$ は $k = 1, \dots, 5$ で次の値になる。
- $k = 1$ : $3 θ \approx 0.758$
- $k = 2$ : $5 θ \approx 1.263$
- $k = 3$ : $7 θ \approx 1.769$
- $k = 4$ : $9 θ \approx 2.274$
- $k = 5$ : $11 θ \approx 2.779$

$π /2 \approx 1.5708$ に最も近いのは $k = 3$ である。

$k = 3$ の値を正確に求める。 $sin 7 θ = 7 s - 56 s^{3} + 112 s^{5} - 64 s^{7}$ （ $s = sin θ = 1/4$ ）を使う。
$sin 7 θ = \frac{7}{4} - \frac{7}{8} + \frac{7}{64} - \frac{1}{256} = \frac{448 - 224 + 28 - 1}{256} = \frac{251}{256}$
よって $P_{3} = (251/256)^{2} = 63001/65536 \approx 0.9613$ となる。

他の $k$ との比較は次の通り。
- $k = 2$ : $sin^{2} (5 θ) \approx 0.909$
- $k = 4$ : $sin^{2} (9 θ) \approx 0.582$

いずれも $P_{3}$ より小さいので、最大は $k = 3$ である。 $251$ は奇数なので、 $63001/65536$ は既約である。

量子情報・量子計算の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題