Clifford Circuits on Qudits of Mixed Dimension

Milo Moses; Jacek Horecki; Konrad Deka; Jan Tułowiecki

doi:10.2478/qic-2026-0009

1. Introduction

Creating a fault-tolerant application-scale quantum computer is the goal of many scientists. One of the steps towards the realization of this goal is the development of low-overhead error correcting codes on which a universal set of logical gates can be applied fault-tolerantly. These error correcting codes are typically stabilizer codes, and the fault-tolerant gates are typically made from constant-depth local unitary circuits.

A fundamental challenge within error correction is that constant-depth local unitary circuits on two dimensional stabilizer codes can only act on the codespace by Clifford gates. This is known as the Bravyi-Koening bound [1], and along with related no-go theorems like the Eastin-Knill theorem [2], it sets out a clear difficulty. Not only is the Clifford gate set a proper subset of all possible quantum gates, but the Gottesman-Knill theorem asserts that the result of any quantum computation using only Clifford gates can be efficiently simulated on a classical computer [3]. Hence, any approach to quantum computing based on two-dimensional local stabilizer codes will need to confront these no-go results, and as such will need to deal with the structure of the space of Clifford operations.

In this paper we discuss a generalized version of the qubit Clifford group, based on qudits with an algebra specified by a finite abelian group G with cyclic factors of mixed dimension. This is the relevant group of logical operations when considering generalized stabilizer codes over a finite group G, such as Kitaev’s quantum double model associated to G [4]. These G-Pauli groups were already known to quantum information researchers a few years before Kitaev’s model [5,6]. We recall this group and its basic properties in Sections 2 and 3. Our analysis of the G-Clifford group is based on three elementary classes of gates - Fourier transforms, automorphism gates, and quadratic phase gates. These gates were introduced in Refs. [7,8], where it was conjectured that they efficiently generate all G-Clifford group. Our main result is the proof of this conjecture. It was shown in Refs. [7,8] that any circuit consisting of elementary Clifford gates can be efficiently classically simulated, and thus our results imply that every G-Clifford circuit can be efficiently classically simulated, a generalization of the Gottesman-Knill theorem. Our technique uses a group-theoretic generalization of the qudit linear algebra performed in Ref. [9].

We additionally provide several constructions related to Fourier transforms, automorphism gates, and quadratic phase gates which we believe will be of utility to the community. We show that every G-Clifford on multiple qudits can be decomposed into one-qudit and two-qudit gates (Section 3), we decompose the CX gate using 2-qudit G-Pauli measurements and elementary one-qudit Clifford gates (Section 4), we give an algorithm to implement non-G-Clifford gates using magic state injection (Section 5), and we simplify the primitive gate set by demonstrating that the global Fourier transform on any finite abelian group G can be used to obtain Fourier transforms on split subgroups of G (Section 6).

2. The G-Pauli Group

Let G be a finite abelian group. Let $\hat{G} = Hom (G, ℂ^{\times})$ be the character group and let $ℂ [G] = span {| g 〉, g \in G}$ be the group algebra. The G-Pauli group is

1

Pauli (G) = {ω X_{g} Z_{χ}, (g, χ) \in G \times \hat{G}, ω \in U (1)},

where the gates X_g and Z_χ are defined by

2

\begin{matrix} X_{g} : ℂ [G] \to ℂ [G], g \in G \\ | h 〉 \mapsto | g h 〉 \end{matrix}

3

\begin{matrix} Z_{χ} : ℂ [G] \to ℂ [G], χ \in \hat{G} \\ | g 〉 \mapsto χ (g) | g 〉 \end{matrix}

The G-Pauli group on n qudits is the space of operators on ℂ[G]ⁿ which are the tensor products of G-Pauli matrices on each component. Alternatively, one can identify this group with Pauli(Gⁿ) via the canonical isomorphism $ℂ [G^{n}] ≅ ℂ [G]^{n}$ . The Pauli group on the product of groups decomposes as a product of U(1)-modules, Pauli $(G \times H) ≅ Pauli (G) \times_{U (1)} Pauli (H)$ . Proposition 1 summarizes some known properties of the G-Pauli group.

Proposition 1.

Let G be a finite abelian group. The following statements about Pauli(G) are all true:

