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 journalArticle

57 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 2003
Externally publishedYes

Fingerprint

fitness
Networks (circuits)
costs
Logic circuits
Evolutionary algorithms
Mathematical operators
Costs
Genetic algorithms
Evolutionary
Fitness

Keywords

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

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Artificial Intelligence

Cite this

Lukac, M., Perkowski, M., Goi, H., Pivtoraiko, M., Yu, C. H., Chung, K., ... Kim, Y. D. (2003). Evolutionary approach to quantum and reversible circuits synthesis. Artificial Intelligence Review, 20(3-4), 361-417. https://doi.org/10.1023/B:AIRE.0000006605.86111.79

Evolutionary approach to quantum and reversible circuits synthesis. / Lukac, Martin; Perkowski, Marek; Goi, Hilton; Pivtoraiko, Mikhail; Yu, Chung Hyo; Chung, Kyusik; Jee, Hyunkoo; Kim, Byung Guk; Kim, Yong Duk.

In: Artificial Intelligence Review, Vol. 20, No. 3-4, 12.2003, p. 361-417.

Research output: Contribution to journalArticle

Lukac, M, Perkowski, M, Goi, H, Pivtoraiko, M, Yu, CH, Chung, K, Jee, H, Kim, BG & Kim, YD 2003, 'Evolutionary approach to quantum and reversible circuits synthesis', Artificial Intelligence Review, vol. 20, no. 3-4, pp. 361-417. https://doi.org/10.1023/B:AIRE.0000006605.86111.79
Lukac, Martin ; Perkowski, Marek ; Goi, Hilton ; Pivtoraiko, Mikhail ; Yu, Chung Hyo ; Chung, Kyusik ; Jee, Hyunkoo ; Kim, Byung Guk ; Kim, Yong Duk. / Evolutionary approach to quantum and reversible circuits synthesis. In: Artificial Intelligence Review. 2003 ; Vol. 20, No. 3-4. pp. 361-417.
@article{78e6b7fc4a1f48b5985d2c6773a95674,
title = "Evolutionary approach to quantum and reversible circuits synthesis",
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.",
keywords = "Genetic algorithm, Minimizing transformation, Quantum CAD, Quantum logic synthesis",
author = "Martin Lukac and Marek Perkowski and Hilton Goi and Mikhail Pivtoraiko and Yu, {Chung Hyo} and Kyusik Chung and Hyunkoo Jee and Kim, {Byung Guk} and Kim, {Yong Duk}",
year = "2003",
month = "12",
doi = "10.1023/B:AIRE.0000006605.86111.79",
language = "English",
volume = "20",
pages = "361--417",
journal = "Artificial Intelligence Review",
issn = "0269-2821",
publisher = "Springer Netherlands",
number = "3-4",

}

TY - JOUR

T1 - Evolutionary approach to quantum and reversible circuits synthesis

AU - Lukac, Martin

AU - Perkowski, Marek

AU - Goi, Hilton

AU - Pivtoraiko, Mikhail

AU - Yu, Chung Hyo

AU - Chung, Kyusik

AU - Jee, Hyunkoo

AU - Kim, Byung Guk

AU - Kim, Yong Duk

PY - 2003/12

Y1 - 2003/12

N2 - 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.

AB - 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.

KW - Genetic algorithm

KW - Minimizing transformation

KW - Quantum CAD

KW - Quantum logic synthesis

UR - http://www.scopus.com/inward/record.url?scp=0345872295&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0345872295&partnerID=8YFLogxK

U2 - 10.1023/B:AIRE.0000006605.86111.79

DO - 10.1023/B:AIRE.0000006605.86111.79

M3 - Article

AN - SCOPUS:0345872295

VL - 20

SP - 361

EP - 417

JO - Artificial Intelligence Review

JF - Artificial Intelligence Review

SN - 0269-2821

IS - 3-4

ER -