特集

5）量子回路の自動設計手法

量子コンピュータと量子計算

5量子回路の自動設計手法
中島 裕美〔日本電信電話（株）NTT コミュニケーション科学基礎研究所〕
河野 泰人〔日本電信電話（株）NTT コミュニケーション科学基礎研究所〕
関川 浩〔日本電信電話（株）NTT コミュニケーション科学基礎研究所〕
現在のコンピュータの演算は，AND, OR, NOT などの基本演算を組み合わせることで実現できる．同様に，量子コンピュータでは，1 量子ビットの演算と 2 量子ビットの演算を基本演算とし，これらを組み合わせることで，所望の n 量子ビットの演算を実現できる．いま，量子コンピュータの基本演算を，現在のコンピュータの論理回路のように記号を用いて表すことにすると，与えられた演算を実現する基本演算の構成を示した図が量子回路である．
入出力の量子ビットの状態をベクトルで表すと，量子コンピュータの演算は行列で表現することができる．n 量子ビットの演算に対応する行列の大きさは 2  2 である．基本演算は，2  2（1 量子ビnnットの演算），または 4  4（2 量子ビットの演算）の行列で表現できる．したがって，n 量子ビットの演算は，基本演算に対応する行列の積で書くことができる．本稿では，この行列表現を用いて，与えられた n 量子ビットの演算（2  2 行列）から量子回路を自動設計する手法を紹介する．量子回路は，nn

量子コンピュータ上の実行命令の系列に対応しているので，本手法は，言い換えれば，量子コンピュータの演算を実行命令の系列に自動翻訳する手法である．利用する技術は行列の特異値分解である．

効率的な演算と量子回路時間が増大するので，効率的な演算とはいえない．これに対して，Shor のアルゴリズムで用いられている量子量子コンピュータは，因数分解を高速に解くアルゴリ

Fourier 変換は，量子ビット数 n に対して，必要な基本ズム（Shor のアルゴリズム）が示されたことで，現在の演算数が O(n ) であるため，量子コンピュータ上で効率コンピュータよりも高い計算能力を持つコンピュータと的に実行することができる．

2して注目されるようになった．では，量子コンピュータ

量子回路とは，図 -1 のように，与えられた演算を実を使うと，すべての演算が現在のコンピュータよりも格現する基本演算の構成を記号で表した図である．基本演段に速くなるのだろうか．実際にはそうではなく，量子算は，図 -2 に示す記号で記述される．横に通った各々コンピュータによって高速になる演算と，現在のコンピの線が 1 量子ビットに対応しており，線上の記号がそのュータとあまり変わらない演算がある．

量子ビットに適用される基本演算で，左から時系列に並量子コンピュータの計算時間は，大まかには，与えらべられている．量子回路に従って，左から順に基本演算れた演算を実行するために必要な基本演算の数に対応を行うと，所望の出力状態まで到達できる．したがって，している．量子コンピュータにおける基本演算は，1 量量子回路は実行命令の系列を表しているともいえる．

子ビットの演算と 2 量子ビットの演算である．これらの本稿では，n 量子ビットの演算から，量子回路を自動基本演算を組み合わせることで，任意の n 量子ビットの設計する手法について解説する．ここでは，量子コンピ演算を作ることができる．一般には，任意の n 量子ビッュータの演算を行列で表現したものを利用する．そこでトの演算を構成するためには，O(4 ) の基本演算が必要

まず，次章では，量子コンピュータの演算と行列計算のである ．量子ビット数 n に対して，指数関数的に計算関係について説明する．次に，行列の特異値分解を応用

n2）IPSJ Magazine Vol.47 No.12 Dec. 20061335

特集：量子コンピュータと量子計算した量子回路の自動設計手法を紹介し，例として，量子時間

Fourier 変換の量子回路の設計を挙げる．最後に今後の第1量子ビット量子コンピュータの演算と行列計算
量子コンピュータにおける演算とは，与えられた量子u3

第2量子ビットu1

第3量子ビット

u2u4

出力

入力

課題について述べる．

図 -1 量子回路の例

ビット状態を，目的とする量子ビットの状態へ遷移させるプロセスである．数学的には，量子ビットの量子状態をベクトル，演算を行列で書くことができる．たとえ示す NOT の演算は，以下のように計算できる．

ば 1 量子ビットの重ね合わせ状態を  0   1 とすると，

