位相推定手順

次に、位相推定問題を解くための量子アルゴリズムである位相推定手順について説明します。

まず精度の低いウォームアップから始め、この手法の基本的な直感を説明します。 続いて、位相推定手順で使用される重要な量子演算である量子フーリエ変換と、その量子回路実装について説明します。 量子フーリエ変換を理解した後、位相推定手順を完全な一般性で記述し、その性能を分析します。

ウォームアップ：低精度による位相の近似

まず、位相推定問題に対して低精度の解を提供する、位相推定手順のいくつかの単純なバージョンから始めます。 これは、レッスンの後半で見る一般的な手順の背後にある直感を説明するのに役立ちます。

位相キックバックの利用

位相推定問題に対するシンプルなアプローチとして、求める値 $\theta$ について何かを学べる方法があります。それは位相キックバック現象に基づいています。 後で見るように、これは本質的に、レッスンの後半で説明する一般的な位相推定手順の1量子ビット版です。

位相推定問題への入力の一部として、演算 $U$ の量子回路が与えられています。 この回路の記述を使って、制御-$U$ 演算の回路を作成できます。次の図はこれを示しています（左に演算 $U$ を量子ゲートとして表し、右に制御-$U$ 演算を示しています）。

制御-$U$ 演算の量子回路を作成するには、まず $U$ の回路に制御量子ビットを追加し、$U$ の回路内のすべてのゲートをそのゲートの制御版に置き換えます。これにより、1つの新しい制御量子ビットが $U$ の回路内のすべてのゲートを効果的に制御します。 これにはすべてのゲートの制御版が必要ですが、ゲートセットに含まれていない場合でも、これらの制御演算の回路を常に構築できます。

次に、以下の回路を考えます。ここで、上の量子ビット以外のすべての量子ビットの入力状態 $\vert\psi\rangle$ は、$U$ の固有ベクトルである量子状態です。

この回路の測定結果の確率は、固有ベクトル $\vert\psi\rangle$ に対応する $U$ の固有値に依存します。 どのように依存するかを正確に決定するために、回路を詳しく分析しましょう。

回路の初期状態は

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

であり、最初のアダマールゲートはこの状態を次のように変換します。

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

次に、制御-$U$ 演算が実行され、状態は次のようになります。

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

$\vert\psi\rangle$ が固有値 $\lambda = e^{2\pi i\theta}$ を持つ $U$ の固有ベクトルであるという仮定を使うと、 この状態を次のように表すことができます。

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

ここで位相キックバック現象が観察されます。 ドイッチュのアルゴリズムやドイッチュ-ジョザアルゴリズムの場合とは少し異なります。クエリゲートを使っていないからですが、考え方は似ています。

最後に、2番目のアダマールゲートが実行されます。少し簡略化すると、この状態の次の式が得られます。

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

測定は以下の確率で結果 $0$ と $1$ を生じます。

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

$\theta$ の関数として、2つの可能な結果 $0$ と $1$ の確率をプロットしたものを示します。

当然ながら、2つの確率の合計は常に $1$ です。 $\theta = 0$ のとき、測定結果は常に $0$ となり、$\theta = 1/2$ のとき、測定結果は常に $1$ となることに注目してください。 つまり、測定結果から $\theta$ が正確に何であるかはわかりませんが、それに関するある情報が得られます。もし $\theta = 0$ または $\theta = 1/2$ のどちらかであることが保証されていれば、この回路からどちらが正しいかをエラーなしに学べます。

直感的には、回路の測定結果を $\theta$ の「1ビットの精度」での推測として考えることができます。 言い換えると、$\theta$ を2進数表記で書いて1ビットに丸めると、次のような数になります。

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

測定結果はビット $a$ の推測と見なすことができます。 $\theta$ が $0$ でも $1/2$ でもない場合、推測が間違える確率はゼロではありませんが、 $0$ または $1/2$ に近づくほど、エラーの確率は小さくなります。

この手順で2つのアダマールゲートが果たす役割を問うのは自然なことです。

• 最初のアダマールゲートは、制御量子ビットを $\vert 0\rangle$ と $\vert 1\rangle$ の均一な重ね合わせに設定します。これにより、位相キックバックが発生するとき、$\vert 0\rangle$ の状態ではなく $\vert 1\rangle$ の状態に対して発生し、測定結果に影響する相対的な位相差が生まれます。これをしなかった場合、位相キックバックがグローバルな位相を生じさせ、異なる測定結果の確率には何の影響も与えないでしょう。

