Clifford Circuits on Qudits of Mixed Dimension

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).

Let G be a finite abelian group. Let G^=Hom(G,ℂ×)\hat G = {\mathop{\rm Hom}\nolimits} \left( {G,{^ \times }} \right) be the character group and let ℂ[G]=span{|g〉,g∈G}[G] = {\mathop{\rm span}\nolimits} \{ |g\rangle ,\,g \in G\} be the group algebra. The G-Pauli group is 1Pauli(G)={ ωXgZχ,(g,χ)∈G×G^,ω∈U(1) },{\mathop{\rm Pauli}\nolimits} (G) = \left\{ {\omega {X_g}{Z_\chi },\,\,(g,\chi ) \in G \times \hat G,\omega \in U(1)} \right\}, where the gates X_g and Z_χ are defined by 2Xg:ℂ[G]→ℂ[G], g∈G|h〉↦|gh〉\matrix{ {{X_g}:{\rm{C}}[G] \to {\rm{C}}[G],g \in G} \cr {|h\rangle \mapsto |gh\rangle } \cr } 3Zχ:ℂ[G]→ℂ[G],χ∈G^|g〉↦χ(g)|g〉\matrix{ {{Z_\chi }:{\rm{C}}[G] \to {\rm{C}}[G],\quad \chi \in \hat G} \cr {|g\rangle \mapsto \chi (g)|g\rangle } \cr }

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 ℂ[ Gn ]≅ℂ[G]n\left[ {{G^n}} \right] \cong {[G]^n}. The Pauli group on the product of groups decomposes as a product of U(1)-modules, Pauli (G×H)≅Pauli(G)×U(1)Pauli(H)(G \times H) \cong {\mathop{\rm Pauli}\nolimits} (G){ \times _{U(1)}}{\mathop{\rm Pauli}\nolimits} (H). Proposition 1 summarizes some known properties of the G-Pauli group.

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

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, 7U|h〉=UXh|1〉=χ(h)XhU|1〉=cgχ(h)Xh|g〉=cgχ(h)|hg〉.U|h\rangle = U{X_h}|1\rangle = \chi (h){X_h}U|1\rangle = {c_g}\chi (h){X_h}|g\rangle = {c_g}\chi (h)|hg\rangle .

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

Given a finite abelian group G, the G-Clifford group is 8Cliff(G)={ U:ℂ[G]→ℂ[G] s.t. UMU†∈Pauli(G),∀M∈Pauli(G) }.{\mathop{\rm Cliff}\nolimits} (G) = \left\{ {U:[G] \to [G]{\rm{ s}}{\rm{.t}}{\rm{. }}UM{U^\dag } \in {\mathop{\rm Pauli}\nolimits} (G),\forall M \in {\mathop{\rm Pauli}\nolimits} (G)} \right\}.

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 9Aτ:ℂ[G]→ℂ[G].|g〉↦|τ(g)〉\matrix{ {{A_\tau }:{\rm{C}}[G] \to {\rm{C}}[G].} \cr {\,\,\,\,\,\,\,\,\,\,\,\,\,\,|\,g\rangle \mapsto |\tau (g)\rangle } \cr }

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 10g,h↦ξ(gh)ξ(g)ξ(h)g,h \mapsto {{\xi (gh)} \over {\xi (g)\xi (h)}} is a character in each component individually. They act by 11Sξ:ℂ[G]→ℂ[G].|g〉↦ξ(g)|g〉\matrix{ {{S_\xi }:[G] \to [G].} \cr {\,\,\,\,\,\,\,\,|g\rangle \mapsto \xi (g)|g\rangle } \cr }

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

The G-Fourier transform is the map 12ℱ:ℂ[G]→ℂ[G^]|g〉↦1|G|∑χ∈G^χ(g)¯|χ〉\matrix{ {{\cal F}:[G] \to [\hat G]} \cr {|g\rangle \mapsto {1 \over {\sqrt {|G|} }}\sum\limits_{\chi \in \hat G} {\overline {\chi (g)} } |\chi \rangle } \cr }

