Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2204.02217 · Electronic Proceedings in Theoretical Computer Science

Generators and Relations for 2-Qubit Clifford+T Operators

Xiaoning Bian, Peter Selinger

Published Nov 14, 2023• 5 citations
arXivHTMLPDF

Abstract

We give a presentation by generators and relations of the group of Clifford+T operators on two qubits. The proof relies on an application of the Reidemeister-Schreier theorem to an earlier result of Greylyn, and has been formally verified in the proof assistant Agda.
DOI
10.4204/eptcs.394.2

Related papers

Generators And Relations for Some Classes of Quantum Circuits

Xiaoning Bian

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.

•Aug 24, 2023•0 citations

Generators and Relations for 3-Qubit Clifford+CS Operators

Xiaoning Bian, Peter Selinger

We give a presentation by generators and relations of the group of 3-qubit Clifford+CS operators. The proof roughly consists of two parts: (1) applying the Reidemeister-Schreier theorem recursively to an earlier result of ours; and (2) the simplification of thousands of relations into 17 relations. Both (1) and (2) have been formally verified in the proof assistant Agda. The Reidemeister-Schreier theorem gives a constructive method for computing a presentation of a sub-monoid given a presentation of the super-monoid. To achieve (2), we devise an almost-normal form for Clifford+CS operators. Along the way, we also identify several interesting structures within the Clifford+CS group. Specifically, we identify three different finite subgroups for whose elements we can give unique normal forms. We show that the 3-qubit Clifford+CS group, which is of course infinite, is the amalgamated product of these three finite subgroups. This result is analogous to the fact that the 1-qubit Clifford+T group is an amalgamated product of two finite subgroups.

arXiv:2306.08530•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•2 citations

Generators and relations for n-qubit Clifford operators

Peter Selinger

We define a normal form for Clifford circuits, and we prove that every Clifford operator has a unique normal form. Moreover, we present a rewrite system by which any Clifford circuit can be reduced to normal form. This yields a presentation of Clifford operators in terms of generators and relations.

arXiv:1310.6813•Logical Methods in Computer Science•Jun 19, 2015•46 citations

A complete theory of the Clifford commutant

Lennart Bittel, Jens Eisert, Lorenzo Leone +2 more

The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group-a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with k -fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of k , constrained by the number of qubits n . In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary n and k . We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations, which generate the unitary group commutant, and at most three other operators. Additionally, we develop a graphical calculus allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all measurable magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension.

arXiv:2504.12263•Quantum•Jul 22, 2026•2 citations

Generalized Clifford groups and simulation of associated quantum circuits

Stephen R. L. Clark, Richard Jozsa, Noah Linden

Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup $G$ of $U(d)$. In particular we seek $G$ such that $G\otimes G$ has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case $d = 2$ we exhaustively treat all finite irreducible subgroups of $U(2)$ and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the $n^{\rm th}$ root of $Z$ for $n \in \N$.

Quantum Information and Computation•Jan 1, 2008•22 citations

Generalised Clifford groups and simulation of associated quantum circuits

Sean Clark, Richard Jozsa, Noah Linden

Quantum computations that involve only Clifford operations are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup G of U(d). In particular we seek G such that G tensor G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2 we exhaustively treat all finite subgroups of U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups G_n generated by X and the n^th root of Z.

arXiv:quant-ph/0701103•Jan 15, 2007•4 citations
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.
We give a presentation by generators and relations of the group of 3-qubit Clifford+CS operators. The proof roughly consists of two parts: (1) applying the Reidemeister-Schreier theorem recursively to an earlier result of ours; and (2) the simplification of thousands of relations into 17 relations. Both (1) and (2) have been formally verified in the proof assistant Agda. The Reidemeister-Schreier theorem gives a constructive method for computing a presentation of a sub-monoid given a presentation of the super-monoid. To achieve (2), we devise an almost-normal form for Clifford+CS operators. Along the way, we also identify several interesting structures within the Clifford+CS group. Specifically, we identify three different finite subgroups for whose elements we can give unique normal forms. We show that the 3-qubit Clifford+CS group, which is of course infinite, is the amalgamated product of these three finite subgroups. This result is analogous to the fact that the 1-qubit Clifford+T group is an amalgamated product of two finite subgroups.
The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group-a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with k -fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of k , constrained by the number of qubits n . In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary n and k . We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations, which generate the unitary group commutant, and at most three other operators. Additionally, we develop a graphical calculus allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all measurable magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension.
Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup GGG of U(d)U(d)U(d). In particular we seek GGG such that G⊗GG\otimes GG⊗G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2d = 2d=2 we exhaustively treat all finite irreducible subgroups of U(2)U(2)U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the nthn^{\rm th}nth root of ZZZ for n∈Nn \in \Nn∈N.
Quantum computations that involve only Clifford operations are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup G of U(d). In particular we seek G such that G tensor G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2 we exhaustively treat all finite subgroups of U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups G_n generated by X and the n^th root of Z.