数理解析研究所講究録 1325 巻 2003 年 45-50

45

節点重み最大クリーク抽出に基づく量子回路の深さ最小化
名久井行秀 (Yukihide Nakui ) * 西野哲朗 (Tetsuro Nishino) \dag er
富田悦次 (Etsuji Tomita) \dag er 中村知倫 (Tomonori Nakumura) \dag er

電気通信大学大学院 電気通信学研究科 電子情報学専攻(The Graduate School of ElectrO-Communications)\dag er
電気通信大学電気通信学部 情報通信工学科 情報メディア工学講座(The University of ElectrO-Communications)*1

ユニタリ変換 $U$ によって推移すると考える:

はじめに

現在, 我々が使用しているコンビュータは, 基本的に論理回路から構成されている. これは, 計算可能な関数が, すべて論理関数として表現可能である
ことに基づいている. つまり, 論理関数の計算は, すべての演算の基礎であり, これを効率的に計算することは, 本質的に重要である.
量子力学の概念に基づく量子コンビュータにおいても, 論理関数の計算は, 非常に基本的なタスクである. したがって, 量子回路上で, 論理関数を構成するための方法や, その最小化, 簡単化の方法を確立することは大変重要である.
一方, 最大クリーク抽出問題に対する厳密解を高速に得るためのアルゴリズムが提案されている [4].
そして, そのアルゴリズムを利用して節点重み最大クリーク抽出アルゴリズムが提案された [6]. 本稿で取り扱う量子論理回路の深さ最小化問題は, 入カサイズに対する多項式時間ではその解を求めることができないと強く予想される. このため量子論理回路の最小化問題をクリーク抽出問題に還元することで,高速にその解を求めることができると期待される.
本研究では, 量子論理回路の深さ最小化問題を, 節点重み最大クリーク抽出問題に還元させて解く方法について述べる. また, その還元アルゴリズムの実働化も行ったので, そのことについても報告する.

$U|x)=|y\rangle$,$(UU^{*}=U^{*}U=I)$.

複合的な量子システムの状態空間は, その空間のテンソル積ベクトル空間で与えられる.との線形結合もまた, その空間 の状態状態である. すなわち, $\beta\in c$ としたとき,$V$$|x\rangle$$|x\rangle$$\alpha,$,$|\alpha|^{2}+\beta|^{2}=1$$\alpha|x\rangle+\beta|y)\in V$(3)となる. (重ね合わせの原理)

この重ねあわせ状態を観測すると,・確率同 2 で, 状態 )$|x$・確率$|\beta|^{2}$で, 状態$|y$)が, 観測される.
観測を行うと重ねあわせ状態は失われ, 観測された状態へ推移する. (波束の収縮)

3量子回路, 量子ゲート
この節では, 基本的な量子ゲートを定義する.

定義 3.1(NOT ゲート)
論理否定 NOT ( で表記する) を計算する量子ゲー
トは, ユニタリ作用素$\overline{x}$$N\equiv\{\begin{array}{ll}0 11 0\end{array}\}$2(2)(4)

量子計算

まず, 量子計算について簡単に説明する.
次元複量子コンビュータのシステムの状態は,素ベクトル空間 $V$ のベクトルで表される. 特に計算
基底状態 ), ) を$2^{n}$$|0$$|1$$|0)=\{\begin{array}{l}10\end{array}\}$,$|1)=\{\begin{array}{l}01\end{array}\}$(1)ととる.

システムの状態は, システムに固有な,で与えられる. すなわち$\forall x\in\{0,1\}$,の(5)が成り立つ. このユニタリ作用素を NOT ゲートと呼ひ, 図 1 のように表す.

定義 32 ( -NOT ゲート)$\mathrm{C}$

次のような論理関数$\forall x,y\in\{0,1\}$$2^{n}\mathrm{x}2^{n}$$N|x)=|\overline{x}\rangle=|\mathrm{N}\mathrm{O}\mathrm{T}(x))$,$f(x,y)\equiv(x,x\oplus y)=$ ( $x$ ,EXOR(X, $y$ )) $(6)$46$|x_{1}\}$$|x_{1})$.