Naively, the G-Fourier transform is not a Clifford gate because its codomain is ℂ[G^][\hat G], not ℂ[G]. For this reason one must parameterize the Fourier transform by some isomorphism i:G^∣→~Gi:\hat G\buildrel \~ \over \longrightarrow G, defining 13ℱi:ℂ[G]→ℂ[G].|g〉↦1|G|∑χ∈G^χ(g)¯|i(χ)〉.\matrix{ {{{\cal F}_i}:[G] \to [G].} \cr {\,\,\,\,\,\,\,\,\,\,|\,\,g\rangle \mapsto {1 \over {\sqrt {|G|} }}\sum\limits_{\chi \in \hat G} {\overline {\chi (g)} } |i(\chi )\rangle .} \cr }

The formula for the inverse Fourier transform is 14ℱi+:ℂ[G]→ℂ[G],|g⟩↦1|G|∑χ∈G^ χ(g)|χ∘i⟩.\matrix{ {{\cal F}_i^ + :[G] \to [G],} \hfill \cr {|\,g\rangle \mapsto {1 \over {\sqrt {|G|} }}\sum\limits_{\chi \in \hat G} \chi (g)|\chi ^\circ i\rangle .} \hfill \cr } where we identify χ◦i with a group element via the double dual isomorphism. We observe that χ◦i = i(χ) if and only if for all χ′∈G^{\chi ^\prime } \in \hat G the equation χ′(i(χ))=χ(i(χ′)){\chi ^\prime }(i(\chi )) = \chi \left( {i\left( {{\chi ^\prime }} \right)} \right) holds, which in general it does not.

We now move on to the case of quadratic phase gates. Let ξ be a quadratic form on Gⁿ. We can decompose 21ξ(g1,g2,⋯gn)=∏k=1nξk(gk)·∏1≤j<k≤nbjk(gj,gk)\xi \left( {{g_1},{g_2}, \cdots {g_n}} \right) = \prod\limits_{k = 1}^n {{\xi _k}} \left( {{g_k}} \right)\cdot\prod\limits_{1 \le j &#x003C; k \le n} {{b_{jk}}} \left( {{g_j},{g_k}} \right) 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≅∏j=1ℓℤrjG \cong \prod\limits_{j = 1}^\ell {{_{{r_j}}}} for some ℓ ≥ 0, r_j ≥ 2. Using the bilinearity of b, we find that 22b((s1,⋯sℓ),(s1′,…sℓ′))=∏1≤j<k≤ℓcjksjsk′b\left( {\left( {{s_1}, \cdots {s_\ell }} \right),\left( {s_1^\prime , \ldots s_\ell ^\prime } \right)} \right) = \prod\limits_{1 \le j &#x003C; k \le \ell } {c_{jk}^{{s_j}s_k^\prime }} 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 cjksjsk′c_{jk}^{{s_j}s_k^\prime }. To do this, we first apply the two-qudit automorphism gate parameterized by the automorphism τ:G×G→G×G,τ((s1,⋯sℓ),(s1′,⋯sℓ′))=((s1,⋯sjsk′′,⋯sℓ),(s1′,⋯sℓ′))\tau :G \times G \to G \times G,\tau \left( {\left( {{s_1}, \cdots {s_\ell }} \right),\left( {s_1^\prime , \cdots s_\ell ^\prime } \right)} \right) = \left( {\left( {{s_1}, \cdots {s_j}s_{{k^\prime }}^\prime , \cdots {s_\ell }} \right),\left( {s_1^\prime , \cdots s_\ell ^\prime } \right)} \right). Then, we apply the one-qudit phase gate S_χ associated to the character χ((s1…sℓ))=cjksj\chi \left( {\left( {{s_1} \ldots {s_\ell }} \right)} \right) = c_{jk}^{{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: 23CX:C[G×G]→C[G×G].|g〉|h〉↦|g〉|gh〉\matrix{ {{\rm{CX}}:{\rm{C}}[G \times G] \to {\rm{C}}[G \times G].} \cr {|g\rangle |h\rangle \mapsto |g\rangle |gh\rangle } \cr }

This gate is visualized as a circuit via

(24)

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,

(25)

(26)

(27)

(28)

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|χ〉=1|G|∑g∈Gχ(g)|g〉∈ℂ[G],χ∈G^.|\chi \rangle = {1 \over {\sqrt {|G|} }}\sum\limits_{g \in G} \chi (g)|g\rangle \in [G],\quad \chi \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:

(30)

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

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:

(32)

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

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∑g∈Gξ(g)|g〉|G{|^{ - 1/2}}\sum\nolimits_{g \in G} \xi (g)|g\rangle . 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].

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.