0 1 abeoe o = e o.
1 0 baこれは以下の 2 次元ベクトルで書ける．

これは，与えられた量子状態  0   1 を  0   1

aa 0 + b 1 = e o.
bという 0 と 1 に対応する確率振幅（ベクトルの要素）が反ここで，量子状態を表すベクトルは，長さが 1（  転した状態へ遷移させる演算であるため，NOT に対応

   1， ， は複素数）である．n 量子ビットの量子状していることが分かる．

22

態は，テンソル積を用いて書ける．たとえば 2 量子ビ

次に，2 量子ビットの演算を考える．入力状態を（1）ットで，第 1 量子ビットの量子状態が  10   11, 第 2とし，第 1 量子ビットを制御ビット，第 2 量子ビットを量子ビットの量子状態が  20   21 の場合は，以下の標的ビットとする制御 NOT 演算を考える．

ような 4 次元ベクトルで表せる．
Ja a NK 1 2Oa1a2
K a1 b 2 O
fb p7fb p = Kb a O.
12K 1 2O
K b 1 b 2O
LP

J1 0 0 0N Ja a N Ja a N
K
O K 1 2O K 1 2O
K0 1 0 0O K a1 b 2O K a1 b 2O
K0 0 0 1O K b1 a 2O = K b1 b 2O ,
O K
O
KK
OK
0 0 1 0O K b1 b 2O K b1 a 2O
L
PLP L
P

（1）

より，制御 NOT は，第 1 量子ビットが 1 のときの第 2ベクトルの次元は，n 量子ビットのとき 2 次元になる．

量子ビットの状態（10 と 11 に対応するベクトルの値）

量子計算は，与えられた量子状態（ベクトル）から別のを反転させる演算である．論理回路に対応させると，ち量子状態（ベクトル）への写像を表す行列として記述でょうど第 2 量子ビットの出力が第 1 量子ビットと第 2 量きる．ここで，入出力のベクトルはどちらも長さが 1 で子ビットの XOR になる．量子回路の場合，入力と出力あるため，演算を表す行列は長さを変えない線形作用素，の線の数（量子ビット数）は同じであるため，XOR のよすなわちユニタリ行列となる．したがって，行列 U のうな 2 入力 1 出力の演算を実現するために，制御 NOT†
1
共役転置行列 (U ) は，逆行列 (U ) と一致する．のような 2 入力 2 出力の演算を用いる．

nたとえば，入力状態を  0   1 とすると，図 -2 に●n1量子ビットの操作（2×2のユニタリ行列）
NOTu●

一般に，n 量子ビットに対する量子計算は，2 次元ベHadamard変換
0 11 0H

1 1 1
2 1 1

2量子ビットの操作（4×4のユニタリ行列）
制御NOT
制御ビット

w

標的ビット

図 -2 基本演算の記号1336 47 巻 12 号

情報処理 2006 年 12 月

SWAP
1000010000010010

第1量子ビット
第2量子ビット

10000010010000015）量子回路の自動設計手法

2n-1

2n-12n-1

U11 U122n-1

U21 U22=V10

R11R12W100V2

R21 R220

W2r1

第1量子ビット
第2量子ビット
第3量子ビット

U=r2V1

W1 W2

第n-1量子ビット

r 2n-11 r 2n-1V2

第n量子ビット

図 -3 Cosine-Sine 分解と対応する量子回路

クトルから別の 2 次元ベクトルへの写像を表す 2  2n対応している．ここで，白丸（）の制御ビットは，制御のユニタリ行列で書ける．また，入力状態を変化させなビットの状態が 0 のときに標的ビットにユニタリ行列をい演算は，単位行列に対応する．

適用する制御演算で，黒丸（•）は，制御ビットの状態がnnすると，図 -1 の量子回路は，以下の行列の積で書ける．

(u3 ^ u4 ^ I) (I ^ C) (I ^ u1 ^ u2)(C ^ I).

（2）

ここで，I は 2  2 の単位行列，u1, u2, u3, u4 は 2  2 のユニタリ行列，C は制御 NOT で，図 -2 に示す 4  4 行列である．行列演算の性質から，量子回路における基本操作の順序（左から右）とは逆順に行列がかかっていることに注意する ．

1 のときに標的ビットにユニタリ行列を適用する制御演算である．また，回路の中央部分に並んでいる制御ビットが n1 個の演算の列は，Cosine-Sine 分解における中央の行列に対応するもので，