..

$|x_{\hslash})$$|x_{n}\}$$N|x\rangle$$\cdot$$.\cdot$

図 1: NOT ゲート$|y)$

図 3: Toffoli ゲートを計算する量子ゲートは,$C_{y}^{l}\equiv|0\rangle\langle 0|\otimes I+|1$(7))( $1|\otimes N$で与えられる. すなわち,$\forall x,y\in\{0,1\}$(8)$C_{y}^{x}|x,y\rangle=|x,x\oplus y)$4

量子論理回路の深さ最小化

定義 41(量子論理回路)
本稿では, ユニタリ変換$U_{f\cdot \mathrm{C}}$(10)$U_{f- \mathrm{C}\cdot \mathrm{N}\mathrm{O}\mathrm{T}}|x)|y\}=|x)|y\oplus f(x))$

が成り立つ. ここで $N$ は式 (4) で定義されたものであり, は, 恒等作用素である. また, $x\oplus y=$
EXOR(x, ) は, と の排他的論理和を表す. この量子ゲートを制御 NOT ゲート (controlled NOTgate, あるいは, -NOT gate) と呼ぶ. これを, 図2 のように表す.
$I$

$x$

$y$

$y$を計算する回路 (f-C-N回路 [1]) が量子論理回路であるとする. f-C-NOT は, function-controlledNOT をあらわす.
$\mathrm{O}\mathrm{T}$$\mathrm{C}$さらに, 本稿ではこの量子論理回路 (f-C-NOT 回路) に対して次の制約を与える:

.

lx》

.

lx\oplus y》

図 2: 制御 NOT ゲート.

.

・構成要素は, NOT ゲートと Toffoli ゲートのみである.

$x=0$ のときは, $N$ が無効になり, 入力 $|x,$ ) が$y$そのまま出力される. ($x=1$ のときは,となる. ($1\oplus y=\overline{y}$$\mathrm{O}\oplus y=y$ト (control bit),であるため)が有効になり, 出力はであるため)$|x,\overline{y}\rangle$

この意味で ) を制御ピッ
を日標ビット (target bit) を呼ぶ.とみることができる.
$|y\rangle$

は, 1 量子ビットで構成され, 目標ビットとしてのみに用いられる.

$|y\rangle$・補助ビットは, 用いない.

このダイアグラムは,$N$} は, $n(\geq 1)$ 量子ビットで構成され, 制御ビットとしてのみに用いられる.

$|x$

$|x$

f-C-NOT 回路は, 最小項に対応するユニタリ変換である最小項ゲートで簡単に構或されうる. 最小項ゲートル は,$\nu^{x}$$M_{y}^{x}$

定義 33(Toffoli ゲート)
$U$ をにのユニタリ行列とする. $n=1,2,$2を次のよのユニタリ行列対して,うに定め, これを $(n+1)$ 量子ビットの一般 Toffoliゲートと呼ぶ. すなわち,$\mathrm{x}2$$\ldots$$2^{n+1}\mathrm{x}2^{n+1}$$\Lambda_{n}U$のように NOT ゲートで挟まれた 1 つの $(n+1)$ ビッ

Toffoli ゲートによって実現されうる. ここでとは, それぞれ, 制御レジスタの第 qubit の状態だけを反転する NOT ゲートと一個の制御ビッと 1 個の目標ビット
トを持つ Toffoli ゲートを$\}\backslash$$N_{\varpi_{i}}$$i$$T_{y}^{x}$$x$$\forall x_{1},$$\ldots,$$x_{n},$$\Lambda_{n}U|x_{1},$$y\in\{0,1\}$$\ldots,$ $x_{n},$$y$表す. そして, f-C-NOT 回路は,,$y)$$U_{f- \mathrm{C}\cdot \mathrm{N}\mathrm{O}\mathrm{T}}= \prod M_{y}^{x}$$|x_{1},$$\ldots,$$x_{n}\}\otimes U|y\}$$\equiv\{$$|x_{1},$$\ldots,$$x_{n},$ $y)$

,

(11)

