@yuichirominato 2019.01.03更新 316views

世界で二番目にやさしい量子フーリエ変換

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

はじめに

量子コンピュータの計算に既存計算機の高速フーリエ変換に対応したアルゴリズムで量子フーリエ変換があります。原理はとても似ていますが、多少量子コンピュータの性質を理解する必要があったり、その活用方法にコツが必要だったりします。簡単に見直します。

参考

量子フーリエ変換の式は簡単にこちらで確認しましたが、今回も確認します。
https://blog.mdrft.com/post/39

Blueqatでの実装はこちら、
https://blog.mdrft.com/post/374

量子フーリエ変換とは?

フーリエ変換は時系列の波を周波数ごとに分解します。フーリエ変換の中で離散値をとるものが離散フーリエ変換で、それを計算機上で高速処理するアルゴリズムが高速フーリエ変換です。量子フーリエ変換はこの高速フーリエ変換を量子コンピュータを使って計算を行います。

量子フーリエ変換の数理

高速フーリエ変換にとても似ています(が符号が違う気が、、、)。ある量子状態を別の量子状態に写します。

$$QFT:\mid x \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \omega_n^{xk}\mid k\rangle \\ \omega_n = e^{\frac{2\pi i}{N}}$$

フーリエ変換を行列表記すると、

$$F_N= \frac{1}{\sqrt{N}} \left[ \begin{array}{rrrr} 1 & 1 & 1 & \cdots &1\\ 1 & \omega_n&\omega_n^2&\cdots&\omega_n^{N-1}\\ 1 & \omega_n^2&\omega_n^4&\cdots&\omega_n^{2(N-1)}\\ 1 & \omega_n^3&\omega_n^6&\cdots&\omega_n^{3(N-1)}\\ \vdots&\vdots&\vdots&&\vdots\\ 1 & \omega_n^{N-1}&\omega_n^{2(N-1)}&\cdots&\omega_n^{(N-1)(N-1)} \end{array} \right]$$

具体的な行列計算を行うことで、再帰計算を通じて計算量の軽減が行われていることがわかります。

$$\begin{align} F_4 &=& \frac{1}{\sqrt{4}} \left[ \begin{array}{rrrr} \omega^0&\omega^0&\omega^0&\omega^0\\ \omega^0&\omega^1&\omega^2&\omega^3\\ \omega^0&\omega^2&\omega^4&\omega^6\\ \omega^0&\omega^3&\omega^6&\omega^9 \end{array} \right]\\ &=& \frac{1}{\sqrt{2}} \left[ \begin{array}{rrrr} 1&0&\omega^0&0\\ 0&1&0&\omega^1\\ 1&0&\omega^2&0\\ 0&1&0&\omega^3 \end{array} \right] \left[ \begin{array}{rrrr} F_2&\\ &F_2 \end{array} \right]\\ &=& \frac{1}{\sqrt{2}} \left[ \begin{array}{rrrr} 1&0&\omega^0&0\\ 0&1&0&\omega^1\\ 1&0&\omega^0 \omega^2&0\\ 0&1&0&\omega^1 \omega^2 \end{array} \right] \cdot ( I \otimes F_2 )\\ &=& \frac{1}{\sqrt{2}} \left[ \begin{array}{rrrr} 1&0&1&0\\ 0&1&0&1\\ 1&0&-1&0\\ 0&1&0&-1 \end{array} \right] \left[ \begin{array}{rrrr} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&\omega^1 \end{array} \right] \cdot ( I \otimes F_2 )\\ &=& \frac{1}{\sqrt{2}} \left[ \begin{array}{rr} 1&1\\ 1&-1 \end{array} \right] \otimes \left[ \begin{array}{rr} 1&0\\ 0&1 \end{array} \right] \cdot \left[ \begin{array}{rrrr} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&\omega^1 \end{array} \right] \cdot ( I \otimes F_2 )\\ &=& ( H \otimes I ) \cdot \left[ \begin{array}{rrrr} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&\omega^1 \end{array} \right] \cdot ( I \otimes F_2 ) \end{align}$$

F4のフーリエ変換がF2の再帰計算にうまく落ちています。

ビットを入力し、位相を量子状態で出力

量子フーリエ変換の入力は01のビットになります。これらのビット入力が位相の形で量子状態として出力されます。出力状態をテンソル積を用いて表現すると、

$$ QFT(\mid x_1,x_2,…,x_n \rangle) = \frac{1}{\sqrt{N}}(\mid 0 \rangle + e^{2\pi i [0.x_n]} \mid 1 \rangle) \otimes … \otimes (\mid 0 \rangle + e^{2\pi i [0.x_1x_2…x_n]} \mid 1 \rangle) $$

