External Memory

プログラミング周辺知識の備忘録メイン

量子回路言語

量子アルゴリズムの構築において、量子計算を記述する効率的な言語である量子回路言語について大雑把にまとめる。
量子アルゴリズムを使えば、素因数分解問題や離散対数問題などを効率よく解くことが可能となる。これらの問題を解くには量子Fourier変換が用いられる。

また、量子回路モデルを用いると、少ない種類の量子ゲートの集合で任意のユニタリーオペレータを近似を表現することが出来る。
つまりこの集合は量子計算に関して普遍的であるといえる。


単一qビットゲートに対する記号はX,Y,Z,H,T(π/8Phase shift gate)があり
これらの量子ゲートについては以下のURL参照
https://en.wikipedia.org/wiki/Quantum_gate


任意の単一qビットオペレータUは以下のように表される
U= exp(iα)R_{\hat{n}}(\theta)
\hat{n}=(n_x,n_y,n_z)は単位ベクトル、\vec{\sigma}は(X,Y,Z)
R_\hat{n}(\theta)\equiv exp(-i\theta\hat{n}*\vec{\sigma}/2)=cos(\theta/2)I-isin(\theta/2)(n_xX+n_yY+n_zZ)
X,Y,ZはPauli行列である。

また、\hat{x},\hat{y},\hat{z}軸周りの回転オペレータ
R_x(\theta)≡e^{-iθX/2}=cos(\theta/2)I-isin(theta/2)X
R_y(\theta)≡e^{-iθY/2}=cos(\theta/2)I-isin(theta/2)Y
R_z(\theta)≡e^{-iθZ/2}=cos(\theta/2)I-isin(theta/2)Z
を使ってオペレータをZ-Y分解して
U=e^{iα}R_z(\beta)R_y(\gamma)R_z(\delta)
となるα~δが存在する

単一qビットオペレータUに対し、以下を満たすユニタリーオペレータA,B,Cが存在する。
U=e^{iα}AXBXC
ABC=I
証明は上記の回転オペレータを用いて式変形することで得られる。

n-qビット演算は以下で述べるように、
単一qビットオペレータと制御NOTを用いることで表現することが出来る。

普遍的量子ゲート
  • 任意のユニタリーオペレータは2つの計算基底状態の張る部分空間の中で有意に働くオペレータの積で正確に表現される。
  • 任意ユニタリー演算は制御NOTと単一qビットゲートで正確に表現することが出来る。
  • 任意の単一qビット演算はアダマール、位相、T(π/8ゲート)は任意の精度で近似することが出来る。

よって任意のユニタリー演算はアダマール、位相、制御NOT、π/8ゲートを使って任意の精度で近似できる。
古典的計算に対して古典的ゲートのAND,OR,NOTの集合は普遍的ゲートと呼ばれるのに対比して、これらのゲートは普遍的量子ゲートと呼ばれる。


多次元Hilbert空間で働くユニタリー行列は、
2準位ユニタリー行列(2つ以下の成分のみに有意に働くユニタリー行列)の積に分解することが出来る。
積はd次元ユニタリー行列の場合、d(d-1)/2≧n回以下の2準位ユニタリー行列の計算を実行し、単位行列とする。
すると
U_nU_{n-1}\ldots U_1U=1だから
U=U_1^\dagger \ldots U_n^\dagger
と2準位ユニタリー行列積に分解できる。


2準位ユニタリー行列は制御NOTを複数回使用するGray符号を使って、
つまり隣接するビットをハミング距離*2回分入れ替えて
単一qビットへのユニタリーオペレータとなるように実行することが出来る。


任意のqビットユニタリー演算をアダマールπ/8ゲートを使って任意の精度で近似できる。
グローバル位相を除き、ゲートTとHTHを組み合わせると

exp(-i\pi Z/8)exp(-i\pi X/8)\\=cos^2\pi I/8-i[cos\pi(X+Z)/8+sin(\pi Y/8)]sin(\pi/8)

でこれはcos(θ/2)≡cos^2π/8で定義される角度θだけ回転することを示す。
よって、アダマールとTゲートだけを使ってR_\hat{n}(\theta)を構成できる。
\hat{n}=(cos\pi/8,sin\pi/8,cos\pi/8)である
ここでθは2πの無理数倍であることが示せる。

(証明は以下の論文参照
https://arxiv.org/pdf/quant-ph/9906054.pdf )

所望の精度をδ>0として2π/δより大きい整数をNとすると0<|\theta_k-\theta_j|<=2\pi/N<\deltaであるような角度間隔となるj,kが存在する。
ここで\theta_k=k\theta(mod\ 2\pi)
またθは2πの無理数倍だから、\theta_{j-k}\neq 0

よって任意の回転R_\hat{n}(\alpha)を用いて、下記の式を満たすnが存在する。
E(R_\hat{n}(\alpha),R_\hat{n}(\theta)^n)<\epsilon'/3
E(U,V)はmax_{|\psi\rangle}\|(U-V)|\psi\rangle\|で表される状態ψにユニタリーオペレータU,Vをそれぞれ作用させたときの誤差である。
E(U,V)が小さければ、測定結果間の確率の差も小さくなる。
この式から任意のユニタリー変換を近似できることを導き出せる。

回転行列の数cとするとε=cε'/3として結局アダマールとTゲートを使って、
ε以下で単一qビットユニタリオペレータUを近似することが出来る。
ゲートの数がmの量子回路の場合、全回路に対してεの精度を得るにはゲート当たりε/mの精度で近似すればよい。

一般にユニタリーオペレータの近似の計算量はqビットの数nの指数関数であるが、
Solovay-Kitaevの定理を用いると計算量は対数多項式で済む。