• 2番目のアダマールゲートにより、干渉という現象を通じて数 $\theta$ について何かを学べます。2番目のアダマールゲートの前の上の量子ビットの状態は

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  であり、この状態を測定すると $0$ と $1$ をそれぞれ確率 $1/2$ で得ることになり、$\theta$ について何も教えてくれません。しかし、2番目のアダマールゲートを実行することで、$\theta$ が出力確率に影響するようになります。

位相の倍増

上の回路は位相キックバック現象を使って $\theta$ を1ビットの精度で近似します。 1ビットの精度で十分な状況もありますが、素因数分解にはそれよりもはるかに高い精度が必要です。 自然な疑問として、$\theta$ についてさらに多くを学ぶにはどうすればよいでしょうか？

非常に単純な方法の1つは、回路内の制御-$U$ 演算を次のような回路のようにこの演算の2つのコピーに置き換えることです。

制御-$U$ 演算の2つのコピーは、制御-$U^2$ 演算と等価です。 $\vert\psi\rangle$ が固有値 $\lambda = e^{2\pi i \theta}$ を持つ $U$ の固有ベクトルであれば、この状態は $U^2$ の固有ベクトルでもあり、今度は固有値 $\lambda^2 = e^{2\pi i (2\theta)}$ を持ちます。

したがって、このバージョンの回路を実行すると、$\theta$ が $2\theta$ に置き換えられる以外は、前と同じ計算を実行していることになります。 $\theta$ が $0$ から $1$ の範囲で変化したときの出力確率を示すプロットを示します。

これにより、$\theta$ に関するさらなる情報が得られます。 $\theta$ の2進数表現が

$$\theta = 0.a_1 a_2 a_3\cdots$$

であれば、$\theta$ を2倍にすることで2進数の小数点が1つ右にシフトされます。

$$2\theta = a_1. a_2 a_3\cdots$$

また、単位円を周回するにつれて $\theta = 1$ を $\theta = 0$ と同一視しているので、ビット $a_1$ は確率に影響せず、$\theta$ を2ビットに丸めた場合の2番目のビットの推測を効果的に得ていることになります。 たとえば、$\theta$ が $0$ または $1/4$ のどちらかであることが事前にわかっていれば、測定結果を完全に信頼してどちらかを判断できます。

ただし、この推定を元の（倍増していない）位相キックバック回路から学んだこととどのように統合して $\theta$ についての最も正確な情報を与えるかは、すぐには明確ではありません。 では、一歩下がって進め方を考えてみましょう。

2量子ビット位相推定

上で説明した2つのオプションを別々に検討するのではなく、次のように1つの回路に組み合わせましょう。

制御演算の後のアダマールゲートは削除され、測定はまだありません。 $\theta$ についてできる限り多くを学ぶためのオプションを検討しながら、回路にさらに追加していきます。

$\vert\psi\rangle$ が $U$ の固有ベクトルであるときにこの回路を実行すると、下の量子ビットの状態は回路全体を通じて $\vert\psi\rangle$ のままであり、位相が上の2量子ビットの状態にキックされます。 次の図を使って回路を注意深く分析しましょう。

状態 $\vert\pi_1\rangle$ は次のように表せます。

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

最初の制御-$U$ 演算が実行されると、$a_0$（上の量子ビット）が $1$ のとき固有値 $\lambda = e^{2\pi i\theta}$ が位相にキックされますが、$0$ のときはキックされません。 したがって、結果の状態を次のように表せます。

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

2番目と3番目の制御-$U$ ゲートも同様のことをしますが、$a_0$ ではなく $a_1$ に対して、$\theta$ が $2\theta$ に置き換えられます。 結果の状態を次のように表せます。

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

2進数文字列 $a_1 a_0$ を2進数表記の整数 $x \in \{0,1,2,3\}$（つまり $x = 2 a_1 + a_0$）として考えると、この状態を次のように表せます。

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

私たちの目標は、この状態から $\theta$ についてできる限り多くの情報を抽出することです。

