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

On the Structure of the CNOT-Dihedral Group

Shelly Garion, Andrew W. Cross

Published Jun 22, 2020• 1 citation
OpenAlex

Abstract

In this note we present explicit canonical forms for all the elements in the $2$-qubit CNOT-Dihedral group, with minimal numbers of controlled-$S$ ($CS$) and controlled-$X$ ($CX$) gates, using the generating set of quantum gates $[X, T, CX, CS]$. We provide an efficient algorithm, with a sharp bound, to successively construct the $n$-qubit CNOT-Dihedral group, asserting an optimal number of controlled-$X$ ($CX$) gates. These results are needed to estimate gate errors via non-Clifford randomized benchmarking and may have further applications to circuit optimization over fault tolerant gate sets.

Related papers

Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates

Shelly Garion, Andrew W. Cross

In this note we present explicit canonical forms for all the elements in the two-qubit CNOT-Dihedral group, with minimal numbers of controlled- S ( CS ) and controlled- X ( CX ) gates, using the generating set of quantum gates [X,T,CX,CS] . We provide an algorithm to successively construct the n -qubit CNOT-Dihedral group, asserting an optimal number of controlled- X ( CX ) gates. These results are needed to estimate gate errors via non-Clifford randomized benchmarking and may have further applications to circuit optimization over fault-tolerant gate sets.

arXiv:2006.12042•Quantum•Dec 7, 2020•8 citations

Optimal two-qubit circuits for universal fault-tolerant quantum computation

Andrew N. Glaudell, Neil J. Ross, Jacob M. Taylor

Abstract We study two-qubit circuits over the Clifford+CS gate set, which consists of the Clifford gates together with the controlled-phase gate CS = diag(1, 1, 1, i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes through magic state distillation. Since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is often desirable to construct circuits that use few CS gates. In the present paper, we introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operator U and outputs a Clifford+CS circuit for U, which uses the least possible number of CS gates. Because the algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for that operator. We give an explicit description of these normal forms and use this description to derive a worst-case lower bound of $$5{{\rm{log}}}_{2}(\frac{1}{\epsilon })+O(1)$$ 5 log 2 ( 1 ϵ ) + O ( 1 ) on the number of CS gates required to ϵ-approximate elements of SU(4). Our work leverages a wide variety of mathematical tools that may find further applications in the study of fault-tolerant quantum circuits.

arXiv:2001.05997•npj Quantum Information•Jun 22, 2021•20 citations

6-qubit optimal Clifford circuits

Sergey B. Bravyi, Joseph A. Latone, Dmitri Maslov

Abstract Clifford group lies at the core of quantum computation—it underlies quantum error correction, its elements can be used to perform magic state distillation and they form randomized benchmarking protocols, Clifford group is used to study quantum entanglement, and more. The ability to utilize Clifford group elements in practice relies heavily on the efficiency of their circuit-level implementation. Finding short circuits is a hard problem; despite Clifford group being finite, its size grows quickly with the number of qubits n, limiting known optimal implementations to n = 4 qubits. For n = 6, the number of Clifford group elements is about 2.1 × 1023. In this paper, we report a set of algorithms, along with their C implementation, that implicitly synthesize optimal circuits for all 6-qubit Clifford group elements by storing a subset of the latter in a database of size 2.1TB (1kB = 1024B). We demonstrate how to extract arbitrary optimal 6-qubit Clifford circuit in 0.0009358 and 0.0006274 s using consumer- and enterprise-grade computers (hardware) respectively, while relying on this database. We use this implementation to establish a new example of quantum advantage by Clifford circuits over CNOT gate circuits and find optimal Clifford 2-designs for up to 4 qubits.

arXiv:2012.06074•npj Quantum Information•Jul 5, 2022•22 citations

Quantum Compiling Methods for Fault-Tolerant Gate Sets of Dimension Greater than Two

Andrew N. Glaudell

Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/√2, i]. We focus on the subrings Z[1/2], Z[1/√2], Z[1/√−2], and Z[1/2, i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X, CX, CCX} with an analogue of the Hadamard gate and an optional phase gate. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.

•Jan 1, 2019•2 citations

An ASP Approach for the Synthesis of CNOT Minimal Quantum Circuits

Piazza C., Romanello R., Wille R.

In the last year, physical working Quantum Computers have been built and made available for the end users. Such devices, working under the rules of Quantum Mechanics, can only apply a finite set of one/two qubit operations that form a universal set of gates. Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. This synthesis procedure, however, is not constraint-free. In fact, we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. We start from a SAT encoding of the problem, and we translate it into an ASP model over a graph, by first working with a generic graph, and then by adopting the structure of a layered DAG. We provide experimental evidence of the scalability of our proposal.

