Synthesis of Quantum Circuits vs. Synthesis of Classical Reversible Circuits

Description

At first sight, quantum computing is completely different from classical computing. Nevertheless, a link is provided by reversible computation. Whereas an arbitrary quantum circuit, acting on ?? qubits, is described by an ?? × ?? unitary matrix with ??=2??, a reversible classical circuit, acting on ?? bits, is described by a 2?? × 2?? permutation matrix. The permutation matrices are studied in group theory of finite groups (in particular the symmetric group ????); the unitary matrices are discussed in group theory of continuous groups (a.k.a. Lie groups, in particular the unitary group U(??)). Both the synthesis of a reversible logic circuit and the synthesis of a quantum logic circuit take advantage of the decomposition of a matrix: the former of a permutation matrix, the latter of a unitary matrix. In both cases the decomposition is into three matrices. In both cases the decomposition is not unique. Acknowledgments Introduction Conventional Computing Boolean Functions of One Variable Boolean Functions of Two Variables Boolean Functions of n Variables The Minterm Expansion The Reed–Muller Expansion The Minimal ESOP Expansion Group Theory Reversible Computing Permutation Groups A Permutation Decomposition Matrix Groups Subgroups Young Subgroups Quantum Computing Bottom-Up vs. Top-Down Bottom The Group S_2 Two Important Young Subgroups of S_2w Controlled Circuits Controlled NOT Gates Controlled Circuits vs. Controlled Gates Primal Decomposition Dual Decomposition Synthesis Efficiency Refined Synthesis Algorithm Examples Variable Ordering Bottom-Up The Square Root of the NOT One-(qu)bit Calculations Two and Multi-(qu)bit Calculations More Roots of NOT NEGATORs NEGATOR Circuits The Group ZU(n) The Group XU(n) A Matrix Decomposition Group Hierarchy Top Preliminary Circuit Decomposition Primal Decomposition Group Structure Dual Decomposition Detailed Procedure Examples Synthesis Efficiency Further Synthesis An Extra Decomposition Top-Down Top vs. Bottom Light Matrices Primal Decomposition Group Hierarchy Dual Decomposition Conclusion Polar Decomposition Bibliography Authors' Biographies Index Blank Page