ここで特殊なケースを考えます。ある整数 $y\in\{0,1,2,3\}$ に対して $\theta = \frac{y}{4}$ であることが保証されている場合です。 言い換えると、$\theta\in \{0, 1/4, 1/2, 3/4\}$ であり、この数を2ビットの2進数表記で正確に表せます（$0.00$、$0.01$、$0.10$、または $0.11$）。 一般には $\theta$ はこれら4つの値のいずれかではないかもしれませんが、この特殊なケースを考えることで、一般的な場合に $\theta$ に関する情報を最も効果的に抽出する方法を見つけるのに役立ちます。

まず、各可能な値 $y \in \{0, 1, 2, 3\}$ に対して2量子ビット状態ベクトルを定義します。

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

指数関数を簡略化すると、これらのベクトルを次のように書けます。

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

これらのベクトルは直交しています。つまり、任意のペアを選んで内積を計算すると $0$ になります。 各ベクトルは単位ベクトルでもあるため、$\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ は正規直交基底です。 したがって、これらを完全に識別できる測定が存在することがすぐにわかります。つまり、どれか1つが与えられてもどれかわからない場合でも、エラーなしにどれであるかを特定できます。

量子回路でこのような識別を行うには、まず標準基底状態を上記の4つの状態に変換するユニタリ演算 $V$ を定義できます。

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

$V$ を $4\times 4$ 行列として書き下すには、$V$ の列を状態 $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ とするだけです。

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

これは特別な行列であり、以前に見たことのある読者もいるでしょう。 これは $4$ 次元の離散フーリエ変換に関連する行列です。 この事実を踏まえて、$V$ ではなく $\mathrm{QFT}_4$ という名前で呼ぶことにします。 $\mathrm{QFT}$ という名前は量子フーリエ変換（quantum Fourier transform）の略で、本質的には離散フーリエ変換をユニタリ演算として見たものです。 量子フーリエ変換については、まもなくより詳細かつ一般的に説明します。

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

この演算の逆を実行することで逆方向に進み、状態 $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ を標準基底状態 $\vert 0\rangle,\ldots,\vert 3\rangle$ に変換できます。 これを実行すれば、$\theta = y/4$ として $\theta$ を記述する値 $y\in\{0,1,2,3\}$ を測定によって学べます。 これを実現する量子回路の図を示します。

まとめると、$y\in\{0,1,2,3\}$ の $y/4$ に対して $\theta = y/4$ のときにこの回路を実行すると、測定直前の状態は $\vert \psi\rangle \vert y\rangle$（$y$ を2ビットの2進数文字列としてエンコード）になり、測定によってエラーなしに値 $y$ が明らかになります。

この回路は $\theta \in \{0,1/4,1/2,3/4\}$ という特殊なケースに動機付けられていますが、任意の $U$ と $\vert \psi\rangle$、したがって任意の $\theta$ の選択で実行できます。 この回路が $\theta$ の任意の選択に対して生成する出力確率のプロットを示します。

これはレッスンの前半で説明した1量子ビット版に比べて明らかな改善です。 完璧ではありません。間違った答えを出すこともあります。しかし、答えは $y/4$ が $\theta$ に近い値の $y$ に向けて大きく偏っています。 特に、最も可能性の高い結果は常に $\theta$ に最も近い $y/4$ の値に対応し（前と同様に $\theta = 0$ と $\theta = 1$ を同一視して）、プロットからこの $x$ の最も近い値は常に約 $40\%$ を超える確率で現れることがわかります。 $\theta$ がちょうど2つの値の中間にある場合、たとえば $\theta = 0.375$ の場合、2つの等しく近い $y$ の値は等しく可能性が高くなります。

多数量子ビットへの一般化の準備

1つの制御量子ビットではなく2つの制御量子ビットを使用することで得られた改善を踏まえ、$4$次元量子フーリエ変換の逆変換と組み合わせると、さらなる制御量子ビットの追加という一般化を自然に検討できます。 これを行うと、一般的な位相推定手続きが得られます。 これがどのように機能するかをすぐに見ていきますが、正確に記述するためには、量子フーリエ変換をより一般的な形で議論し、他の次元でどのように定義されるか、また量子回路でそれ（またはその逆変換）をどのように実装できるかを理解する必要があります。

量子フーリエ変換

量子フーリエ変換は、任意の正の整数次元 $N$ に対して定義できるユニタリ演算です。 このセクションでは、この演算がどのように定義されるか、そして $N = 2^m$ のときに $m$ 量子ビット上でコスト $O(m^2)$ の量子回路によってどのように実装できるかを見ていきます。