cos i k -sin i kr k = f sin i cos i p , k = 1, 2, g, 2 n-1 .
kk

ここで， k は（3）と対応している．
Cosine-Sine 分解の 3 つの行列の積のうち，両端の行6）

このような行列の記述を利用すると，2  2 のユニ列は制御ビットを無視すると，n1 量子ビットの演算タリ行列を，（2）のような基本演算に対応する行列の積（V1, V2, W1, W2）であるため，再帰的に Cosine-Sine 分解へ変換することで，量子回路の設計ができることが分かを行うことができる．すると，図 -4 のように，最終的る．次章では，行列の特異値分解を利用して，これを実に n1 個の制御ビットを持つ 1 量子ビットの演算の列現する手法を紹介する．にまで分解することができる．この演算は，図 -4 の (c)nnのような基本演算の列に分解できるので，最終的に入力行列分解を用いた量子回路の自動設計行列分解を用いた量子回路設計では，特異値分解や固のユニタリ行列に対応する基本演算の列（量子回路）を設計することができる．図 -4 の (b) から (c) への変換を求める場合には，uj (j  1,…, 2) と ak (k  1,…, 2n1  1)n1

有値分解が応用されている．ここでは，Cosine-Sine 分の行列間の対応関係を利用して，方程式を解くような形解という一般化特異値分解を求める手法を応用した量子で基本演算の系列を求めることができる ．なお，図 -4回路の設計手法について述べる

2），4）

2）

．Cosine-Sine 分解

では，半月型の制御ビットの記号を用いているが，これは，行列を図 -3 のような特徴を持った 3 つの行列の積は (b) のような制御ビットが白と黒の場合で異なる演算に分解する手法で，入力の行列 U を 4 分割した各々のを適用する演算を省略して記述したものである．

部分 Ujk について，Ujk  Vj Rjk Wk（j, k  1, 2）が，それCosine-Sine 分解が量子回路設計に適している理由は，ぞれ特異値分解となるような分解手法である．ここで，図 -3 に示すように，分解後の行列が制御演算の積で表Rjk (j, k  1, 2) は，以下のような 2n1  2n1 の対角行列され，標的ビットの演算だけを見ると n 量子ビットよりである．

も量子ビット数の少ない演算で書けることにある．このR11  R22  diag (cos  1,…, cos  2n1),
R21  R12  diag (sin  1,…, sin  2n1),

ことにより，再帰的に Cosine-Sine 分解を適用すること（3）

Cosine-Sine 分解の 3 つの行列の積は，図 -3 量子回路にで，標的ビットの演算を 1 量子ビットの演算に近づけることができる．
IPSJ Magazine Vol.47 No.12 Dec. 20061337

特集：量子コンピュータと量子計算①②

第1量子ビット

8×8行列

第2量子ビット
第3量子ビット(a)③4×4行列(b)4×4行列(c)

u1 u 2 u3 u 4Ua1a2a3a4a5

図 -4 Cosine-Sine 分解を再帰的に利用した量子回路設計

もっと一般的には，量子回路の設計に適した行列分解

なる 2  2 のユニタリ行列で書ける．
nnは，Lie 群論における KAK 分解という枠組みでとらえることができる．KAK 分解とは，ある N  N の行列からなる群 G に対して，g  G が次式のような 3 つの行列

❐ 量子回路の設計

F̃n を以下の式で定義する．の積に分解できることを意味する．

FDFn - 1
Fun = f n - 1.
Fn - 1 - DFn - 1pg  k2ak1, k1, k2  K, a  A.
ここで，K, A は G の部分群である．Cosine-Sine 分解はここで，D は以下の対角行列である．
D  diag ( 0,  1, …,  2n1

KAK 分解の一例で，この場合，K は図 -3 の 3 つの行列

1).の積の両端の行列で用いられているブロック対角行列F̃n は，量子 Fourier 変換 Fn の列を［奇数列，偶数列］の順からなる部分群，A は（3）を満たす行列からなる部分群に入れ替えることで得られる．たとえば，8  8 の量子である．Cosine-Sine 分解以外にも，量子回路設計のたFourier 変換の場合だと，列の順序をめに考案された KAK 分解 (Khaneja-Glaser 分解 ) がある．

[1,2,3,4,5,6,7,8] → [1,3,5,7,2,4,6,8]

