Excepting the final measurement, quantum computations are reversible computations. Quantum computers are infamously hard to construct, but reversible computers are easy (by seminal results of Toffoli). This paper aims to rigorously establish the relationship between quantum and reversible computation.

Quantum computing with n qubits is based on the group U(n) of n-by-n unitary matrices, whereas reversible computation with n bits is based on the group of n-by-n permutation matrices. The authors introduce two intermediate groups. First, the group XU(n) consists of all those n-by-n unitary matrices in which every row and every column adds up to one, and naturally represents reversible computation on n classical bits within the quantum setting of U(n). Second, the group ZU(n) consists of all those n-by-n diagonal unitary matrices whose upper-left entry is one, and represents local phase gates in quantum circuits. The main result is that every element of U(n) is a product of elements of XU(n) and ZU(n), in fact at most n(n-1)+4 of them. In this sense, XU(n) and ZU(n) form generators for all of U(n). Some relations between the two are mentioned, but the main development is left open.

This ties in with the recent development of calculi for quantum computation on n qubits, such as questions of soundness and completeness of the ZX-calculus; the paper could be seen as an explanation of this in terms of matrix algebra. For another example, the group XU(n) is linked to so-called negator gates, studied previously by the authors. Finally, the approach is related to finding optimal universal sets of quantum gates that can approximate any unitary matrix, such as the Clifford and T gates.