© The Institution of Engineering and Technology
Two questions have been addressed here: how many logic levels are necessary to synthesise a specific instance of a reversible circuit, and how much better to have large gate libraries, and what gates should be required in libraries. Group theory is applied to 3bit reversible gate synthesis to create a library useful in hierarchical design. It has been shown that arbitrary 3bit reversible circuit can be synthesised with fourlogic levels, using this new gate library. The respective universal library for the fourlevel synthesis is constructed and optimised it on the level of nuclear magnetic resonance pulses. A very fast algorithm to synthesise arbitrary 3bit reversible function to gates from our library is also presented. The algorithm demonstrates dramatic speed benefit and results in a maximum of fourlevel circuit for arbitrary 3bit reversible function. The gates are optimised on the level of pulses to decrease their cost and allow for objective comparison with standard CNOT, NOT, Toffoli gates (CNT) circuits. This library guarantees a fourlevel circuit for any 3qubit reversible function and is also intended to be used in a hierarchical design of larger circuits.
References


1)

Toffoli, T.: `Reversible computing', Tech. Memo MIT/LCS/TM151, MIT Lab for Comp. Sci, 1980.

2)

Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: `Reversible logic circuit synthesis', Int. Workshop on Logic Synthesis, June 2002, New Orleans, LU, USA.

3)

A. De Vos ,
B. Raa ,
L. Storme
.
Generating the group of reversible logic gates.
J. Physics A: Math. Gen.
,
7063 
7078

4)

R. Forf
.
(1999)
Artificial intelligence search algortihms, Algorithms and theory of computation handbook.

5)

Perkowski, M., Lukac, M., Pivtoraiko, M., Kerntopf, P., Folgheraiter, M.: `A hierarchical approach to computer aided design of quantum circuits', Proc. 6th Int. Symp. on Representations and Methodology of Future Computing Technology, March 2003, Trier, Germany, p. 201–209.

6)

Bullock, S.S., Markov, I.L.: `An arbitrary twoqubit computation in 23 elementary gates', Proc. Design Automation Conf, June 2003.

7)

Perkowski, M.: `Synthesis of large circuits with faulttolerant reversible gate libraries', Technical Report, 2005.

8)

M.A. Neilsen ,
I.L. Chuang
.
(2000)
Quantum computation and quantum information.

9)

J.A. Smolin ,
D.P. Di Vincenzo
.
Five twobit quantum gates are sufficient to implement the quantum Fredkin gate.
Phys. Rev. A
,
2855 
2856

10)

R.J. Hughes ,
D.F.V. James ,
E.H. Knill ,
R. Laflamme ,
A.G. Petschek
.
(2002)
Decoherence bounds on quantum computation with trapped ions.

11)

Shor, P.W.: `Faulttolerant quantum computation', IEEE 37th Annual Symp. on Foundations of Computer Science, October 1996, Burlington, VT.

12)

Miller, D.M., Maslov, D., Dueck, G.W.: `A transformation based algorithm for reversible logic synthesis', Proc. Design Automation Conf., June 2003.

13)

Khlopotine, A., Perkowski, M., Kerntopf, P.: `Reversible logic synthesis by iterative compositions', Proc. International Workshop on Logic Synthesis, 4–7 June 2002.

14)

Yang, G., Song, X., Perkowski, M.: `Fast synthesis of exact minimal reversible circuits using group theory', Proc. ASP DAC 2005, January 2005, Shangai, PRC.

15)

Lukac, M., Perkowski, M.: `Combining evolutionary programming and exhaustive search to invent the least cost quantum circuits realized in NMR technology', Proc. ULSI, 2005.

16)

S. Lee ,
SJ. Lee ,
T. Kim ,
JS. Lee ,
J. Biamonte ,
M. Perkowski
.
The cost of quantum gate primitives.
J. MultiValued Logic Soft Comput.
,
561 
573

17)

Hung, W.N.N., Song, X., Yang, G., Yang, J., Perkowski, M.: `Quantum logic synthesis by symbolic reachability analysis', Proc. Design Automation Conf., June 2004.

18)

L. Storme ,
A. De Vos ,
G. Jacobs
.
Group theoretical aspects of reversible logic gates.
J. Universal Comput. Sci.
,
5 ,
307 
321

19)

The GAP Group, GAP – Groups, Algorithms, and Programming, version 4.4.9, 2006, http:\\www.gapsystemorg.

20)

J.D. Dixon ,
B. Mortimer
.
(1996)
Permutation groups.

21)

M.I. Kargapolov ,
Ju.I. Merzljakov
.
(1979)
Fundamentals of the theory of groups.

22)

G. Yang ,
W.N.N. Hung ,
X. Song ,
M. Perkowski
.
Majoritybased reversible logic gates.
Theor. Comput. Sci.
,
259 
274

23)

D. Maslov ,
D.M. Miller
.
Comparison of the Cost Metrics for Reversible and Quantum Logic Synthesis.

24)

Knill, E., Laflamme, R., Ashikhmin, A., Barnum, H., Viola, L., Zurek, W.H.: `Introduction to quantum error correction', Technical Report LAUR026132 and LAUR024311, July 2002, Los Alamos National Lab.

25)

R. Harris ,
A.J. Berkley ,
M.W. Johnson
.
Sign and magnitude tunable coupler for superconducting flux qubits.
http://iet.metastore.ingenta.com/content/journals/10.1049/ietcdt_20060097
Related content
content/journals/10.1049/ietcdt_20060097
pub_keyword,iet_inspecKeyword,pub_concept
6
6