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

1. 2 次元部分空間への帰着

印のついた要素の一様重ね合わせを $|w⟩=\frac{1}{\sqrt{M}}{\sum }_{f(x)=1}|x⟩$、印のない要素の一様重ね合わせを $|u⟩=\frac{1}{\sqrt{N-M}}{\sum }_{f(x)=0}|x⟩$ とする。$\sin \theta =\sqrt{M/N}$ $(0<\theta <\pi /2)$ とおくと
$$|s⟩=\cos \theta |u⟩+\sin \theta |w⟩$$
である。$O_f$ は $|u⟩$ 軸に関する鏡映、$D$ は $|s⟩$ に関する鏡映である。$G$ は $|u⟩,|w⟩$ の張る平面を保ち、2 つの鏡映の積なのでこの平面内の角度 $2\theta$ の回転になる。したがって
$$G^k|s⟩=\cos ((2k+1)\theta )|u⟩+\sin ((2k+1)\theta )|w⟩$$
となる。測定で印のついた要素が得られる確率は
$$P_M(k)={\sin }^2((2k+1){\theta }_M)$$
である。

2. 漸化式による厳密計算

$a_k=\sin ((2k+1)\theta )$ とおく。加法定理 $\sin (\alpha +2\theta )+\sin (\alpha -2\theta )=2\cos 2\theta \sin \alpha$ から
$$a_{k+1}=2\cos 2\theta a_k-a_{k-1},a_{-1}=-\sin \theta ,a_0=\sin \theta$$
が成り立つ。ここで $\cos 2\theta =1-2{\sin }^2\theta =1-\frac{2M}{N}$ である。

(i) $M=1$ のとき：$\sin {\theta }_1=\frac{1}{4}$、$2\cos 2{\theta }_1=\frac{7}{4}$。
- $a_0=\frac{1}{4}$
- $a_1=\frac{7}{4}\cdot \frac{1}{4}+\frac{1}{4}=\frac{11}{16}$
- $a_2=\frac{7}{4}\cdot \frac{11}{16}-\frac{1}{4}=\frac{61}{64}$
- $a_3=\frac{7}{4}\cdot \frac{61}{64}-\frac{11}{16}=\frac{251}{256}$
- $a_4=\frac{7}{4}\cdot \frac{251}{256}-\frac{61}{64}=\frac{781}{1024}$
- $a_5=\frac{7}{4}\cdot \frac{781}{1024}-\frac{251}{256}=\frac{1451}{4096}$

(ii) $M=2$ のとき：$\sin {\theta }_2=\frac{1}{2\sqrt{2}}$、$2\cos 2{\theta }_2=\frac{3}{2}$。$a_k=\sin {\theta }_2{b}_k$ とおくと、$b_k$ も同じ漸化式 $b_{k+1}=\frac{3}{2}{b}_k-b_{k-1}$（$b_{-1}=-1,b_0=1$）に従う。
- $b_0=1$
- $b_1=\frac{5}{2}$
- $b_2=\frac{11}{4}$
- $b_3=\frac{13}{8}$
- $b_4=-\frac{5}{16}$
- $b_5=-\frac{67}{32}$

このとき $P_2(k)=\frac{b_k^2}{8}$ である。

3. 平均成功確率の比較

$\bar{P}(k)=\frac{1}{2}\left(P_1(k)+P_2(k)\right)$ を計算する。
- $k=0$: $\frac{1}{2}\left(\frac{1}{16}+\frac{1}{8}\right)=\frac{3}{32}\approx 0.094$
- $k=1$: $\frac{1}{2}\left(\frac{121}{256}+\frac{25}{32}\right)=\frac{321}{512}\approx 0.627$
- $k=2$: $\frac{1}{2}\left(\frac{3721}{4096}+\frac{121}{128}\right)=\frac{1}{2}\cdot \frac{3721+3872}{4096}=\frac{7593}{8192}\approx 0.927$
- $k=3$: $\frac{1}{2}\left(\frac{63001}{65536}+\frac{169}{512}\right)=\frac{84633}{131072}\approx 0.646$
- $k=4$: $\frac{1}{2}\left(\frac{609961}{1048576}+\frac{25}{2048}\right)\approx \frac{1}{2}(0.582+0.012)\approx 0.297$
- $k=5$: $\frac{1}{2}\left(\frac{2105401}{16777216}+\frac{4489}{8192}\right)\approx \frac{1}{2}(0.125+0.548)\approx 0.337$

なお $M=1$ だけを想定すると最適は $k=3$ である。しかし $k=3$ では $M=2$ の場合に回転しすぎ、$P_2(3)=\frac{169}{512}$ まで下がる。平均では $k=2$ が最大になる。

以上より、最大の平均成功確率は
$$\bar{P}(2)=\frac{7593}{8192}$$
である。

$\sin \theta =\sqrt{M/N}$ とおくと、$k$ 回の反復後の成功確率は $P_M(k)={\sin }^2((2k+1)\theta )$ である。$u_j=\sin (j\theta )/\sin \theta$ は漸化式 $u_{j+2}=2\cos 2\theta u_j-u_{j-2}$（$u_1=1,u_{-1}=-1$）に従う。ここで $\cos 2\theta =1-2{\sin }^2\theta$ である。$P_M(k)={\sin }^2\theta u_{2k+1}^2$ として計算する。

$M=1$（${\sin }^2\theta =1/16$、$\cos 2\theta =7/8$）：$u_1,u_3,u_5,u_7,u_9,u_{11}=1,11/4,61/16,251/64,781/256,1451/1024$。
$P_1(k)$（$k=0,\dots ,5$）$=1/16,121/256,3721/4096,63001/65536,609961/1048576,2105401/16777216$。数値では約 $0.0625,0.473,0.908,0.961,0.582,0.125$。

$M=2$（${\sin }^2\theta =1/8$、$\cos 2\theta =3/4$）：$u_1,\dots ,u_{11}=1,5/2,11/4,13/8,-5/16,-67/32$。
$P_2(k)=1/8,25/32,121/128,169/512,25/2048,4489/8192$。数値では約 $0.125,0.781,0.945,0.330,0.012,0.548$。

平均 $\bar{P}(k)=(P_1+P_2)/2$ は、$k=0$ で約 $0.094$、$k=1$ で約 $0.627$、$k=2$ で約 $0.927$、$k=3$ で約 $0.646$、$k=4$ で約 $0.297$、$k=5$ で約 $0.337$ である。したがって $k=2$ が最大である。

$\bar{P}(2)=\frac{1}{2}\left(\frac{3721}{4096}+\frac{3872}{4096}\right)=\frac{7593}{8192}$。分母は $2^{13}$ で分子は奇数なので、これは既約である。