•Jan 1, 2023•0 citations

CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries

Priyanka Mukhopadhyay

Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer $${\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^T$$ J n CS ⊂ J n T , where $${\mathcal {J}}_n^{CS}$$ J n CS and $${\mathcal {J}}_n^T$$ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying $${\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}$$ J n Tof = J n CS , where $${\mathcal {J}}_n^{Tof}$$ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.

Scientific Reports•Jun 17, 2024•2 citations
In this note we present explicit canonical forms for all the elements in the 222-qubit CNOT-Dihedral group, with minimal numbers of controlled-SSS (CSCSCS) and controlled-XXX (CXCXCX) gates, using the generating set of quantum gates [X,T,CX,CS][X, T, CX, CS][X,T,CX,CS]. We provide an efficient algorithm, with a sharp bound, to successively construct the nnn-qubit CNOT-Dihedral group, asserting an optimal number of controlled-XXX (CXCXCX) gates. These results are needed to estimate gate errors via non-Clifford randomized benchmarking and may have further applications to circuit optimization over fault tolerant gate sets.
In this note we present explicit canonical forms for all the elements in the two-qubit CNOT-Dihedral group, with minimal numbers of controlled- S ( CS ) and controlled- X ( CX ) gates, using the generating set of quantum gates [X,T,CX,CS] . We provide an algorithm to successively construct the n -qubit CNOT-Dihedral group, asserting an optimal number of controlled- X ( CX ) gates. These results are needed to estimate gate errors via non-Clifford randomized benchmarking and may have further applications to circuit optimization over fault-tolerant gate sets.
Abstract We study two-qubit circuits over the Clifford+CS gate set, which consists of the Clifford gates together with the controlled-phase gate CS = diag(1, 1, 1, i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes through magic state distillation. Since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is often desirable to construct circuits that use few CS gates. In the present paper, we introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operator U and outputs a Clifford+CS circuit for U, which uses the least possible number of CS gates. Because the algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for that operator. We give an explicit description of these normal forms and use this description to derive a worst-case lower bound of 5log2(1ϵ)+O(1)5{{\rm{log}}}_{2}(\frac{1}{\epsilon })+O(1)5log2​(ϵ1​)+O(1) 5 log 2 ( 1 ϵ ) + O ( 1 ) on the number of CS gates required to ϵ-approximate elements of SU(4). Our work leverages a wide variety of mathematical tools that may find further applications in the study of fault-tolerant quantum circuits.
Abstract Clifford group lies at the core of quantum computation—it underlies quantum error correction, its elements can be used to perform magic state distillation and they form randomized benchmarking protocols, Clifford group is used to study quantum entanglement, and more. The ability to utilize Clifford group elements in practice relies heavily on the efficiency of their circuit-level implementation. Finding short circuits is a hard problem; despite Clifford group being finite, its size grows quickly with the number of qubits n, limiting known optimal implementations to n = 4 qubits. For n = 6, the number of Clifford group elements is about 2.1 × 1023. In this paper, we report a set of algorithms, along with their C implementation, that implicitly synthesize optimal circuits for all 6-qubit Clifford group elements by storing a subset of the latter in a database of size 2.1TB (1kB = 1024B). We demonstrate how to extract arbitrary optimal 6-qubit Clifford circuit in 0.0009358 and 0.0006274 s using consumer- and enterprise-grade computers (hardware) respectively, while relying on this database. We use this implementation to establish a new example of quantum advantage by Clifford circuits over CNOT gate circuits and find optimal Clifford 2-designs for up to 4 qubits.
Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/√2, i]. We focus on the subrings Z[1/2], Z[1/√2], Z[1/√−2], and Z[1/2, i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X, CX, CCX} with an analogue of the Hadamard gate and an optional phase gate. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.
In the last year, physical working Quantum Computers have been built and made available for the end users. Such devices, working under the rules of Quantum Mechanics, can only apply a finite set of one/two qubit operations that form a universal set of gates. Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. This synthesis procedure, however, is not constraint-free. In fact, we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. We start from a SAT encoding of the problem, and we translate it into an ASP model over a graph, by first working with a generic graph, and then by adopting the structure of a layered DAG. We provide experimental evidence of the scalability of our proposal.
Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer JnCS⊂JnT{\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^TJnCS​⊂JnT​ J n CS ⊂ J n T , where JnCS{\mathcal {J}}_n^{CS}JnCS​ J n CS and JnT{\mathcal {J}}_n^TJnT​ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying JnTof=JnCS{\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}JnTof​=JnCS​ J n Tof = J n CS , where JnTof{\mathcal {J}}_n^{Tof}JnTof​ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.