symmetry groups for the decomposition of reversible computers, quantum computers, and computers in between对称群的分解可逆计算机、量子计算机,计算机.pdfVIP

Symmetry 2011, 3, 305-324; doi:10.3390/sym3020305 OPEN ACCESS symmetry ISSN 2073-8994 /journal/symmetry Article Symmetry Groups for the Decomposition of Reversible Computers, Quantum Computers, and Computers in between Alexis De Vos ,⋆ and Stijn De Baerdemacker Department of Electronics and Information Systems, Universiteit Gent, Sint Pietersnieuwstraat 41, B-9000 Gent, Belgium “FWO-Vlaanderen” post-doctoral fellow, Department of Physics and Astronomy, Universiteit Gent, Proeftuinstraat 86, B-9000 Gent, Belgium; E-Mail: stijn.debaerdemacker@UGent.be ⋆ Author to whom correspondence should be addressed; E-Mail: alex@elis.UGent.be; Tel.: +32 9 264 33 76; Fax: +32 9 264 35 94 Received: 11 January 2011; in revised form: 24 May 2011 / Accepted: 27 May 2011 / Published: 7 June 2011 Abstract: Whereas quantum computing circuits follow the symmetries of the unitary Lie group, classical reversible computation circuits follow the symmetries of a finite group, i.e., the symmetric group. We confront the decomposition of an arbitrary classical reversible circuit with w bits and the decomposition of an arbitrary quantum circuit with w qubits. Both decompositions use the control gate as building block, i.e., a circuit transforming only one (qu)bit, the transformation being controlled by the other w − (qu)bits. We explain why the former circuit can be decomposed into w − control gates, whereas the latter circuit needs w − control gates. We investigate whether computer circuits, not based on the full unitary group but instead on a subgroup of th