Four-level realisation of 3-qubit reversible functions

Buy article PDF
© The Institution of Engineering and Technology
Published 30/07/2012

Abstract

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 3-bit reversible gate synthesis to create a library useful in hierarchical design. It has been shown that arbitrary 3-bit reversible circuit can be synthesised with four-logic levels, using this new gate library. The respective universal library for the four-level synthesis is constructed and optimised it on the level of nuclear magnetic resonance pulses. A very fast algorithm to synthesise arbitrary 3-bit reversible function to gates from our library is also presented. The algorithm demonstrates dramatic speed benefit and results in a maximum of four-level circuit for arbitrary 3-bit 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 four-level circuit for any 3-qubit reversible function and is also intended to be used in a hierarchical design of larger circuits.

Inspec keywords: quantum gates; group theory

Other keywords: gate library; group theory; 3-bit reversible gate functions; nuclear magnetic resonance pulses; universal library

Subjects: Quantum computing theory; Algebra

References

    1. 1)
      • Toffoli, T.: `Reversible computing', Tech. Memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980
    2. 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. 3)
    4. 4)
      • Forf, R.: Artificial intelligence search algortihms, Algorithms and theory of computation handbook, 1999 (CRC Press)
    5. 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. 6)
      • Bullock, S.S., Markov, I.L.: `An arbitrary two-qubit computation in 23 elementary gates', Proc. Design Automation Conf, June 2003
    7. 7)
      • Perkowski, M.: `Synthesis of large circuits with fault-tolerant reversible gate libraries', Technical Report, 2005
    8. 8)
      • Neilsen, M.A., Chuang, I.L.: Quantum computation and quantum information, 2000 (Cambridge University Press)
    9. 9)
    10. 10)
      • Hughes, R.J., James, D.F.V., Knill, E.H., Laflamme, R., Petschek, A.G.: Decoherence bounds on quantum computation with trapped ions, 2002 (Los Alamos National LaboratoryLos Alamos, New Mexico)
    11. 11)
      • Shor, P.W.: `Fault-tolerant quantum computation', IEEE 37th Annual Symp. on Foundations of Computer Science, October 1996, Burlington, VT
    12. 12)
      • Miller, D.M., Maslov, D., Dueck, G.W.: `A transformation based algorithm for reversible logic synthesis', Proc. Design Automation Conf., June 2003
    13. 13)
      • Khlopotine, A., Perkowski, M., Kerntopf, P.: `Reversible logic synthesis by iterative compositions', Proc. International Workshop on Logic Synthesis, 4–7 June 2002
    14. 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. 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. 16)
      • Lee, S., Lee, S-J., Kim, T., Lee, J-S., Biamonte, J., Perkowski, M.: `The cost of quantum gate primitives', J. Multi-Valued Logic Soft Comput., 2006, 12, p. 561-573
    17. 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. 18)
      • Storme, L., De Vos, A., Jacobs, G.: `Group theoretical aspects of reversible logic gates', J. Universal Comput. Sci., 1999, 5, (5), p. 307-321
    19. 19)
      • The GAP Group, GAP – Groups, Algorithms, and Programming, version 4.4.9, 2006, http:\\www.gap-system-org
    20. 20)
    21. 21)
    22. 22)
    23. 23)
      • Maslov, D., Miller, D.M.: Comparison of the Cost Metrics for Reversible and Quantum Logic Synthesis
    24. 24)
      • Knill, E., Laflamme, R., Ashikhmin, A., Barnum, H., Viola, L., Zurek, W.H.: `Introduction to quantum error correction', Technical Report LAUR-02-6132 and LAUR-02-4311, July 2002, Los Alamos National Lab
    25. 25)
      • Harris, R., Berkley, A.J., Johnson, M.W.: Sign and magnitude tunable coupler for superconducting flux qubits
Print this page
This is a required field
Please enter a valid email address