位数発見は $U_a$ の位相推定である

相対エントロピーから情報と物理を組み立てる　第6部 第3章 §6.3.2　★★★ 掛け算の置換 $U_a$ の固有値は $\mathrm{e}^{2\pi\mathrm{i} s/r}$。固有ベクトルの和が $| 1 \rangle$ なので、準備の難しい固有ベクトルを作らずに位相推定ができる

掛け算のユニタリと固有ベクトル

$n$ 量子ビットのレジスタの計算基底 $| y \rangle$（$0\le y<2^n$）に対し、

$$U_a| y \rangle =\begin{cases}| ay\bmod N \rangle & (0\le y<N)\\ | y \rangle & (N\le y<2^n)\end{cases}\tag{6.3.3}$$

と定める。$a$ が $N$ と互いに素なので $y\mapsto ay\bmod N$ は $\{0,\dots,N-1\}$ の並べ替えで、$U_a$ は置換行列、したがってユニタリである。

$| 1 \rangle$ に $U_a$ を繰り返し当てると $| 1 \rangle ,| a \rangle ,| a^2 \rangle ,\dots$（$\bmod N$）を巡り、$r$ 回で戻る。この $r$ 個の基底が張る部分空間の上で $U_a$ は巡回置換で、その固有ベクトルは

$$| u_s \rangle =\frac{1}{\sqrt r}\sum_{k=0}^{r-1}\mathrm{e}^{-2\pi\mathrm{i} sk/r}| a^k\bmod N \rangle ,\qquad s=0,1,\dots,r-1\tag{6.3.4}$$

である。実際、$U_a$ を当てると $| a^k \rangle$ が $| a^{k+1} \rangle$ に移るので、和の添字を $k'=k+1$ に付け替えると

$$U_a| u_s \rangle =\frac1{\sqrt r}\sum_{k'=1}^{r}\mathrm{e}^{-2\pi\mathrm{i} s(k'-1)/r}| a^{k'}\bmod N \rangle =\mathrm{e}^{2\pi\mathrm{i} s/r}| u_s \rangle$$

となる（$k'=r$ の項は $a^r\equiv1$ なので $k'=0$ の項と同じ）。固有値の位相は $\varphi_s=s/r$ で、位相の分母が求めたい位数である。

固有ベクトル $| u_s \rangle$ そのものを準備するには $r$ を知っている必要がある。ところが式 (6.3.4) を $s$ について足すと、$k\neq0$ の項は1の $r$ 乗根の和として消え、

$$\frac1{\sqrt r}\sum_{s=0}^{r-1}| u_s \rangle =| 1 \rangle\tag{6.3.5}$$

が残る。簡単に準備できる $| 1 \rangle$ が、$r$ 個の固有ベクトルの等しい重みの重ね合わせになっている。$| 1 \rangle$ を入れて位相推定を走らせると、固有ベクトルが互いに直交しているので、結果は「$s$ を $\{0,\dots,r-1\}$ から一様に選び、$| u_s \rangle$ で位相推定をした」ときの分布に一致する。$s$ が何になるかは選べないが、どの $s$ でも位相 $s/r$ の分母に $r$ が含まれている。

回路

位相推定（第6部第2章）は、第1のレジスタの $t$ 個の量子ビットに Hadamard ゲートを当て、$j$ 番目の量子ビットで制御した $U_a^{2^j}$ を第2のレジスタに当て、第1のレジスタに逆量子 Fourier 変換を当てて測る（図 6.3.1）。制御した $U_a^{2^j}$ を全部当てた直後の状態は

$$\frac{1}{2^{t/2}}\sum_{x=0}^{2^t-1}| x \rangle | a^x\bmod N \rangle\tag{6.3.6}$$

で、第2のレジスタに関数 $f(x)=a^x\bmod N$ の値が重ね合わせで書かれている。$f$ は周期 $r$ の関数なので、この章の問題は「関数の周期を求める問題」とも言える。

$U_a^{2^j}$ を「$U_a$ を $2^j$ 回」当てると手間が $2^t$ に比例してしまう。しかし $U_a^{2^j}=U_{a^{2^j}\bmod N}$ で、$a^{2^j}\bmod N$ は前の値を2乗して $N$ で割る操作（反復2乗）を $j$ 回行えば古典の計算で求まる。したがって各ゲートは「決まった数 $a^{2^j}\bmod N$ を掛けて $N$ で割った余りを取る」1回の掛け算の回路で済む。

出力の分布

$| u_s \rangle$ に対する位相推定で $m$ を得る確率は、第6部第2章の式 (6.2.8) で求めたとおり

$$P(m\,|\,s)=F_t\Bigl(\frac sr-\frac m{2^t}\Bigr),\qquad F_t(\delta)\coloneqq\biggl|\frac1{2^t}\sum_{x=0}^{2^t-1}\mathrm{e}^{2\pi\mathrm{i} x\delta}\biggr|^2=\frac{\sin^2(\pi2^t\delta)}{2^{2t}\sin^2(\pi\delta)}\tag{6.3.7}$$

である。$| 1 \rangle$ から始めると $s$ が一様に混ざるので、出力 $m$ の分布は

$$P(m)=\frac1r\sum_{s=0}^{r-1}F_t\Bigl(\frac sr-\frac m{2^t}\Bigr)\tag{6.3.8}$$

になる。$F_t(\delta)$ は $\delta=0$ で $1$、$\delta$ が $1/2^t$ の整数倍（$0$ 以外）で $0$ になる、幅 $1/2^t$ の鋭い山である。したがって $P(m)$ は$m\approx2^ts/r$ の $r$ か所に山を持つ。$r$ が $2^t$ を割り切るときは山の位置がちょうど整数になり、$P(m)$ はそこに $1/r$ ずつ乗った分布になる。図 6.3.2 は $N=21$、$a=2$（$r=6$）、$t=9$ の分布で、式 (6.3.8) と、状態ベクトルを直接計算した分布が一致することを検算で確かめてある。