(35)

By the defining formula of i_ξ(χ) we get that ξ(iξ(χ))ξ(g)χ(g)¯=ξ(giξ(χ))\xi \left( {{i_\xi }(\chi )} \right)\xi (g)\overline {\chi (g)} = \xi \left( {g{i_\xi }(\chi )} \right). Hence, changing variables via h = gi_ξ (χ) we arrive at 37(ℱiξSξ)3|g〉=ℱiξSξℱiξ|G|∑h∈Gξ(h)|g−1h〉.{\left( {{{\cal F}_{{i_\xi }}}{S_\xi }} \right)^3}|g\rangle = {{{{\cal F}_{{i_\xi }}}{S_\xi }{{\cal F}_{{i_\xi }}}} \over {\sqrt {|G|} }}\sum\limits_{h \in G} \xi (h)\left| {{g^{ - 1}}h} \right\rangle .

Expanding further, we obtain 38(ℱiξSξ)3|g〉=ℱiξ|G|∑χ∈G^∑h∈Gξ(h)ξ(iξ(χ))χ(h)¯χ(g)|iξ(χ)〉.{\left( {{{\cal F}_{{i_\xi }}}{S_\xi }} \right)^3}|g\rangle = {{{{\cal F}_{{i_\xi }}}} \over {|G|}}\sum\limits_{\chi \in \hat G} {\sum\limits_{h \in G} \xi } (h)\xi \left( {{i_\xi }(\chi )} \right)\overline {\chi (h)} \chi (g)\left| {{i_\xi }(\chi )} \right\rangle .

Applying the defining relation ξ(h)ξ(iξ(χ))χ(h)¯=ξ(hiξ(χ))\xi (h)\xi \left( {{i_\xi }(\chi )} \right)\overline {\chi (h)} = \xi \left( {h{i_\xi }(\chi )} \right) and changing variables via h↦h·iξ(χ)¯h \mapsto h\cdot\overline {{i_\xi }(\chi )} gives 39(ℱiξSξ)3|g〉=(1|G|∑h∈Gξ(h))⋅ℱiξ|G|∑χ∈G^χ(g)|iξ(χ)〉{\left( {{{\cal F}_{{i_\xi }}}{S_\xi }} \right)^3}|g\rangle = \left( {{1 \over {\sqrt {|G|} }}\sum\limits_{h \in G} \xi (h)} \right) \cdot {{{{\cal F}_{{i_\xi }}}} \over {\sqrt {|G|} }}\sum\limits_{\chi \in \hat G} \chi (g)\left| {{i_\xi }(\chi )} \right\rangle 40=(1|G|∑h∈Gξ(h))|g〉. = \left( {{1 \over {\sqrt {|G|} }}\sum\limits_{h \in G} \xi (h)} \right)|g\rangle .

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.

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×G^(G)/U(1) \cong G \times \hat G, we get a natural map Cliff(G)→Aut(G×G^){\mathop{\rm Cliff}\nolimits} (G) \to {\mathop{\rm Aut}\nolimits} (G \times \hat G). To understand Cliff (G) we study the properties of this map. Define the symplectic group on G to be 41Sp(G)={σ∈Aut(G×G^) s.t. β(σ(x),σ(y))=β(x,y)},{\mathop{\rm Sp}\nolimits} (G) = \{ \sigma \in {\mathop{\rm Aut}\nolimits} (G \times \hat G){\rm{ s}}{\rm{.t}}{\rm{. }}\beta (\sigma (x),\sigma (y)) = \beta (x,y)\} , where β is the bilinear form 42β:(G×G^)×(G×G^)→ℂ×(g0,χ0)×(g1,χ1)↦χ0(g1)χ1(g0)¯.\matrix{ {\beta :(G \times \hat G) \times (G \times \hat G) \to {^ \times }} \hfill \cr {\,\,\,\,\,\,\,\,\,\,\,\,\left( {{g_0},{\chi _0}} \right) \times \left( {{g_1},{\chi _1}} \right) \mapsto {\chi _0}\left( {{g_1}} \right)\overline {{\chi _1}\left( {{g_0}} \right)} .} \hfill \cr }

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×G^)(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: 45SymBil(G)={ b:G×G→C×s.t. b(x,y)=b(y,x) }.{\mathop{\rm SymBil}\nolimits} (G) = \left\{ {b:G \times G \to {{\bf{C}}^ \times }{\rm{s}}{\rm{.t}}{\rm{. }}b(x,y) = b(y,x)} \right\}.

Every symmetric bilinear form b induces a map b˜:G→G^\tilde b:G \to \hat G sending g to b(g, –). This map satisfies b˜(x)(y)=b˜(y)(x)\tilde b(x)(y) = \tilde b(y)(x). Similarly, every symmetric homomorphism G→G^G \to \hat G induces a symmetric bilinear form. We will conflate symmetric bilinear forms and their induced homomorphisms G→G^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)).

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 47G≅ℤq0×ℤq1×ℤq2…×ℤqdG \cong {_{{q_0}}} \times {_{{q_1}}} \times {_{{q_2}}} \ldots \times {_{{q_d}}} with q_j|q_j–1. We write elements of G×G^G \times \hat G as vectors

