Generators And Relations for Some Classes of Quantum Circuits
Abstract
We give three finite presentations in terms of generators and relations for three groups
of operators. The operators are frequently used in quantum computation. The result
can potentially be used to optimize quantum circuits. Two of the three proofs use
the Reidemeister-Schreier theorem. Both the Reidemeister-Schreier theorem and the
two proofs using it have been formally verified in the proof assistant Agda.
First, we give a finite presentation of the group of 2-qubit Clifford+T operators.
The proof applies the Reidemeister-Schreier theorem to a finite presentation of a
supergroup of the 2-qubit Clifford+T group that was given by Greylyn. The process
generates hundreds of relations. We then simplify them to 20 relations using a Pauli
rotation representation as an almost-normal form.
Second, we give a finite presentation of U_n (Z[1/2, i]), the group of unitary n × n-
matrices with entries in Z[1/2, i]. Amy, Glaudell, and Ross showed that this group is
generated by a certain set of two-level matrices, and they also gave an exact synthesis
algorithm that converts any element of U_n (Z[1/2, i]) to a word in these generators. We
say that a word is in normal form if it is an output of the exact synthesis algorithm.
Using what we call semantically guided rewriting, we show that each word in the
two-level generators is equivalent to a normal form under the congruence generated
by finitely many relations.
Third, we give a finite presentation of the group of 3-qubit Clifford+CS operators.
Amy, Glaudell, and Ross proved that up to a condition on the determinant,
the n-qubit Clifford+CS group is exactly U_(2^n) (Z[1/2, i]). In particular, the 3-qubit
Clifford+CS group is a subgroup of U_8 (Z[1/2, i]) of index 2. Using a similar technique
as in our first result, we repeatedly apply the Reidemeister-Schreier theorem to the
presentation of U_8 (Z[1/2, i]) (from our second result), and then simplify thousands of
relations into 17 relations. To do the simplification, we devise an almost-normal form
for Clifford+CS operators. We also show that the 3-qubit Clifford+CS group, which
is of course infinite, is the amalgamated product of three finite subgroups.