量子フーリエ変換を記述する行列は、離散フーリエ変換として知られる $N$ 次元ベクトルへの類似演算から導出されます。 この演算はさまざまな観点から考えることができます。 たとえば、離散フーリエ変換を純粋に抽象的な数学的観点から線形写像として考えることができます。 あるいは、計算的な観点から考えることもできます。この場合、複素数の $N$ 次元ベクトルが与えられ（実部と虚部を二進表記でエンコードするとします）、離散フーリエ変換を適用して得られる $N$ 次元ベクトルを計算することが目標です。 ここでは3番目の観点、すなわちこの変換を量子系で実行できるユニタリ演算として捉えることに焦点を当てます。

与えられた入力ベクトルに対して離散フーリエ変換を計算する効率的なアルゴリズムとして、高速フーリエ変換があります。 これは信号処理やその他多くの分野で応用されており、これまでに発見されたアルゴリズムの中でも最も重要なものの1つと多くの人が考えています。 実際、$N$ が2の冪乗のときに学習する量子フーリエ変換の実装は、高速フーリエ変換を可能にするのとまったく同じ基本構造に基づいています。

量子フーリエ変換の定義

量子フーリエ変換を定義するにあたり、まず各正の整数 $N$ に対して複素数 $\omega_N$ を次のように定義します。

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

これは複素単位円上の数であり、$1$ から出発して反時計回りに $2\pi/N$ ラジアン、すなわち円周の $1/N$ の弧長だけ進んだ位置にあります。いくつかの例を示します。

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

これで $N$ 次元量子フーリエ変換を定義できます。これは $N\times N$ 行列で記述され、その行と列は標準基底状態 $\vert 0\rangle,\ldots,\vert N-1\rangle$ に対応します。 位相推定では $N = 2^m$ が2の冪乗の場合のみ必要ですが、この演算は任意の正の整数 $N$ に対して定義できます。

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

すでに述べたように、これは $N$ 次元離散フーリエ変換に対応する行列です。 この行列の定義では先頭の $1/\sqrt{N}$ の係数が省略されることも多いですが、ユニタリ行列を得るためにはこれを含める必要があります。

$N$ の小さな値に対する量子フーリエ変換を行列として示します。

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

特に、$\mathrm{QFT}_2$ はアダマール演算の別名であることに注意してください。

ユニタリ性

$N$ の任意の選択に対して $\mathrm{QFT}_N$ がユニタリであることを確認しましょう。 これを示す一つの方法は、その列が正規直交基底を形成することを示すことです。 列番号 $y$（$y = 0$ から $y = N-1$ まで）に対応するベクトルを次のように定義します。

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

これらのベクトル間の内積を取ると、次の式が得られます。

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

このような和は、等比数列の最初の $N$ 項の和に関する次の公式を用いて評価できます。

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

具体的には、$\alpha = \omega_N^{y-z}$ のときにこの公式を使用できます。 $y = z$ のとき $\alpha = 1$ なので、公式を使って $N$ で割ると

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

$y\neq z$ のとき $\alpha \neq 1$ なので、公式より次が分かります。

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

これは $\omega_N^N = e^{2\pi i} = 1$ であるため $\omega_N^{N(y-z)} = 1^{y-z} = 1$ となり分子がゼロになる一方、$\omega_N^{y-z} \neq 1$ より分母はゼロではないことによります。 直感的に言えば、単位円上に均等に分布した点の総和を取っており、それらが打ち消し合って $0$ になるということです。

したがって、$\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ が正規直交集合であることが示されました。

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

これにより $\mathrm{QFT}_N$ がユニタリであることが明らかになります。

制御位相ゲート

量子回路で量子フーリエ変換を実装するには、制御位相ゲートを使用する必要があります。 位相演算とは、任意の実数 $\alpha$ に対して次の形の単一量子ビットユニタリ演算であることを思い出してください。

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

このゲートの制御版は次の行列を持ちます。

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

この制御ゲートでは、どちらの量子ビットが制御でどちらがターゲットであるかは実際には問題になりません。なぜなら2つの可能性は等価だからです。 量子回路図でこのゲートを表すには、次のいずれかの記号を使用できます。

3番目の形式では、都合に応じて制御線の側面または下側の制御の下に $\alpha$ のラベルが付くこともあります。

$N = 2^m$ かつ $m\geq 2$ のときに量子フーリエ変換を実行するには、$m$ 量子ビット上で次の作用を持つ演算を実行する必要があります。

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