(48)

We write elements of the endomorphism group End (G×G^)(G \times \hat G) as matrices. To compare cyclic groups of different orders, we view each ℤ_qj as the subgroup of ℤ_q0 consisting of multiples of q₀/q_j. For convenience with comparison between group elements and characters we canonically identify ℤ^qj{\widehat _{{q_j}}} with ℤ_qj 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

(49)

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×G^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

(50)

Then, further row reductions can be performed on the factors ℤ_q1 …ℤ_qd without affecting the ℤ_q0-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:

(51)

We start by applying S_ξ operators. By Bézout’s lemma, there exist integers k_i such that ri+kiri′=gcd(ri,ri′){r_i} + {k_i}r_i^\prime = \gcd \left( {{r_i},r_i^\prime } \right) in ℤ_qi. Let b be the map which acts as multiplication by k_i on the ℤ_qi 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

(52)

Now, let i:G→~G^i:G\buildrel \~ \over \longrightarrow \hat G be the isomorphism induced by our identifcation ℤqj≅ℤ^qj{_{{q_j}}} \cong {\widehat _{{q_j}}}. Postcomposing with the Fourier transform ℱ_i has the effect of swapping the ℤ_qi and ℤ^qi{\widehat _{{q_i}}} components by Proposition 2. Thus, we arrive at

(53)

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(r0,r0′)…gcd(rd,rd′)\gcd \left( {{r_0},r_0^\prime } \right) \ldots \gcd \left( {{r_d},r_d^\prime } \right) 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(r0,r0′),…gcd(rd,rd′))\left( {\gcd \left( {{r_0},r_0^\prime } \right), \ldots \gcd \left( {{r_d},r_d^\prime } \right)} \right) to (1, 0, 0‥, 0). Applying A_τ and using the commutation relationship of Proposition 2, we reduce our matrix to

(54)

Now, define the homomorphism b:G→G^b:G \to \hat G by sending (1, 0, 0‥, 0) to (−r0′′,−r1′′…,−rd′′)\left( { - r_0^{\prime \prime }, - r_1^{\prime \prime } \ldots , - r_d^{\prime \prime }} \right) 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

(55)

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

(56)

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 ℤ^q0{\widehat _{{q_0}}} row has all zeros outside of the (ℤ^q0,ℤ^q0)\left( {{{\widehat }_{{q_0}}},{{\widehat }_{{q_0}}}} \right) entry. Thus, we arrive at the reduction

(57)

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.