Complexity of reversible circuits and their quantum implementations

被引：10
|
作者：
Abdessaied, Nabila [1 ,2 ]
Amy, Matthew [3 ]
Drechsler, Rolf [1 ,2 ]
Soeken, Mathias [1 ,2 ]
机构：
[1] Univ Bremen, Fac Math & Comp Sci, D-28359 Bremen, Germany
[2] DFKI GmbH, Cyber Phys Syst, Bremen, Germany
[3] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada
来源：
THEORETICAL COMPUTER SCIENCE | 2016年 / 618卷
关键词：
Complexity analysis; Reversible functions; Reversible circuits; Quantum circuits; Upper bounds; Synthesis; Technology mapping; ALGORITHM; OPTIMIZATION; COST;
D O I：
10.1016/j.tcs.2016.01.011
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We provide an extensive overview of upper bounds on the number of gates needed in reversible and quantum circuits. As reversible gate libraries we consider single-target gates, mixed-polarity multiple-controlled Toffoli gates, and the set consisting of the NOT, the CNOT, and the two-controlled Toffoli gate. As quantum gate libraries we consider the semi-classical NCV library (consisting of NOT, CNOT, and the square-root of NOT called V) as well as the universal and commonly used Clifford + T gate library. Besides a summary of known bounds, the paper provides several new and tighter bounds. Several synthesis approaches and mapping schemes were used to calculate the bounds. (C) 2016 Published by Elsevier B.V.
引用
收藏
页码：85 / 106
页数：22
相关论文
共 50 条
  • [21] DIAGONAL-UNITARY 2-DESIGN AND THEIR IMPLEMENTATIONS BY QUANTUM CIRCUITS
    Nakata, Yoshifumi
    Murao, Mio
    INTERNATIONAL JOURNAL OF QUANTUM INFORMATION, 2013, 11 (07)
  • [22] Quantum reversible circuits for GF(28) multiplicative inverse
    Luo, Qing-bin
    Yang, Guo-wu
    Li, Xiao-yu
    Li, Qiang
    EPJ QUANTUM TECHNOLOGY, 2022, 9 (01)
  • [23] Designing Novel Quaternary Quantum Reversible Subtractor Circuits
    Haghparast, Majid
    Monfared, Asma Taheri
    INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 2018, 57 (01) : 226 - 237
  • [24] Design of New Quantum/Reversible Ternary Subtractor Circuits
    Monfared, Asma Taheri
    Haghparast, Majid
    JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2016, 25 (02)
  • [25] Optimizing the Mapping of Reversible Circuits to Four-Valued Quantum Gate Circuits
    Soeken, Mathias
    Sasanian, Zahra
    Wille, Robert
    Miller, D. Michael
    Drechsler, Rolf
    2012 42ND IEEE INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL), 2012, : 173 - 178
  • [26] Designing Novel Quaternary Quantum Reversible Subtractor Circuits
    Majid Haghparast
    Asma Taheri Monfared
    International Journal of Theoretical Physics, 2018, 57 : 226 - 237
  • [27] Optimizing Quantum Reversible Circuits Using Reinforcement Learning
    Yang, Sheng
    Peng, Guan-Ju
    2023 IEEE 22ND INTERNATIONAL CONFERENCE ON TRUST, SECURITY AND PRIVACY IN COMPUTING AND COMMUNICATIONS, TRUSTCOM, BIGDATASE, CSE, EUC, ISCI 2023, 2024, : 2310 - 2314
  • [28] QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits
    Miller, D. Michael
    Thornton, Mitchell A.
    ISMVL 2006: 36TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC, 2006, : 177 - +
  • [29] Improving the Mapping of Reversible Circuits to Quantum Circuits Using Multiple Target Lines
    Wille, Robert
    Soeken, Mathias
    Otterstedt, Christian
    Drechsler, Rolf
    2013 18TH ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC), 2013, : 145 - 150
  • [30] An Algorithmic Construction of Quantum Circuits of High Descriptive Complexity
    Fouche, Willem L.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2008, 221 : 61 - 69
12345