A Reduction from the minimization problem of the quantum logic

数理モデル化と問題解決 42−14
（２００２． １１． ２８）
量子論理回路深さ最小化問題のクリーク問題への還元
*1
*2
名久井 行秀
西野 哲朗
あらまし:
量子計算では, 量子回路という計算モデルが広く用いられている. また, 論理関数の計算は, す
べての計算の基礎であり, 量子計算においても, 重要な位置を占める. したがって, 量子回路上で論理関数を
計算する方法や, その最小化, 簡単化について研究することは, 大変重要となる. 本研究では, 量子論理回路
の深さ最小化問題を明確に定式化し, 量子論理回路の深さ最小化問題を, クリーク問題に還元して解く方法
について述べる.
A Reduction from the minimization problem of the quantum
logic circuit to CLIQUE
*1
Yukihide Nakui
*2
Tetsuro Nishino
Abstract: In quantum computation, a computational model called quantum circuit is widely used. To
evaluate logic function is a basis for all kinds of computations, and takes an important roll in quantum
computation. Therefore, it is very important to study how to evaluate logic functions on quantum circuits
and how to minimize or simplify the circuits. In this paper, we formalize the minimization problem of
the depth of quantum logic circuits and reduce this problem to CLIQUE problem.
1
はじめに
ゲートと呼ぶ. すなわち,
現在, 我々が使用しているコンピュータは, 基本
的に論理回路から構成されている. これは, 計算可
能な関数が, すべて論理関数として表現可能である
ことに基づいている. つまり, 論理関数の計算は, す
べての演算の基礎であり, これを効率的に計算する
ことは, 本質的に重要である.
量子力学の概念に基づく量子コンピュータにおい
ても, 論理関数の計算は, 非常に基本的なタスクで
ある. したがって, 量子回路上で, 論理関数を構成す
るための方法や, その最小化, 簡単化の方法を確立
することは大変重要である.
本研究では, 量子論理回路の深さ最小化問題をク
リーク問題に帰着させて解く方法について述べる.
2
諸定義
定義 2.1 (Toffoli ゲート)
U を 2 × 2 のユニタリ行列とする. n = 1, 2, . . . に対
して, 2n+1 × 2n+1 のユニタリ行列 Λn U を次のよう
に定め, これを (n + 1) キュービットの一般 Toffoli
∀x1 , . . . , xn, y ∈ {0, 1}, |0 =
Λn U |x1, . . . , xn , y
|x1 , . . . , xn ⊗ U |y,
≡
|x1 , . . . , xn, y,
1
0
, |1 =
,
0
1
if
x1 ∧ · · · ∧ xn = 1
if
x1 ∧ · · · ∧ xn = 0
(1)
と定める. ここで, a ∧ b は a, bの論理積を表す.
特に U が U = N (≡
0
1
1
0
) であるとき, Λn N
を (n + 1) キュービットの Toffoli ゲート Tyx と呼
ぶ. そして, これを図 1 のように表すことにする.
そして, n = 0 のときの Toffoli ゲートは, NOT
ゲート N であるとする. また, n = 1 のときは,
C-NOT ゲート (controlled not ゲート) と呼ばれ
る. |x は, 制御ビット(control bit), |y は, 目標
ビット(target bit) と呼ばれる.
|x1 ..
.
|x1 ..
.
|xn *1 電気通信大学大学院
電気通信学研究科 電子情報学専攻 The
Graduate School of Electro-Communications
e-mail: [email protected]
*2 電気通信大学 電気通信学部 情報通信工学科 情報メディア
工学講座 The University of Electro-Communications
e-mail: [email protected]
1
−57−
..
.
|xn |y
図 1: Toffoli ゲート
3
量子論理回路の深さ最小化
定義 3.1 (量子論理回路)
本稿では, ユニタリ変換 Uf-C-NOT
Uf-C-NOT |x|y = |x|y ⊕ f(x)
ESOP 最小化問題の定式化
4
ここまでの議論で, f-C-NOT 回路の深さ最小化
問題が, ESOP の最小化問題に深く関係があること
がわかった. この節では, ESOP の最小化問題につ
いて述べる.
ESOP における積項による最小項の被覆関係は,
偶奇性を持つカバー問題であり, 以下の Helliwell
方程式 で表される. [2]
(2)
を計算する回路 (f -C-NOT 回路 [1]) が量子論理回
路であるとする. f-C-NOT は, function-controlledNOT をあらわす.
f-C-NOT 回路は, 最小項に対応するユニタリ変
換である最小項ゲートで簡単に構成されうる. 最小
項ゲート Myx は,
Nxi
(3)
Nxi Tyx
Myx ≡
H(g) = H(g0 , g1 , . . . , gξ−1 ) =
N−1
Si = 1
(5)
i=0

