Asymptotically optimal synthesis of reversible circuits

Abstract

Reversible circuits have been studied extensively and intensively, and have plenty of applications in various areas, such as digital signal processing, cryptography, and especially quantum computing. In 2003, the lower bound $\Omega (2^{n}n/\log n)$ for the synthesis of $n$-wire reversible circuits was proved. Whether this lower bound has a matching upper bound was listed as one of the future challenging open problems in the survey (M. Saeedi and I. L Markov, ACM Computing Surveys, 45(2):1-34, 2013). In this paper we propose an algorithm to implement an arbitrary $n$-wire reversible circuit with no more than $O(2^{n}n/\log n)$ elementary gates, and thus close the open problem.

accepted by Information and Computation

References in corpus (7)

• Elementary gates for quantum computation
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Synthesis and Optimization of Reversible Circuits - A Survey
• Efficient Networks for Quantum Factoring
• Quantum Circuit Simplification and Level Compaction
• Reversible Circuit Synthesis Using a Cycle-Based Approach
• Five Two-Qubit Gates Are Necessary for Implementing Toffoli Gate