Evolutionary approach to quantum and reversible circuits synthesis

Martin Lukac, Marek Perkowski, Hilton Goi, Mikhail Pivtoraiko, Chung Hyo Yu, Kyusik Chung, Hyunkoo Jee, Byung Guk Kim, Yong Duk Kim

Research output: Contribution to journalArticlepeer-review

61 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)361-417
Number of pages57
JournalArtificial Intelligence Review
Volume20
Issue number3-4
DOIs
Publication statusPublished - Dec 1 2003

Keywords

  • Genetic algorithm
  • Minimizing transformation
  • Quantum CAD
  • Quantum logic synthesis

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Evolutionary approach to quantum and reversible circuits synthesis'. Together they form a unique fingerprint.

Cite this