文献あり

量子コンピュータにおける素因数分解(3): 量子フーリエ変換

117

はじめに

この記事は量子コンピュータによる素因数分解のアルゴリズムである「Shorのアルゴリズム」の解説記事第3回目です。1,2回目は以下：

第3回は量子フーリエ変換（Quantum Fourier Transform, QFT）に関して書きます。前回導入したべき剰余の計算
$\begin{array}{r} a^{x} mod N \end{array}$
を行う量子回路と共に、Shorのアルゴリズムにおいて中心的な役割を担います。

本記事ではフーリエ変換の基礎知識はあるものとして話を進めます（※深い知識は必要ないです。定義+αくらい知っていれば十分です）。ご了承ください。

本記事はRef.1を参考にしています。

量子フーリエ変換（QFT）とは

以下の変換を行う量子回路を考えます：

$\begin{array}{r} (1) & | j ⟩ \to \frac{1}{2^{n / 2}} \sum_{k = 0}^{2^{n} - 1} \exp (2 π i j k / 2^{n}) | k ⟩ \end{array}$

前回までの記事にあるように、 $| j ⟩ (j は 0 \leq j < 2^{n} をみたす整数)$ とは、 $j$ を2進数表示した各桁を $j_{i} \in {0, 1} (i = 0, 1, 2, \dots, n - 1)$ として
$\begin{array}{r} | j ⟩ := | j_{0} ⟩ | j_{1} ⟩ \dots | j_{n - 1} ⟩ \end{array}$
のことです（2値を取る量子状態 $| 0 ⟩, | 1 ⟩$ の存在は仮定します）。Eq.(1)の変換ができれば、 $\sum_{j = 0}^{N - 1} x_{j} | j ⟩$ という重ね合わせの状態にこれを施すことで
$\begin{array}{r} \sum_{j = 0}^{N - 1} x_{j} | j ⟩ \to \sum_{k = 0}^{N - 1} y_{k} | k ⟩, y_{k} = \frac{1}{\sqrt{N}} \sum_{l = 0}^{N - 1} \exp (2 π i k l / N) x_{l}, N = 2^{n} \end{array}$
を得ます。このようにして $x_{j}$ の離散フーリエ変換 $y_{j}$ の情報を持つ状態を作ることができます。ただし実際に量子状態を観測して $y_{j}$ を得るのは現実的でないことに注意してください（Ref.Nielsen P220）。この観測はQFTの速さを無意味にするほど時間がかかります。QFTの量子回路は、あくまで他のアルゴリズム（今回はShorのアルゴリズム）の部品、サブルーチンとして使うものです。

以下Eq.(1)を実現する量子回路、すなわちQFTの量子回路を構成します。

QFTを実現する量子回路の構成

QFTの量子回路において次が成立することが重要です：
$\begin{aligned} \frac{1}{2^{n / 2}} \sum_{k = 0}^{2^{n} - 1} e^{2 π i j k / 2^{n}} | k ⟩ & = \frac{1}{2^{n / 2}} \sum_{k_{0} = 0}^{1} \sum_{k_{1} = 0}^{1} \dots \sum_{k_{n - 1} = 0}^{1} e^{2 π i j (\sum_{l = 1}^{n} k_{l - 1} / 2^{l})} | k_{0} ⟩ | k_{1} ⟩ \dots | k_{n - 1} ⟩ \\ = \frac{1}{2^{n / 2}} (\sum_{k_{0} = 0}^{1} e^{2 π i j k_{0} / 2^{1}} | k_{0} ⟩) (\sum_{k_{1} = 0}^{1} e^{2 π i j k_{1} / 2^{2}} | k_{1} ⟩) \dots (\sum_{k_{n - 1} = 0}^{1} e^{2 π i j k_{n - 1} / 2^{n}} | k_{n - 1} ⟩) \\ (2) & = \frac{1}{2^{n / 2}} (| 0 ⟩ + e^{2 π i j / 2^{1}} | 1 ⟩) (| 0 ⟩ + e^{2 π i j / 2^{2}} | 1 ⟩) \dots (| 0 ⟩ + e^{2 π i j / 2^{n}} | 1 ⟩) \end{aligned}$
最初の行では $k = k_{0} 2^{n - 1} + k_{1} 2^{n - 2} + \dots + k_{n - 1} 2^{0}$ としています。

