On Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory

2015/05/10 by Zakablukov, Dmitry V. · 1 citation
#Computational Complexity (cs.CC) #Emerging Technologies (cs.ET) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1505.02372

Abstract

The reversible logic can be used in various research areas, e.g. quantum computation, cryptography and signal processing. In the paper we study reversible logic circuits with additional inputs, which consist of NOT, CNOT and C\textsuperscript2NOT gates. We consider a set F(n,q) of all transformations \mathbb Bⁿ → \mathbb Bⁿ that can be realized by reversible circuits with (n+q) inputs. An analogue of Lupanov's method for the synthesis of reversible logic circuits with additional inputs is described. We prove upper asymptotic bounds for the Shannon gate complexity function L(n,q) and the depth function D(n,q) in case of q > 0: L(n,q₀) \lesssim 2ⁿ if q₀ ∼ n 2^n-o(n) and D(n,q₁) \lesssim 3n if q₁ ∼ 2ⁿ.

Cited by

• Nearly optimal quantum circuits for Boolean oracles

Related

• On Asymptotic Gate Complexity and Depth of Reversible Circuits Without Additional Memory
• On Synthesis of Reversible Circuits with Small Number of Additional Inputs Consisting of NOT, CNOT and 2-CNOT Gates
• General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates
• Asymptotic bounds of depth for a reversible circuit consisting of NOT, CNOT and 2-CNOT gates
• Reversible Logic Circuit Complexity Analysis via Functional Decomposition