ここで, Si = 

gj  ⊕ f(ai ) ⊕ 1 であり, N は,
gj ∈Ti
のように NOT ゲートで挟まれた 1 つの (n + 1) ビッ
ト Toffoli ゲートによって実現されうる. ここで Nxi
と Tyx は, それぞれ, 制御レジスタの第 i qubit の状
態だけを反転する NOT ゲートと, n 個の制御ビッ
ト x と 1 個の目標ビット y を持つ Toffoli ゲートを
表す. そして, f-C-NOT 回路は,
Myx
(4)
Uf-C-NOT =
のように, その最小項ゲートすべての積で得られる.
ここで, この積は, 最小項 m(x) について m(x) = 1
を満たす x に関する (すなわち, true miniterm に関
する) ものである.
次に, 積項ゲートを定義する. 各変数に対して高々
1 つのリテラル (x, x) を論理積で結合した式を積項と
呼ぶことにする. そして, Toffoli ゲートを NOT ゲー
トで挟み, この積項に対応する状態で制御されるよ
うにしたゲートを積項ゲートと呼ぶことにする.
これらの積項ゲートに関して次の命題が示される
[5].
【命題】 3.1
積項ゲートの積は, 対応する論理表現においては,
その積項の排他的論理和 (EXOR) で表すことがで
きる.
また, 任意の積項を排他的論理和で結合した ANDEXOR 論理式を ESOP(Exclusive-or Sum Of
Product) と定義し, 論理関数 f を ESOP で表現
したときに積項数が最小になる ESOP を論理関数
f の最小 ESOP と定義する.
そして, これまでの命題から, 次のことが示され
る [5].
定理 3.1 (量子論理回路の深さ最小化)
論理関数 f の最小 ESOP は, f-C-NOT 回路に対す
る深さ最小の量子回路を与える.
最小項の個数 (= 2n ), ξ は, すべての可能な積項の
数 (= 3n ) である. そして, Ti は, i 番目の最小項を
被覆する積項の集合であるとする. f(ai ) は, i 番目
の最小項を 1 にするような入力が与えられたときの
f の値である. (f(ai ) ∈ {0, 1}) gj は, gj = 1 のと
き, j 番目の積項 gj が, ESOP に含まれることを意
味する変数とする.
すなわち, Si は, i 番目の最小項が, 偶奇性 (つまり,
true minterm ならば積項によって奇数回被覆され,
false minterm ならば偶数回被覆される) を満たすた
めの条件をあらわす. そして, H(g0 , g1 , . . . , gξ−1 ) =
1 は, すべての最小項において, 偶奇性が満たされて
いることを意味する.
したがって, ESOP の最小化問題は, H(g) = 1 を
満たす g の中で, 最小の割り当てのものを求める問
ξ−1
題といえる. ここで g の最小の割り当ては, (
gi )
i=0
を最小にするものをさすものとする.
例 1
2 変数関数の場合 Helliwell 方程式は以下のように
なる.
H(g)
=
H(g0 , g1 , . . . , g8 )
(g0 ⊕ g4 ⊕ g6 ⊕ g8 ⊕ f (0, 0) ⊕ 1)
·(g1 ⊕ g4 ⊕ g7 ⊕ g8 ⊕ f (0, 1) ⊕ 1)
·(g2 ⊕ g5 ⊕ g6 ⊕ g8 ⊕ f (1, 0) ⊕ 1)
·(g3 ⊕ g5 ⊕ g7 ⊕ g8 ⊕ f (1, 1) ⊕ 1) = 1 (6)
ここで, g0 , g1 , . . . , g8 については, 図 2 に示す.
しかし, 効率的に g の最小の割り当てを求めるア
ルゴリズムは, 知られていない. そこで, この問題
を CLIQUE 問題に還元させることを考える. これ
は, CLIQUE 問題を高速に解く方法が提案されてお
り [4], この還元により, このアルゴリズムを用いる
ことができるようにするためである.
2
−58−
x1
x2
0
1
g1
0
g0
x1
g4
0
x1
1
0
g6
1
1
g2
x2
x2
0
1
x1
x2
0
0
0
1
1
1
g3
g5
g7
g8
図 2: 2 変数の積項の対応図
【命題】 5.1
N -ESOP は, N − 1 個の 3-ESOP に変換できる.
CLIQUE への還元
5
同様な方法で, 式 (7) は, すべて, 3-ESOP による
連立方程式に変換可能である.
以上で述べた方法によって, 一般に, 1 つの N ESOP を N − 1 個の 3-ESOP に変換するには, 構文
木の内部節点の数に比例するステップで変換でき,
要する時間計算量は O(N ) ステップである.
CLIQUE は, 次のように定義される. [3]
5.2
CLIQUE
充足列の定義
次に, 1 つの 3-ESOP に着目する. 例えば,
INSTANCE:
y01 ⊕ g0 ⊕ g4 = 1
グラフ G = (V, E) と正整数 K ≤ |V |.
に着目することにする.
ここで, ある 3-ESOP を満たす割り当てに対し, 充
足列を定義する. 充足列は, 記号列 a1 a2 · · · am (ai ∈
{0, 1, X}) で表される (1 ≤ i ≤ m):
QUESTION:
G は, サイズ K 以上のクリークを持つか?
5.1
Helliwell 方程式から 3-ESOP へ
例えば, 2 変数論理関数に対する Helliwell 方程式
(6) から, 以下の連立方程式が導き出せる. (ただし,
f(0, 0) 等は given とする. )


