量子フーリエ変換と位相推定

量子フーリエ変換 $∣ x ⟩ \mapsto N^{- 1/2} \sum_{y} e^{2 π i x y / N} ∣ y ⟩$ の作用を計算し、位相推定で各測定結果が得られる確率 $\frac{1}{N} \sum_{k} e^{2 π ik (φ - y / N)}^{2}$ を求められる

前提

量子ゲートと量子回路の計算（大学院物理量子情報・量子計算）
離散フーリエ変換の計算と逆変換（大学院数学フーリエ解析）

この技能までの道筋（118 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
対角化と行列の累乗（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
三角比の定義と値（数学I 図形と計量）
内積となす角（数学C ベクトル）
内積空間とグラム・シュミットの直交化（大学数学線形代数）
対称行列の直交対角化（大学数学線形代数）
2 次形式の標準形と符号（大学数学線形代数）
エルミート行列とエルミート形式の符号（大学数学線形代数）
音の伝わり方と大きさ・高さ（中学理科物理分野の用語と知識）
音の振動数と波形（中学理科光と音）
比例・反比例の式とグラフ（中学数学関数）
光子のエネルギーと運動量（高校物理原子）
根号の乗除と加減（中学数学数と式）
分母の有理化（中学数学数と式）
乗法公式・分配法則を使う根号の式の展開（中学数学数と式）
根号を含む式の計算と分母の有理化（数学I 数と式）
重力と力の大きさ（中学理科力のはたらき）
2 力のつり合いと作用・反作用（中学理科力のはたらき）
力の種類とはたらき（中学理科物理分野の用語と知識）
重力・垂直抗力・張力の性質（高校物理力と運動（知識））
慣性の法則と力のつり合い（高校物理力と運動（知識））
力の分解と質点のつり合い（高校物理力と運動）
静止摩擦力・最大摩擦力・動摩擦力（高校物理力と運動（知識））
静止摩擦力と動摩擦力（高校物理力と運動）
仕事（高校物理仕事・エネルギーと運動量）
運動エネルギーと仕事の関係（高校物理仕事・エネルギーと運動量）
物質波（ド・ブロイ波）（高校物理原子）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
$sin x / x$ の極限（数学III 極限）
三角関数の導関数（数学III 微分法）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の計算（数学II 微分法と積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
広義積分（大学数学微分積分）
波動関数の規格化と確率解釈（大学物理量子力学（1 次元の問題））
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
複素数と 2 次方程式の虚数解（数学II 複素数と方程式）
演算子と期待値（大学物理量子力学（1 次元の問題））
スピン 1/2 とパウリ行列（大学物理量子力学（角運動量・近似法））
密度行列と混合状態（大学院物理量子情報・量子計算）
テンソル積と部分トレース（大学院物理量子情報・量子計算）
量子ゲートと量子回路の計算（大学院物理量子情報・量子計算）
極形式と積・商（数学C 複素数平面）
ド・モアブルの定理（数学C 複素数平面）
方程式 $z^{n} = a$ の解（数学C 複素数平面）
$1 + cos θ + i sin θ$ の極形式（数学C 複素数平面）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
複素数平面と絶対値・共役複素数（数学C 複素数平面）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
$z^{n} = a$ の解を使った和と積（数学C 複素数平面）
（等差）×（等比）の数列の和（数学B 数列）
離散フーリエ変換の計算と逆変換（大学院数学フーリエ解析）

説明

量子フーリエ変換（QFT）は、 $t$ 量子ビットの計算基底 $∣ x ⟩$ （ $x = 0, 1, \dots, N - 1$ 、 $N = 2^{t}$ ）を $∣ x ⟩ \mapsto N^{- 1/2} \sum_{y = 0}^{N - 1} e^{2 π i x y / N} ∣ y ⟩$ と写すユニタリ変換で、状態の振幅に離散フーリエ変換をほどこす働きをします。位相推定は、ユニタリ $U$ の固有状態 $∣ u ⟩$ （ $U ∣ u ⟩ = e^{2 π i φ} ∣ u ⟩$ 、 $0 \leq φ < 1$ ）の位相 $φ$ を、制御 $U^{2^{j}}$ と逆 QFT を使って $t$ ビットの 2 進数として読み出す回路です。この技能では、測定結果 $y$ が得られる確率 $P (y) = \frac{1}{N} \sum_{k = 0}^{N - 1} e^{2 π ik (φ - y / N)}^{2}$ を計算できるようにします。これはショアのアルゴリズムやエネルギー固有値の推定の中心となる計算です。

なぜそうしてよいのか