Every element of Pauli(G) is unitary.
We have that X_g₀ X_g₁ = X_g₁X_g₀ = X_g₀g₁ and Z_χ₀ Z_χ₁ = Z_χ₁ Z_χ₀ = Z_χ₀χ₁ for all g₀, g₁ ∈ G,_χ₀, $χ_{1} \in \hat{G} .$ .
We have that Z_χX_g = χ(g)X_gZ_χ for all g ∈ G, $χ \in \hat{G} .$ .
If a unitary operator U : ℂ[G] → ℂ[G] commutes with all elements of Pauli(G) it must be a scalar multiple of the identity.
If a unitary operator U : ℂ[G] → ℂ[ G ] commutes with all elements of Pauli(G) up to phase it must be a Pauli operator.

Proof.

Points (1)-(3) are straightforward. For point (4), suppose that

4

U | 1 〉 = \sum_{g \in G} c_{g} | g 〉 .

We have that

5

Z_{χ} U | 1 〉 = U Z_{χ} | 1 〉 = U | 1 〉 \forall χ \in \hat{G}

and hence χ(g)c_g = c_g for all

χ \in \hat{G}

so c_g = 0 for all g ≠ 1. Thus, U|1〉 = c₁|1〉. We conclude that U = c₁I, since

6

U | g 〉 = U X_{g} | 1 〉 = X_{g} U | 1 〉 = c_{1} X_{g} | 1 〉 = c_{1} | g 〉 .

We now move on to point (5). By assumption, Z_χU equals UZ_χ up to a phase for every $χ \in \hat{G}$ . The map $\hat{G} \to ℂ^{\times}$ sending χ to this phase is clearly a homomorphism. Since every character on $\hat{G}$ is induced by application on a group element, there exists g ∈ G such that Z_χU = χ(g)UZ_χ for all $χ \in \hat{G}$ . U |1〉 = Σ_h∈G ch |h〉 as before, then we have χ(h)c_h = χ(g)c_h. Thus, $U | 1 〉 = c_{g} | g 〉 .$ .

Now, we know by assumption that UX_h equals X_hU up to a phase. The map G → ℂ^× sending a group element to the phase it induces is a homomorphism, and thus there exists a character χ such that UX_h = χ(h)X_hU. Hence,

7

U | h 〉 = U X_{h} | 1 〉 = χ (h) X_{h} U | 1 〉 = c_{g} χ (h) X_{h} | g 〉 = c_{g} χ (h) | h g 〉 .

Thus, U = c_gX_gZ_χ so U is a Pauli operator as desired.

3. The G-Clifford Group

Given a finite abelian group G, the G-Clifford group is

8

Cliff (G) = {U : ℂ [G] \to ℂ [G] s .t . U M U^{†} \in Pauli (G), \forall M \in Pauli (G)} .

The qubit Clifford group can be generated by the Hadamard gate, S gate, and controlled-X gate as shown in Ref. [3]. We now describe the generalizations of these gates to the G-Clifford group, as introduced in Ref. [7]. We will see in Theorem 1 that these families are enough to generate all of Cliff (G).

The automorphism gates A_τ are parameterized by automorphisms τ : G → G. They act by

9

\begin{array}{r} A_{τ} : ℂ [G] \to ℂ [G] . \\ | g 〉 \mapsto | τ (g) 〉 \end{array}

For example, if G = ℤ₂ × ℤ₂ the automorphism τ((a, b)) = (a, a + b) induces the usual qubit CX gate.

The quadratic phase gates S_ξ are parameterized by quadratic forms ξ : G → ℂ ^×. That is, maps ξ such that the assignment

10

g, h \mapsto \frac{ξ (g h)}{ξ (g) ξ (h)}

is a character in each component individually. They act by

11

\begin{matrix} S_{ξ} : ℂ [G] \to ℂ [G] . \\ | g 〉 \mapsto ξ (g) | g 〉 \end{matrix}

We do not require our quadratic forms to be homogeneous, that is, it can be the case that ξ(g ⁻¹) ≠ (g). This implies that $ξ (g^{n}) = ξ (g)^{\frac{(n + 1) n}{2}} ξ {(g^{- 1})}^{\frac{(n - 1) n}{2}}$ .

The G-Fourier transform is the map

12

\begin{array}{l} ℱ : ℂ [G] \to ℂ [\hat{G}] \\ | g 〉 \mapsto \frac{1}{\sqrt{| G |}} \sum_{χ \in \hat{G}} \bar{χ (g)} | χ 〉 \end{array}

