General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates

2017/02/26 by Zakablukov, Dmitry V. · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1702.08045

Abstract

The paper discusses the gate complexity and the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates in the case, when the number of additional inputs is limited. We study Shannon's gate complexity function L(n, q) and depth function D(n, q) for a reversible circuit implementing a Boolean transformation f\colon \mathbb Z₂ⁿ → \mathbb Z₂ⁿ with 8n < q \lesssim n2^n-o(n) additional inputs. The general upper bounds L(n,q) \lesssim 2ⁿ + 8n2ⁿ \mathop / (log₂ (q-4n) - log₂ n - 2) and D(n,q) \lesssim 2ⁿ⁺¹(2,5 + log₂ n - log₂ (log₂ (q - 4n) - log₂ n - 2)) are proved for this case.

Cited by

• Nearly optimal quantum circuits for Boolean oracles

Related

• On Synthesis of Reversible Circuits with Small Number of Additional Inputs Consisting of NOT, CNOT and 2-CNOT Gates
• On Asymptotic Gate Complexity and Depth of Reversible Circuits Without\n Additional Memory
• On Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory
• Asymptotic bounds of depth for a reversible circuit consisting of NOT, CNOT and 2-CNOT gates
• Synthesis methods for reversible circuits consisting of NOT, CNOT and 2-CNOT gates (Ph.D. thesis)