Khaneja-Glaser 分解は，行列の対角化を応用して求めるとなるように入れ替えを行う．この列の入れ替えは，量ことができる ．

子計算では量子ビットの入れ替え（SWAP）で実現できる．

3）

列の入れ替えを Qn とおき，Fn  F̃n Qn とする．S(j, k) を

例 : 量子 Fourier 変換の量子回路の設計

第 j 量子ビットと第 k 量子ビットの SWAP とすると，Qn  S(1, n) S(2, n) … S(n1,n),❐ 量子 Fourier 変換とはと書ける．

子状態の離散 Fourier 変換になるようなユニタリ変換でここで，In1 は 2ある．n 量子ビットの入力と出力の量子状態をそれぞれ，n1 量子ビットの量子 Fourier 変換なので，再帰的にこF̃n の Cosine-Sine 分解を考えると，図 -5 のようになる．

量子 Fourier 変換とは，出力の量子状態が，入力の量n1n12の単位行列を表す．Fn1 はtx  (x0, x1, …, x2n1) ,の分解を繰り返す．残された基本演算でない要素は，第y  (y0, y1, …, y2n1) ,1 量子ビットを制御ビットとして，n1 量子ビットにtとおく．ここで，出力 y の各成分 y0, …, y2n1 は，入力 xD を施す演算である．制御ビットを無視して，n1 量の離散 Fourier 変換

子ビットの演算 D について考えると，図 -6 のように分解できる．ここで，dk は，D の (0, 0) 成分から (2nkyk =12n2 n-1

2ri~ x j, ~ = exp e n o ,2j=0!

2jk

1,1) 成分までの要素からなる対角行列nkdk  diag ( 0,  1, …,  2nk),1となる（k  0, 1, …, 2 1）．このようなユニタリ変換 Fnである．dk は，図 -6 に示すように再帰的に分解していは，その (k, j) 成分 Fn[k, j] がくと，最終的に n1 個の 1 量子ビットの基本演算列がnFn [k, j] =1338 47 巻 12 号

1 ~ jk ,2n
情報処理 2006 年 12 月

（4）

求まる．ここで，5）量子回路の自動設計手法

2 n-1
2 n-1~H  In-1

2 n-1

2 n-1

Fn-1DFn-1

Fn-1

DFn-10In-1


01In-12

1In-1 1 In-122In-1Qn†
第1量子ビットFn-100DFn-1~Z H~
H×

第2量子ビット

1 In-12×Fn

第n-1量子ビット×

第n量子ビット

×× ×

Fn-1



D1~
H
2~
Fn  Fn Qn†


1 1
1 1

Fn-1

D~
Z  1 0 , HZ  H (Hadamard変換)
0 1

図 -5 量子 Fourier 変換 Fn の Cosine-Sine 分解と対応する量子回路

1 0n-2I
0 V 2  n-2d2

V 2 d2n-2

V 2 In-2

P(1/4)

P(1/4)

P(1/4)

P(1/8)

P(1/8)

n-2

第3量子ビット
第4量子ビットd2

In-2D

第2量子ビットI1  d2d2d2

P(1/16)d3

P(1/2n)第n量子ビット

図 -6 対角行列 D の分解と対応する量子回路

P (,) = f

10p.
0 exp _2ri, i

この 1 量子ビットの演算の列を図 -5 の D の部分に挿入すると，第 1 量子ビットを制御ビットとする演算の列分解を利用すると，Qn を事前に適用しなくても，効率的な量子回路を求めることができる ．
3）

今後の課題が得られる．これらの結果を合わせると，4 量子ビット

本稿では，特異値分解を利用した量子回路の設計手法の場合は図 -7 の回路が得られる．ここで，SWAP は列について概説した．この手法は，n 量子ビットの量子計の交換に対応している．Qn は n1 個の SWAP から構成算の実現に必要な基本演算数や，制御 NOT の数の下限されるため，4 量子ビットの場合だと，Q2 Q3 Q4 の列にを求める研究に応用されている

2）
〜 4）

．

対応する 6 個の SWAP の列であるが，簡単化すること量子回路の設計手法は，n 量子ビットの量子計算を，で，2 個の SWAP で実現できる．一般に，Fn を分解す量子コンピュータ上の実行命令の系列へ自動翻訳するコ

2
ると，n 個の Hadamard 変換と (n n)2 個の 2 量子ビッンパイラの要素技術としての応用も考えられるが，そのトの演算（標的ビットのユニタリ行列が P() である演算）ためには，計算コストや回路の最適化など多くの課題がと，n2 個の SWAP の系列に分解できる．

