Transformation rules for designing CNOT-based quantum circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Transformation rules for designing CNOT-based quantum circuits

Full text

Pdf (284 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 39th annual Design Automation Conference table of contents

New Orleans, Louisiana, USA

SESSION: Advances in synthesis table of contents

Pages: 419 - 424

Year of Publication: 2002

ISBN ~ ISSN:0738-100X , 1-58113-461-4

Authors

Kazuo Iwama	Kyoto University
Yahiko Kambayashi	Kyoto University
Shigeru Yamashita	NTT Communication Science Labs.

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 29, Citation Count: 16

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/513918.514026 What is a DOI?

ABSTRACT

This paper gives a simple but nontrivial set of local transformation rules for Control-NOT(CNOT)-based combinatorial circuits. It is shown that this rule set is complete, namely, for any two equivalent circuits, S1 and S2, there is a sequence of transformations, each of them in the rule set, which changes S1 to S2. Our motivation is to use this rule set for developing a design theory for quantum circuits whose Boolean logic parts should be implemented by CNOT based circuits. As a preliminary example, we give a design procedure based on our transformation rules which reduces the cost of CNOT-based circuits.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Review A, 52(5):3457--3467, Nov. 1995.
	2	R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. R. Wang. MIS: A Multiple-Level Logic Optimization System. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, CAD-6(6):1062--1081, Nov. 1987.
	3	J. Darringer, W. Joyner, L. Berman, and L. Trevillyan. LSS: Logic synthesis through local transformations. IBM J. Res. and Develop., 25(4):272--280, July 1981.
	4	M. Davio, J.-P. Deshamps, and A. Thayse. Discrete and Switching Functions. McGraw Hill International, 1978.
	5	Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
	6	J. Gruska. Quantum Computing. McGraw Hill, 1999.
	7	Gary D. Hachtel , Fabio Somenzi, Logic Synthesis and Verification Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
	8	Kazuo Iwama , Sunao Sawada , Kensuke Hino , Hiroyuki Kurokawa, Random Benchmark Circuits with Controlled Attributes, Proceedings of the 1997 European conference on Design and Test, p.90, March 17-20, 1997
	9	J.-S. Lee, Y. Chung, J. Kim, and S. Lee. A Practical Method of Constructing Quantum Combinational Logic Circuits. Technical Report http://arXiv.org/abs/quant-ph/9911053, LANL e-print, 1999.
	10	Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
	11	T. Toffoli. Reversible computing. Technical Report MIT/LCS/TM-151, MIT LCS, Feb. 1980.
	12	A. Yao. Quantum circuit complexity. In Proc. 34th Annual IEEE Symposium on Foudations of Computer Science, pages 352--361, 1993.

CITED BY 16

	D. Michael Miller , Dmitri Maslov , Gerhard W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Vivek V. Shende , Stephen S. Bullock , Igor L. Markov, Synthesis of quantum logic circuits, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Pawel Kerntopf, A new heuristic algorithm for reversible logic synthesis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Martin Lukac , Marek Perkowski , Hilton Goi , Mikhail Pivtoraiko , Chung Hyo Yu , Kyusik Chung , Hyunkoo Jeech , Byung-Guk Kim , Yong-Duk Kim, Evolutionary Approach to Quantum andReversible Circuits Synthesis, Artificial Intelligence Review, v.20 n.3-4, p.361-417, December 2003
	William N. N. Hung , Xiaoyu Song , Guowu Yang , Jin Yang , Marek Perkowski, Quantum logic synthesis by symbolic reachability analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Guowu Yang , William N. N. Hung , Xiaoyu Song , Marek Perkowski, Majority-based reversible logic gates, Theoretical Computer Science, v.334 n.1-3, p.259-274, 11 April 2005
	Martin Lukac , Marek Perkowski , Hilton Goi , Mikhail Pivtoraiko , Chung Hyo Yu , Kyusik Chung , Hyunkoo Jee , Byung-Guk Kim , Yong-Duk Kim, Evolutionary approach to quantum and reversible circuits synthesis, Artificial intelligence in logic design, Kluwer Academic Publishers, Norwell, MA, 2004
	Afshin Abdollahi , Massoud Pedram, Analysis and synthesis of quantum circuits by using quantum decision diagrams, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Aditya K. Prasad , Vivek V. Shende , Igor L. Markov , John P. Hayes , Ketan N. Patel, Data structures and algorithms for simplifying reversible circuits, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.2 n.4, p.277-293, October 2006
	D. Maslov , G. W. Dueck , D. M. Miller, Techniques for the synthesis of reversible Toffoli networks, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.42-es, September 2007
	Dmitri Maslov , Gerhard W. Dueck , D. Michael Miller, Fredkin/Toffoli Templates for Reversible Logic Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.256, November 09-13, 2003
	D. Maslov , C. Young , D. M. Miller , G. W. Dueck, Quantum Circuit Simplification Using Templates, Proceedings of the conference on Design, Automation and Test in Europe, p.1208-1213, March 07-11, 2005
	James Donald , Niraj K. Jha, Reversible logic synthesis with Fredkin and Peres gates, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.4 n.1, p.1-19, March 2008
	Abhinav Agrawal , Niraj K. Jha, Synthesis of Reversible Logic, Proceedings of the conference on Design, automation and test in Europe, p.21384, February 16-20, 2004
	Mehdi Saeedi , Morteza Saheb Zamani , Mehdi Sedighi, Moving forward: a non-search based synthesis method toward efficient CNOT-based quantum circuit synthesis algorithms, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Mehdi Saeedi , Mehdi Sedighi , Morteza Saheb Zamani, A novel synthesis algorithm for reversible circuits, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California