Evolutionary Approach to Quantum and Reversible Circuit Synthesis

Martin Lukac, Marek Perkowski, Hilton Goi, Mihail Pivtoraiko, Chung Hyo Yu, Kyusik Chung, Hyunkoo Jee, Byung-Guk Kim, and Yong-Duk Kim. Evolutionary Approach to Quantum and Reversible Circuit Synthesis. Artificial Intelligence Review, 20(3-4):361–417, Springer Netherlands, 2003.

Download

[pdf]  [ps.gz]  [ps]  [HTML] 

Abstract

The paper discusses the evolutionary computation approach to the problem of optimal synthesis of Quantum and Reversible Logic circuits. Our approach uses standard Genetic Algorithm (GA) and its relative power as compared to previous approaches comes from the encoding and the formulation of the cost and fitness functions for quantum circuits synthesis. We analyze new operators and their role in synthesis and optimization processes. Cost and fitness functions for Reversible Circuit synthesis are introduced as well as local optimizing transformations. It is also shown that our approach can be used alternatively for synthesis of either reversible or quantum circuits without a major change in the algorithm. Results are illustrated on synthesized Margolus, Toffoli, Fredkin and other gates and Entanglement Circuits. This is for the first time that several variants of these gates have been automatically synthesized from quantum primitives.

BibTeX

@ARTICLE{lukac_etal_air04,
  author = {Martin Lukac and Marek Perkowski and Hilton Goi and Mihail Pivtoraiko
	and Chung Hyo Yu and Kyusik Chung and Hyunkoo Jee and Byung-Guk Kim
	and Yong-Duk Kim},
  title = {Evolutionary Approach to Quantum and Reversible Circuit Synthesis},
  journal = {Artificial Intelligence Review},
  year = {2003},
  volume = {20},
  pages = {361--417},
  number = {3-4},
  abstract = {The paper discusses the evolutionary computation
                  approach to the problem of optimal synthesis of
                  Quantum and Reversible Logic circuits. Our approach
                  uses standard Genetic Algorithm (GA) and its
                  relative power as compared to previous approaches
                  comes from the encoding and the formulation of the
                  cost and fitness functions for quantum circuits
                  synthesis. We analyze new operators and their role
                  in synthesis and optimization processes. Cost and
                  fitness functions for Reversible Circuit synthesis
                  are introduced as well as local optimizing
                  transformations.  It is also shown that our approach
                  can be used alternatively for synthesis of either
                  reversible or quantum circuits without a major
                  change in the algorithm. Results are illustrated on
                  synthesized Margolus, Toffoli, Fredkin and other
                  gates and Entanglement Circuits. This is for the
                  first time that several variants of these gates have
                  been automatically synthesized from quantum
                  primitives.},
  bib2html_pubtype = {Journal Papers},
  bib2html_rescat = {Reversible Circuit Synthesis},
  doi = {10.1023/B:AIRE.0000006605.86111.79},
  publisher = {Springer Netherlands}
}

Generated by bib2html.pl (written by Patrick Riley ) on Wed May 15, 2013 18:16:05