ある．

ここでは簡単のため，量子 Fourier 変換に前処理とし

まず，ここで述べた量子回路の設計手法は特異値分†て列の入れ替え Qn を適用した行列 F̃n を用いて，効率的解を利用するが，対象となる入力行列のサイズは，n 量な回路を求めているが，Cosine-Sine 分解とは別の KAK

子ビットに対して 2  2 という大きな行列となるた
nnIPSJ Magazine Vol.47 No.12 Dec. 20061339

特集：量子コンピュータと量子計算

H×P(1/4)

H××

P(1/4)

H×H

P(1/4)

P(1/8)

P(1/8)
P(1/16)

図 -7 4 量子ビットの量子 Fourier 変換の回路

め，計算コストが大きく，多量子ビットの演算にそのまま適用するのは難しい．また，量子 Fourier 変換は行列分解のみによって効率的な量子回路が自動生成できることを示したが，実際にはそれだけではなく，回路の最適化が必要な場合が多い．量子回路の最適化手法としては，これまでに Palindrome を用いた最適化手法

5）や，制御NOT のみで構成される量子回路を最適化する手法1）が提案されている．

Quantum Circuits Using KAK Decompositions, Quantum Inf. Comput., Vol.6,No.1, pp.67-80 (2006).
4）Shende, V. V., Markov, I. L. and Bullock, S. S. : Synthesis of Quantum
Llogic Circuits, IEEE Trans. on Computer-Aided Design, Vol.25, No.6,
pp.1000-1010 (2006).
5）Svore, K. M. and Aho, A. V. : The Design and Optimization of Quantum
Circuits Using the Palindrome Transform, the ERATO Conference on
Quantum Information Sciences (EQIS), Kyoto, Japan, pp.5-7 (2003).
http://arxiv.org/abs/quant-ph/0311008
6）上坂吉則 : 量子コンピュータの基礎数理，コロナ社 (2000).
（平成 18 年 10 月 20 日受付）

基本演算として何を用いるか，という点も重要な問題である．本稿では，1 量子ビットの任意の演算と制御NOT を基本演算としたが，1 量子ビットの演算は無限に存在する．したがって，基本演算としてこれらのすべてを実現するのは困難である．一方で，基本演算の集合として，あらかじめ有限個の基本演算を用意し，これらを組み合わせて任意のユニタリ演算を近似的に実現する方法が知られている（Solovay-Kitaev の定理）
．近似を用いて効率的な量子回路を自動設計する手法を考案することも，今後の課題の 1 つである．
参考文献
1）Iwama, K., Kambayashi, Y. and Yamashita, S. : Transformation Rules
for Designing CNOT-based Quantum Circuits, 39th Design Automation
Conference, pp.419-424 (2002).
2）Möttönen, M., Vartiainen, J. J., Bergholm, V. and Salomaa, M. : Quantum
Circuits for General Multiqubit Gates, Phys. Rev. Lett., Vol.93, No.13,p.130502 (2005).
3）Nakajima, Y., Kawano, Y. and Sekigawa, H. : An Algorithm for Producing

1340 47 巻 12 号

情報処理 2006 年 12 月

中島 裕美（正会員）
nakajima@theory.brl.ntt.co.jp
2001 年愛媛大学工学部情報工学科卒業．2003 年同大学院博士前期課程修了．同年日本電信電話（株）入社．現在，同社 NTT コミュニケーション
科学基礎研究所にて，量子情報処理，特に量子回路設計理論の研究に従事．
河野 泰人
kawano@theory.brl.ntt.co.jp
NTT コミュニケーション科学基礎研究所主任研究員．1989 年大阪大学理学部数学科卒業．1991 年名古屋大学大学院前期課程修了．同年日本電信電話（株）入社．博士（情報科学）．現在の主な研究テーマは量子情報理論．電子情報通信学会，日本ソフトウェア科学会各会員．
関川浩（正会員）
sekigawa@theory.brl.ntt.co.jp
1989 年東京大学大学院理学系研究科修士課程修了．同年日本電信電話（株）入社．2000 年から 2002 年まで西日本電信電話（株）勤務．ハードウ
ェア設計支援技術の研究を経て，数式処理，数値­数式融合計算の研究に従事．博士（数理科学）．