QFTのメモ

この記事は, 旧ブログから移植された記事です. よって, その内容として, 旧ブログに依存した文脈が含まれている可能性があります. 予めご了承下さい.

お題自由な学校のレポート課題1内で, ショアのアルゴリズムを説明するために QFT の概要について示したのだが, 折角なのでその内容の一部を抜粋し, こちらのブログのほうにも載せておくことにした. ショアのアルゴリズムについては, 調べればいくらでも出てくるし, 学会誌, 書籍等で分かり易く述べられていることも多いので, 本エントリで特別取り上げることはしないが, その大体は以下のアクティビティ図の手順の通りである2.

ショアのアルゴリズムのアクティビティ図

なお, 私自身は量子力学, 量子コンピュータ分野における専門家ではないため, 注意してください. 間違った箇所, 不自然な箇所等ございましたら, ご報告いただけると幸いです.

まず, DFT を次のようにおく3. F(t)=x=0n1f(x)exp(j2πtxn)(1)\displaystyle F(t) = \sum_{x = 0}^{n-1} f(x)\exp(-j\dfrac{2\pi tx}{n}\tag{1}) ここで, f(x)f(x) は入力の関数, jj は虚数単位である. QFT は, 正規化係数を 1n\dfrac{1}{\sqrt{n}} とした有限次元内積空間内における正規直交基底 0,,n1|0\rangle, \cdots, |n-1\rangle 上の状態, x=0n1f(x)x\displaystyle \sum_{x=0}^{n-1} f(x)|x\rangle の各係数となる複素関数の値を離散フーリエ変換したものであるといえる. すなわち, 式 $$ の定義をふまえて, x=0n1f(x)xi=0n1F(i)i\displaystyle \sum_{x = 0}^{n-1} f(x)|x\rangle \mapsto \sum_{i = 0}^{n-1}F(i) |i\rangle または, x1nk=0n1exp(j2πxkn)k\displaystyle |x\rangle \mapsto \dfrac{1}{\sqrt{n}}\sum_{k=0}^{n-1}\exp(-j\dfrac{2\pi xk}{n}) |k\rangle と表すことができ, いま mm Qubit があるならば, 扱えるデータ数は 2m2^m となるため x12mk=02m1exp(j2πxk2m)k\displaystyle |x\rangle \mapsto \dfrac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1}\exp(-j\dfrac{2\pi xk}{2^m}) |k\rangle と表せる. これを量子回路として実装していく. 結論から言うと, この量子回路は, アダマールゲートと, 制御ビットが 11 のときのみ, 信号量子ビットの位相を exp(j2π2k+1)\exp(\dfrac{j2\pi}{2^{k+1}}) だけシフトする 制御位相シフトゲートを利用することで実現できる. 次に, 2 Qubit を用いた QFT の量子回路図を示す4.

アダマールゲートと制御位相シフトゲートによる 2 qubit QFT 量子回路

ここで q1|q_1\rangle0+exp(jπq1)10+exp(jπ2(2q1+q0))1(2)|0\rangle + \exp(j\pi q_{1})|1\rangle \to |0\rangle + \exp(\dfrac{j\pi}{2}(2q_1+q_0))|1\rangle \tag{2} と変化し, q0|q_0\rangle0+exp(jπq0)1(3)|0\rangle + \exp(j\pi q_{0})|1\rangle \tag{3} と変化することがいえる. いま, 式 (2)(2) の結果を a0|a_0\rangle, 式 (3)(3) の結果を a1|a_1\rangle としたとき a1a0={0+exp(jπq0)1}{0+exp(jπq1+jπq02)1}(4)|a_1\rangle |a_0\rangle = \left\{|0\rangle + \exp(j\pi q_0)|1\rangle\right\}\left\{|0\rangle + \exp(j\pi q_1 + \dfrac{j\pi q_0}{2})|1\rangle\right\}\tag{4} がいえる. ここで, qq および aa の値の 22 進表記をそれぞれ [q1,q0], [a1,a0][q_1, q_0],\ [a_1, a_0] とすると, q=2q1+q0, a=2a1+a0q = 2q_1 + q_0,\ a = 2a_1+a_0 であるので式 (4)(4) は,

a=0+exp(jπ2q)1+exp(jπ2q×2)2+exp(jπ2q×3)3|a\rangle = |0\rangle + \exp(\dfrac{j\pi}{2}q)|1\rangle + \exp(\dfrac{j\pi}{2}q\times 2)|2\rangle + \exp(\dfrac{j\pi}{2}q\times 3)|3\rangle と展開できる. a|a\rangle の各状態の係数が q|q\rangle の各状態の係数のフーリエ変換になっていることがわかる.


  1. 内容の全コンテンツをリポジトリにまとめているのでもし良ければ.↩︎

  2. 図は plantuml で生成: コード. この画像もレポート用に生成したものだが, 折角なのでこちらにも貼っておくことにした.↩︎

  3. 単純にコードに落とし込むだけであるので大したことはないのだが, レポート内で説明するために Haskell で DFT と IDFT を実装してあるので, 一例としてもし良ければ. 一応テスト済み.↩︎

  4. 図は qasm2circ で生成: コード.↩︎


活動継続のためのご支援を募集しています