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

Generators and Relations for the Group $\mathrm{O}_n(\mathbb{Z}[1/2])$

Sarah Meng Li, Neil J. Ross, Peter Selinger

Published Jun 2, 2021• 0 citations
OpenAlex

Abstract

We give a finite presentation by generators and relations for the group $\mathrm{O}_n(\mathbb{Z}[1/2])$ of $n$-dimensional orthogonal matrices with entries in $\mathbb{Z}[1/2]$. We then obtain a similar presentation for the group of $n$-dimensional orthogonal matrices of the form $M/\sqrt{2}{}^k$, where $k$ is a nonnegative integer and $M$ is an integer matrix. Both groups arise in the study of quantum circuits. In particular, when the dimension is a power of $2$, the elements of the latter group are precisely the unitary matrices that can be represented by a quantum circuit over the universal gate set consisting of the Toffoli gate, the Hadamard gate, and the computational ancilla.

Related papers

Generators and Relations for the Group On(Z[1/2])

Sarah Meng Li, Neil J. Ross, Peter Selinger

We give a finite presentation by generators and relations for the group O_n(Z[1/2]) of n-dimensional orthogonal matrices with entries in Z[1/2]. We then obtain a similar presentation for the group of n-dimensional orthogonal matrices of the form M/sqrt(2)^k, where k is a nonnegative integer and M is an integer matrix. Both groups arise in the study of quantum circuits. In particular, when the dimension is a power of 2, the elements of the latter group are precisely the unitary matrices that can be represented by a quantum circuit over the universal gate set consisting of the Toffoli gate, the Hadamard gate, and the computational ancilla.

arXiv:2106.01175•Electronic Proceedings in Theoretical Computer Science•Sep 9, 2021•3 citations

Generators and relations for $U_n(\mathbb Z [\frac{1}{2}, i])$

Xiaoning Bian, Peter Selinger

Consider the universal gate set for quantum computing consisting of the gates X, CX, CCX, ${\omega}{\dagger}H$ and S. All of these gates have matrix entries in the ring $\mathbb Z [\frac{1}{2}, i]$, the smallest subring of the complex numbers containing $\frac{1}{2}$ and $i$. Amy, Glaudell, and Ross proved the converse, i.e., any unitary matrix with entries in $\mathbb Z [\frac{1}{2}, i]$ can be realized by a quantum circuit over the above gate set using at most one ancilla. In this paper, we give a finite presentation by generators and relations of $U_n(\mathbb Z [\frac{1}{2}, i])$, the group of unitary $n\times n$-matrices with entries in $\mathbb Z [\frac{1}{2}, i]$.

•May 28, 2021•0 citations

Generators and Relations for Un(Z[1/2,i])

Xiaoning Bian, Peter Selinger

Consider the universal gate set for quantum computing consisting of the gates X, CX, CCX, omega^dagger H, and S. All of these gates have matrix entries in the ring Z[1/2,i], the smallest subring of the complex numbers containing 1/2 and i. Amy, Glaudell, and Ross proved the converse, i.e., any unitary matrix with entries in Z[1/2,i] can be realized by a quantum circuit over the above gate set using at most one ancilla. In this paper, we give a finite presentation by generators and relations of U_n(Z[1/2,i]), the group of unitary nxn-matrices with entries in Z[1/2,i].

arXiv:2105.14047•Electronic Proceedings in Theoretical Computer Science•Sep 9, 2021•3 citations

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 the group $U_4(\mathbb{Z}[1/\sqrt{2},i])$

Seth Eveson Murray Greylyn

We give a presentation by generators and relations of the group $U_4(\mathbb{Z}[1/\sqrt{2},i])$ of unitary $4\times 4$ matrices with entries in the ring $\mathbb{Z}[1/\sqrt{2},i]$. This is motivated by the problem of exact synthesis for the Clifford+T gate set in quantum computation.

arXiv:1408.6204•Aug 22, 2014•4 citations

Generators and Relations for the Group U₄(ℤ[1/√2, i])