Naively, the G-Fourier transform is not a Clifford gate because its codomain is $ℂ [\hat{G}]$ , not ℂ[G]. For this reason one must parameterize the Fourier transform by some isomorphism $i : \hat{G} ∣ \tilde{\to} G$ , defining

13

\begin{array}{l} ℱ_{i} : ℂ [G] \to ℂ [G] . \\ | g 〉 \mapsto \frac{1}{\sqrt{| G |}} \sum_{χ \in \hat{G}} \bar{χ (g)} | i (χ) 〉 . \end{array}

The formula for the inverse Fourier transform is

14

\begin{array}{l} ℱ_{i}^{+} : ℂ [G] \to ℂ [G], \\ | g ⟩ \mapsto \frac{1}{\sqrt{| G |}} \sum_{χ \in \hat{G}}^{} χ (g) | χ \circ i ⟩ . \end{array}

where we identify χ◦i with a group element via the double dual isomorphism. We observe that χ◦i = i(χ) if and only if for all

χ^{'} \in \hat{G}

the equation

χ^{'} (i (χ)) = χ (i (χ^{'}))

holds, which in general it does not.

Proposition 2.

Let G be a finite abelian group. For all g ∈ G, $χ \in \hat{G}$ we have that

A_τ is a Clifford gate, for all automorphism $τ : G \tilde{\to} G .$ . Namely,
15
$A_{τ} X_{g} A_{τ}^{†} = X_{τ (g)},$

16
$A_{τ} Z_{χ} A_{τ}^{†} = Z_{χ ° τ^{- 1}} .$
S_ξ is a Clifford gate, for quadratic forms ξ : G → ℂ^×. Namely,
17
$S_{ξ} X_{g} S_{ξ}^{†} = ξ (g) X_{g} Z_{b_{ξ} (g, -)}$

18
$S_{ξ} Z_{χ} S_{ξ}^{†} = Z_{χ} .$
where b_ξ(g, h) = ξ(gh)/(ξ(g)ξ(hf))
ℱ_i is a Clifford gate, for isomorphisms $i : \hat{G} \tilde{\to} G$ Namely,
19
$ℱ_{i} X_{g} ℱ_{i}^{†} = Z_{\bar{g ° i^{- 1}}},$

20
$ℱ_{i} Z_{χ} ℱ_{i}^{†} = X_{i (χ)},$
where $χ ° i \in \hat{\hat{G}}$ is identified with an element of G via the double dual isomorphism.

Proof.

These follow from direct calculations.

In Section 7 we prove the converse:

Theorem 1.

Let G be a finite abelian group. Every Clifford gate on G can be constructed from ≤ 5 log₂ |G| gates of the form A_τ, S_ξ, and ℱ_i.

It was demonstrated in Ref. [8] for every finite group G that circuits consisting of automorphism gates, quadratic phase gates, and Fourier gates can be efficiently simulated by classical computers. This result was extended in Ref. [7], which allowed the quantum computer to perform mid-circuit G-Pauli measurements. Thus, from Theorem 1 one concludes that the results of Refs. [7,8] apply to all G-Clifford circuits.

We now discuss Cliff(Gⁿ), which we refer to as the group of n-qudit G-Clifford gates.

Proposition 3.

Every G-Clifford operation can be decomposed into one-qudit G-Clifford gates and two-qudit automorphism gates.

Proof.

In light of Theorem 1, we only need to demonstrate the result for the A_τ, S_ξ, and ℱ_i gates. Choosing an appropriate isomorphism i, the Fourier transform on ℂ[Gⁿ] is the tensor product of the Fourier transform on components. Thus, the global Fourier transform decomposes into one-qudit Clifford gates because the Fourier transform on each component is itself Clifford.

We now move on to the case of quadratic phase gates. Let ξ be a quadratic form on Gⁿ. We can decompose

21

ξ (g_{1}, g_{2}, \dots g_{n}) = \prod_{k = 1}^{n} ξ_{k} (g_{k}) \cdot \prod_{1 \leq j < k \leq n} b_{j k} (g_{j}, g_{k})

where ξ_k (g) = ξ(1,… g,…1) is ξ with a non-identity entry only at the k index, b_jk(h, k) = b((1, … h, … 1), (1, …g, … 1)) with non-identity entries only at indices j, k, and b(g, h) = ξ(gh)/(ξ(g)ξ(h)).