ここで $j$ を $j = j_{0} 2^{n - 1} + j_{1} 2^{n - 2} + \dots + j_{n - 1} 2^{0}$ のように2進数表示します。Eq.(1)の各括弧内の位相ファクター $\exp (2 π i (j / 2^{l}))$ において、 $j / 2^{l}$ の整数部分は無視できます。ゆえに $\exp$ の肩は
$\begin{aligned} j / 2^{1} \to j_{n - 1} / 2^{1} \\ j / 2^{2} \to j_{n - 2} / 2^{1} + j_{n - 1} / 2^{2} \\ ⋮ \\ j / 2^{n} \to j_{0} / 2^{1} + j_{1} / 2^{2} + \dots + j_{n - 1} / 2^{n} \end{aligned}$
としてよいです。よって
$\begin{array}{r} (3) & Eq.(2) = \frac{1}{2^{n / 2}} (| 0 ⟩ + e^{2 π i (j_{n - 1} / 2^{1})} | 1 ⟩) (| 0 ⟩ + e^{2 π i (j_{n - 2} / 2^{1} + j_{n - 1} / 2^{2})} | 1 ⟩) \dots (| 0 ⟩ + e^{2 π i (j_{0} / 2^{1} + j_{1} / 2^{2} + \dots + j_{n - 1} / 2^{n})} | 1 ⟩) \end{array}$
となります。よって初期状態として
$\begin{array}{r} | j ⟩ = | j_{0} ⟩ | j_{1} ⟩ \dots | j_{n - 1} ⟩ \end{array}$
を用意し、この各qubitをEq.(3)のように変換する量子回路を組めばフーリエ変換ができたことになります。

ここで「小数バイナリ表示」を導入します:

小数バイナリ表示

$\begin{array}{r} j_{0} / 2^{1} + j_{1} / 2^{2} + \dots + j_{n - 1} / 2^{n} を 0. j_{0} j_{1} \dots j_{n - 1} のように表す \end{array}$

するとEq.(3)は
$\begin{array}{r} (4) & Eq.(3) = \frac{1}{2^{n / 2}} (| 0 ⟩ + e^{2 π i 0. j_{n - 1}} | 1 ⟩) (| 0 ⟩ + e^{2 π i 0. j_{n - 2} j_{n - 1}} | 1 ⟩) \dots (| 0 ⟩ + e^{2 π i 0. j_{0} j_{1} \dots j_{n - 1}} | 1 ⟩) \end{array}$
と書けます。文献ではこの形で書くことが多いです。

Eq.(4)を実現するのに以下の2つの量子ゲートを導入します：

QFTに必要な量子ゲート

アダマール（Hadamard）ゲート:
これは1 qubitに作用するゲートであり、以下の変換を行う
$\begin{array}{r} | 0 ⟩ \mapsto \frac{| 0 ⟩ + | 1 ⟩}{\sqrt{2}}, | 1 ⟩ \mapsto \frac{| 0 ⟩ - | 1 ⟩}{\sqrt{2}} \end{array}$
このゲートを ${\hat{H}}^{(i)}$ で表す。 $i$ はHadamrdゲートが作用するqubitの番号。量子回路図では以下のように表す：
Hadamardゲートの量子回路図
制御 $R_{k}$ （controlled- $R_{k}$ ）ゲート:
2 qubitに作用するゲート。1つはcontrol qubit, もうひとつがtarget qubit。control qubitが $| 1 ⟩$ のとき、target qubitの $| 1 ⟩$ に $e^{2 π i / 2^{k}}$ の位相をかける。このゲートを ${\hat{R}}_{k}^{(l m)}$ で表す。ここで $l$ はcontrol qubitの番号、 $m$ はtarget qubitの番号。量子回路図では $R_{k}^{(l m)}$ を以下のように表す：
${\hat{R}}_{k}^{(l m)}$ の量子回路図

