Reversible Computation, Quantum Computation, and Computer Architectures in Between
Alexis De Vos, Michiel Boes and Stijn De Baerdemacker
Thanks to the cosine-sine decomposition of unitary matrices, an arbitrary quantum circuit, acting on w qubits, can be decomposed into 2w − 1 elementary quantum gates, called controlled V gates. Thanks to the Birkhoff decomposition of doubly stochastic matrices, an arbitrary (classical) reversible circuit, acting on w bits, can be decomposed into 2w − 1 elementary gates, called controlled NOT gates. The question arises under which conditions these two synthesis methods are applicable for intermediate cases, i.e. computers based on some group, which simultaneously is a subgroup of the unitary group U(2w) and a supergroup of the symmetric group S2w. It turns out that many groups either belong to a class that might have a cosine-sine-like decomposition but no Birkhoff-like decomposition and a second class that might have both decompositions. For an arbitrary group, in order to find out to which class it belongs, it suffices to evaluate a function (m), deduced either from its order (in case of a finite group) or from its dimension (in case of a Lie group). Here m = 2w is the degree of the group.
Keywords: Reversible computation, quantum computation, group theory, Birkhoff decomposition, cosine-sine decomposition.