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

共 36 条

[1]

Abdessaied N, 2014, LECT NOTES COMPUT SC, V8507, P149, DOI 10.1007/978-3-319-08494-7_12

[2] Upper bounds for reversible circuits based on Young subgroups [J].

Abdessaied, Nabila ;

Soeken, Mathias ;

Thomsen, Michael Kirkedal ;

Drechsler, Rolf .

INFORMATION PROCESSING LETTERS, 2014, 114 (06) :282-286

[3] Polynomial-Time T-Depth Optimization of Clifford plus T Circuits Via Matroid Partitioning [J].

Amy, Matthew ;

Maslov, Dmitri ;

Mosca, Michele .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2014, 33 (10) :1476-1489

[4] A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits [J].

Amy, Matthew ;

Maslov, Dmitri ;

Mosca, Michele ;

Roetteler, Martin .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2013, 32 (06) :818-830

[5]

[Anonymous], 2010, REVERSIBLE COMPUTING, DOI DOI 10.1002/9783527633999

[6]

[Anonymous], 1994, FDN COMPUTER SCI

[7]

Athas W. C., 1994, Proceedings. Workshop on Physics and Computation PhysComp '94, P111, DOI 10.1109/PHYCMP.1994.363692

[8] ELEMENTARY GATES FOR QUANTUM COMPUTATION [J].

BARENCO, A ;

BENNETT, CH ;

CLEVE, R ;

DIVINCENZO, DP ;

MARGOLUS, N ;

SHOR, P ;

SLEATOR, T ;

SMOLIN, JA ;

WEINFURTER, H .

PHYSICAL REVIEW A, 1995, 52 (05) :3457-3467

[9]

Chuang I. N., 2000, Quantum Computation and Quantum Information

[10] Young subgroups for reversible computers [J].

De Vos, Alexis ;

Van Rentergem, Yvan .

ADVANCES IN MATHEMATICS OF COMMUNICATIONS, 2008, 2 (02) :183-200

← 1 2 3 4 →