Kitaev の方法：1つの補助量子ビットで桁を決める

相対エントロピーから情報と物理を組み立てる　第6部 第2章 §6.2.4　★★ 逆 QFT を測定と古典の制御に置き換え、補助の量子ビット1個で桁を順に決める。くり返しの多数決で位相の周期の曖昧さを段階的に消す

反復位相推定

逆 QFT は、補助の量子ビットの間に制御位相回転を必要とする。ところが、制御側の量子ビットをすぐ測ってしまっても、測定値で古典的に制御して回転を当てれば同じ結果になる（Griffiths と Niu の半古典 Fourier 変換¹1R. B. Griffiths and C.-S. Niu (1996), Phys. Rev. Lett. 76, 3228。下の脚注へ閉じる）。制御 $R_k$ は制御と標的について対称なので、先に測った量子ビットを制御側に回せるからである。こうすると補助の量子ビットは同時に $t$ 個並べる必要がなく、1個を使い回すことができる。

$\varphi=0.\varphi_1\varphi_2\cdots\varphi_t$ が書き切れる場合で手順を述べる。下の桁から決める。

1. 補助の量子ビットを $| 0 \rangle$ に用意して $H$ を当て、制御 $\hat U^{2^{t-1}}$ を当てる。位相は $2\pi\cdot2^{t-1}\varphi\equiv2\pi\times0.\varphi_t$ で、$0$ か $\pi$ なので、$H$ を当てて測れば確率 $1$ で $\varphi_t$ が出る。
2. 一般に $k$ 桁目では制御 $\hat U^{2^{k-1}}$ で位相 $2\pi\times0.\varphi_k\varphi_{k+1}\cdots\varphi_t$ を書き戻し、すでに分かった桁の分 $2\pi\times0.0\varphi_{k+1}\cdots\varphi_t$ を位相回転 $\mathrm{diag}(1,\mathrm{e}^{-\mathrm{i}\omega_k})$ で引く。残りは $2\pi\times0.\varphi_k$ で、$H$ と測定で $\varphi_k$ が確定する。

この回路を図 6.2.4 に示す。1回の測定で1ビットが決まり、$\hat U$ の使用回数は合わせて $T-1$ 回で、元の位相推定と同じである。

図 6.2.4　反復位相推定の1段（$k$ 桁目）。$\omega_k=2\pi\times0.0\varphi_{k+1}\cdots\varphi_t$ はそれまでに測った桁から古典的に計算する。$\omega_k=0$ で $\mathrm{diag}(1,\mathrm{e}^{-\mathrm{i}\omega})$ を外し、$H$ の代わりに $X$ 基底・$Y$ 基底で測れば Ramsey 型の干渉計になる。

Kitaev の方法：多数決と継ぎ合わせ

$\varphi$ が書き切れない一般の場合、1回の測定では桁は確定しない。Kitaev は、各 $\theta_j=2^j\varphi\bmod1$（$j=0,1,\dots,t-1$）を粗く、ただし確実に推定し、それを継ぎ合わせる方法を示した²2A. Yu. Kitaev (1995), “Quantum measurements and the Abelian stabilizer problem,” arXiv:quant-ph/9511026。下の脚注へ閉じる。

補助の量子ビットに制御 $\hat U^{2^j}$ で位相 $2\pi\theta_j$ を書き戻した後、$H$ を当てて測ると $0$ が出る確率は $(1+\cos2\pi\theta_j)/2$、$\mathrm{diag}(1,-\mathrm{i})$ を挟んでから測ると $(1+\sin2\pi\theta_j)/2$ である。それぞれを $s$ 回くり返して頻度から $\cos2\pi\theta_j$ と $\sin2\pi\theta_j$ を推定すれば、角度 $2\pi\theta_j$ が推定できる。

継ぎ合わせ (i) は、第3部第8章で GHZ 状態の位相を $N$ 倍に増幅したときに残った「$N\theta$ は分かるが $\theta$ がどの周期にいるかは分からない」という曖昧さを、増幅率の小さい測定（$2^j$ の小さい段）の結果で1段ずつ解く手順になっている。増幅率の大きい測定は細かい桁を、小さい測定は周期の番号を受け持つ。

$\hat U$ の使用回数は、段 $j$ で $2s$ 回の測定に各 $2^j$ 回なので、合わせて $2s(2^t-1)$ 回である。到達する精度は $2^{-(t+2)}$ なので、誤差と使用回数の積は $s/2$ 程度の定数になり、$s$ は全体の失敗の確率 $\eta$ に対して $8\ln(4t/\eta)$ でよい。精度は使用回数に反比例し、比例係数に $\ln(t/\eta)$ の対数がつくだけである。