$\equiv(\prod N_{x:})T_{y}^{x}(\prod N_{\varpi:})$

.

, if

$x_{1}\wedge\cdots\wedge x_{n}=1$if$x_{1}\Lambda\cdots\wedge x_{n}=0$(9)(12)のように, その最小項ゲートすべての積で得られる.
ここで, この積は, 最小項 $m(x)$ について $m(x)=1$を満たす に関する (すなわち, true miniterm に関する) ものである. また, どの最小項ゲートも, 入力の 1 つの状態だけに対して動作するので, 最小項$x$の論理積を表す.と定める. ここで,を $(n+1)$ 量
特に $U$ が $U=N$ であるとき?と呼ぶ. そして, こ
子ビットの Toffi 市ゲートれを図 3 のように表すことに\mbox{\boldmath $\tau$}る.
$n=0$ のときの Toffoli ゲートは, NOT ゲート $N$であるとする. また, $n=1$ のときは, -NOT ゲー
ト (controlled not ゲート) [こ相当する.
$a\wedge b$

は $a,$$b$$\Lambda_{n}N$$T_{\mathrm{y}}^{\varpi}$$\mathrm{C}$ゲートの積の順序は可換である.
次に, 積項ゲートを定義する. 各変数に対して高々を論理積で結合した式を積項と1 つのリテラノレ呼ぶことにする. すなわち, 最小項に対して don’tcare bit を許したものが積項である. そして, Toffoli$(x,\overline{x})$47
ゲートを NOT ゲートで挟み, この積項に対応する状態で制御されるようにしたゲートを積項ゲートと呼ぶことにする.
これらの積項ゲートに関して次の命題が示される[5].

例 12 変数関数の場合 Helliwell 方程式は以下のようになる.
$H(g)$$=$$H(g_{\mathrm{O}}, g_{1}, \ldots, g_{8})$$=$$(g0\oplus g_{4}\oplus g_{6}\oplus g_{8}\oplus f(0,0)\oplus 1)$【命題】 4.1
積項ゲートの積は, 対応する論理表現においては,その積項の排他的論理和 (EXOR) で表すことができる.

$.(g_{1}\oplus g_{4}\oplus g_{7}\oplus g_{8}\oplus f(0,1)\oplus 1)$$.(g_{2}\oplus g_{5}\oplus g_{6}\oplus g_{8}\oplus f(1,0)\oplus 1)$.

$.(g_{3}$ $\oplus g_{8}\oplus g_{7}\oplus g_{8}\oplus f(1,1)\oplus 1)=\mathrm{I}14)$

ここで, go,

ここで, 任意の積項を排他的論理和で結合した
AND-EXOR 論理式を ESOP(Exclusive-0rSumOf Product) と定義する. また, 論理関数 をESOP で表現したときに積項数が最小になる ESOPを論理関数 の最小 ESOP と定義する.
そして, これまでの命題から, 次のことが示される [5].

$g_{1},$$\ldots,$$g_{8}$

については, 図 4 に示す.

$f$

$f$

定理 41(量子論理回路の深さ最小化)
論理関数 $f$ の最小 ESOP は, f-C-NOT 回路に対する深さ最小の量子回路を与える.

ESOP 最小化問題の定式化

5

ここまでの議論で, f-C-NOT 回路の深さ最小化問題が, ESOP の最小化問題に深く関係があることがわかった. この節では, ESOP の最小化問題について述べる.
ESOP における積項による最小項の被覆関係は,偶奇性を持つカバー問題であり, 以下の Helliwell方程式で表される. [2](13)$H(g)=H(g0_{1}g_{1}, \ldots,g\xi-1)=.\wedge S:N-1|=0=1$

図 4: 2 変数の積項の対応図

しかしながら, 効率的に の最小の割り当てを求めるアルゴリズムは, 知られていない. そこで, この問題を CLIQUE 問題に還元させることを考える.
これは, 最大クリーク抽出問題の厳密解を高速に求めるアルゴリズムが提案されており $[4],[6]$ , この還元により, 比較的高速にその最小割り当てを求めることができると期待されるためである.
$g$

