# Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis

Authors: Zhiqiang Li; Hanwu Chen; Guowu Yang; Wenjie Liu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Owing to the exponential nature of the memory and run-time complexity, many methods can only synthesize 3-bit reversible circuits and cannot synthesize 4-bit reversible circuits well. We mainly absorb the ideas of our 3-bit synthesis algorithms based on hash table and present the efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits with many types of gates and at mini-length cost based on constructing the shortest coding and the specific topological compression; thus, the lossless compression ratio of the space ofn-bit circuits reaches near 2×n!. This paper presents the first work to create all 3120218828 optimal 4-bit reversible circuits with up to 8 gates for the CNT (Controlled-NOT gate, NOT gate, and Toffoli gate) library, and it can quickly achieve 16 steps through specific cascading created circuits.


---

## Body

## 1. Introduction

Quantum computer is equivalent to quantum Turing machine, and quantum Turing machine is equivalent to a quantum logic circuit. Therefore, the quantum computer can be constructed by cascading and combining the quantum logical gates. Nowadays, many kinds of reversible quantum gates have been proposed, for example, CNOT gate [1], Toffoli gate, and Fredkin gate [2]. How to automatically construct the quantum circuit at small cost using given quantum gates? Several approaches for reversible logic circuit synthesis have been presented. Song et al. [3] presented algebraic characteristics of reversible gates. Iwama et al. [4] introduced transformation rules for CNOT-based circuits. Miller et al. [5] gave a synthesis method based on truth table and used template technology to simplify the circuit. Mishchenko and Perkowski [6] proposed a Reed Muller-based algorithm for optimizing quantum circuit. Gupta et al. [7] also gave a heuristic algorithm based on Reed Muller; Li et al. [8] proposed a general template algorithm. Shende et al. [9, 10] reduced the synthesis for reversible logic circuit to permutation and gave an effective recursive algorithm. Then, Yang et al. [11] reduced the synthesis for reversible logic circuit to group theory and presented a novel algorithm based on group-theory algebraic software GAP, while its performance was better than most others. Until today, we have not found a general and effective algorithm for multivariable quantum circuit synthesis. Owing to the exponential nature of the memory and run-time complexity, many existing methods can only synthesize 3-bit reversible circuits, and they perform only four steps for the CNP library in 4-bit circuit synthesis with mini-length for memory overflow [11–13], however, [14–16] are able to achieve 12 steps by using an enhanced bidirectional synthesis approach. We mainly absorb the ideas of our efficient 3-bit synthesis algorithms based on hash table and present the novel and efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits [17]. Using lossless compression and cascading created circuits, our algorithms can get all the mini-length circuits whose lengths range from 0 to 8 with numbers 1, 28, 576, 9886, 147841, 1986374, 24375385, 274500662, and 2819198076, respectively; it can synthesize all the optimal 16-gate mini-length circuits for the CNT library.


## 2. Background