ここで $a$ は1ビットであり、$y \in \{0,\ldots,2^{m-1} - 1\}$ は $m-1$ ビットの二進表記でエンコードされた数です。 これは制御位相ゲートを使って、$m=5$ の次の例を一般化することで実現できます。

一般に、$m\geq 2$ の任意の選択に対して、ビット $a$ に対応する最上位の量子ビットを制御として考えることができます。位相ゲート $P_{\alpha}$ の $\alpha$ は、$y$ の最下位ビットに対応する量子ビットの $\alpha = \pi/2^{m-1}$ から $y$ の最上位ビットに対応する量子ビットの $\alpha = \frac{\pi}{2}$ まで変化します。 これらの制御位相ゲートはすべて互いに可換であり、任意の順序で実行できます。

QFTの回路実装

次元 $N = 2^m$ が2の冪乗の場合に、量子回路で量子フーリエ変換をどのように実装できるかを見ていきます。 実際、量子フーリエ変換を実装する方法は複数ありますが、これはおそらく知られている中で最も単純な方法です。 量子フーリエ変換を量子回路で実装する方法が分かれば、その逆変換の実装も簡単です。各ゲートをその逆（同等に言えば、共役転置）に置き換え、逆順にゲートを適用すれば良いのです。 ユニタリゲートのみで構成された量子回路はすべてこの方法で逆変換できます。

実装は再帰的な性質を持つため、そのように説明するのが最も自然です。 基底ケースは $m=1$ であり、このとき量子フーリエ変換はアダマール演算です。

$m \geq 2$ の $m$ 量子ビット上で量子フーリエ変換を実行するには、次のステップを実行します。$x\in\{0,\ldots,2^{m-1} - 1\}$ を二進表記で $m-1$ ビットにエンコードされた整数、$a$ を単一ビットとして、$\vert x \rangle \vert a\rangle$ の形の標準基底状態に対する各ステップの作用を説明します。

1. まず、下位/左側の $m-1$ 量子ビットに $2^{m-1}$ 次元量子フーリエ変換を適用して次の状態を得ます。

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   これは、単一量子ビットでのアダマール演算を基底ケースとして、1量子ビット少ない場合の方法を再帰的に適用することで行います。

2. 上位/右側の量子ビットを制御として使用し、残りの $m-1$ 量子ビットの各標準基底状態 $\vert y\rangle$ に位相 $\omega_{2^m}^y$ を注入して（上記の方法で）次の状態を得ます。

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. 上位/右側の量子ビットにアダマールゲートを適用して次の状態を得ます。

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. 最下位ビットが最上位ビットになり、他のすべてが上位/右側にシフトされるように量子ビットの順序を入れ替えます。

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

たとえば、$N = 32 = 2^5$ の場合に得られる回路を示します。 この図では、明確にするために量子ビットに（入力の）標準基底ベクトル $\vert x\rangle \vert a\rangle$ と（出力の）$\vert b\rangle \vert y\rangle$ に対応する名前が付けられています。

解析

上記の回路が $2^m$ 次元量子フーリエ変換を実装していることを検証するために必要な重要な公式は次のとおりです。

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

この公式は任意の整数 $a,$ $b,$ $x,$ $y$ に対して成り立ちますが、$a,b\in\{0,1\}$ かつ $x,y\in\{0,\ldots,2^{m-1}-1\}$ の場合のみ使用します。 右辺の指数の積を展開することで確認できます。

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

ここで2番目の等号は次の観察を利用しています。

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

$2^m$ 次元量子フーリエ変換は、すべての $u\in\{0,\ldots,2^m - 1\}$ に対して次のように定義されます。

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

$u$ と $v$ を

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

（$a,b\in\{0,1\}$ かつ $x,y\in\{0,\ldots,2^{m-1} - 1\}$）と書くと、次が得られます。

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

最後に、標準基底状態 $\vert x \rangle \vert a\rangle$ と $\vert b \rangle \vert y \rangle$ を $\{0,\ldots,2^m-1\}$ の範囲の整数の二進エンコードとして考えると、

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

上記の回路が必要な演算を実装していることが分かります。 この量子フーリエ変換の実装方法が驚くべきものに見えるとすれば、それは実際にそうだからです。これは本質的に量子回路の形での高速フーリエ変換です。

最後に、上記の回路で使用されるゲートの数を数えましょう。 制御位相ゲートは前のレッスンで議論した標準ゲートセットにはありませんが、まずこれを無視して、それぞれを単一のゲートとして数えます。