6CLIQUE への還元
この節において, Helliwell 方程式の解法をCLIQUE 問題へと還元する. まず, CLIQUE 問題について述べる. CLIQUE 問題は, 次のように定義される. [3]

CLIQUEINSTANCE:
ここで,. $=(_{g\in T-}j\oplus gj)\oplus f(a:)\oplus 1$ であり, $N$ は,$S_{*}$最小項の個数 $(=2^{n}),$ は, すべての可能な積項の数 $(=3^{n})$ である. そして, . は, 番目の最小項を被覆する積項の集合であるとする. $f(a:)$ は, 番目の最小項を 1 にするような入力が与えられたときのの値である. $(f(a:)\in\{0,1\})gj$ は, $gj=1$ のとき, 番目の積項 $gj$ が, ESOP に含まれることを意味する変数とする.
すなわち, は, 番目の最小項が, 偶奇性 (つまり,true minterm ならば積項によって奇数回被覆され,false minterm ならば偶数回被覆される) を満たすための条件をあらわす. そして,は, すべての最小項において, 偶奇性が満たされていることを意味する.
したがって, ESOP の最小化問題は, $H(g)=1$ を満たす の中で, 最小の割り当てのものを求める問

グラフ $G=(V, E)$ と正整数 $K\leq|V|$.

QUESTION:$\xi$$T_{1}$

$i$

$i$

$f$

$i$

$s_{\dot{l}}$

$i$

$G$

