Reversible Computation, Quantum Computation, and Computer Architectures in Between

Thanks to the cosine-sine decomposition of unitary matrices, an arbitrary quantum circuit, acting on w qubits, can be decomposed into 2(w) - 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 2(w) - 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(2(w)) and a supergroup of the symmetric group S(2w). 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 phi(m), deduced either from its order (in case of a finite group) or from its dimension (in case of a Lie group). Here m = 2(w) is the degree of the group.