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

ユニタリ演算子 $U$ と、その固有状態 $|u⟩$（$U|u⟩=e^{2\pi i\phi }|u⟩$, $\phi =\frac{1}{8}$）がある。$t=2$ 量子ビットの制御レジスタ（$N=2^t=4$）を使って、標準的な量子位相推定を行う。すなわち、制御レジスタを $|0{⟩}^{\otimes 2}$ からアダマールゲートで一様な重ね合わせ $\frac{1}{2}{\sum }_{k=0}^3|k⟩$ にし、制御 $U^k$ 演算によって状態を $\frac{1}{2}{\sum }_{k=0}^3{e}^{2\pi i\phi k}|k⟩|u⟩$ とした後、制御レジスタに逆量子フーリエ変換 $|k⟩\mapsto \frac{1}{\sqrt{N}}{\sum }_{y=0}^{N-1}{e}^{-2\pi iky/N}|y⟩$ を作用させて計算基底で測定する。測定結果が $y=0$ となる確率を、根号を含む正確な値で求めよ。

$4$ 量子ビットのグローバー探索を考える。探索空間は $N=2^4=16$ 個の計算基底状態 $|x⟩$ $(x=0,1,\dots ,15)$ であり、オラクルは $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ で与えられる。ここで $f:\{0,\dots ,15\}\to \{0,1\}$ であり、$f(x)=1$ となる $x$ を「印のついた要素」と呼ぶ。印のついた要素の個数 $M$ は事前にはわからず、$M=1$ である確率と $M=2$ である確率がそれぞれ $\frac{1}{2}$ であることだけがわかっている。

アルゴリズムは次のとおりである。初期状態 $|s⟩=H^{\otimes 4}|0000⟩=\frac{1}{4}{\sum }_{x=0}^{15}|x⟩$ を用意し、グローバー演算子 $G=D{O}_f$（$D=2|s⟩⟨s|-I$）を $k$ 回作用させたのち、計算基底で測定する。測定結果が印のついた要素であれば成功とする。

反復回数 $k$ は $M$ を知らないまま事前に $\{0,1,2,3,4,5\}$ の中から $1$ つ選ぶ（デコヒーレンスのため $k\le 5$ に制限されている）。$M$ についての平均をとった成功確率が最大になるように $k$ を選ぶとき、その最大の成功確率を既約分数で求めよ。ゲートやオラクルには誤差がないものとする。

$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}\sum _{x=0}^{15}|x⟩$$
とする。オラクルを $O|x⟩=(-1{)}^{f(x)}|x⟩$、グローバー反復を $G=(2|s⟩⟨s|-I)O$ と定める。$|s⟩$ に $G$ を $k$ 回作用させた後、計算基底で測定して $w$ を得る確率を $P_k$ とする。ここで $k$ は $1\le k\le 5$ の整数とし、すべての操作は誤りなく行われるものとする。

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

3 ビットの入力 $x=x_1{x}_2{x}_3\in \{0,1{\}}^3$ に対する関数 $f:\{0,1{\}}^3\to \{0,1\}$ を
$$f(x)=\{\begin{array}{ll}1& (x\in \{000,001,010,100\})\\ 0& (\text{それ以外})\end{array}$$
で定める（$f$ は 8 個の入力のうち 4 個で $1$ をとる均衡関数である）。オラクル $U_f$ は $U_f|x⟩|b⟩=|x⟩|b\oplus f(x)⟩$（$b\in \{0,1\}$, $\oplus$ は 2 を法とする和）と作用する。

ドイチュ・ジョザのアルゴリズムとして、次の操作を行う。
1. 3 量子ビットの入力レジスタを $|000⟩$、補助量子ビットを $|1⟩$ に用意する。
2. 4 個すべての量子ビットにアダマールゲート $H$ を作用させる。
3. $U_f$ を 1 回作用させる。
4. 入力レジスタの 3 量子ビットそれぞれに $H$ を作用させる。
5. 入力レジスタを計算基底で測定する。

ここで $H|0⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$, $H|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ とする。測定結果が $111$ となる確率を求めよ。

1 量子ビットの計算基底を $|0⟩$, $|1⟩$ とし、行列はこの順の基底で表す。アダマールゲートと位相ゲートを
$$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),P(\phi )=\left(\begin{array}{cc}1& 0\\ 0& e^{i\phi }\end{array}\right)$$
とする。初期状態 $|0⟩$ に $H$、$P\left(\frac{\pi }{3}\right)$、$H$ をこの順に作用させたあと、計算基底で測定する。測定結果が $0$ となる確率を既約分数で求めよ。