Multiplicative depth-2 cone rewriting

アイデア

• $y1,\cdots ,ym$ のサブセットのうちクリティカルなノードから回路を上方に走査, 最初に見つかったANDゲートで停止

このようにして、乗法的深さ2の円錐が得られる。
以下ではこのような円錐を書き換えて，全体の乗法深さが減少するような書き換える方法を紹介します。
円錐形の書き換え演算子は、前述したように、
XORゲート $U_y$ のcritical inputに対して、深さ2のパス書き換え演算子を適用することと等価
変換後に新たに生成されるノードの数を減らすことを目的
まず, 乗法深さ2のConeのための変換を提示し, それを任意深さの円錐に一般化
mult-depth 2の critical cone ${\delta }^2$
ANDゲート $v_t$ で終わり、ANDゲート

$$v_1,\cdots ,v_n(v_i\in \mathrm{anc}({\mathrm{v}}_{\mathrm{t}}))$$

で終わる

$$l(v_i)=l(v_t)-1({}^{\forall }i=1,\cdots ,n)$$

$v_1,\cdots ,v_n$
の出力はXORゲート
$U_y$
によって結合され,
$v_t$
の1入力となる

もうひとつの入力は
$a_t$

$$a_1^{(i)},a_2^{(i)}(s.t.l(a_1^{(i)}))\ge l(a_2^{(i)}))$$

を
$v_i$
の2入力とする.

$U_y$
の入力
$y_1,\cdots ,y_m$
は
critical
ではない
式にすると

$$(\underset{i=1}{\overset{n}{⨁}}(a_1^{(i)}\cdot a_2^{(i)})\oplus \underset{i=1}{\overset{m}{⨁}}{y}_i)\cdot a_t$$

変換後は

$$(\underset{i=1}{\overset{n}{⨁}}(a_t\cdot a_2^{(i)})\cdot a_1^{(i)})\oplus (a_t\cdot \underset{i=1}{\overset{m}{⨁}}{y}_i)$$

この変換によってANDゲート

$$u^{(i)}=(a_2^{(i)}\cdot a_t)\cdot a_1^{(i)}$$

は
mult-depth
が下がった

$U_y^{\prime }$
はcritical inputs を持たない

$r$
の
mult-depth
は1下がった

$$\underset{u\in \mathrm{pred}(v_k)}{\min }l(u)<l(v_t)-2,{}^{\forall }{v}_k,k\in \{1,\cdots ,n,t\}$$

… (3)
を満たすとき
mult-depth
は削減できる
(意味): todo