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 条
  • [41] A Method for Decomposing and Optimizing MCT Gate Quantum Reversible Circuits
    Zhang S.
    Guan Z.
    Yang X.
    Dianzi Keji Daxue Xuebao/Journal of the University of Electronic Science and Technology of China, 2024, 53 (01): : 155 - 160
  • [42] Realizing Reversible Circuits Using a New Class of Quantum Gates
    Sasanian, Zahra
    Wille, Robert
    Miller, D. Michael
    2012 49TH ACM/EDAC/IEEE DESIGN AUTOMATION CONFERENCE (DAC), 2012, : 36 - 41
  • [43] Optimized reversible quantum circuits for F28 multiplication
    Imana, Jose L.
    QUANTUM INFORMATION PROCESSING, 2021, 20 (01)
  • [44] Fault tolerance in reversible logic circuits and quantum cost optimization
    Arunachalam K.
    Perumalsamy M.
    Ponnusamy K.K.
    Computing and Informatics, 2021, 39 (05) : 1099 - 1116
  • [45] Geometric Refactoring of Quantum and Reversible Circuits Using Graph Algorithms
    Lukac, Martin
    Nursultan, Saadat
    Krylov, Georgiy
    Keszocze, Oliver
    Rakhmettulayev, Abilmansur
    Kameyama, Michitaka
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2024, E107D (08) : 930 - 939
  • [46] FAULT TOLERANCE IN REVERSIBLE LOGIC CIRCUITS AND QUANTUM COST OPTIMIZATION
    Arunachalam, Kamaraj
    Perumalsamy, Marichamy
    Ponnusamy, Kaviyashri K.
    COMPUTING AND INFORMATICS, 2020, 39 (05) : 1099 - 1116
  • [47] Complexity of Representations of Multiple-Output Boolean Functions in the Reversible Logic Circuits
    Vinokurov, S. F.
    Frantseva, A. S.
    PROCEEDINGS OF THE XIX IEEE INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND MEASUREMENTS (SCM 2016), 2016, : 374 - 376
  • [48] Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
    Babbush, Ryan
    Gidney, Craig
    Berry, Dominic W.
    Wiebe, Nathan
    McClean, Jarrod
    Paler, Alexandra
    Fowler, Austin
    Neven, Hartmut
    PHYSICAL REVIEW X, 2018, 8 (04):
  • [49] Design of Combinational Logic circuits for Low power Reversible Logic circuits in Quantum Cellular Automata
    Anand, I. Vivek
    Kamaraj, A.
    2014 INTERNATIONAL CONFERENCE ON INFORMATION COMMUNICATION AND EMBEDDED SYSTEMS (ICICES), 2014,
  • [50] Reversible modified reconstructability analysis of Boolean circuits and its quantum computation
    Al-Rabadi, AN
    Zwick, M
    KYBERNETES, 2004, 33 (5-6) : 921 - 932
12345