$m$ の各選択肢に必要なゲート数を $s_m$ とします。 $m=1$ のとき、量子フーリエ変換は単にアダマール演算なので、

$$s_1 = 1.$$

$m\geq 2$ のとき、上記の回路では $m-1$ 量子ビットの量子フーリエ変換に $s_{m-1}$ ゲート、$m-1$ 個の制御位相ゲート、1つのアダマールゲート、$m-1$ 個のスワップゲートが必要なので、

$$s_m = s_{m-1} + (2m - 1).$$

総和を取ることで閉形式の表現が得られます。

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

実際には、この方法が記述するほど多くのスワップゲートは必要ではありません。 ゲートを少し並べ替えると、すべてのスワップゲートを右側に押し出し、必要なスワップゲートの数を $\lfloor m/2\rfloor$ に削減できます。 漸近的に言えば、これは大きな改善ではありません。$\mathrm{QFT}_{2^m}$ を実行するための回路のサイズは依然として $O(m^2)$ です。

標準ゲートセットのゲートのみを使って量子フーリエ変換を実装したい場合は、各制御位相ゲートをセットのゲートで構築または近似する必要があります。 必要な数は必要な精度によって異なりますが、$m$ の関数としての総コストは二次のままです。

実際、$\alpha$ が非常に小さいとき $P_{\alpha}$ は恒等演算に非常に近いという事実を利用することで、制御位相ゲートのほとんどを省略しても精度の損失はほとんどないため、二次より少ないゲート数で量子フーリエ変換をかなり精密に近似することが可能です。

一般的な手続きと解析

いよいよ位相推定手続きを一般的な形で検討します。 上記で考えた2量子ビット版の位相推定を、次の図が示す自然な方法で拡張することが基本的なアイデアです。

各新しい制御量子ビットを上部に追加するたびに、ユニタリ演算 $U$ の実行回数が2倍になることに注目してください。 これは、各制御ユニタリ演算の $U$ の冪によって図中に示されています。

制御-$U^k$ 演算を何らかの $k$ の選択に対して実装する最も単純な方法は、単に制御-$U$ 演算を $k$ 回繰り返すことです。 この方法が採用される場合、制御量子ビットの追加が回路のサイズに大きく寄与することを認識しなければなりません。$m$ 個の制御量子ビットがある場合（図が示すように）、合計で $2^m - 1$ コピーの制御-$U$ 演算が必要です。 つまり、$m$ を増やすにつれて大きな計算コストが発生しますが、後に見るように、$\theta$ のより正確な近似も得られます。

ただし、一部の $U$ の選択については、単に $k$ 回繰り返す方法よりも効率的に演算 $U^k$ を実装する回路を構成できる場合があることに注意することが重要です。 これについては、後のレッスンの整数因数分解の文脈で具体的な例を見ます。前のレッスンで議論したモジュラー冪乗の効率的なアルゴリズムが役に立ちます。

次に、上記の回路を解析しましょう。 逆量子フーリエ変換の直前の状態は次のようになります。

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

特殊なケース

$m=2$ のケースで行ったことと同様に、まず $y\in\{0,\ldots,2^m-1\}$ に対して $\theta = y/2^m$ となる特殊なケースを考えます。 この場合、逆量子フーリエ変換の前の状態は次のように書き直すことができます。

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

したがって、逆量子フーリエ変換を適用すると、状態は

$$\vert\psi\rangle \vert y\rangle$$

となり、測定によって $y$（2進数で符号化）が得られます。

確率の上下界

$\theta$ が $y/2^m$（$y$ は整数）という形を取らない他の値の場合、測定結果は確定的ではありませんが、異なる結果の確率に対して上下界を証明することができます。 以下では、$0\leq \theta < 1$ を満たす任意の $\theta$ を考えます。

逆量子フーリエ変換が実行された後、回路の状態は次のようになります。

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

したがって、上位 $m$ 個の量子ビットに対して測定を行うと、各結果 $y$ は次の確率で観測されます。

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

これらの確率をより詳しく理解するために、以前に見た等比数列の初項から $N$ 項の和の公式を利用します。

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

$p_y$ の式に現れる和を、$\alpha = e^{2\pi i (\theta - y/2^m)}$ と置くことで簡略化できます。 得られる結果は以下の通りです。

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