これらのゲートを用いてQFTの量子回路を作ります。ゲートの定義より $\begin{aligned} {\hat{H}}^{(i)} (α | 0 ⟩_{i} + β | 1 ⟩_{i}) = \frac{1}{\sqrt{2}} (α + β) | 0 ⟩_{i} + \frac{1}{\sqrt{2}} (α - β) | 1 ⟩_{i}, \\ {\hat{R}}_{k}^{(l m)} | j_{l} ⟩ (α | 0 ⟩_{m} + β | 1 ⟩_{m}) = | j_{l} ⟩ (α | 0 ⟩_{m} + e^{2 π i j_{l} / 2^{k}} β | 1 ⟩_{m}) \end{aligned}$
が成立します。最初の式より ${\hat{H}}^{(i)} | j_{i} ⟩, j_{i} \in {0, 1}$ は以下のようにかけることがわかります：
$\begin{aligned} {\hat{H}}^{(i)} | j_{i} ⟩ & = \frac{1}{\sqrt{2}} (| 0 ⟩_{i} + e^{π i j_{i}} | 1 ⟩_{i}) \\ = \frac{1}{\sqrt{2}} (| 0 ⟩ + e^{2 π i j_{i} / 2^{1}} | 1 ⟩) \\ = \frac{1}{\sqrt{2}} (| 0 ⟩ + e^{2 π i 0. j_{i}} | 1 ⟩) \end{aligned}$
これらの式から以下が成立します：
$\begin{aligned} {\hat{H}}^{(0)} | j_{0} ⟩ & = \frac{1}{2^{1 / 2}} (| 0 ⟩ + e^{2 π i 0. j_{0}} | 1 ⟩), \\ {\hat{R}}_{2}^{(1 0)} {\hat{H}}^{(0)} | j_{0} ⟩ | j_{1} ⟩ & = \frac{1}{2^{1 / 2}} (| 0 ⟩ + e^{2 π i 0. j_{0} j_{1}} | 1 ⟩) | j_{1} ⟩, \\ {\hat{R}}_{3}^{(2 0)} R_{2}^{(1 0)} {\hat{H}}^{(0)} | j_{0} ⟩ | j_{1} ⟩ | j_{2} ⟩ & = \frac{1}{2^{1 / 2}} (| 0 ⟩ + e^{2 π i 0. j_{0} j_{1} j_{2}} | 1 ⟩) | j_{1} ⟩ | j_{2} ⟩, \\ ⋮ \end{aligned}$
一般化すると以下が成立することがわかります：

$\begin{aligned} R_{k}^{(i + k i)} R_{k - 1}^{(i + k - 1 i)} \dots R_{2}^{(i + 1 i)} {\hat{H}}^{(i)} | j_{0} ⟩ | j_{1} ⟩ \dots | j_{i - 1} ⟩ | j_{i} ⟩ | j_{i + 1} ⟩ \dots | j_{i + k} ⟩ \\ = (| j_{0} ⟩ | j_{1} ⟩ \dots | j_{i - 1} ⟩) \frac{1}{2^{1 / 2}} (| 0 ⟩_{i} + e^{2 π i 0. j_{i} j_{i + 1} \dots j_{i + k}} | 1 ⟩_{i}) | j_{i + 1} ⟩ | j_{i + 2} ⟩ \dots | j_{i + k} ⟩ \end{aligned}$

ここで $\hat{K} (i; k)$ を以下のように定義します：
$\begin{array}{r} \hat{K} (i; k) := {\hat{R}}_{k}^{(i + k - 1 i)} {\hat{R}}_{k - 1}^{(i + k - 2 i)} \dots R_{2}^{(i + 1 i)} {\hat{H}}^{(i)} \end{array}$
すると
$\begin{array}{r} (5) & Eq.(4) = {\hat{H}}^{(n - 1)} \hat{K} (n - 2; 2) \dots \hat{K} (1; n - 1) \hat{K} (0; n) | j_{0} ⟩ | j_{1} ⟩ \dots | j_{n - 1} ⟩ \end{array}$
と書けます。