Seth Eveson Murray Greylyn

We give a presentation by generators and relations of the group U₄(ℤ[1/√2, i]) of unitary 4×4 matrices with entries in the ring ℤ[1/√2, i]. This is motivated by the problem of exact synthesis for the Clifford+T gate set in quantum computation.

•Aug 22, 2014•0 citations
Generators and Relations for the Group On(Z[1/2])\mathrm{O}_n(\mathbb{Z}[1/2])On​(Z[1/2])
We give a finite presentation by generators and relations for the group On(Z[1/2])\mathrm{O}_n(\mathbb{Z}[1/2])On​(Z[1/2]) of nnn-dimensional orthogonal matrices with entries in Z[1/2]\mathbb{Z}[1/2]Z[1/2]. We then obtain a similar presentation for the group of nnn-dimensional orthogonal matrices of the form M/2kM/\sqrt{2}{}^kM/2​k, where kkk is a nonnegative integer and MMM is an integer matrix. Both groups arise in the study of quantum circuits. In particular, when the dimension is a power of 222, the elements of the latter group are precisely the unitary matrices that can be represented by a quantum circuit over the universal gate set consisting of the Toffoli gate, the Hadamard gate, and the computational ancilla.
We give a finite presentation by generators and relations for the group O_n(Z[1/2]) of n-dimensional orthogonal matrices with entries in Z[1/2]. We then obtain a similar presentation for the group of n-dimensional orthogonal matrices of the form M/sqrt(2)^k, where k is a nonnegative integer and M is an integer matrix. Both groups arise in the study of quantum circuits. In particular, when the dimension is a power of 2, the elements of the latter group are precisely the unitary matrices that can be represented by a quantum circuit over the universal gate set consisting of the Toffoli gate, the Hadamard gate, and the computational ancilla.
Generators and relations for Un(Z[12,i])U_n(\mathbb Z [\frac{1}{2}, i])Un​(Z[21​,i])
Consider the universal gate set for quantum computing consisting of the gates X, CX, CCX, ω†H{\omega}{\dagger}Hω†H and S. All of these gates have matrix entries in the ring Z[12,i]\mathbb Z [\frac{1}{2}, i]Z[21​,i], the smallest subring of the complex numbers containing 12\frac{1}{2}21​ and iii. Amy, Glaudell, and Ross proved the converse, i.e., any unitary matrix with entries in Z[12,i]\mathbb Z [\frac{1}{2}, i]Z[21​,i] can be realized by a quantum circuit over the above gate set using at most one ancilla. In this paper, we give a finite presentation by generators and relations of Un(Z[12,i])U_n(\mathbb Z [\frac{1}{2}, i])Un​(Z[21​,i]), the group of unitary n×nn\times nn×n-matrices with entries in Z[12,i]\mathbb Z [\frac{1}{2}, i]Z[21​,i].
Consider the universal gate set for quantum computing consisting of the gates X, CX, CCX, omega^dagger H, and S. All of these gates have matrix entries in the ring Z[1/2,i], the smallest subring of the complex numbers containing 1/2 and i. Amy, Glaudell, and Ross proved the converse, i.e., any unitary matrix with entries in Z[1/2,i] can be realized by a quantum circuit over the above gate set using at most one ancilla. In this paper, we give a finite presentation by generators and relations of U_n(Z[1/2,i]), the group of unitary nxn-matrices with entries in Z[1/2,i].
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.
Generators and relations for the group U4(Z[1/2,i])U_4(\mathbb{Z}[1/\sqrt{2},i])U4​(Z[1/2​,i])
We give a presentation by generators and relations of the group U4(Z[1/2,i])U_4(\mathbb{Z}[1/\sqrt{2},i])U4​(Z[1/2​,i]) of unitary 4×44\times 44×4 matrices with entries in the ring Z[1/2,i]\mathbb{Z}[1/\sqrt{2},i]Z[1/2​,i]. This is motivated by the problem of exact synthesis for the Clifford+T gate set in quantum computation.