$$[0.x_1x_2…] = \frac{x_1}{2}+\frac{x_2}{2^2}+…$$

位相にビットが現れた状態での量子状態が得られます。ここで注意したいのは、各量子状態の出現確率は確率振幅の二乗で表せられますが、どの量子状態も出現確率は同一なので測定を通じて位相が得られない点です。

量子回路

量子回路は上記の行列演算からわかる通りに再帰計算の再帰回路となっています。一番簡単な回路は2量子ビットで、

--H--Rz2-----
-----*----H--

となりますが、C-RzはコントロールZ回転ゲートを表します。こちらは実質的にはRz回転とCX(CNOT)をつかって表現できます。

--H----Rz(lambda/2)--X--Rz(-lambda/2)--X------
                     |                 |
---------------------*-----------------*---H--

Blueqatのコードとして書くと、

from blueqat import Circuit
import math
Circuit().x[0].x[1].h[0].rz(math.pi/4)[0].cx[1,0].rz(-math.pi/4)[0].cx[1,0].h[1].run()

array([ 5.00000000e-01+0.j , -8.32667268e-17-0.5j, -5.00000000e-01+0.j ,
        8.32667268e-17+0.5j])

次にもう少し大きくN=4の場合をみてみます。

--H--Rz2--Rz3--Rz4--------------------------
-----*----|----|----H--Rz2--Rz3-------------
----------*----|-------*----|----H--Rz2-----
---------------*------------*-------*----H--

アダマールゲートとRzゲートを組み合わせて再帰回路を組みます。Blueqatのコードでは下記になります。

Circuit().x[:].h[0].rz(math.pi/4)[0].cx[1,0].rz(-math.pi/4)[0].cx[1,0].rz(math.pi/8)[0].cx[2,0].rz(-math.pi/8)[0].cx[2,0].rz(math.pi/16)[0].cx[3,0].rz(-math.pi/16)[0].cx[3,0].h[1].rz(math.pi/4)[1].cx[2,1].rz(-math.pi/4)[1].cx[2,1].rz(math.pi/8)[1].cx[3,1].rz(-math.pi/8)[1].cx[3,1].h[2].rz(math.pi/4)[2].cx[3,2].rz(-math.pi/4)[2].cx[3,2].h[3].run()                                                                    

array([ 2.50000000e-01+6.93889390e-18j,  2.30969883e-01-9.56708581e-02j,
        1.76776695e-01-1.76776695e-01j,  9.56708581e-02-2.30969883e-01j,
       -5.55111512e-17-2.50000000e-01j, -9.56708581e-02-2.30969883e-01j,
       -1.76776695e-01-1.76776695e-01j, -2.30969883e-01-9.56708581e-02j,
       -2.50000000e-01-6.93889390e-18j, -2.30969883e-01+9.56708581e-02j,
       -1.76776695e-01+1.76776695e-01j, -9.56708581e-02+2.30969883e-01j,
        5.55111512e-17+2.50000000e-01j,  9.56708581e-02+2.30969883e-01j,
        1.76776695e-01+1.76776695e-01j,  2.30969883e-01+9.56708581e-02j])

このように、実際にコードを用いて簡単に行うことができました。こちらが量子フーリエ変換です。

検算

量子フーリエ変換は量子状態を直接観測できないので、使いどころが難しいです。そのため最初はシミュレータで状態ベクトルを取得して、既存の高速フーリエ変換FFTと比較するのが良いでしょう。

高速フーリエ変換はPythonの一般的なライブラリのNumpyに収録されていて、

import numpy as np
pprint(np.fft.fft(np.array([0,0,0,1])/2))                                                                           
[ 0.5+0.j   0. +0.5j -0.5+0.j   0. -0.5j]

このようにビットを入力することで、実際に量子フーリエ変換における状態ベクトルからの値と比べて確認をすることができます。上記は最初の二量子ビットの状態と対応していることが確認できます。ビットは状態ベクトルの形に直す必要があるので、1,1のビットは0001と表現されます。

まとめ

量子フーリエ変換は数理がしっかりしているので迷うことがありません。定義を見直してきちんと確認しておけば良いと思います。また、出力が量子状態なので使い所が難しいですが、位相推定アルゴリズムのように、量子状態からビットへ変換する際などに有用ですので、大事なアルゴリズムの成り立ちとして覚えておくのがいいと思います。以上です。

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方