Definition 1.
LetM be a finite set; then, a permutation of M is a bijection σ:M→M. If |M|=m, σ is an m permutation. Normally, the permutation of group theory begins from one, but our program in c++ can work well if the permutation contains zero. Let M={0,1,…,m-1}, and a permutation σ=(01⋯m-1p0p1⋯pm-1)=(p0,p1,…,pm-1). It can be denoted as the cyclic form; for example, τ=(a1a2⋯ai), i⩽m; that is, a1↦a2⋯↦ai↦a1, σ-1=(p0p1⋯pm-101⋯m-1), and πe=(01⋯m-101⋯m-1) is the identity permutation of M, such that πe∘σ=σ∘πe=σ for any permutation σ of M.The reversible function can be described by permutation or truth table. The 3-bit reversible logic circuit in Figure1 can be described by the permutation σ=(0123456726017354)=(2,6,0,1,7,3,5,4)=(02)(1653)(47) or the truth table in Table 1, where the input or output is 〈xn-1,…,x1,x0〉2=∑i=0n-1‍(xi·2i) and 〈yn-1,…,y1,y0〉2=∑i=0n-1‍(yi·2i), respectively. Let the permutations of NOT gate, Toffoli gate, and CNOT gate be σ1, σ2, σ3; then, σ=σ1∘σ2∘σ3=σ1σ2σ3.Table 1
True table.
Input
Output
〈
x
2
,
x
1
,
x
0
〉
2
x
2
x
1
x
0
〈
y
2
,
y
1
,
y
0
〉
2
y
2
y
1
y
0
0
0
0
0
2
0
1
0
1
0
0
1
6
1
1
0
2
0
1
0
0
0
0
0
3
0
1
1
1
0
0
1
4
1
0
0
7
1
1
1
5
1
0
1
3
0
1
1
6
1
1
0
5
1
0
1
7
1
1
1
4
1
0
0Figure 1
Quantum reversible logic circuit.In order not to repeat explanation, the following definitions are given.(1)
LetC be any n-bit reversible logic circuit with length l; it is a cascade of quantum gates g1,g2,…,gl, denoted by C=g1g2⋯gl.(2)
LetSF={1,2,…,n!}, SM={1,2,…,m}, and SB={0,1}.(3)
For permutationσ=(0,1,…,n-1), there are n! kinds of permutations, which are denoted by σ1,σ1,…,σn!, respectively.(4)
Letπ(g) be the permutation of quantum gate g; then, the permutation of circuit C is π(C)≡π(g1g2⋯gl)=π(g1)π(g2)⋯π(gl).(5)
Letcost(C) be the cost of quantum circuit C and cost(g) be the cost of quantum gate g.(6)
All the circuits in the paper are the reversible logic circuits.Because permutation is often used in our algorithms, the effective expression of permutation is very important to improve the algorithms. Thus, we present the shortest coding scheme with saving plenty of space, which maps a permutation to an integer with the fewest bytes.Definition 2.
LetOpi be ordinal number of pi in sequence p0,p1,…,pi,…,p2n-1; then, it is the number of members which are both smaller than and before pi; that is,
(1)Opi=∑j=0i-1‍sgn(pi-pj),sgn(x)={1,(x>0),0,else.Ordinal numbers of all members in the sequencep0,p1,…,pi,…,p2n-1 construct ordinal number sequence: (Op0,Op1,…,Op2n-1), and obviously Op0≡0 and Op2n-1≡P2n-1. For example, the ordinal number sequence of σ=(2,6,0,1,7,3,5,4) is (0,1,0,1,4,3,4,4).Lemma 3.
The ordinal number ofpi in Definition 2 can also be defined as
(2)Opi=pi-∑j=i+12n-1‍sgn(pi-pj).Proof.
From (1), Opi is the number of members which are both smaller than and before pi, and ∑j=i+12n-1‍sgn(pi-pj) is the number of members which are both smaller than and after pi; so, the sum of them is the number of members which are smaller than pi in the sequence Opi+∑j=i+12n-1‍sgn(pi-pj)=|{0,1,…,pi-1}|=pi.Theorem 4.
One can get the ordinal number sequence in Definition2 by 22n-2-2n-1 comparison times merely.Proof.
The comparison times using (1) and Lemma 3 are i and 2n-1-i for computing Opi, respectively, and comparison times are all ∑i=12n-1‍i=∑i=12n-1‍(2n-1-i)=22n-1-2n-1 for computing ordinal number sequence. These two formulas can be chosen depending on condition to reduce the comparisons times. We use (1) if i<2n-1-i; that is, i≤2n-1-1, and use Lemma 3 if i>2n-1-i; that is, i≥2n-1. So, our method is that using (1) when pi is in the first half part of the sequence, and otherwise using Lemma 3, their comparison times are ∑i=12n-1-1‍i and ∑i=2n-12n-1‍(2n-1-i), respectively. Finally, the whole comparison times are ∑i=12n-1-1‍i+∑i=2n-12n-1‍(2n-1-i)=22n-2-2n-1; it is lesser than the half of 22n-1-2n-1.Definition 5.
The shortest coding of the permutation(p0,p1,…,p2n-1) is Code(p0,p1,…,p2n-1)=∑i=12n-1‍(Opi·i!).Lemma 6.
If the ordinal number sequences of two permutations are the same, then the two permutations must be also the same.Proof.
Suppose that we get any two permutations of the setS={0,1,…,2n-1}, P=(p0,p1,…,p2n-1), and Q=(q0,q1,…,q2n-1); if their ordinal number sequences are all B=(b0,b1,…,b2n-1), then we will prove that P=Q; namely, for all i∈{0,1,…,2n-1}, p2n-1-i=q2n-1-i.
Proof by Mathematical Induction
Basis. Clearly, Op2n-1=b2n-1, Oq2n-1=b2n-1; then, P has b2n-1 elements which are lesser than p2n-1; that is, p2n-1 is (b2n-1+1)th small element in S. Similarly, q2n-1 is (b2n-1+1)th small element in S, and so p2n-1=q2n-1=b2n-1; that is, p2n-1-i=q2n-1-i for i=0.
Inductive Assumption. Let p2n-1-i=q2n-1-i for i=0,1,…,j.
Inductive Step. When i=j+1, Op2n-2-j=b2n-2-j, and P has b2n-2-j elements which are both lesser than and before p2n-2-j; that is, p2n-2-j is (b2n-2-j+1)th small element in {p0,p1,…,p2n-2-j}, and let Tp={p2n-1-j,p2n-j,…,p2n-1}, Tq={q2n-1-j,q2n-j,…,q2n-1}; then {p0,p1,…,p2n-2-j}=S-Tp; that is, p2n-2-j is (b2n-1-j+1)th small element in S-Tp. Similarly, q2n-2-j is (b2n-1-j+1)th small element in S-Tq. Now, using the inductive assumption, we get Tp=Tq; that is, S-Tp=S-Tq, and so p2n-2-j=q2n-2-j; thus, p2n-1-i=q2n-1-i for i=j+1.Lemma 7.
The coding function Code maps each ordinal number sequence to a distinct coding.Proof.
Letc=Code(p0,p1,…,p2n-1)=∑i=12n-1‍Opi·i!; that is, the function Code maps ordinal number sequence B=(Op0,Op1,…,Op2n-1) to coding c, and so the remainder is Op1 when c is divided by 2, the quotient is ∑i=22n-1‍(Opi·i!/2), and the remainder is Op2 when this quotient is divided by 3. Follow the same steps; the recursive formula is n1=c, ni+1=⌊ni/(i+1)⌋, Opi=ni-(i+1)ni+1, i∈{1,2,…,2n-1}. Clearly, the coding function Code maps each ordinal number sequence to a distinct coding, and vice versa; so, it is a one-to-one correspondence between each coding and ordinal number sequence.Theorem 8.
The function Code is the shortest coding function.Proof.
2
n different elements in {0,1,…,2n-1} totally have 2n! permutations. According to Lemma 6, two different ordinal number sequences corresponding to two permutations must be different, and according to Lemma 7, coding function Code maps each ordinal number sequence to a distinct coding. So, the codings of all permutations are different.
By Definition5, max(Opi)=i, min(Opi)=0, min(H(p0,p1,…,p2n-2,p2n-1))=min(∑i=12n-1‍(Opi·i!))=∑i=12n-1‍(min(Opi)·i!)=∑i=12n-1‍(0·i!)=0, max(H(p0,p1,…,p2n-2,p2n-1))=max(∑i=12n-1‍(Opi·i!))=∑i=12n-1‍(max(Opi)·i!)=∑i=12n-1‍(i·i!)=2n!-1. So, the number of all codings is L=MAXH-MINH+1=2n!-1-0+1=2n!(n>0). There are 2n different elements in {0,1,…,2n-1} corresponding to 2n! different coding, and thus the minimum number of all the codings is 2n!. Therefore, the function Code is the shortest coding function.The subject of topology is concerned with those features of geometry which remain unchanged after twisting, stretching, or other deformations of a geometrical space; any continuous change which can be continuously undone is allowed, but cannot be broken.Definition 9.
Line permutation is the operation which permutes quantum lines in quantum circuit without break. Obviously, it is a specific topological transformation. LetPσ(g) be quantum gate g being operated by line permutation σ. The circuit G=g1g2, operated by line permutation σ, is Pσ(G)=Pσ(g1g2)=Pσ(g1)Pσ(g2).For example, in Figure2, quantum circuit G is operated by line permutation σ, where σ=(012201)=(02)(01).Figure 2
The line permutation of quantum circuit.The circuit after applying topological transformation can be simplified, because the gate's function cannot be changed when the order of its same kind of points is changed.ConsiderPσ(C)=Pσ(g1g2⋯gl)=Pσ(g1)Pσ(g2)⋯Pσ(gl). If there are m basal gates in quantum gate library L, g1,g2,…, and gm, then L=⋃‍j∈SF,i∈SMPσj(gi), and the set of all permutations of the gates in L is σ=⋃‍j∈SF,i∈SMPσj(π(gi)).The set of all circuits ofS operated by line permutation σ is denoted by Pσ(S)={Pσ(G)∣G∈S}.Definition 10.
Direction transform (Figure3) has two kinds of operations, obverse direction transform and reverse direction transform. It is also a specific topological transformation; the obverse direction transform b of gate g is denoted by Rb(g). Thus, R0(g)=g, R1(g)=g-1. Gate g is symmetric, if g=g-1, and otherwise it is asymmetric. Let circuit G=g1g2, and the two gates are symmetric; then, R1(G)=R1(g1g2)=g2-1g1-1=g2g1.Figure 3
The direction transform of quantum circuit.ConsiderR1(C)=R1(g1g2⋯gl)=(g1g2⋯gl)-1=gl-1gl-1-1⋯g2-1g1-1. R1(C)=glgl-1⋯g2g1, if all the gates in C are symmetric. Direction transform can be used in our synthesis algorithms only if all quantum gates are symmetric or their inverse gates are all in the quantum gate library.The set of all circuits ofS operated by direction transform b is denoted by Rb(S)={Rb(G)∣G∈S}.From Definitions9 and 10, the following properties can be gotten.Property 1.
P
σ
(
P
τ
(
C
)
)
=
P
σ
∘
τ
(
C
) and Pσ(Pσ-1(C))=Pσ-1(Pσ(C))=C, but Pσ(Pτ(C))≠Pτ(Pσ(C)), where Pσ(Pτ(C)) denotes the circuit C being operated by line permutation τ and line permutation σ; so, Pσ(Pτ(C))=Pτ∘σ(C). σ∘σ-1=σ-1∘σ=πe, and thus Pσ-1(Pσ(C))=Pσ(Pσ-1(C))=Pπe(C)=C. Normally, τ∘σ≠σ∘τ; hence, Pσ(Pτ(C))≠Pτ(Pσ(C)).Property 2.
R
b
1
(
R
b
2
(
C
)
)
=
R
b
2
(
R
b
1
(
C
)
)
=
R
b
1
⊕
b
2
(
C
), where Rb1(Rb2(C)) denotes the circuit C being operated by direction transform b1 and direction transform b2. The circuit is not changed, if b1=b2, and otherwise, it is operated by reverse direction transform; thus, Rb1(Rb2(C))=Rb1⊕b2(C). In the same way, Rb2(Rb1(C))=Rb1⊕b2(C).Property 3.
R
b
(
P
σ
(
C
)
)
=
P
σ
(
R
b
(
C
)
), where Rb(Pσ(C)) denotes the circuit C being operated by line permutation σ and direction transform b, and Pσ(Rb(C)) denotes that the circuit C is operated by direction transform b and line permutation σ. Line permutation is vertical transform, and direction transform is horizontal transform; so, the order of the two operations does not affect their compound function, and thus Rb(Pσ(C))=Pσ(Rb(C)).We show by Properties1, 2, and 3 that the order of the previous topological transformations except the line permutations in quantum circuits can not affect their compound functions.Lemma 11.
For allk∈SF, for all b∈SB, cost(C)=cost(Rb(Pσk(C))).Proof.
Consider any quantum gateg, operated by any line permutation σk, whose type is not changed so, cost(Pσk(g))=cost(g). When any quantum circuit C is operated by any direction transform, its direction may be changed, but its cost can not be changed; thus, for all b∈SB, cost(Rb(C))=cost(C), and then cost(Rb(Pσ(C)))=cost(Pσ(C))=∑i=1l‍cost(Pσ(gi))=∑i=1l‍cost(gi)=cost(C), where cost(C) of optimal C should be minimal with the cost function. If for all i∈{1,2,…,l}, cost(gi)=1, then cost(C)=l; that is, the length of C is minimal, and thus minimum cost standard degenerates to mini-length standard.Lemma 12.
Any optimal circuit after any specific topological transformation must be optimal.Proof.
Let the circuitC be optimal, and circuit D=Rb(Pσ(C)). Assume that circuit D is not optimal, and so there is an optimal circuit E with π(E)=π(D) and cost(E)<cost(D); thus, π(Rb(Pσ-1(E)))=π(Rb(Pσ-1(D)))=π(Rb(Pσ-1(Rb(Pσ(C)))))=π(C). Let circuit F=Rb(Pσ-1(E)); by the Lemma 11, there is π(F)=π(C), and cost(F)=cost(E), cost(D)=cost(C). Thus, cost(F)<cost(C); that is, the functions of circuit F and circuit C are the same, but F is more optimal than C in contradiction to C being optimal.Lemma 13.
By Definition9,  for all k∈SF, Pσk(L)=L.Proof.
By permutation group theory, for alli,j∈SF, σiσj∈{σ1,σ2,…,σn!}, and i≠j→σi≠σj, and thus for all k∈SF, σiσk≠σjσk, |{σ1σk,σ2σk,…,σn!σk}|=n!, {σ1σk,σ2σk,…,σn!σk}={σ1,σ2,…,σn!}. Similarly, we have
(3)∀k∈SF,{σkσ1,σkσ2,…,σkσn!}={σ1,σ2,…,σn!}.
For all k∈SF, Lnew=Pσk(L) = Pσk(⋃‍j∈SF,i∈SMPσj(gi)) = ⋃‍j∈SF,i∈SMPσjσk(gi)=(3)⋃‍i∈SM(⋃‍j∈SFPσj(gi)) = ⋃‍j∈SF,i∈SMPσj(gi)=L.Definition 14.
LetG be a circuit, Min(π(G))=min{Rb(Pσj(π(G)))∣j∈SF,b∈SB}, and thus ∃k∈SF, ∃c∈SB, Rc(Pσk(τ))=Min(π(G)). Let Min(G)=Rc(Pσk(G)); Min(G) is the minimal permutation circuit of G. All circuits gotten by all the specific topological transformations of G compose the set S=⋃‍j∈SF,b∈SBRb(Pσj(G)). The function GetMin(τ,σ,b) returns the minimal permutation π, line permutation σ and direction transform b, where π=Rb(Pσ(τ))=Min(τ).Theorem 15.
From Definition14, Min(G) is a circuit of S, and S can be gotten only by Min(G); that is, the lossless compression ratio of the space is near 2×n!.Proof.
Obviously, all the minimal permutation circuits ofS must be Min(G),S=⋃‍j∈SF,b∈SBRb(Pσj(G)), Min(G)=Rc(Pσk(G)). Let S′ be the set of all circuits gotten by all the specific topological transformations of Min(G); thus, S′=⋃‍j∈SF,b∈SBRb(Pσj(Min(G))) = ⋃‍j∈SF,b∈SBRb(Pσj(Rc(Pσk(G))))=Property3⋃‍j∈SF,b∈SBRb⊕c(Pσkσj(G))=(3)⋃‍j∈SF,b∈SBRb(Pσj(G) = S, where |SF|=n!, |SB|=2; that is, |SF|×|SB|=2×n!, and few specific topological transformation circuits may be the same. Thus |S|≤2×n! and |S|≈2×n!. Then, the lossless compression ratio of the set S is near 2×n!.LetLn,G be an n-bit quantum gate library with gates G, and T(Ln,G) a set of all n-bit reversible circuits synthesized by any gates in Ln,G. For example, 2×n!|n=4=48. The average compression ratio of T(L4,CNT), whose circuits are synthesized 8 layers at minimal cost, is 47.95.Given two quantum logic circuits,D and G, ∃h,j∈SF, ∃b,c∈SB, Rb(Pσh(G))=Rc(Pσj(D))→G,D∈S→Min(D)=Min(G).Taking all specific topological transformations of a 3-bit circuit as an example, there are2×n!|n=3=12 kinds of transformations. In Table 2, the bidirectional arrow expresses exchanging the two quantum lines, and the minimal permutation circuit of all circuits is circuit B by computing coding.Table 2
All the specific topological transformations of 3-bit logic circuit.
Line permutation
Obverse direction
Coding
Reverse direction
Coding
(
0
1
2
0
1
2
)
=
π
e
23759
28679
(
0
1
2
1
0
2
)
=
(
0
1
)
25199
34439
(
0
1
2
0
2
1
)
=
(
1
2
)
11951
16985
(
0
1
2
1
2
0
)
=
(
0
1
)
(
0
2
)
8949
18903
(
0
1
2
2
0
1
)
=
(
0
2
)
(
0
1
)
14975
32969
(
0
1
2
2
1
0
)
=
(
0
2
)
9333
29241The way of computing the shortest coding of circuitA in Table 2 is given.  (1)
By Definition1, the permutation of circuit A is σ=(0,1,2,3,6,7,5,4).(2)
By Definition2, the ordinal number sequence of σ is (0,1,2,3,4,5,4,4).(3)
By Definition5, the shortest coding is 23759.Definition 16.
Given two circuit setsS and Q, the set of all circuits of S cascaded by all circuits of Q is denoted by S×Q={G1G2∣G1∈S∧G2∈Q}.Lemma 17.
Given two circuit setsS and Q, Pσ(S×Q)=Pσ(S)×pσ(Q).Proof.
By Definition16, S×Q={G1G2∣G1∈S∧G2∈Q}, thus Pσ(S×Q) = Pσ({G1G2∣G1∈S∧G2∈Q}) = {Pσ(G1G2)∣G1∈S∧G2∈Q} = {Pσ(G1)Pσ(G2)∣Pσ(G1)∈Pσ(S)∧Pσ(G2)∈Pσ(Q)} = Pσ(S)×Pσ(Q).Theorem 18.
Given the setSl of all optimal circuits with length l, Min(Sl+1)=Min((⋃‍b∈SBRb(Min(Sl)))×L)=Min(Sl×L).For saving memory, we only store minimal permutation circuitsMin(Sl). The common computing method is that, firstly, Sl can be gotten by decompressing Min(Sl), secondly, Sl+1 can be gotten by Sl×L, and lastly, Min(Sl+1) can be gotten by compressing Sl×L. Its number of decompressing circuit is 2×n!×|Min(Sl)|, but ours is zero based on Theorem 15. The number of cascading circuit and the number of compressing circuit in the common method all are n! times than ours; so, our method is better.


## 3. New Synthesis Algorithm

A quantum logic gate realizes certain permutation in essence; quantum circuit is the cascade of some quantum gates, and so the basic function of quantum circuit can be represented the multiplication of permutations. The basic idea of the hash-based 3-bit synthesis algorithm which we previously advanced is constructing an optimal circuit using WFS, making a one-to-one correspondence between the elements in the hash table and different circuits. Thus, we need only one step to check whether the circuit of the same function has already been found to decide whether it is optimal. But it is unfeasible if we use this algorithm directly in 4-bit circuit synthesis, since the length of the hash table is at leastn2!; so, it is extremely memory consuming. Otherwise, if we use DFS, it will be meaningless that the algorithm runs too slowly or can not realize optimal. To sum up, we adopt the BFS, with higher speed and more synthesis capability, and some lossless data compression methods to reduce memory consumption.(1)
Represent the permutation using the shortest encoding. Only⌈log22n!|n=4⌉=45 bits is required to represent 4-bit circuit permutations using the permutation encoding method in Definition 5, rather than 64 bits as usual.(2)
Compress the optimal circuits without loss. Using line permutation alone, nearlyn!|n=4=24 times compression can be reached, while using both line permutation and direction transformation, nearly n!×2|n=4=48 times compression can be reached, which is the backbone of this paper.(3)
Use hash table with length216 in the top of the data structure, with each element pointing to a different RB tree in Figure 4 and each node in the tree reduces 2 bytes. Hash table and RB tree always remain effective, and RB tree can also allocate the memory dynamically. Therefore the data structure can not only permit a faster access speed, but also save memory space.Figure 4
The data structure of the minimal permutation circuit with lengthi.How to determine the length of hash table? Let the permutation ofn-bit circuit be π, whose shortest coding is Code(Min(π)), {0,1}⌈log2n!⌉ in binary. Use the rear k×8 bits as the hash address, the rest ⌈log2n!⌉-k×8 bits as the value of the nodes in the RB tree. Suppose that the length of the elements in hash table is j bytes; so, hash table uses j×28k bytes while the RB tree saves k×|S[i]| bytes, and the maximum space this structure saves is maxfm(k,j,i)=k×|S[i]|-j×28k. Take the 4-bit circuit based on CNT quantum gate library as an example; each element in hash table is a pointer pointing to the different tree, taking 4 bytes. The number of minimum permutation circuits with length 8 is 58777916, when k=2, and the maximum of the function is fm(2,4,8)=117293688; so, the optimal length of hash table is 28k|k=2=65536.In this paper, we use BFS to get all the firstN layers of optimal circuits. If the gate library is determined, then the optimal circuits are determined. In order to save time, we store all minimum permutation circuits in the first N layers in a file. If CNT gate library is used, then N=8, and we get a 700 MB file. As there are considerable gates in the 4-bit circuit quantum gate library, thus lots of optimal circuits are generated at each length. When a circuit reaches a certain length, the memory will overflow, and so N has practical upper lower limit related to memory. After the lossless compression mentioned earlier, only the minimum permutation circuits are stored, saving 47.95 times less of circuits. The length of the overall synthesis circuits reaches 8 instead of 6, 117.7 times larger; the synthesizable length grows form 12 to 16 [14].


### 3.1. Minimal Length Algorithm

The node type of our RB tree is defined as follows:struct rbtnode {gate; // the gate is in the end of the circuitGcpm; // the permutation of the circuit Min(G)binv; // the current circuit is inverted or notlnpm; // Min(π(G)) ≡ GetMin(π(G); binv; lnpm)pcpm; // the permutation of the previous circuitpbinv; // the previous circuit is inverted or not}To enhance readability, two ways are used to simplify the algorithms.(1)
All permutations are not transformed into the relevant shortest codings.(2)
The hash table in the top of Figure4 is omitted, and all the minimum permutation circuits in each layer are only saved in a RB tree; for example, S[i] is the RB tree which has saved all minimum permutation circuits with length i.


### 3.2. Algorithm for the Minimal Permutation Quantum Reversible Logic Circuits Representation in QML

For more details, see Algorithm2.


### 3.3. General Algorithm for the Quantum Reversible Logic Circuits Representation in QML (Algorithm1)

Algorithm 1:Quantum_Minimum_Length (QML).
Input: Quantum Gate Library L
Output:
max
l
,
N
[
0
…
max
l
]
,
S
[
0
…
max
l
]
1:S[0]={cmp:πe},j=0,N[0]=1
2:whileN[j]≠0do
3:j=j+1,S[j]=Ø
4:foreach node Node x in S[j-1]do
5:c=Nodex.cpm
6:forv=0to1do
7:ifv=1then
8:c=c-1
9:end if
10:foreach gate g in Ldo
11:p=c°π(g),π=GetMin(p,σ,b)
12:ifπ∉⋃i=0jS[i]then
13:S[j]=S[j]∪{(gate:g,cpm:π,lnpm:
σ,binv:b,pcpm:p,
pbinv:v)}
14:ifmemory overflow errorthen
15:freeS[j],j=j-1,goto23
16:end if
17:end if
18:end for
19:end for
20:end for
21:N[j]=∑G∈S[j]|⋃i∈SF,b∈SBRb(Pσi(G))|
22:end while
23:maxl=jAlgorithm 2:Minimal_Quantum_Representation (MQR).
Input:Quantum Gate Library L, minimal permutation p,
circuit lengthl
Output:Circuit of minimal permutation p with mini-length
1: computeS[0…maxl] as in QML(L) for the first time;
2:i=l,mynode[i]=s[i].find(p)
3:pcpmx=mynode[i].pcpm
4:whilei>1do
5:i=i-1
6:mynode[i]=S[i].find(pcpmx)
7:pcpmx=mynode[i].pcpm
8: end while
9:σ=mynode[1].lnpm,b=mynode[1].binv
10:G1=PσRb(mynode[1].gate)
11:fori=2 to ldo
12:σ=mynode[i].lnpm,b=mynode[i].binv
13:c=mynode[i].pbinv,g=mynode[i].gate
14:Gi=Rb(Pσ(Rc(Gi-1)g))
15:end for
16:returnGlFor more details, see Algorithm3.Algorithm 3:Quantum_Minimum _Representation (QMR).
Input:Quantum Gate Library L, permutation p
Output:Circuit of permutation p with mini-length
1:if∃l∈{0,1,2,…,maxl},GetMin(p,σ,b)∈S[l]then
2:G=MQR(GetMin(p,σ,b),l)
3:returnRb(Pσ-1(G))
4:else if∃i∈SF,∃b∈SB,∃l∈{1,2,…,maxl},
∃Nodex∈S[l],
GetMin(Rb(Pσi(p))°(Nodex.cpm)-1,τ,c)
∈
S
[
max
l
]
then
5:G2=MQR(Nodex.cpm,l)
6:ρ=GetMin(Rb(Pσi(P))°(Nodex.cpm)-1,τ,c)
7:G1=MQR(ρ,maxl)
8:returnRb(Pσi-1(Rc(Pτ-1(G1))G2))
9: else
10: returnNULL
11: end if


## 3.1. Minimal Length Algorithm

The node type of our RB tree is defined as follows:struct rbtnode {gate; // the gate is in the end of the circuitGcpm; // the permutation of the circuit Min(G)binv; // the current circuit is inverted or notlnpm; // Min(π(G)) ≡ GetMin(π(G); binv; lnpm)pcpm; // the permutation of the previous circuitpbinv; // the previous circuit is inverted or not}To enhance readability, two ways are used to simplify the algorithms.(1)
All permutations are not transformed into the relevant shortest codings.(2)
The hash table in the top of Figure4 is omitted, and all the minimum permutation circuits in each layer are only saved in a RB tree; for example, S[i] is the RB tree which has saved all minimum permutation circuits with length i.


## 3.2. Algorithm for the Minimal Permutation Quantum Reversible Logic Circuits Representation in QML

For more details, see Algorithm2.


## 3.3. General Algorithm for the Quantum Reversible Logic Circuits Representation in QML (Algorithm1)

Algorithm 1:Quantum_Minimum_Length (QML).
Input: Quantum Gate Library L
Output:
max
l
,
N
[
0
…
max
l
]
,
S
[
0
…
max
l
]
1:S[0]={cmp:πe},j=0,N[0]=1
2:whileN[j]≠0do
3:j=j+1,S[j]=Ø
4:foreach node Node x in S[j-1]do
5:c=Nodex.cpm
6:forv=0to1do
7:ifv=1then
8:c=c-1
9:end if
10:foreach gate g in Ldo
11:p=c°π(g),π=GetMin(p,σ,b)
12:ifπ∉⋃i=0jS[i]then
13:S[j]=S[j]∪{(gate:g,cpm:π,lnpm:
σ,binv:b,pcpm:p,
pbinv:v)}
14:ifmemory overflow errorthen
15:freeS[j],j=j-1,goto23
16:end if
17:end if
18:end for
19:end for
20:end for
21:N[j]=∑G∈S[j]|⋃i∈SF,b∈SBRb(Pσi(G))|
22:end while
23:maxl=jAlgorithm 2:Minimal_Quantum_Representation (MQR).
Input:Quantum Gate Library L, minimal permutation p,
circuit lengthl
Output:Circuit of minimal permutation p with mini-length
1: computeS[0…maxl] as in QML(L) for the first time;
2:i=l,mynode[i]=s[i].find(p)
3:pcpmx=mynode[i].pcpm
4:whilei>1do
5:i=i-1
6:mynode[i]=S[i].find(pcpmx)
7:pcpmx=mynode[i].pcpm
8: end while
9:σ=mynode[1].lnpm,b=mynode[1].binv
10:G1=PσRb(mynode[1].gate)
11:fori=2 to ldo
12:σ=mynode[i].lnpm,b=mynode[i].binv
13:c=mynode[i].pbinv,g=mynode[i].gate
14:Gi=Rb(Pσ(Rc(Gi-1)g))
15:end for
16:returnGlFor more details, see Algorithm3.Algorithm 3:Quantum_Minimum _Representation (QMR).
Input:Quantum Gate Library L, permutation p
Output:Circuit of permutation p with mini-length
1:if∃l∈{0,1,2,…,maxl},GetMin(p,σ,b)∈S[l]then
2:G=MQR(GetMin(p,σ,b),l)
3:returnRb(Pσ-1(G))
4:else if∃i∈SF,∃b∈SB,∃l∈{1,2,…,maxl},
∃Nodex∈S[l],
GetMin(Rb(Pσi(p))°(Nodex.cpm)-1,τ,c)
∈
S
[
max
l
]
then
5:G2=MQR(Nodex.cpm,l)
6:ρ=GetMin(Rb(Pσi(P))°(Nodex.cpm)-1,τ,c)
7:G1=MQR(ρ,maxl)
8:returnRb(Pσi-1(Rc(Pτ-1(G1))G2))
9: else
10: returnNULL
11: end if


## 4. Experimental Results

Our experiments were conducted using many benchmark functions for 4-bit reversible logic circuits synthesis, and [14, 15] dealt with the synthesis of 4-qubit circuit for the high complexity of the algorithm. Based on CNP quantum gate library, using the mini-length as criteria, [14] added 4 layers in the basis of [11] through bidirection synthesis, and another 4 layers by combining DFS, thus realized a 12 layers synthesis of arbitrary circuits. Yet [14] can only synthesize the first 4 layers of the optimal circuit at a time, while in our previous study, for example, the hash-based 3-bit synthesis algorithm, the average speed of the mini-length and minimum cost are 49.15 and 365.13 times of [11], respectively. In this paper, we used CNT quantum gate library and mini-length criteria, creating all optimal circuits with up to 8 gates. By bidirection cascading the generated circuits, we can quickly synthesize the optimal quantum circuits within the length of 16, without consuming more memory. Our bidirection cascading is quite different with the bidirection synthesis used in [14]; they calculated the head and tail of the circuit, respectively, then moved forward to the middle. In order to avoid repeated computation, we first synthesize the former parts of the circuit, then perform specific topology transformations on them and reuse them in the latter part.To evaluate the ability of the algorithm while synthesizing complicated circuits, we have run our program on a great number of circuits, and none of them has been found not to be synthesized. Then, we only give two examples.(1) We cascaded the two optimal circuits 4_49 and Hwb4 to get one circuit in Figure 5A. By using the generated all minimal permutation circuits with up to 8 gates, it took only 35 s to generate circuit B. It is easy to prove that the permutation of both A and B are (15,2,3,12,5,9,1,11,0,10,14,6,4,8,7,13). (2) Synthesized Alhagi01 (2,12,8,13,0,9,6,15,10,11,14,4,5,3,1,7) circuit is given in Figure 6.Figure 5
The 4-bit reversible logic circuits synthesis.Figure 6
Alhagi01 circuit synthesis.


## 5. Conclusions

Based on the idea that the synthesis of reversible logic circuit is a permutation problem in essence, we present the novel and efficient quantum circuit synthesis algorithms. Among them, we elaborately construct a shortest encoding method of the permutation and compress the memory space of then-bit optimal circuits to 2×n! times less using certain topology transformation of quantum circuits. By bidirectional cascading of the generated optimal circuits, using several quantum gates and the mini-length cost metric, our algorithms can efficiently generate most optimal 4-bit reversible logic circuits.



---

*Source: 291410-2013-04-08.xml*