g0 ⊕ g4 ⊕ g6 ⊕ g8



g1 ⊕ g4 ⊕ g7 ⊕ g8

g2 ⊕ g5 ⊕ g6 ⊕ g8



g3 ⊕ g5 ⊕ g7 ⊕ g8
= f(0, 0)
= f(0, 1)
= f(1, 0)
= f(1, 1)
(7)
まず, この連立方程式のうちの 1 つに着目する. 例
えば,
g0 ⊕ g4 ⊕ g6 ⊕ g8 = f(0, 0)
ここで, 1 ⊕ x = x を利用した.
f(0, 0)
⊕
y01
y02
⊕
g0
⊕
g4 g6
g8
図 3: 式 (8) の構文木
ai = 0(or 1),
ai = X,
(9)
if ai に 0(または, 1) が割り当てられる.
if ai はその 3-ESOP では, 特定されない.
(11)
ただし, A = {a1 , a2 , · · · , am } は, 着目している
N -ESOP に対する構文木の根を除く節点のラベ
ルに対応している. 例えば, 式 (8) では, A =
{y01 , y02 , g0 , g1 , . . . , g8 } とである. そして, 式 (10)
に関する充足列は,
y01
y02
g0
g1
g2
g3
g4
g5
g6
g7
g8
1
1
0
0
X
X
X
X
0
1
0
1
X
X
X
X
X
X
X
X
X
X
X
X
1
0
0
1
X
X
X
X
X
X
X
X
X
X
X
X
X
X (12)
X
X
(8)
に着目することにする. この方程式の左辺の積項
数は 4(=N = 2n ) である. これを N -ESOP と呼ぶ
ことにする. この 1 つの N -ESOP を N − 1 個の
3-ESOP に変換することを考える.
この 1 つの N -ESOP は, 次のように N − 1 個の
3-ESOP に変換できる. (図 3 参照).


 f(0, 0) ⊕ y01 ⊕ y02 = 1
y01 ⊕ g0 ⊕ g4 = 1


