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 条
  • [1] Nanoelectronic implementations of reversible and quantum logic
    Bandyopadhyay, S
    Balandin, A
    Roychowdhury, VP
    Vatan, F
    SUPERLATTICES AND MICROSTRUCTURES, 1998, 23 (3-4) : 445 - 464
  • [2] Statistical complexity of quantum circuits
    Bu, Kaifeng
    Koh, Dax Enshan
    Li, Lu
    Luo, Qingxian
    Zhang, Yaobo
    PHYSICAL REVIEW A, 2022, 105 (06)
  • [3] Efficient reversible and quantum implementations of symmetric Boolean functions
    Maslov, D.
    IEE PROCEEDINGS-CIRCUITS DEVICES AND SYSTEMS, 2006, 153 (05): : 467 - 472
  • [4] Window Optimization of Reversible and Quantum Circuits
    Soeken, Mathias
    Wille, Robert
    Dueck, Gerhard W.
    Drechsler, Rolf
    PROCEEDINGS OF THE 13TH IEEE SYMPOSIUM ON DESIGN AND DIAGNOSTICS OF ELECTRONIC CIRCUITS AND SYSTEMS, 2010, : 341 - 345
  • [5] Geometric Refactoring of Quantum and Reversible Circuits: Quantum Layout
    Lukac, Martin
    Nursultan, Saadat
    Krylov, Georgiy
    Keszocze, Oliver
    2020 23RD EUROMICRO CONFERENCE ON DIGITAL SYSTEM DESIGN (DSD 2020), 2020, : 428 - 435
  • [6] Quantum State Complexity in Computationally Tractable Quantum Circuits
    Iaconis, Jason
    PRX QUANTUM, 2021, 2 (01):
  • [7] A Design for Testability Technique for Quantum Reversible Circuits
    Mondal, Joyati
    Das, Debesh K.
    Kole, Dipak K.
    Rahaman, Hafizur
    PROCEEDINGS OF IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS 2013), 2013,
  • [8] Decision Diagrams for the Design of Reversible and Quantum Circuits
    Wille, Robert
    Niemann, Philipp
    Zulehner, Alwin
    Drechsler, Rolf
    2018 INTERNATIONAL SYMPOSIUM ON DEVICES, CIRCUITS AND SYSTEMS (ISDCS), 2018,
  • [9] Reducing the Depth of Linear Reversible Quantum Circuits
    De Brugière T.G.
    Baboulin M.
    Valiron B.
    Martiel S.
    Allouche C.
    IEEE Transactions on Quantum Engineering, 2021, 2
  • [10] Evolutionary Approach to Quantum and Reversible Circuits Synthesis
    Martin Lukac
    Marek Perkowski
    Hilton Goi
    Mikhail Pivtoraiko
    Chung Hyo Yu
    Kyusik Chung
    Hyunkoo Jeech
    Byung-Guk Kim
    Yong-Duk Kim
    Artificial Intelligence Review, 2003, 20 : 361 - 417
12345