したがって、$\theta = y/2^m$ の場合は $p_y = 1$（この特殊ケースの考察からすでにわかっていた通り）であり、$\theta \neq y/2^m$ の場合は

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2$$

となります。

単位円上の弧長と弦長の関係を考えることで、これらの確率についてさらに詳しく知ることができます。 以下の図は、任意の実数 $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$ に対して必要な関係を示しています。

まず、弦長（青で描かれている）は弧長（紫で描かれている）より大きくなることはあり得ません。

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

逆方向でこれらの長さを関連付けると、弧長と弦長の比が最大になるのは $\delta = \pm 1/2$ のときであり、この場合の比は円の半周を直径で割ったもの、すなわち $\pi/2$ となります。 したがって、

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

となり、

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert$$

が成り立ちます。

これらの関係に基づく解析により、以下の2つの事実が明らかになります。

1. $\theta$ を実数とし、$y\in \{0,\ldots,2^m-1\}$ が

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}$$

   を満たすと仮定します。

   これは、$y/2^m$ が $\theta$ に対する最善の $m$ ビット近似であるか、あるいは $y/2^m$ と $(y-1)/2^m$ または $(y+1)/2^m$ のちょうど中間にあること、すなわち $\theta$ に対する2つの最善近似の一方であることを意味します。

   この場合、$p_y$ はかなり大きくなることを証明します。 考えている仮定から $\vert 2^m \theta - y \vert \leq 1/2$ が導かれるので、弧長と弦長の関係に関する上記の2番目の観察を使って次のように結論付けることができます。

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   また、弧長と弦長に関する1番目の観察を使って次のように結論付けることもできます。

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   この2つの不等式を $p_y$ に適用すると、

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405$$

   が明らかになります。

   これにより、前述の $m=2$ の位相推定において最善の結果が $40\%$ を超える確率で生じるという観察が説明されます。 正確には $40\%$ ではなく $4/\pi^2$ であり、実際にこの下界はすべての $m$ の選択に対して成立します。

2. 今度は、$y\in \{0,\ldots,2^m-1\}$ が

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}$$

   を満たすと仮定します。

   これは、$\theta$ と $y/2^m$ の間に $\theta$ に対するより良い近似 $z/2^m$ が存在することを意味します。

   今度は $p_y$ がそれほど大きくならないことを証明します。 単位円上の任意の2点の絶対値の差は最大でも $2$ であるという事実から、

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2$$

   という単純な観察から始めることができます。

   また、今度は $p_y$ の分子ではなく分母に対して上記の弧長と弦長の2番目の観察を使って、

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}$$

   と結論付けることができます。

   2つの不等式を合わせると、

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}$$

   が明らかになります。

   この上界は目的には十分ですが、かなり粗い推定であることに注意してください。実際の確率は通常 $1/4$ よりもはるかに低くなります。

この解析から重要な結論として、$\theta$ への非常に近い近似は高い確率で生じるということが言えます。すなわち、最善の $m$ ビット近似が $40\%$ を超える確率で得られる一方で、$2^{-m}$ 以上ずれた近似は生じにくく、その確率は $25\%$ で上から抑えられます。

これらの保証が得られることにより、位相推定の手順を複数回繰り返して $\theta$ に関する統計的な証拠を集めることで、確信度を高めることができます。 ここで重要なのは、下部の量子ビット群の状態 $\vert\psi\rangle$ は位相推定の手順によって変化しないため、何度でも手順を実行するために使用できるという点です。 特に、回路を実行するたびに $40\%$ を超える確率で $\theta$ に対する最善の $m$ ビット近似が得られ、$2^{-m}$ 以上ずれる確率は $25\%$ で上から抑えられます。 回路を複数回実行し、最も頻繁に現れた結果を採用すれば、最も頻繁に現れた結果が最大でも $25\%$ の確率でしか生じないものである可能性は極めて低くなります。 その結果、$\theta$ の値から $1/2^m$ 以内の近似 $y/2^m$ が得られる可能性が非常に高くなります。 実際、$1/2^m$ 以上ずれる低い確率は、手順を繰り返す回数に対して指数的に減少します。

以下は、$m = 3$ および $m=4$ の場合について、$\theta$ の関数として3つの連続する $y$ の値に対する確率を示した2つのグラフです。 （明瞭さのために3つの結果のみを示しています。他の結果の確率は、同じ基本的な関数を周期的にシフトすることで得られます。）