Universal Computation via T-Gate Synthesis in S4 Subgroups We investigate the computational complexity class of the finite monoid M_ext. We demonstrate that the algebraic structure supports a framework for universal quantum computation. 1. Clifford Group Mapping: The base structure (S4, Order 24) is shown to be isomorphic to the Clifford group operations acting on qubits. 2. Universal Resource: The symmetry-breaking boundary condition provides the necessary non-Clifford resource (analogous to Magic State injection or T-Gate) required for universality. 3. Turing Completeness: The braiding of algebraic generators allows for the approximation of unitary target gates, defining a complete computational model.
Universal Computation via T-Gate Synthesis in S4 Subgroups We investigate the computational complexity class of the finite monoid M_ext. We demonstrate that the algebraic structure supports a framework for universal quantum computation. 1. Clifford Group Mapping: The base structure (S4, Order 24) is shown to be isomorphic to the Clifford group operations acting on qubits. 2. Universal Resource: The symmetry-breaking boundary condition provides the necessary non-Clifford resource (analogous to Magic State injection or T-Gate) required for universality. 3. Turing Completeness: The braiding of algebraic generators allows for the approximation of unitary target gates, defining a complete computational model.
Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford+T. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the T gate (a T unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between n-qubit matchgate circuits and the standard representation of SO(2n), which reduces the compilation from 2n×2n unitaries to 2n×2n ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error εSO(2n) incurred in this smaller-dimensional representation translates at most into an O(nεSO(2n)) error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries U such that U⊗U∗ has entries in the ring Z[1/2,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic XX Hamiltonian on n=4,8 qubits.
We developed a general framework for synthesizing target gates by using a finite set of basic gates, which is a crucial step in quantum compilation. When approximating a gate in SU(n), a naive brute-force search requires a computational complexity of O(1/ε(n2−1)) to achieve an approximation with error ε. In contrast, by using our method, the complexity can be reduced to O(−n2logε/ε((n2−1)/2)). This method requires almost no assumptions and can be applied to a variety of gate sets, including Clifford+T and Clifford+V. Further, we introduce a suboptimal but short run-time algorithm for synthesizing multi-qubit controlled gates. This approach highlights the role of subgroup structures in reducing synthesis complexity and opens a new direction of study on the compilation of multi-qubit gates. The framework is broadly applicable to different universal gate sets, and our analysis suggests that it can serve as a foundation for resource-efficient quantum compilation in near-term architectures.
The Clifford hierarchy of unitary operators is a foundational concept for universal quantum computation. It was introduced to show that universal quantum computation can be realized via quantum teleportation, given access to certain standard resources. While the full structure of the hierarchy is still not understood, Cui et al. [S. X. Cui et al., Phys. Rev. A 95, 012329 (2017)] recently described the structure of diagonal unitaries in the hierarchy. They considered diagonal unitaries whose action on a computational basis qudit state is described by a 2kth root of unity raised to some polynomial function of the state, and they established the level of such unitaries in the hierarchy as a function of k and the degree of the polynomial. For qubit systems, we consider kth-level diagonal unitaries that can be described just by quadratic forms of the state over the ring Z2k of integers modulo 2k. The quadratic forms involve symmetric matrices over Z2k that can be used to efficiently describe all two-local and certain higher locality diagonal gates in the hierarchy. We also provide explicit algebraic descriptions of their action on Pauli matrices, which establishes a natural recursion to diagonal unitaries from lower levels. The result involves symplectic matrices over Z2k and hence our perspective unifies a subgroup of diagonal gates in the Clifford hierarchy with the binary symplectic framework for gates in the Clifford group. We augment our description with simple examples for certain standard gates. In addition to demonstrating structure, these formulas might prove useful in applications such as (i) classical simulation of quantum circuits, especially via the stabilizer rank approach, (ii) synthesis of logical non-Clifford unitaries, specifically alternatives to expensive magic state distillation, and (iii) decomposition of arbitrary unitaries beyond the Clifford+T set of gates, perhaps leading to shorter depth circuits. Our results suggest that some nondiagonal gates in the hierarchy might also be understood by generalizing other binary symplectic matrices to integer rings.
Non-Clifford gates, used to generate quantum magic, are essential for universal quantum computation. We show that non-Clifford gates arise naturally from path integrals in topological quantum field theories, where their magic-generating properties are determined by the algebraic data of the theory. In Chern-Simons theory, we construct the Ising interaction gate, whose generator is prepared by path integration over simple three-boundary manifolds, and show that it produces non-local magic away from discrete Clifford points. We show that the Toffoli gate is obstructed in SU(2)1 by the Z2 fusion structure, while SU(2)3 is the minimal theory supporting the required conditional logic, given the density of the mapping class group in the projective unitary group on the manifold boundary. Finally, we demonstrate that the T gate arises as a path integral in Dijkgraaf-Witten theory, with gauge group Z4, where a single Dehn twist on the boundary torus produces the gate without approximation. These results show that topological path integrals construct gates in multiple levels of the Clifford hierarchy, and across distinct classes of field theories, with implications for topological quantum computing.
For universal quantum computation, a major challenge to overcome for practical implementation is the large amount of resources required for fault-tolerant quantum information processing. An important aspect is implementing arbitrary unitary operators built from logical gates within the quantum error correction code. A synthesis algorithm can be used to approximate any unitary gate up to arbitrary precision by assembling sequences of logical gates chosen from a small set of universal gates that are fault-tolerantly performable while encoded in a quantum error-correction code. However, current procedures do not yet support individual assignment of base gate costs and many do not support extended sets of universal base gates. We analysed cost-optimal sequences using an exhaustive search based on Dijkstra’s pathfinding algorithm for the canonical Clifford+ T set of base gates and compared them to when additionally including Z -rotations from higher orders of the Clifford hierarchy. Two approaches of assigning base gate costs were used. First, costs were reduced to T -counts by recursively applying a Z -rotation catalyst circuit. Second, costs were assigned as the average numbers of raw (i.e. physical level) magic states required to directly distil and implement the gates fault-tolerantly. We found that the average sequence cost decreases by up to 54±3% when using the Z -rotation catalyst circuit approach and by up to 33±2% when using the magic state distillation approach. In addition, we investigated observed limitations of certain assignments of base gate costs by developing an analytic model to estimate the proportion of sets of Z -rotation gates from higher orders of the Clifford hierarchy that are found within sequences approximating random target gates.
We examine the following problem: given a collection of Clifford gates, describe the set of unitaries generated by circuits composed of those gates. Specifically, we allow the standard circuit operations of composition and tensor product, as well as ancillary workspace qubits as long as they start and end in states uncorrelated with the input, which rule out common "magic state injection" techniques that make Clifford circuits universal. We show that there are exactly 57 classes of Clifford unitaries and present a full classification characterizing the gate sets which generate them. This is the first attempt at a quantum extension of the classification of reversible classical gates introduced by Aaronson et al., another part of an ambitious program to classify all quantum gate sets. The classification uses, at its center, a reinterpretation of the tableau representation of Clifford gates to give circuit decompositions, from which elementary generators can easily be extracted. The 57 different classes are generated in this way, 30 of which arise from the single-qubit subgroups of the Clifford group. At a high level, the remaining classes are arranged according to the bases they preserve. For instance, the CNOT gate preserves the X and Z bases because it maps X-basis elements to X-basis elements and Z-basis elements to Z-basis elements. The remaining classes are characterized by more subtle tableau invariants; for instance, the T_4 and phase gate generate a proper subclass of Z-preserving gates.