QFT が本当にユニタリであることは、1 の $N$ 乗根の和の性質から分かります。 $∣ x ⟩$ と $∣ x^{'} ⟩$ の像の内積は $\frac{1}{N} \sum_{y} e^{2 π i (x - x^{'}) y / N}$ で、 $x = x^{'}$ なら $1$ 、 $x \neq = x^{'}$ （ $0 < ∣ x - x^{'} ∣ < N$ ）なら公比 $e^{2 π i (x - x^{'}) / N} \neq = 1$ の等比数列の和が $\frac{1 - e ^{2 π i (x - x^{'})}}{1 - e ^{2 π i (x - x^{'}) / N}} = 0$ になるので $0$ です。振幅で書くと、 $\sum_{x} a_{x} ∣ x ⟩$ は $\sum_{y} b_{y} ∣ y ⟩$ 、 $b_{y} = N^{- 1/2} \sum_{x} a_{x} e^{2 π i x y / N}$ に写り、逆 QFT は指数の符号を負にした $∣ y ⟩ \mapsto N^{- 1/2} \sum_{x} e^{- 2 π i x y / N} ∣ x ⟩$ です。

位相推定では、 $t$ 個の制御ビットをそれぞれ $∣ + ⟩ = \frac{∣0 ⟩ + ∣1 ⟩}{2}$ にし、 $j$ 番目のビット（ $j = 0, \dots, t - 1$ ）で制御 $U^{2^{j}}$ を標的 $∣ u ⟩$ に作用させます。 $U^{2^{j}} ∣ u ⟩ = e^{2 π i 2^{j} φ} ∣ u ⟩$ なので、位相キックバックにより $j$ 番目のビットは $\frac{∣0 ⟩ + e ^{2 π i 2^{j} φ} ∣1 ⟩}{2}$ になります。 $k = \sum_{j} k_{j} 2^{j}$ と 2 進展開してこれらのテンソル積を展開すると、各 $∣ k ⟩$ の位相は $\prod_{j} e^{2 π i k_{j} 2^{j} φ} = e^{2 π ik φ}$ なので、制御側は
$\frac{1}{N} k = 0 \sum N - 1 e^{2 π ik φ} ∣ k ⟩$
になります（標的 $∣ u ⟩$ は変化せず、以後は省く）。これは $N φ$ が整数なら、ちょうど $∣ N φ ⟩$ の QFT です。そこで逆 QFT をかけると、 $∣ y ⟩$ の振幅は
$c_{y} = \frac{1}{N} k = 0 \sum N - 1 e^{2 π ik φ} e^{- 2 π ik y / N} = \frac{1}{N} k = 0 \sum N - 1 e^{2 π ik δ}, δ = φ - \frac{y}{N}$
となり、 $P (y) = ∣ c_{y} ∣^{2}$ です。

この和は公比 $e^{2 π i δ}$ の等比数列の和です。 $0 \leq φ < 1$ 、 $0 \leq \frac{y}{N} < 1$ なので $- 1 < δ < 1$ で、公比が $1$ になるのは $δ = 0$ のときだけです。 $δ = 0$ （すなわち $N φ$ が整数で $y = N φ$ ）なら各項が $1$ で $P = 1$ 、つまり位相が $t$ ビットで正確に書けるときは確実に $y = N φ$ が出ます。 $δ \neq = 0$ なら、 $∣1 - e^{i α} ∣ = 2∣ sin \frac{α}{2} ∣$ を使って
$P (y) = \frac{1}{N ^{2}} \frac{1 - e ^{2 π i N δ}}{1 - e ^{2 π i δ}}^{2} = \frac{sin ^{2} ( π N δ )}{N ^{2} sin ^{2} ( π δ )}$
となり、 $y / N$ が $φ$ に近いほど大きい確率で得られます。特に $N δ$ が整数で $δ \neq = 0$ （ $N φ$ が整数で $y \neq = N φ$ ）なら分子が $0$ で $P (y) = 0$ となり、正しい $y = N φ$ 以外は決して出ないことと合っています。

手順

固有値を $e^{2 π i φ}$ （ $0 \leq φ < 1$ ）の形に書き、制御ビット数 $t$ から $N = 2^{t}$ を決める
制御操作の後の制御レジスタの状態を書く: $\frac{1}{N} \sum_{k = 0}^{N - 1} e^{2 π ik φ} ∣ k ⟩$ （ $j$ 番目のビットが $U^{2^{j}}$ を制御し、位相キックバックで $e^{2 π i 2^{j} φ}$ が付く）
逆 QFT $∣ k ⟩ \mapsto N^{- 1/2} \sum_{y} e^{- 2 π ik y / N} ∣ y ⟩$ を作用させ、知りたい $y$ の振幅 $c_{y} = \frac{1}{N} \sum_{k = 0}^{N - 1} e^{2 π ik δ}$ （ $δ = φ - y / N$ ）を書く
$δ = 0$ なら $c_{y} = 1$ で $P (y) = 1$ 。 $δ \neq = 0$ なら等比数列の和で $P (y) = \frac{s i n ^{2} ( π N δ )}{N ^{2} s i n ^{2} ( π δ )}$ とまとめる（ $N δ$ が 0 でない整数なら $P (y) = 0$ ）
必要なら半角の公式などで三角関数の値を計算し、確率を正確な値にする

例題

