Complexity of reversible circuits and their quantum implementations

详细信息    查看全文

• 作者：Nabila Abdessaied^a ; ^b ; ^{nabila@informatik.uni-bremen.de" class="auth_mail" title="E-mail the corresponding author} ; Matthew Amy^c ; Rolf Drechsler^a ; ^b ; Mathias Soeken^a ; ^b ;
• 关键词：Complexity analysis ; Reversible functions ; Reversible circuits ; Quantum circuits ; Upper bounds ; Synthesis ; Technology mapping
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：7 March 2016
• 年：2016
• 卷：618
• 期：Complete
• 页码：85-106
• 全文大小：664 K

文摘

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 de8bb" title="Click to view the MathML source">Clifford+Tden">de">$\text{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.