To implement S_ξ, we implement gates which act by each of the constituent phases within equation (21). The terms ξ_k (g_k) are one-qudit G-Clifford gates since each ξ_k is itself a quadratic form on G. To realize the b_jk phases, for any symmetric bilinear map b : G × G → ℂ^× we construct a decomposition of the two-qudit G-Clifford gate |(g₁, g₂)〉 ↦ b(g₁, g₂) |(g₁, g₂)〉 into one-qudit G-Cliffords and two-qudit automorphism gates.

We decompose G in terms of cyclic groups, $G ≅ \prod_{j = 1}^{ℓ} ℤ_{r_{j}}$ for some ℓ ≥ 0, r_j ≥ 2. Using the bilinearity of b, we find that

22

b ((s_{1}, \dots s_{ℓ}), (s_{1}^{'}, \dots s_{ℓ}^{'})) = \prod_{1 \leq j < k \leq ℓ} c_{j k}^{s_{j} s_{k}^{'}}

where C_jk = b((0, … 1, … 0), (0, … 1, … 0)) with non-zero entries only indices j, k. It thus suffices to construct a gate which realizes the phases

c_{j k}^{s_{j} s_{k}^{'}}

. To do this, we first apply the two-qudit automorphism gate parameterized by the automorphism

τ : G \times G \to G \times G, τ ((s_{1}, \dots s_{ℓ}), (s_{1}^{'}, \dots s_{ℓ}^{'})) = ((s_{1}, \dots s_{j} s_{k^{'}}^{'}, \dots s_{ℓ}), (s_{1}^{'}, \dots s_{ℓ}^{'}))

. Then, we apply the one-qudit phase gate S_χ associated to the character

χ ((s_{1} \dots s_{ℓ})) = c_{j k}^{s_{j}}

. We then apply the two-qudit automorphism gate parameterized by the automorphism τ⁻¹.

The last case is automorphism gates. This amounts to asking whether every automorphisms of Gⁿ can be written as a composition of automorphisms which affect only two of the components. To demonstrate this we appeal to the matrix theory of automorphisms, described in detail in Ref. [10] and used in Section 7 to prove Theorem 1. Every automorphism can be embedded into a matrix group with modular entries. Gaussian elimination shows that every invertible matrix can be row-reduced to the identity matrix. Each step in row reduction touches at most two rows, and hence can be implemented by an automorphism which touches at most two components. Hence, every automorphism can be decomposed as an iterated composition of automorphisms which touch at most two components.

We observe that Proposition 3 does not imply that every G-Clifford operation can be turned into one-qudit gates and CX gates. In particular, there are automorphism gates which cannot be decomposed into one-qudit automorphisms and CX automorphisms. This is in contrast to the case when G = ℤ_d is cyclic, where every Clifford can be generated by one-qudit gates and CX only. The generalized CX gate is defined as follows:

23

\begin{matrix} CX : C [G \times G] \to C [G \times G] . \\ | g 〉 | h 〉 \mapsto | g 〉 | g h 〉 \end{matrix}

This gate is visualized as a circuit via

The following proposition characterizes the behavior of the CX gate:

Proposition 4.

Let G be a finite abelian group. The CX gate is Clifford. Explicitly,

Proof.

This follows from a direct calculation.

An example of a group where not every two-qubit G-Clifford gate can be decomposed into one qudit gates and CX gates is G = ℤ₂ × ℤ₄.

Proposition 5.

Let G = ℤ₂ × ℤ₄. Consider the subgroup H of Aut(G²) generated by automorphisms which act by the identity on G × {0} or {0} × G, along with the automorphisms (g, h) ↦ (g, g + h), (g, h) ↦ (g + h, h). The subgroup H is a proper subgroup. In particular, the map ((a₀, b₀), (a₁, b₁)) ↦ ((a₀, b₀), (a₀ + a₁, b₁)) is not contained in H.

Proof.

All of the automorphisms ψ ∈ H satisfy the property that the projection of ψ((a, 0), (b, 0)) onto ℤ₂ × ℤ₂ ⊂ G × G is congruent modulo 2 to the projection of ψ((0, a), (0, b)) onto ℤ₄ × ℤ₄ ⊂ G × G. The morphism ((a₀, b₀), (a₁, b₁)) ↦ ((a₀, b₀), (a₀ + a₁, b₁)) does not have this property and hence it is not contained in H.

4. Implementing the CX Gate

A computational primitive which finds use in topological quantum computing is the decomposition of the CX gate in terms of two-qubit Pauli measurements. We show that this algorithm generalizes to G-Cliffords for all finite groups G. In light of Proposition 5, this does not show that every multi-qudit G-Clifford can be decomposed into one-qudit gates and two-qudit G-Pauli measurements.

We recall the properties of X and Z measurements over a generic finite abelian group G. The X_g operators commute, and thus one can perform a measurement in their simultaneous eigenbasis, that is, the character basis

29

| χ 〉 = \frac{1}{\sqrt{| G |}} \sum_{g \in G} χ (g) | g 〉 \in ℂ [G], χ \in \hat{G} .

Similarly, the operators Z_χ commute, and their simultaneous eigenspace is the group basis {|g〉, g ∈ G}. We now give a circuit for the CX gate in terms of these measurements:

Proposition 6.

The following equality holds, up to global phase:

where ZZ, XX, Z denote Pauli measurement channels, and p, χ, q are results of the respective measurements.

Proof.

We apply the right hand side of equation (30) to |g〉 |0〉 |h〉. After applying the Fourier transform, the state is |G|^−1/2 ∑_k |g〉 |k〉 |h〉. Measuring p under ZZ means we project orthogonally onto the subspace with p = gk. This results in the state |g〉 |pg⁻¹〉 |h〉. The XX measurement with result χ yields

31

\frac{1}{\sqrt{| G |}} \sum_{k \in G} \bar{χ (k)} | g 〉 | p g^{- 1} k 〉 | h k 〉 .

Measuring q under Z projects onto the subspace in which pg⁻¹ k = q, yielding the state $\bar{χ (q p^{- 1} g)} | g 〉 | q 〉 | h q p^{- 1} g 〉$ . Applying the final corrections gives $\bar{χ (q p^{- 1})} | g 〉 | 0 〉 | h g 〉$ . Since the phase $\bar{χ (q p^{- 1})}$ is independent of g and h, we have demonstrated the desired result.

5. Magic States

In this section we discuss magic state injection over a finite group G. The G-Clifford magic state injection circuit is demonstrated in Proposition 7.

Proposition 7.

Let ξ : G → U(1) be any function. Let S_ξ : ℂ[G] → ℂ[G] be the operator S_ξ |g〉 = ξ(g) |g〉. The following equality holds up to phase:

where k is the result of the measurement on the Z measurement, and b_ξ(k, g) = ξ(kg)/(ξ(k)ξ(g)).

Proof.

We apply the circuit to the state |g〉. After applying CX^†, the state is

33

\frac{1}{\sqrt{| G |}} \sum_{h \in G} ξ (h) | g 〉 | g^{- 1} h 〉 .

Measuring k = g⁻¹ h results in the state ξ(gk) |g〉 |k). Applying $S_{\bar{b_{\tilde{ξ}} (k, -)}}$ yields ξ(g)ξ(k) |g〉 |k〉. Since ξ(k) is a global phase, the result is as desired.

Wherever ξ : G → U(1) is a function such that b_ξ(k,–) is a quadratic form for every k ∈ G, Proposition 7 gives an algorithm form performing the gate S_ξ using only G-Cliffords and an ancillary state of the form of the form $| G |^{- 1 / 2} \sum_{g \in G} ξ (g) | g 〉$ . Choosing suitable ξ, the G-Clifford gates along with S_ξ can be used to perform universal quantum computing, following the techniques from for cyclic qudits presented in Ref. [11].

6. Fourier Transform on Split Subgroups

Whenever there is an equality of finite abelian groups G = H × K, the Fourier transform on H times the identity gate on K is a Clifford gate on G = H × K. In this section we show this H-Fourier transform gate can be decomposed into elementary G-Cliffords, namely, in terms of the Fourier transform on G. This is a necessary step in our proof of Theorem 1, which allows us to decompose every G-Clifford into elementary G-Cliffords.

Theorem 2.

Let ξ : G → ℂ^× be a non-degenerate quadratic form. Given $χ \in \hat{G} l e t i_{ξ} (χ)$ be the unique element of G such that

34

\frac{ξ (g) \tilde{ξ} (i_{ξ} (χ))}{ξ (g i_{ξ} (χ))} = χ (g), \forall g \in G .

(F_{i_ξ} Sξ)³ = I up to global phase
$F_{i_{ξ}}^{2} = A_{{(-)}^{- 1}},$ , where A(–)⁻¹ is the automorphism gate associated to the inversion automorphism, g ↦ g⁻¹.
Let H be another finite group, and let $i : \hat{H} \tilde{\to} H$ be any isomorphism. Letting the top qudit denote the Hilbert space ℂ[G] and letting the bottom qudit denote ℂ[H], we have that

Proof.

We begin by proving part (1). Choose g ∈ G. We compute

36

{(ℱ_{i_{ξ}} S_{ξ})}^{3} | g 〉 = \frac{ℱ_{i_{ξ}} S_{ξ} ℱ_{i_{ξ}}}{\sqrt{| G |}} \sum_{χ \in \hat{G}} ξ (i_{ξ} (χ)) ξ (g) \bar{χ (g)} | i_{ξ} (χ) 〉 .

By the defining formula of i_ξ(χ) we get that $ξ (i_{ξ} (χ)) ξ (g) \bar{χ (g)} = ξ (g i_{ξ} (χ))$ . Hence, changing variables via h = gi_ξ (χ) we arrive at

37

{(ℱ_{i_{ξ}} S_{ξ})}^{3} | g 〉 = \frac{ℱ_{i_{ξ}} S_{ξ} ℱ_{i_{ξ}}}{\sqrt{| G |}} \sum_{h \in G} ξ (h) | g^{- 1} h 〉 .

Expanding further, we obtain

38

{(ℱ_{i_{ξ}} S_{ξ})}^{3} | g 〉 = \frac{ℱ_{i_{ξ}}}{| G |} \sum_{χ \in \hat{G}} \sum_{h \in G} ξ (h) ξ (i_{ξ} (χ)) \bar{χ (h)} χ (g) | i_{ξ} (χ) 〉 .

Applying the defining relation $ξ (h) ξ (i_{ξ} (χ)) \bar{χ (h)} = ξ (h i_{ξ} (χ))$ and changing variables via $h \mapsto h \cdot \bar{i_{ξ} (χ)}$ gives

39

{(ℱ_{i_{ξ}} S_{ξ})}^{3} | g 〉 = (\frac{1}{\sqrt{| G |}} \sum_{h \in G} ξ (h)) \cdot \frac{ℱ_{i_{ξ}}}{\sqrt{| G |}} \sum_{χ \in \hat{G}} χ (g) | i_{ξ} (χ) 〉

40

= (\frac{1}{\sqrt{| G |}} \sum_{h \in G} ξ (h)) | g 〉 .

Since |g〉 was chosen arbitrarily and the phase has no dependence on g, we conclude the result. Part (2) follows from direct calculation, and part (3) follows from the first two.

7. The Generating Set of Clifford Gates

In this section we prove Theorem 1, which asserts that every G-Clifford gate can be efficiently decomposed into Fourier, quadratic phase, and automorphism gates. Our proof is in terms of the algebra of the symplectic group, which we recall now. Every Clifford operator U induces a map Pauli(G)/U(1) → Pauli(G)/U(1) by sending P to UPU^†. Seeing as Pauli $(G) / U (1) ≅ G \times \hat{G}$ , we get a natural map $Cliff (G) \to Aut (G \times \hat{G})$ . To understand Cliff (G) we study the properties of this map. Define the symplectic group on G to be

41

Sp (G) = {σ \in Aut (G \times \hat{G}) s .t . β (σ (x), σ (y)) = β (x, y)},

where β is the bilinear form

42

\begin{array}{l} β : (G \times \hat{G}) \times (G \times \hat{G}) \to ℂ^{\times} \\ (g_{0}, χ_{0}) \times (g_{1}, χ_{1}) \mapsto χ_{0} (g_{1}) \bar{χ_{1} (g_{0})} . \end{array}

Proposition 8.

The image of the natural map $Cliff (G) \to Aut (G \times \hat{G})$ is contained in Sp(G), and the sequence

43

0 \to Pauli (G) \to Cliff (G) \to Sp (G)

is exact.

Proof.

To begin, we observe that for every pair of pairs (g₀,χ₀), $(g_{1}, χ_{1}) \in G \times \hat{G}$ we have that

44

(X_{g_{0}} Z_{χ_{0}}) (X_{g_{1}} Z_{χ_{1}}) = χ_{0} (g_{1}) \bar{χ_{1} (g_{0})} (X_{g_{1}} Z_{χ_{1}}) (X_{g_{0}} Z_{χ_{0}}) .

Thus, we can re-cast β ((g₀,χ₀), (g₁, χ₁)) as the relative phase that appears upon commuting X_g0 Z_χ0 and X_g1 Z_χ1. Conjugating by U ∈ Cliff(G) must preserve this relative phase. Thus, the image of U in Aut $(G \times \hat{G})$ must preserve β(x,y), and thus the image of U must lie in Sp(G).

The kernel of the map Cliff(G) → Sp(G) consists of all matrices which act trivially on Pauli(G)/U(1). That is, matrices which commute with Pauli(G) up to phase. By Proposition 2, these are exactly the Pauli matrices.

We will make use of the group of symmetric bilinear forms:

45

SymBil (G) = {b : G \times G \to C^{\times} s .t . b (x, y) = b (y, x)} .

Every symmetric bilinear form b induces a map $\tilde{b} : G \to \hat{G}$ sending g to b(g, –). This map satisfies $\tilde{b} (x) (y) = \tilde{b} (y) (x)$ . Similarly, every symmetric homomorphism $G \to \hat{G}$ induces a symmetric bilinear form. We will conflate symmetric bilinear forms and their induced homomorphisms $G \to \hat{G}$ . Letting Quad(G) denote the group of quadratic forms, we have a map Quad(G) → SymBil(G) defined by sending ξ : G → ℂ^× to b(g,h) = ξ(gh)/(ξ(g)ξ(h)).

Lemma 1.

For any finite group G, we have a short exact sequence

46

0 \to \hat{G} \to Quad (G) \to SymBil (G) \to 0.

Proof.

A modern exposition of this result is given in Theorem 2.1 of Ref. [12].

We now describe the matrix theory of automorphisms (c.f., for instance, Ref. [10]). In this theory, group elements correspond to vectors and endomorphisms correspond to matrices. Matrix-vector products and matrix-matrix products correspond to application of endomorphisms of composition of endomorphisms respectively. The fundamental theorem of finite abelian groups tells us that

47

G ≅ ℤ_{q_{0}} \times ℤ_{q_{1}} \times ℤ_{q_{2}} \dots \times ℤ_{q_{d}}

with q_j|q_j–1. We write elements of

G \times \hat{G}

as vectors

We write elements of the endomorphism group End $(G \times \hat{G})$ as matrices. To compare cyclic groups of different orders, we view each ℤ_{q_j} as the subgroup of ℤ_q₀ consisting of multiples of q₀/q_j. For convenience with comparison between group elements and characters we canonically identify ${\hat{ℤ}}_{q_{j}}$ with ℤ_{q_j} by working with the distinguished generator n ↦ e^2πin/^q_j.

Every homomorphism between cyclic groups is a scalar multiplication, and as such we write the entries of the matrix as integers. For example, if G = ℤ₄ × ℤ₂ we have the matrix equation

Our strategy for proving Theorem 1 is as follows. Representing automorphisms as matrices, we will use rowreduction operations to show that every matrix in Sp(G) can be decomposed into products of the matrices associated to A_τ, S_ξ, ℱ_i. This shows that the subgroup generated by the A_τ, S_ξ, ℱ_i surjects onto Sp(G). Combining with Proposition 8 we can conclude the result.

Proof of Theorem 1.

We begin with a generic automorphism of $G \times \hat{G}$ in Sp(G) and reduce to the identity matrix using automorphisms of the form A_τ, S_ξ, and ℱ_i. We proceed by induction on the number of cyclic factors in the canonical decomposition of G. Suppose that we can always reduce elements of Sp(G) to matrices with 0s and 1s in the following configuration, and arbitrarily elements elsewhere

Then, further row reductions can be performed on the factors ℤ_q₁ …ℤ_{q_d} without affecting the ℤ_q₀-entries. This is true for A_τ and S_ξ gates because applying automorphisms and phases on one collection of cyclic factors does not affect the others, and it is true for ℱ_i gates because we can apply partial Fourier transforms by Proposition 2. In particular, by induction we would arrive at a proof of the main result. Thus, the proof amounts to finding a series of reductions to arrive at a matrix of this form. We begin the process of finding such moves with a generic matrix, as below:

We start by applying S_ξ operators. By Bézout’s lemma, there exist integers k_i such that $r_{i} + k_{i} r_{i}^{'} = \gcd (r_{i}, r_{i}^{'})$ in ℤ_{q_i}. Let b be the map which acts as multiplication by k_i on the ℤ_{q_i} component. By the short exact sequence of Lemma 1, there exists some quadratic form ξ such that b(g, –) = ξ (g · –)/(ξ(g)ξ(–)). Postcomposing with S_ξ and using the commutation relation in Proposition 2, we reduce our matrix to

Now, let $i : G \tilde{\to} \hat{G}$ be the isomorphism induced by our identifcation $ℤ_{q_{j}} ≅ {\hat{ℤ}}_{q_{j}}$ . Postcomposing with the Fourier transform ℱ_i has the effect of swapping the ℤ_{q_i} and ${\hat{ℤ}}_{q_{i}}$ components by Proposition 2. Thus, we arrive at

Now, since the matrix is an automorphism the greatest common divisor of the first column must be 1. Hence, the greatest common divisor of $\gcd (r_{0}, r_{0}^{'}) \dots \gcd (r_{d}, r_{d}^{'})$ is 1. Using the fact that q₀ is an element of maximal order in G, we know there exists an automorphism τ of G which maps $(\gcd (r_{0}, r_{0}^{'}), \dots \gcd (r_{d}, r_{d}^{'}))$ to (1, 0, 0‥, 0). Applying A_τ and using the commutation relationship of Proposition 2, we reduce our matrix to

Now, define the homomorphism $b : G \to \hat{G}$ by sending (1, 0, 0‥, 0) to $(- r_{0}^{''}, - r_{1}^{''} \dots, - r_{d}^{''})$ and acting by 0 on all other components. Using Lemma 1 we know that b is induced by a quadratic form ξ. Applying the corresponding S_ξ gate, we reduce without loss of generality to

We now apply the symplectic condition of S_p(G) to the pair of pairs x = (g₀, 0) and y = (0,χ₁), where g₀ = (1, 0, 0, …0), χ₁ = (1, 0, 0, …0). It gives us that r = b(σ(x), σ(y)) = b(x, y) = 1. We now repeat the same procedure as before but dualized, postcomposing with the appropriate A_τ and S_ξ gates. This reduces us to

Importantly, such postcomposition does not affect the entries in the first column. We now apply the symplectic condition with the pair of pairs x = (0, χ₀) and y = (g₁, χ₁), where χ₀ = (1, 0, 0, …0). Varying g₁ and χ₁, we conclude that the first row has all zeros after the 1st entry. Similarly, applying the symplectic condition with x = (g₀, 0), g₀ = (1, 0, 0, …0) we conclude that the ${\hat{ℤ}}_{q_{0}}$ row has all zeros outside of the $({\hat{ℤ}}_{q_{0}}, {\hat{ℤ}}_{q_{0}})$ entry. Thus, we arrive at the reduction

By induction on the number of cyclic factors in G, we conclude the decomposition into elementary gates.

We now count how many gates were used in the decomposition. At every step in the induction, we used five gates. Namely, a quadratic phase gate, followed by a Fourier transform on a split subgroup, followed by by an automorphism gate, followed by another quadratic phase gate, followed by another automorphism gate. The Fourier transform on a split subgroup is performed using the method in Proposition 2, which uses six elementary G-Clifford gates. So, the total number of gates is 10d. Since |G| ≥ 2^d, we get the desired bound.

Notes

[1] Contributed by Author Contributions

M.M. conceived the idea of the project, directed the research, and wrote the manuscript. M.M., J.H., K.D., and J.T. collaborated on the proof of Theorem 1. M.M. and J.T. collaborated on the revisions of the manuscript. All authors have read and agreed to the published version of the manuscript.

[2] Conflicts of interest Conflicts of Interest

The authors declare no conflicts of interest.

[3] Data Availability Statement

No data was analyzed or generated during the study.

Clifford Circuits on Qudits of Mixed Dimension

Full Article

1. Introduction

2. The G-Pauli Group

1

2

3

Proposition 1.

Proof.

4

5

6

7

3. The G-Clifford Group

8

9

10

11

12

13

14

Proposition 2.

15

16

17

18

19

20

Proof.

Theorem 1.

Proposition 3.

Proof.

21

22

23

(24)

Proposition 4.

(25)

(26)

(27)

(28)

Proof.

Proposition 5.

Proof.

4. Implementing the CX Gate

29

Proposition 6.

(30)

Proof.

31

5. Magic States

Proposition 7.

(32)

Proof.

33

6. Fourier Transform on Split Subgroups

Theorem 2.

34

(35)

Proof.

36

37

38

39

40

7. The Generating Set of Clifford Gates

41

42

Proposition 8.

43

Proof.

44

45

Lemma 1.

46

Proof.

47

(48)

(49)

Proof of Theorem 1.