は, サイズ $K$ 以上のクリークを持つか61Helliwell 方程式から 3-ESOP ヘ
次に, Helliwell 方程式の解法を CLIQUE 問題へと還元する方法について述べていくが, 理解を助けるために簡単な具体例を用いて説明していく. 例えば, 2 変数論理関数に対する Helliwell 方程式 (14) から, 以下の連立方程式が導き出せる. (ただし, $f(0,0)$等は given とする . )$H(\mathit{9}\mathit{0},g_{1}, \ldots,g\epsilon-1)=$$g_{0}\oplus g_{4}\oplus g_{6}\oplus g_{8}=f(0,0)$$1$$g_{1}\oplus g_{4}\oplus g_{7}\oplus g_{8}=f(0,1)$$\{$$g_{2}\oplus g_{6}\oplus g_{6}\oplus g_{8}=f(1,0)$(15)$g_{3}\oplus g_{6}\oplus g_{7}\oplus g_{8}=f(1,1)$$g$

題といえる. ここで$g$の最小の割り当ては,を最小にするものをさすものとする.

$(. \cdot\sum_{=0}^{\xi-1}g_{1}.)$

まず, この連立方程式のうちの 1 つに着目する. ここでは,$g_{0}\oplus g_{4}\oplus g_{6}\oplus g_{8}=f(0,0)$(16)

48に着目することにする. この方程式の左辺の積項数は $4(=N=2^{n})$ である. これを $N$ -ESOP と呼ぶことにする. この 1 つの $N$ -ESOP を $N-1$ 個の-ESOP に変換することを考える.
この 1 つの N-ESOP は, 次のように $N-1$ 個の3-.ESOP に変換できる. (図 5 参照).
$3$$\overline{f(0,0)}\oplus y_{01}\oplus y_{02}=1$$\{$(17)$\overline{y_{01}}\oplus g_{0}\oplus g_{4}=1$$\overline{y_{02}}\oplus g_{6}\oplus g_{8}=1$

ここで,を利用した.

$1\oplus x=\overline{x}$となる. これらは, それぞれ, 式 (18) の充足割り当) $=(1,0,1),$ $(1,1,0),$ $(0,0,0),$ $(0,1,1)$て ( $y01$ , go,$g_{4}$に対応している. すなわち, 充足列は, 充足割り当てに冗長性を持たせたものである. 1 つの -ESOP に対しては, この充足列は, 4 つのみであることに注意されたい. (2-ESOP に関しては, 充足列は 2 つのみである). そして, 前節で 3-ESOP にした方程式すべてに対して, その充足列が求められる.
また, ある 2 つの充足列について, その割り当てに矛盾が生じない場合その 2 つの充足列は両立可能であると呼ぶことにする. そうでない場合, その2 つの充足列は, 両立不可能であると呼ぶことにすにとる. すなわち, 充足列
対し, すべての $(1\leq l\leq m)$ について, $a_{l}’\neq X$ かつ $a_{l}’’\neq X$ ならば,が成り立つとき, その充とは, 両立可能である.
足列から派生した充足列は, 常に互いに1 つの$3$$a_{1}’a_{2}’\cdots a_{m}’$$a_{1}’’a_{2}’’\cdots a_{m}’’$$l,$$a_{l}’=a_{l}’’$$a_{1}’a_{2}’\cdots a_{m}’$$a_{1}’’a_{2}’’\cdots a_{m}’’$$3 \frac{-}{}\mathrm{E}\mathrm{S}\mathrm{O}\mathrm{P}$

図 5: 式 (16) の構文木

同様な方法で, 式 (15) は, すべて, -ESOP による連立方程式に変換可能である. ただし, $f(0,0)$ 等の値は, given であるとしているので, $f(0,0)$ 等を含む式に関しては, 2-ESOP であるといえる.
以上で述べた方法によ で, 一般に, 1 つの NESOP を $N-1$ 個の 3-ESOP に変換するには, 構文木の内部節点の数に比例するステップで変換でき,要する時間計算量は $O(N)$ ステップである.
$\text{っ}$

両立不可能であることに注意されたい.
1 つの -ESOP から 4 つの充足列を生成するための時間計算量は, $O(1)$ ステップである.

63CLIQUE への遺元
次に, 前節で求めた充足列に対して, その充足列をノードラベルとするようなグラフを描く. そして,そのグラフに対し, 辺は, そのラベルに関して, 両立可能なノード間に張られるとする. (図 6 参照)【命題】 6.1$N$-ESOP は, $N-1$ 個の番 ESOP に変換できる.

62充足列の定義

次に, 1 つの 3–ESOP に着目する. 例えば, 式 (17)における(18)$\overline{y_{01}}\oplus g_{0}\oplus g_{4}=1$に着目することにする.

ここで, ある 3-ESOP を満たす割り当てに対し, 充足列を定義する. 充足列は, 記号列$\{0,1, X\})$ で表される $(1 \leq i\leq m)$ :$a_{1}’a_{2}’\cdots a_{m}’(a’.\cdot\in$$\{$ $a’..\cdot=Xa’\cdot=0(,\mathrm{o}\mathrm{r}1)$

, if
if

$\mathfrak{y}$$arrow \mathrm{c}$$b\mathrm{h}6$$a:\}_{\llcorner}^{\vee}0(\# f.\mathrm{t}1,1\hslash \mathrm{P}$$a$.

は, 特定されない特.
: はその 3-ESOP では(19)

ただし, $A=\{a_{1}, a_{2}, \cdots, a_{m}\}$ は, 着目している$N$-ESOP に対する構文木の根を除く節点のラベルに対応している.

{$y_{01},y_{02},$go,$g_{1},$$\ldots,$

関する充足列は,$y\mathrm{o}\iota$

1
10
0

$y02$

$X$
$X$

$X$
$X$

go0
10
1$g\epsilon$

例えば, 式 (16) では, $A=$} である. そして, 式 (18) に$g_{1}$$g\mathrm{a}$$g\mathrm{s}$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$g_{4}$

1001$g\epsilon$$g\epsilon$$g\tau$$g_{8}$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

$X$

(20)

図 6: 式 (17) に対応するグラフ (ただし, $f(0,0)=1$とする)
ここで, 連立している 3–ESOP 式の総数を $M$ とする. そのようなグラフに対して, M- クリークが存在すると, その連立 3-ESOP 方程式を充足する解が存在することになる. 例えば, 図 6 については,式 (17) は, 3 つの式からなるので, 図 6 において,シクリークを見つければ, そのノードラベルから解がわかる. 図 6 にシクリークのうちの 1 つを示したが, これは, 式 (17) を満たす解のうちの 1 つが,$(y_{01},y_{02},g_{0},g_{4},g_{6},g_{8})=(1,0,1,0,0,0)$ であることを示している.
前節までの議論によって, HeUiwell 方程式から導かれる 3–ESOP と 2-ESOP の総数 $M$ は, $N(N-1)$ 個である. そして, その充足列から CLIQUE 問題のインスタンスとしてのグラフの節点数は, $2N(2N-3)$となる. したがって, グラフを構成するための時間計算量は, $O((2N(2N-3))^{2})=O(N^{4})$ ステツ

49プである. 本研究では,変数論理関数として真理値表が入力されるとしているので, そのサイズは$O(2^{n})=O(N)$ であり, この還元は, 入カサイズに関して多項式である.

系 6.1
直前で述べた方法で, 得られた節点重みつきグラフにおいて, 節点重み最大クリークを求めることにより, 最小 ESOP が得られる.

【命題】 62

いては, ノードラベルである充足列の長さに比例し,$n$

1 つの節点に重みを与えるための時間計算量につ$M(=N(N-1))$ を連立方程式に含まれる式の数とする. 上で述べた方法で構成したグラフにおいて,M- クリークが存在することと, その連立方程式に,解が存在することは等価である.
64

重みつきクリーク問題の利用

ここまでに述べた方法で, Helliwell 方程式の解法を CLIQUE 問題に還元できることがわかった. しかし, Helliwell 方程式のみでは, ESOP に含まれる積項数が, 考慮されないことに注意しなければならな
い. そこで, 重み付きクリーク抽出問題を考えることにより, 最小 ESOP を求める方法について考える.
まず, ノードに重みを持つグラフとその節点重みが最小な最大クリーク抽出問題について考える. 節
点重みが最小な最大クリーク抽出問題とは, 最大クリークのうちで, 節点の重みの総和が, 最小となるようなクリークを発見する問題である. そして, これが節点重みが最大な最大クリーク抽出問題 (以降,節点重み最大クリーク抽出問題とする) に還元できることを示す. 節点重み最大クリーク抽出問題に対する高速なアルゴリズムについては, 文献 [6] で提案されている.

積項数を考慮するための節点の重みは, 次のように与える.

・充足列の に相当する記号が 1 で, その積項が被覆する最小項の数力 q ならば, 与える重みは, $N/l$ とする. ここで, $N(=2^{n})$ は, 最小項の総数である.
$g_{i}$$g\dot{.}$.に相当する記号が 0 か $X$ のときは, 重みに貢献しない. また, 構文木の内部節点から生成された変数 : は, 重みに貢献しない.
$g\dot{.}$$y$

この重み付けは, Heffiwell 方程式からわかるように,その連立方程式に : が, それが被覆する最小項の数だけ現れることによる. つまり, 各 . に関して, その連立方程式 (すなわち, 1 つのクリーク) において,出現回数 重みが一定となる.
$g$$g_{1}$$O(2^{n})=O(N)$ ステップである. 節点の総数は, 前
節で述べたように $2N(2N-3)$ であり, グラフすべての節点に重みを与えるのに, $O(N^{3})$ ステップかかる. つまり, 重みの付与も入カサイズに関して多項式時間の計算量で求めることができる.

7

実働化とその実行時間

ここまでに述べた還元アルゴリズムを 言語で実働化した. そして, 文献 [6] に基づくアルゴリズムを用いて, 実際に論理関数の最小 ESOP を求めた結果を表 1, 表 2 に示す.
計算機環境は, 以下のとおりである.
$\mathrm{C}$.
.

$\mathrm{C}\mathrm{P}\mathrm{U}$$\mathrm{P}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{u}\mathrm{m}4$$2.8\mathrm{G}\mathrm{H}\mathrm{z}$OSLinux・コンバイラ, およひコンパイルオプション

gcc-O2

実際のプログラムの実行に要した時間を表 1, 表2 に示す. ここで用いた節点重み最大クリーク抽出
アルゴリズム VWMC 等については, 文献 [6] において提案されたものである. 詳細は省略するが, 簡単に述べておく:

VWMC : 最大クリークを求めながら, 節点重み最大クリークを求めるアルゴリズム.

VWMC, : 最大クリークのサイズ をあらかじめ与え, 節点重み最大クリークを求めていくもの.
$\omega$$\mathrm{V}\mathrm{W}\mathrm{M}\mathrm{C}_{\omega}+$:VWMC, にクリーク重みの上界による分枝限定を加えたもの.

表中で用いている論理関数の表記法については,以下のとおりである. 論理関数 $f(x_{1},x_{2}, \ldots, x_{n})$は, その論理関数の最小項の論理和に対して係数$m_{2^{n}-1}m_{2^{n}-2}\cdots m_{1}m_{0}(m:\in\{0,1\})$ を与えることで表現するできる:$f(x_{1},x_{2}, \ldots,x_{n})$$=$$m_{0}\overline{x_{1}}\overline{x_{2}}\cdots\overline{x_{n}}$$\mathrm{v}$$m_{1}\overline{x_{1}}\overline{x_{2}}\cdots\overline{x_{\mathfrak{n}-\sim}}x_{\mathfrak{n}}$$\vee$$m_{2}\overline{x_{1}}\overline{x_{2}}\cdots\overline{x_{n-1}}x_{n}$$\mathrm{x}$【命題】 6.3
上で述べた方法で得られた節点重みつきグラフにおいて, 節点重みが最小な最大クリークを求めることにより, 最小 ESOP が得られる.
また, 充足列において, 1 の数の代わりに, 0 の数について考えると, ESOP の最小化問題は, 節点重み最大クリーク抽出問題に還元できる.

$m_{2^{n}-2}x_{1}x_{2}\cdots x_{n-1}\overline{x_{n}}$$m_{2^{n}-1}x_{1}x_{2}\cdots xn-1xn(21)$ビ
そして, その係数列 $m_{2^{n}-1}m_{2^{n}-2}\cdots m_{1}m0$ を
桁の 16
ットの 2 進数とみる. さらに, それを$2^{n}$$2^{\mathfrak{n}}/4$進数としたもので論理関数を表現している.

508

表 1: 2 変数論理関数の場合 (節点数: 40

枝密度: 0.80000)

表 2: 3 変数論理関数の場合 (節点数: 208

枝密度: 0.946860)[31考察
1. 3 変数までの規模では, 還元に要する計算時間は無視できる程小さいことがわかった. また, 還元だけに関すれば, 4 変数の場合: 000000 秒, 5変数の場合: 005000 秒, 6 変数の場合: 1.00000秒で計算ができることもわかった.

2. 3 変数において VWMC 訝の結果が他に比べて非常に高速であることがわかる.
3. 4 変数以上の論理関数については, 計算時間が24 時間以上かかることがわかった. これは, 枝密度が高く (4 変数では, 0.984172), 節点数が928(4 変数の場合) というグラフが生或され,最大クリークが多数存在することによると考えられる.

このグラフにおいて重みを無視して, 最大クリークを 1 つ抽出する場合, 枝密度が高い場合に効による実率化されたアルゴリズム
この基本アルゴリ
行結果は, 15 秒以下であり,ズムの考慮により, 改善が期待される.
$\mathrm{M}\mathrm{C}\mathrm{Q}\mathrm{d}+[4]$4. 少なくとも 3 変数までに限れば, 論理関数の種類による実行時間の差は, ほとんどないことがわかる.

参考文献,[1] Jae Seung Lee, Yongwook Chung, Jaehyun
Soonchil Lee: “A Practieal Method of Constructing Quantum Combinational Logic Circuit\S ’’, 1999. LANL quant-Ph/9911053
Exact Minimization of AND[2] T. Sasao:
EXOR Expressions Using Reduced Covering
FunctiOn8”, Proc. of the Synthesis and Simulation
Meeting and International Interchange, October
2022, 1993, PP. 374-383.
$\mathrm{K}\mathrm{i}\mathrm{m}$$\mathrm{m}\mathrm{d}$$‘\iota \mathrm{A}\mathrm{n}$

[4]

[5]

[6]