1 量子ビットのユニタリ $U = (10 0 e^{iπ /4})$ の固有状態 $∣1 ⟩$ （ $U ∣1 ⟩ = e^{2 π i φ} ∣1 ⟩$ 、 $φ = \frac{1}{8}$ ）を標的とし、制御ビットを $t = 2$ 個（ $N = 4$ ）用いる位相推定を行う。制御レジスタは $∣ k ⟩$ （ $k = k_{0} + 2 k_{1}$ ）で表し、 $j$ 番目の制御ビット $k_{j}$ が $U^{2^{j}}$ を制御する。制御操作の後に逆量子フーリエ変換 $∣ k ⟩ \mapsto \frac{1}{2} \sum_{y = 0}^{3} e^{- 2 π ik y /4} ∣ y ⟩$ を作用させてから制御レジスタを測定するとき、測定結果が $y = 0$ となる確率を求めよ。

例題の解答

手順 1: $φ = \frac{1}{8}$ 、 $N = 4$ 。

手順 2: 制御操作の後の制御レジスタは $\frac{1}{2} \sum_{k = 0}^{3} e^{2 π ik /8} ∣ k ⟩ = \frac{1}{2} \sum_{k = 0}^{3} e^{iπ k /4} ∣ k ⟩$ 。

手順 3: $y = 0$ なので $δ = φ - \frac{0}{4} = \frac{1}{8}$ で、振幅は
$c_{0} = \frac{1}{4} k = 0 \sum 3 e^{2 π ik /8} .$

手順 4: $δ = \frac{1}{8} \neq = 0$ なので、等比数列の和から
$P (0) = \frac{sin ^{2} ( π \cdot 4 \cdot \frac{1}{8} )}{4 ^{2} sin ^{2} ( \frac{π}{8} )} = \frac{sin ^{2} \frac{π}{2}}{16 sin ^{2} \frac{π}{8}} = \frac{1}{16 sin ^{2} \frac{π}{8}} .$

手順 5: 半角の公式より $sin^{2} \frac{π}{8} = \frac{1 - c o s \frac{π}{4}}{2} = \frac{2 - 2}{4}$ 。よって
$P (0) = \frac{1}{4 ( 2 - 2 )} = \frac{2 + 2}{4 ( 4 - 2 )} = \frac{2 + 2}{8} (\approx 0.427) .$
（ $y = 1$ も $δ = - \frac{1}{8}$ で同じ確率になり、真の値 $φ = \frac{1}{8}$ をはさむ 2 つの結果 $y / N = 0, \frac{1}{4}$ が合わせて約 $85%$ を占める。）

答え: $\frac{2 + 2}{8}$

よくある誤り

逆 QFT の指数の符号を QFT と同じ正のまま使い、 $c_{y} = \frac{1}{N} \sum_{k} e^{2 π ik (φ + y / N)}$ としてしまう誤り。制御レジスタの位相 $e^{2 π ik φ}$ を打ち消すには負の符号が必要で、正しくは $c_{y} = \frac{1}{N} \sum_{k} e^{2 π ik (φ - y / N)}$ （このとき $N φ$ が整数なら $y = N φ$ が確率 $1$ で出る）。
規格化を $\frac{1}{N}$ で 1 回分しか付けず、 $P (y) = \frac{1}{N} \sum_{k} e^{2 π ik δ}^{2}$ としてしまう誤り。初めの重ね合わせと逆 QFT で $\frac{1}{N}$ が 2 回かかるので、正しくは $P (y) = \frac{1}{N ^{2}} \sum_{k} e^{2 π ik δ}^{2}$ （ $δ = 0$ で $P = 1$ になるかで確かめられる）。
まとめた式の分子と分母を取り違え、 $P (y) = \frac{s i n ^{2} ( π δ )}{N ^{2} s i n ^{2} ( π N δ )}$ としてしまう誤り。等比数列の和の分子 $1 - e^{2 π i N δ}$ が $N$ 倍の角に対応するので、正しくは $P (y) = \frac{s i n ^{2} ( π N δ )}{N ^{2} s i n ^{2} ( π δ )}$ （ $δ \neq = 0$ とする）。
$δ = 0$ のときにも $\frac{s i n ^{2} ( π N δ )}{N ^{2} s i n ^{2} ( π δ )}$ に代入して $\frac{0}{0}$ で行き詰まる、または $0$ としてしまう誤り。分母が $0$ になる場合は公比が $1$ で等比数列の和の公式が使えないので、正しくは元の和に戻って $\frac{1}{N} \sum_{k = 0}^{N - 1} 1 = 1$ 、すなわち $P (y) = 1$ 。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
ユニタリ演算子 $U$ と、その固有状態 $∣ u ⟩$ （ $U ∣ u ⟩ = e^{2 π i φ} ∣ u ⟩$ , $φ = \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 π i φ k} ∣ k ⟩ ∣ u ⟩$ とした後、制御レジスタに逆量子フーリエ変換 $∣ k ⟩ \mapsto \frac{1}{N} \sum_{y = 0}^{N - 1} e^{- 2 π ik y / N} ∣ y ⟩$ を作用させて計算基底で測定する。測定結果が $y = 0$ となる確率を、根号を含む正確な値で求めよ。