An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition

Abstract

An algorithm for reversible logic synthesis is proposed. The task is, for a given $n$-bit substitution map $P_n:\{0,1{\}}^n\to \{0,1{\}}^n$, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates denoted by $C^{m}X$, where $m$ is the number of control bits that ranges from 0 to $n-1$. Controlled gates with large $m(>2)$ are then further decomposed into $C^{0}X$, $C^{1}X$, and $C^{2}X$ gates. A primary concern in designing the algorithm is to reduce the use of $C^{2}X$ gate (also known as Toffoli gate) which is known to be universal. The main idea is to view an $n$-bit substitution map as a rank-$2n$ tensor and to transform it such that the resulting map can be written as a tensor product of a rank-($2n-2$) tensor and the $2\times 2$ identity matrix. Let ${\mathcal{P}}_n$ be a set of all $n$-bit substitution maps. What we try to find is a size reduction map ${\mathcal{A}}_{\mathrm{red}}:{\mathcal{P}}_n\to \{P_n:P_n=P_{n-1}\otimes I_2\}$. %, where $I_m$ is the $m\times m$ identity matrix. One can see that the output $P_{n-1}\otimes I_2$ acts nontrivially on $n-1$ bits only, meaning that the map to be synthesized becomes $P_{n-1}$. The size reduction process is iteratively applied until it reaches tensor product of only $2\times 2$ matrices.

Added a C implementation on GitHub and updated the AES S-box results using it

References in corpus (17)

• Quantum Mechanics helps in searching for a needle in a haystack
• The density-matrix renormalization group in the age of matrix product states
• Improved Simulation of Stabilizer Circuits
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Quantum Circuits for General Multiqubit Gates
• Breaking Symmetric Cryptosystems using Quantum Period Finding
• Synthesis and Optimization of Reversible Circuits - A Survey
• Techniques for the Synthesis of Reversible Toffoli Networks
• Reversible Circuit Synthesis Using a Cycle-Based Approach
• A Study of Optimal 4-bit Reversible Toffoli Circuits and Their Synthesis
• Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
• Optimal quantum circuit synthesis from Controlled-U gates
• Could Grover's quantum algorithm help in searching an actual database?
• Optimization of Clifford Circuits
• 6-qubit Optimal Clifford Circuits
• Application of Permutation Group Theory in Reversible Logic Synthesis
• Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function

Cited by in corpus (1)

• Partial Equivalence Checking of Quantum Circuits