2.5. SYNTHESIS EFFICIENCY 39
statistical distribution of gate costs [29], ranging from 0 to
3
2
2
w
2 D 10, with an average gate
cost of about 5.9.
e average result of 5.9 is a lower cost than the average cost of 6.6 in Section 2.3. Also
the above maximum cost of 3 2
w1
2 is cheaper than the maximum cost of .3
w
1/=2,
found in Section 2.3. We note that it is thanks to eorem 1.2 of Section 1.8 that the primal
synthesis method of the previous section needs only a cost of order 3
w
. Applying eorem 1.1
instead of eorem 1.2 would lead to a cost of order 4
w
. In contrast, the dual synthesis method
of the present section leads to a cost of order only 2
w
, irrespective of which theorem is applied.
Choosing eorem 1.2, as we did above, merely causes one of the two controlled NOTs to have
a control function f .A
2
; A
3
; : : : ; A
w
/ that satisfies f .0; 0; : : : ; 0/ D 0. is is explicitly realized
in our procedure by starting the first coil with label F
1
.1/ D 0.
2.5 SYNTHESIS EFFICIENCY
According to Sections 2.3 and 2.4, respectively, we need for the primal synthesis of a 3-bit circuit,
on average, 6.6 controlled NOTs, whereas for the dual synthesis, on average, only 5.9 controlled
NOTs. Below, we will investigate why the dual decomposition is more efficient than the primal
one.
Both synthesis methods decompose an arbitrary element of a given group G (here the
group P(n) of the n n permutation matrices) into a product of three building blocks:
• a member g
1
of a subgroup G
1
,
• a member g
2
of a subgroup G
2
, and
• a member g
3
of a subgroup G
3
.
ere exist order.G
1
/ order.G
2
/ order.G
3
/ cascades g
1
–g
2
–g
3
. Because some of the products
g
1
g
2
g
3
can be equal, this yields order.G
1
/ order.G
2
/ order.G
3
/ different products or less dif-
ferent products. As we need synthesis of all order.G/ elements of G, we have the necessary
condition
order.G
1
/ order.G
2
/ order.G
3
/ order.G/ : (2.6)
An efficient synthesis method has a product order.G
1
/order.G
2
/order.G
3
/ that exceeds
order.G/ as little as possible. en, we indeed synthesize all members of G with building blocks
that are as simple as possible. We will call the ratio
order.G
1
/ order.G
2
/ order.G
3
/
order.G/
the synthesis overhead . is number, necessarily equal to or larger than 1, should be as small
as possible.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.