Qiskit (32) - らんだむな記憶 の最後で触れた詳細についてニールセン&チャンに書いてあるということで調べると、II pp.73-74 で説明されているようなので、今回の 3 量子ビットのケースに当てはめて読んでみたい。この話は、$2^3 \theta \in \Z$ では自明（確率 1 で真の位相が求まる）なので、$\theta \in [0, 1), 2^3 \theta \not\in \Z$ とする。
Qiskit (32) - らんだむな記憶 の (3) 式から始めると、第 1 レジスタの状態ベクトルは
$$
\begin{align*}
\frac{1}{2^3} \sum_{x=0}^{2^3-1} \sum_{k=0}^{2^3-1} e^{- \frac{2 \pi i k}{2^3}(x - 2^3 \theta)} \ket{x}
\tag{1}
\end{align*}
$$
であった。$x \in \Z, 0 \leq x \leq 2^3 - 1$ で $x \approx 2^3 \theta$ となる状態が最も多く観測されるであろうということであった。振幅の 2 乗は $\frac{x-2^3\theta}{2^3} \in \Z$ で最大値をとり、具体的には $x_0 = 2^3\theta$ であった。
ここで、$x_1 \in \Z$ として $x_1 = \lfloor x_0 \rfloor$ と置く。$2^3 \theta \not\in \Z$であるので、明らかに、$0 \leq x_1 \leq 2^3 - 1$ である。また、$2^3 \theta - 1 = x_0 - 1 < x_1 = \lfloor x_0 \rfloor \leq x_0 = 2^3 \theta$ であるので、$\delta \equiv \theta - \frac{x_1}{2^3}$ と置くと、$0 \leq \delta < \frac{1}{2^3}$ である。つまり、ニールセン&チャンの $b$ はこの $x_1$ のことである。
$\ell \in \Z$ をとって、$a_\ell$ を $\ket{x_1 + \ell\ (\bmod{2^3})}$ の確率振幅とする。つまり、(1) 式を
$$
\begin{align*}
\frac{1}{2^3} \sum_{\ell=-x_1}^{2^3-x_1-1} \sum_{k=0}^{2^3-1} e^{- \frac{2 \pi i k}{2^3}(x_1 + \ell - 2^3 \theta)} \ket{x_1 + \ell} = \sum_{\ell=-x_1}^{2^3-x_1-1} a_\ell \ket{x_1 + \ell}
\tag{1'}
\end{align*}
$$
と書き換えると、$a_\ell = \frac{1}{2^3} \sum_{k=0}^{2^3-1} e^{- \frac{2 \pi i k}{2^3}(x_1 + \ell - 2^3 \theta)}$ である。$r = e^{- \frac{2 \pi i}{2^3}(x_1 + \ell - 2^3 \theta)}$ とおくと、$a_\ell = \frac{1}{2^3} \sum_{k=0}^{2^3-1} r^k = \frac{1}{2^3} \frac{1-r^{2^3}}{1-r}$ となるので、
$$
\begin{align*}
a_\ell &= \frac{1}{2^3} \left( \frac{1-e^{- 2 \pi i (x_1 + \ell - 2^3 \theta)}}{1-e^{- \frac{2 \pi i}{2^3}(x_1 + \ell - 2^3 \theta)}} \right) \\
&= \frac{1}{2^3} \left( \frac{1-e^{2 \pi i (\delta - \ell)}}{1-e^{2 \pi i(\delta - \frac{\ell}{2^3})}} \right)
\tag{2}
\end{align*}
$$
を得る。ここで、後のために $\ell \equiv \ell^\prime \mod 2^3$ の時 $a_\ell = a_{\ell^\prime}$ が成立することに注意する。
理想的には、第 1 レジスタを測定した結果、$|a_0|^2$ が最も大きくなる、つまり $\ket{x_1}$ が最も多く観測されてほしい。実際に最頻値として観測されたものが $\ket{x}$ である時に、$x$ が $x_1$ に近い確率、或いは逆に遠い確率が知りたい。ここではニールセン&チャンそのものであるが、 $x_1$ から遠い値が観測される確率を求める。
$e \in \Z_{> 0}$ なる値を $e < 2^2 - 1$ の範囲でとって、値 $x$ が観測された時、これが $x_1$ から $e$ より大きく離れている確率 $p(|x - x_1| > e)$ を計算したい。これは $\ket{0}, \cdots, \ket{x_1 - (e+1)}, \ket{x_1 + (e+1)}, \cdots$ の確率振幅の絶対値の 2 乗の総和なので、以下のようになる:
$$
\begin{align*}
p(|x - x_1| > e) = \sum_{\ell = -2^2 + 1}^{-(e+1)} |a_\ell|^2 + \sum_{\ell = e+1}^{2^2} |a_\ell|^2
\tag{3}
\end{align*}
$$
なお、和の範囲は一見 (1') 式とは異なっている。これは、$a_\ell$ は $\ell$ の周期 $2^3$ で循環しており、和の範囲は下限と上限の差が $2^3$ であれば好きにとれることによる。よって、$b - a + 1 =2^3$ なる $a,b \in \Z$ をとって、$\sum_{\ell = a}^b$ から $|\ell| \leq e$ の範囲をくり抜けば良く、そのような $a,b$ として上記では $e$ の上限を一番大きくとれる $a= -2^2+1, b = 2^2$ を選んでいる。
任意の $\phi \in \R$ に対して、三角不等式から $|1 - e^{i \phi}| \leq 2$ なので、(2) 式から
$$
\begin{align*}
|a_\ell| \leq \frac{2}{2^3 | 1-e^{2 \pi i(\delta - \frac{\ell}{2^3})} |}
\tag{4}
\end{align*}
$$
と評価できる。また、$-\pi \leq \phi \leq \pi$ の時、倍角の公式と $\varphi \in [0, \frac{\pi}{2}]$ に対して $0 \leq \frac{2}{\pi} \varphi \leq \sin \varphi$ に注意して、
$$
\begin{align*}
|1 - e^{i \phi}|^2 &= (1 - e^{i \phi}) \overline{(1 - e^{i \phi})} \\
&= 2(1 - \cos \phi) \\
&= 4 \sin^2 \frac{\phi}{2} \geq 4 \left(\frac{\phi}{\pi} \right)^2
\end{align*}
$$
が成立するので、$|1 - e^{i \phi}| \geq 2 \left| \frac{\phi}{\pi} \right|$ を得る。このことと (4) 式から
$$
\begin{align*}
|a_\ell| \leq \frac{1}{2^4 (\delta - \frac{\ell}{2^3})}
\tag{5}
\end{align*}
$$
を得る。$0 \leq \delta < \frac{1}{2^3}$ であったことに注意して、(5) 式を (3) 式に代入することで、
$$
\begin{align*}
p(|x - x_1| > e) &= \sum_{\ell = -2^2 + 1}^{-(e+1)} |a_\ell|^2 + \sum_{\ell = e+1}^{2^2} |a_\ell|^2 \\
&\leq \frac{1}{4} \left[ \sum_{\ell = -2^2 + 1}^{-(e+1)} \frac{1}{(\ell - 2^3 \delta)^2} + \sum_{\ell = e+1}^{2^2} \frac{1}{(\ell - 2^3 \delta)^2} \right] \\
&\leq \frac{1}{4} \left[ \underbrace{\sum_{\ell = -2^2 + 1}^{-(e+1)} \frac{1}{\ell^2}}_{-\ell \to \ell} + \underbrace{\sum_{\ell = e+1}^{2^2} \frac{1}{(\ell - 1)^2}}_{\ell - 1 \to \ell} \right] \\
&= \frac{1}{4} \left[ \sum_{\ell = e + 1}^{2^2 - 1} \frac{1}{\ell^2} + \sum_{\ell = e}^{2^2 - 1} \frac{1}{\ell^2} \right] \\
&\leq \frac{1}{2} \sum_{\ell = e}^{2^2 - 1} \frac{1}{\ell^2} \leq \frac{1}{2} \int_{e - 1}^{2^2 - 1} \frac{d\ell}{\ell^2} = \frac{1}{2} \left(\frac{1}{e - 1} - \frac{1}{2^2 - 1} \right)
\end{align*}
$$
を得る。
上記から、$e = 2$ の時、
$$
\begin{align*}
p \left(\left|\frac{x}{2^3} - \frac{x_1}{2^3}\right| \leq \frac{2}{2^3} \right) \geq 1 - \frac{1}{2} \left(\frac{1}{1} - \frac{1}{2^2 - 1} \right) = \frac{2}{3}
\tag{6}
\end{align*}
$$
となる。$x_0 - 1 < x_1 \leq x_0$ より、$\theta - \frac{1}{2^3} < \frac{x_1}{2^3} \leq \theta$ であったので、$|\frac{x}{2^3} - \frac{x_1}{2^3}| \geq |\frac{x}{2^3} - \theta| - |\theta - \frac{x_1}{2^3}| \geq |\frac{x}{2^3} - \theta| - \frac{1}{2^3}$ となる。よって、(6) 式は
$$
\begin{align*}
p \left(\left|\frac{x}{2^3} - \theta \right| \leq \frac{3}{2^3} \right) \geq \frac{2}{3}
\end{align*}
$$
を導く。今回は 3 量子ビットで位相の近似値をコード化するケースを考えたが、ビット数を増やすことで、近似の精度が高まることが期待できる。
なお、今回のケースであれば、$e = 1$ の時などに直接計算でもっと精度を上げられる。つまり、$\frac{1}{4} \left[ \sum_{\ell = e + 1}^{2^2 - 1} \frac{1}{\ell^2} + \sum_{\ell = e}^{2^2 - 1} \frac{1}{\ell^2} \right] = \frac{1}{4}[(1/2^2+1/3^2) + (1+ 1/2^2+1/3^2))] = \frac{31}{72}$ であるので、$p \left(\left|\frac{x}{2^3} - \theta \right| \leq \frac{1}{2^2} \right) \geq 1 - \frac{31}{72} = \frac{41}{72}$ と見積もることができる。
あまり意味はないが更に精度を高めることもできる。このために、(3) 式の和の範囲を変更する。具体的には、$x_1 \leq x \leq x_1 + 1$ の範囲を除外したい。この時、和は $\sum_{\ell = -2^2+1}^{-1} + \sum_{\ell = 2}^{2^2}$ となり、$\frac{1}{4}(2(1 + 1/2^2 + 1/3^2)) = \frac{49}{72}$ となる。よって、$p(\frac{x_1}{2^3} \leq \frac{x}{2^3} \leq \frac{x_1}{2^3} + \frac{1}{2^3}) \geq 1 - \frac{49}{72} = \frac{23}{72}$ を得る。$\frac{x_1}{2^3} \leq \theta < \frac{x_1}{2^3} + \frac{1}{2^3}$ であったので、$\frac{x_1}{2^3} \leq \frac{x}{2^3} \leq \frac{x_1}{2^3} + \frac{1}{2^3}$ でもあるとすると、$|\frac{x}{2^3} - \theta| \leq \frac{1}{2^3}$ が成立する。$\{|\frac{x}{2^3} - \theta| \leq \frac{1}{2^3}\} \supset \{\frac{x_1}{2^3} \leq \frac{x}{2^3} \leq \frac{x_1}{2^3} + \frac{1}{2^3}\}$ であるので、$p(|\frac{x}{2^3} - \theta| \leq \frac{1}{2^3}) \geq \frac{23}{72}$ を得る。
Quantum Phase Estimation では、$x \approx 2^n \theta$ になる確率を $n$ に無関係に $\frac{4}{\pi^2}$ で見積もっているが、ニールセン&チャンの評価では $n$ に依存する評価になるし、最終的には $\pi$ は出てこないと思うので、どういう計算で求めた内容かはよく分からない。良い確率で $x \approx 2^n \theta$ となるという主張そのものは真である。
