Classical reversible computers on w bits are isomorphic to the (finite) symmetric group S 2 w ; quantum computers on w qubits are isomorphic to the (Lie) unitary group U(2 w ). We investigate and classify groups X which represent computers intermediate between classical reversible computers and quantum computers. Such intermediate groups X may exist in three flavours: finite groups of order larger than (2 w )!, infinite but discrete groups, and Lie groups of dimension smaller than (2 w ). For our purpose, we start from 1-qubit transformations, represented by 2 × 2 unitary matrices. We call this group the creator. Its members are called gates and act on one qubit. Controlled gates are quantum circuits acting on w qubits, such that the 1-qubit transformation (applied to a particular qubit) depends on the state of the w − 1 other qubits. The controlled gates generate the group X of 2 w × 2 w matrices, called the creation. We discuss all creators of order up to 8. Additionally a creator of order 16 and one of order 192 are discussed.
As two basic building blocks for any quantum circuit, we consider the 1-qubit PHASOR circuit ϕ( θ ) and the 1-qubit NEGATOR circuit N ( θ ). Both are roots of the IDENTITY circuit. Indeed: both ϕ(0) and N (0) equal the 2 × 2 unit matrix. Additionally, the NEGATOR is a root of the classical NOT gate. Quantum circuits (acting on w qubits) consisting of controlled PHASORs are represented by matrices from ZU(2 w ); quantum circuits consisting of controlled NEGATORs are represented by matrices from XU(2 w ). Here, ZU( n ) and XU( n ) are subgroups of the unitary group U( n ): the group XU( n ) consists of all n × n unitary matrices with all 2 n line sums (i.e. all n row sums and all n column sums) equal to 1 and the group ZU( n ) consists of all n × n unitary diagonal matrices with first entry equal to 1. Any U( n ) matrix can be decomposed into four parts: U = exp( iα ) Z 1 XZ 2 , where both Z 1 and Z 2 are ZU( n ) matrices and X is an XU( n ) matrix. We give an algorithm to find the decomposition. For n = 2 w it leads to a four-block synthesis of an arbitrary quantum computer.
Classical reversible circuits, acting on
w~bits, are represented by permutation matrices of size
2w×2w. Those matrices form the group P(
2w), isomorphic to the symmetric group {\bf S}
2w. The permutation group P(
n), isomorphic to {\bf S}
n, contains cycles with length~
p, ranging from~1 to
L(n), where
L(n) is the so-called Landau function. By Lagrange interpolation between the
p~matrices of the cycle, we step from a finite cyclic group of order~
p to a 1-dimensional Lie group, subgroup of the unitary group U(
n). As U(
2w) is the group of all possible quantum circuits, acting on
w~qubits, such interpolation is a natural way to step from classical computation to quantum computation.
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−1 (qu)bits. We explain why the former circuit can be decomposed into 2w − 1 control gates, whereas the latter circuit needs 2w − 1 control gates. We investigate whether computer circuits, not based on the full unitary group but instead on a subgroup of the unitary group, may be decomposable either into 2w − 1 or into 2w − 1 control gates.