y02 ⊕ g6 ⊕ g8 = 1
(10)
となる. これらは, それぞれ, 式 (10) の充足割り当
て (y01 , g0 , g4 ) = (1, 0, 1), (1, 1, 0), (0, 0, 0), (0, 1, 1)
に対応している. 1 つの 3-ESOP に対しては, この
充足列は, 4 つのみであることに注意されたい. そ
して, 前節で 3-ESOP にした方程式すべてに対して,
その充足列が求められる.
また, ある 2 つの充足列について, その割り当て
に矛盾が生じない場合その 2 つの充足列は両立可
能であると呼ぶことにする. そうでない場合, その
2 つの充足列は, 両立不可能であると呼ぶことにす
る. すなわち, 充足列 a1 a2 · · · am と a1 a2 · · · am に
対し, すべての l, (1 ≤ l ≤ m) について, al = X か
つ al = X ならば, al = al が成り立つとき, その充
足列 a1 a2 · · · am と a1 a2 · · · am は, 両立可能である.
1 つの 3-ESOP から派生した充足列は, 常に互いに
両立不可能であることに注意されたい.
1 つの 3-ESOP から 4 つの充足列を生成するため
の時間計算量は, O(1) ステップである.
3
−59−
5.3
• gi に相当する記号が 0 か X のときは重みに貢
献しない. また, 構文木の内部節点から生成さ
れた変数 yi も, 重みに貢献しない.
CLIQUE への還元
次に, 前節で求めた充足列に対して, その充足列
をノードラベルとするようなグラフを描く. そして,
そのグラフに対し, 辺は, そのラベルに関して, 両立
可能なノード間に張られるとする. (図 4 参照. )
この重み付けは, Helliwell 方程式からわかるように,
その連立方程式に gi が, それが被覆する最小項の数
だけ現れることに基づいて決定された.
10XXXX
1X10XX
X0XX11
1X01XX
X0XX00
0X00XX
X1XX10
0X11XX
X1XX01
【命題】 5.3
上で述べた方法で得られた節点重みつきグラフにお
いて, 節点重み最小最大クリークを求めることによ
り, 最小 ESOP が得られる.
01XXXX
ノードラベル (y01 y02 g0 g4 g6 g8 )
図 4: 式 (9) に対応するグラフ (ただし, f(0, 0) = 1
とする)
連立している 3-ESOP 式の総数を M とする. そ
のようなグラフに対して, M クリークが存在する
と, その連立 3-ESOP 方程式を充足する解が存在す
ることになる. 例えば, 図 4 については, 式 (9) は, 3
つの式からなるので, 図 4 において, 3-clique を見つ
ければ, そのノードラベルから解がわかる. 図 4 に
3-clique のうちの 1 つを示したが, これは, 式 (9) を
満たす解のうちの 1 つが, (y01 , y02 , g0 , g4 , g6 , g8 ) =
(1, 0, 1, 0, 0, 0) であることを示している.
【命題】 5.2
M を連立方程式に含まれる式の数とする. 上で述
べた方法で構成したグラフにおいて, M -clique が存
在することと, その連立方程式に解が存在すること
は等価である.
5.4
重みつき CLIQUE 問題の利用
ここまでに述べた方法で, Helliwell 方程式を解く
問題を CLIQUE に還元できることがわかった. し
かし, Helliwell 方程式のみでは, ESOP に含まれる
積項数が, 考慮されないことに注意しなければなら
ない. そこで, 重みを持つ CLIQUE を考えることに
より, 最小 ESOP を求める方法について考える.
ここでは, ノードに重みを持つグラフとその節点
重み最小最大クリーク問題について考える. 節点重
み最小最大クリーク問題とは, 最大クリークのうち
で, 節点の重みの総和が, 最小となるようなクリー
クを発見する問題である.
重みは次のように与える.
• 充足列の gi に相当する記号が 1 で, その積項 gi
が被覆する最小項の数が l ならば, 与える重み
は, N/l とする. ここで, N (= 2n ) は, 最小項の
総数である.
また, 充足列において, 1 の数の代わりに, 0 の数
について考えると, ESOP の最小化問題は, 節点重
み最大最大クリーク問題に還元できる.
系 5.1
直前で述べた方法で, 得られた節点重みつきグラフ
において, 節点重み最大最大クリークを求めること
により, 最小 ESOP が得られる.
重みの割り当てにかかる時間計算量は, O(16n ) =
O((2n )4 ) ステップである. これは, 入力 (論理関数
の真理値表) のサイズ O(2n ) に対して, 多項式の時
間計算量である.
6
結び
本稿においては, 量子論理回路の一般的構成法, お
よび, その深さ最小化法について述べた. 量子論理
回路の深さ最小化は, ESOP の最小化問題に深く関
係があることを示した. また, 高速に深さ最小 f-CNOT 回路を求めるために, この問題を, 重み付き
CLIQUE 問題のインスタンスに帰着可能であるこ
とを示した. 今後の課題として, 実際にこの方法で
f-C-NOT 回路を求めるプログラムを実装すること
があげられる.
参考文献
[1] Jae-Seung Lee, Yongwook Chung, Jaehyun Kim, and
Soonchil Lee: “A Practical Method of Constructing
Quantum Combinational Logic Circuits”, 1999. LANL
quant-ph/9911053
[2] T. Sasao: “An Exact Minimization of AND-EXOR Expressions Using Reduced Covering Functions”, Proc.
of the Synthesis and Simulation Meeting and International Interchange, October 20-22, 1993, pp. 374-383.
[3] M.R.Garey and D.S.Johnson: “COMPUTERS AND
INTRACTABILITY A Guide to the Theory of NPCompleteness”, Freeman, San Fransisco, 1979.
[4] E. Tomita and T. Seki,
“An efficient branchand-bound algorithm for finding a maximum clique
and computational experiments”,
Technical Report, UEC-TR-CAS7, The University of ElectroCommunications, 2002.
[5] 名久井行秀, 西野哲朗: 「量子論理回路の深さ最小化につい
て」, 第 6 回量子技術研究会資料 QIT2002-22, pp113-118,
2002.
4-E
−60−