# The Magic of Universal Quantum Computing with Permutations

Authors: Michel Planat; Rukhsan Ul Haq
Journal: Advances in Mathematical Physics
 (2017)

---

## Abstract

The role of permutation gates for universal quantum computing is investigated. The “magic” of computation is clarified in the permutation gates, their eigenstates, the Wootters discrete Wigner function, and state-dependent contextuality (following many contributions on this subject). A first classification of a few types of resulting magic states in low dimensionsd≤9 is performed.


---

## Body

## 1. Introduction

Quantum physics and (universal) computing are now considered to be deeply interrelated. This relatively new idea of science owes much to Feynman [1], Deutsch [2], Nielsen and Chuang [3], Bravyi and Kitaev [4], to mention a few popular landmarks. The timeline of quantum computing also includes other important marks with many of them, during the last two decades, dedicated to quantum computing platforms (let us mention Intel and NTT for spin qubits in semiconductors, Google, IBM, and D-Wave for superconducting qubits, Lockheed, and INFINEON for trapped ions. Other hardware efforts are being accomplished at university laboratories with linear optics, atoms and cavity QED, quantum dots, impurity spins in solids, etc. [5, 6].). Feynman already understood that the simulation of a quantum system on a classical computer would need exponential resources. Later Deutsch proposed a universal quantum computer made of quantum gates as a way of simulating a quantum system with at most a polynomial overhead. We know from Nielsen and Chuang that a quantum computer is able to factor large integers in polynomial time by exploiting the parallelism in the implementation of quantum Fourier transform [3, p. 221] and that quantum error correction may circumvent the undesirable effects due to decoherence by the use of quantum error-correcting codes [3, p. 435]. Bravyi and Kitaev introduced the principle of “magic state distillation”: universal quantum computation may be realized thanks to the stabilizer formalism (Clifford group unitary operators, preparations, and measurements [7]) and the ability to prepare an ancilla in an appropriate single qubit mixed state. Following [8, Sec. IIC], in this paper, a nonstabilizer pure state will be called a magic state.Within the frame of universal quantum computation based on the stabilizer formalism, it is being actively discussed if there exist critical resources responsible for the power of quantum computation. Remarkably, in odd dimensions, contextuality of the magic states seems to be the magic ingredient [9]. In addition, the contextuality of states is witnessed by the negative entries of a quasiprobability distribution, the discrete Wigner function (DWT). For even dimensions, the situation is more obscure since state-independent contextuality (correlated with the negativity of DWT) occurs from stabilizer states. Filtering of the quantum states involved in the computation based on full state tomography has been proposed [10]. Finally, according to [11], contextuality is required not just for measurement procedures but for preparation procedures as well, in order that the two notions of nonclassicality are revealed to be equivalent.Wigner function was recognized to contain permutation symmetry in its structure [12]. Interestingly enough, the experimental implementation of a simple quantum algorithm for determining the parity of a permutation was performed [13]. We claim in this paper that permutation symmetry can sometimes be considered lying beneath the concepts of magic states and contextuality that are responsible for the universality and efficiency of quantum computation. Permutation gates in the Clifford group (whose important elements are the CNOT gate and the Toffoli or CCNOT gate) reveal nonstabilizer states in their eigenvectors. The focus of this contribution is the use of two-generator permutation groups seen as sets of permutation gates and being the source of quantum states (stabilizer or magic) arising from their eigenstates. The groups of interest are in general different from the ones encountered in the previous investigation of the Kochen-Specker theorem [14]. Only state-dependent contextuality is involved in quantum computational universality, magic state distillation through quantum error-correcting codes, and possibly computational speed-up, as already emphasized [9].In Section2, we remind standard results about the generalized Pauli group, the phase-point operators, Wootters discrete Wigner function, and its link to quantum contextuality. In Section 3, we derive several types of magic states arising from permutation matrices in small dimensions d≤9, we make their Wigner function explicit and obtain state-dependent proofs of contextuality based on the existence of pentagons between the appropriate states (stabilizer and magic). Section 4 describes open vistas for further study.From Permutations to Quantum Gates. It is unusual to recognize the relationship of permutations with quantum gates as we intend to do in this work. A n-letter permutation admits a n×n binary matrix representation with exactly one entry of 1 in each row and each column and 0 s elsewhere. “Magic” permutation matrices are those showing one entry of 1 on their main diagonals. Some well-known permutation matrices/gates are the Pauli gate X=0110≡(2,1), I⊗X≡(2,1)(4,3), CNOT=1000010000010010≡(1,2)(4,3), CCNOT≡(1,2,3,4,5,6)(8,7), that acts on one, two, or three qubits, respectively. Similarly permutation gates may act on qudits as the shift gate X=010001100≡(2,3,1) acting on qutrits.In Section3, we focus on magic groups generated by two magic permutation gates (they exist as soon as d≥4 as in (10) of Section 3.3).


## 2. The Generalized Pauli Group, the Discrete Wigner Function, and Contextuality

Standard tools useful for the subsequent sections are mentioned.


### 2.1. The Generalized Pauli Group

Letd be a prime number; the qudit Pauli group is generated by the shift and clock operators as follows: (1)Xj=j+1modd,Zj=ωjj,with ω=exp(2iπ/d) being a dth root of unity. In dimension d=2, X and Z are the Pauli spin matrices σx and σz.A general Pauli (also called Heisenberg-Weyl) operator is of the following form:(2)Tm,j=ijmZmXjifd=2ω-jm/2ZmXjifd≠2,where (j,m)∈Zd×Zd. For N particles, one takes the Kronecker product of qudit elements N times.Stabilizer states are defined as eigenstates of the Pauli group.


### 2.2. The Discrete Wigner Function

Associated with eachd-dimensional Hilbert space (d a prime) is a discrete phase space, a d×d array of points on Zd×Zd. A set of phase point operators on the discrete phase space is defined as follows [16, 17] (see also [18]): (3)Aα=1d∑j,m=0d-1ωpj-qm+jm/2XjZm,α=q,p∈Zd×Zd.Wootters relations (10) and (11) in [16] follow.Phase point operators have been built to satisfy properties analogous to those of the continuous phase space in the context of the continuous Wigner functionW(q,p)=∫‍ρ(q+x/2,q-x/2)exp(ipx)dx in which p and q are position and momentum, and ρ(x,x′)=ψ∗(x)ψ(x) is a density matrix for a particle of coordinate x in a pure state of wave function ψ(x) [1, p. 477]. It is required that the operators Aα satisfy the following:(i) For each pointα, Aα is Hermitian.(ii) For any two pointsα and β, trAαAβ=dδαβ.(iii) Taking any complete set ofd parallel lines (called a striation), construct the average Pλ=1/d∑α∈λ‍Aα on each line λ. The d operators Pλ form a set of mutually orthogonal projectors the sum of which is the identity operator.Thed2 phase point operators Aα are linearly independent and form a basis for the space of Hermitian operators acting on a d-dimensional Hilbert space. As a result, any density operator can be developed as (4)ρ=∑q,pWρq,pAq,p,in which the real coefficients are explicitly given by the Wootters discrete Wigner function: (5)Wρq,p=1dtrρAq,p.Unlike the continuous Wigner function, the discrete Wigner function is a quasiprobability distribution that may take negative values. It is shown in [19] that, on a Hilbert space of odd dimension, the only pure states to possess a nonnegative discrete Wigner function are stabilizer states.On the contrary, a nonstabilizer pure state will be called a magic state. This definition follows from [20, Corollary 1] which establishes that any single-qubit pure state not one of the six Pauli eigenstates, together with Clifford group operations and Pauli eigenstate preparation and measurement, allows universal quantum computation. For arbitrary prime dimensions, magic state distillation is investigated in [15, 21–23]. For multiple qubits, see [20, Corollary 2]; any pure state which is not a stabilizer state allows universal quantum computation and [10].


### 2.3. State-Dependent Quantum Contextuality

Quantum contextuality forbids theories revealing preexisting values of observables under test if the specific experimental setup for measuring such observables is not taken into account. One way to characterize quantum contextuality is to use a no-go approach a la Kochen-Specker involving sets of quantum observables (as the Mermin square) or special subsets of their eigenstates shared by their mutually commuting operators [24]. The smallest proof of state-independent contextuality is not a Kochen-Specker set; it needs 13 rays in the three-dimensional Hilbert space [25]. State-independent contextuality can be obtained within the stabilizer formalism for multiple qubits but is not manifested with qudits (when d≠2).The starting point of a state-dependent proof of quantum contextuality consists of a set ofk binary tests that are represented by k rank one projectors {Πi=vivi,i=1⋯k}. The tests are compatible if and only if the projectors are mutually orthogonal. An (exclusivity) graph Γ is associated to the tests wherein each vertex corresponds to the projectors Πi and an edge corresponds to compatible projectors. A witness operator ΣΓ is defined as follows: (6)ΣΓ=∑i=1kΠi.It is required that a value of 1 is assigned to at most one projector in each joint measurement of (compatible) observables located on a selected edge. For a noncontextual hidden variable theory, one expects that the results of tests are such that ΣΓmax≤α(Γ), where α(Γ) is the independence number of the graph Γ and the cardinality of the largest set of vertices such that no two elements are connected by an edge. But a quantum contextual theory may bypass this bound and be such that α(Γ)≤ΣΓmax≤θ(Γ), in which the upper bound is the Lovasz number of the exclusivity graphs [9, 26]. It is calculated from θ(G)=maxψ∑i=1k‍ψ∣vi2, where the maximum is taken over all unit vectors ψ.The simplest state-dependent proof of quantum contextuality corresponds to the cyclic graphC5 (also called a pentagon) in which θ(C5)=5>α(C5)=2. It was originally obtained for a spin-1 quantum system or qutrit [27]. Each exclusivity graph Γ where α(Γ)<θ(Γ) allows a state-dependent proof of quantum contextuality. If ΣΓmax>α(Γ) for every state, then the proof of contextuality is state-independent. To summarize, graphs in which α(Γ)<θ(Γ) may be considered a proof of quantum contextuality if, for appropriately chosen projectors Πi and a state ρ, the following noncontextuality inequality is violated [23]: (7)TrΣΓρ≤αΓ.Is contextuality needed for universality and quantum computational speed-up? For qudits (in odd dimension), only states lying outside the stabilizer polytope [28] manifest the negativity of the Wigner function and simultaneously violate the inequality (7) through appropriate two-qudit projectors; hence they display state-dependent contextuality [9, Theorem 1]. Thus the answer is yes.For even dimensions, nonstabilizer pure states of single or multiple qubits are magic. But neither the condition of negativity nor the criterion of contextuality is sufficient to promote such states to computational universality. This is because there exist (well characterized) Kochen-Specker sets of multiqubits [14]. However, it is shown in a recent paper [10] that contextuality is needed whenever two conditions are satisfied: (i) the contextuality is state-dependent and (ii) one retains a filtered set of quantum states able to ensure a full state tomography.


## 2.1. The Generalized Pauli Group

Letd be a prime number; the qudit Pauli group is generated by the shift and clock operators as follows: (1)Xj=j+1modd,Zj=ωjj,with ω=exp(2iπ/d) being a dth root of unity. In dimension d=2, X and Z are the Pauli spin matrices σx and σz.A general Pauli (also called Heisenberg-Weyl) operator is of the following form:(2)Tm,j=ijmZmXjifd=2ω-jm/2ZmXjifd≠2,where (j,m)∈Zd×Zd. For N particles, one takes the Kronecker product of qudit elements N times.Stabilizer states are defined as eigenstates of the Pauli group.


## 2.2. The Discrete Wigner Function

Associated with eachd-dimensional Hilbert space (d a prime) is a discrete phase space, a d×d array of points on Zd×Zd. A set of phase point operators on the discrete phase space is defined as follows [16, 17] (see also [18]): (3)Aα=1d∑j,m=0d-1ωpj-qm+jm/2XjZm,α=q,p∈Zd×Zd.Wootters relations (10) and (11) in [16] follow.Phase point operators have been built to satisfy properties analogous to those of the continuous phase space in the context of the continuous Wigner functionW(q,p)=∫‍ρ(q+x/2,q-x/2)exp(ipx)dx in which p and q are position and momentum, and ρ(x,x′)=ψ∗(x)ψ(x) is a density matrix for a particle of coordinate x in a pure state of wave function ψ(x) [1, p. 477]. It is required that the operators Aα satisfy the following:(i) For each pointα, Aα is Hermitian.(ii) For any two pointsα and β, trAαAβ=dδαβ.(iii) Taking any complete set ofd parallel lines (called a striation), construct the average Pλ=1/d∑α∈λ‍Aα on each line λ. The d operators Pλ form a set of mutually orthogonal projectors the sum of which is the identity operator.Thed2 phase point operators Aα are linearly independent and form a basis for the space of Hermitian operators acting on a d-dimensional Hilbert space. As a result, any density operator can be developed as (4)ρ=∑q,pWρq,pAq,p,in which the real coefficients are explicitly given by the Wootters discrete Wigner function: (5)Wρq,p=1dtrρAq,p.Unlike the continuous Wigner function, the discrete Wigner function is a quasiprobability distribution that may take negative values. It is shown in [19] that, on a Hilbert space of odd dimension, the only pure states to possess a nonnegative discrete Wigner function are stabilizer states.On the contrary, a nonstabilizer pure state will be called a magic state. This definition follows from [20, Corollary 1] which establishes that any single-qubit pure state not one of the six Pauli eigenstates, together with Clifford group operations and Pauli eigenstate preparation and measurement, allows universal quantum computation. For arbitrary prime dimensions, magic state distillation is investigated in [15, 21–23]. For multiple qubits, see [20, Corollary 2]; any pure state which is not a stabilizer state allows universal quantum computation and [10].


## 2.3. State-Dependent Quantum Contextuality

Quantum contextuality forbids theories revealing preexisting values of observables under test if the specific experimental setup for measuring such observables is not taken into account. One way to characterize quantum contextuality is to use a no-go approach a la Kochen-Specker involving sets of quantum observables (as the Mermin square) or special subsets of their eigenstates shared by their mutually commuting operators [24]. The smallest proof of state-independent contextuality is not a Kochen-Specker set; it needs 13 rays in the three-dimensional Hilbert space [25]. State-independent contextuality can be obtained within the stabilizer formalism for multiple qubits but is not manifested with qudits (when d≠2).The starting point of a state-dependent proof of quantum contextuality consists of a set ofk binary tests that are represented by k rank one projectors {Πi=vivi,i=1⋯k}. The tests are compatible if and only if the projectors are mutually orthogonal. An (exclusivity) graph Γ is associated to the tests wherein each vertex corresponds to the projectors Πi and an edge corresponds to compatible projectors. A witness operator ΣΓ is defined as follows: (6)ΣΓ=∑i=1kΠi.It is required that a value of 1 is assigned to at most one projector in each joint measurement of (compatible) observables located on a selected edge. For a noncontextual hidden variable theory, one expects that the results of tests are such that ΣΓmax≤α(Γ), where α(Γ) is the independence number of the graph Γ and the cardinality of the largest set of vertices such that no two elements are connected by an edge. But a quantum contextual theory may bypass this bound and be such that α(Γ)≤ΣΓmax≤θ(Γ), in which the upper bound is the Lovasz number of the exclusivity graphs [9, 26]. It is calculated from θ(G)=maxψ∑i=1k‍ψ∣vi2, where the maximum is taken over all unit vectors ψ.The simplest state-dependent proof of quantum contextuality corresponds to the cyclic graphC5 (also called a pentagon) in which θ(C5)=5>α(C5)=2. It was originally obtained for a spin-1 quantum system or qutrit [27]. Each exclusivity graph Γ where α(Γ)<θ(Γ) allows a state-dependent proof of quantum contextuality. If ΣΓmax>α(Γ) for every state, then the proof of contextuality is state-independent. To summarize, graphs in which α(Γ)<θ(Γ) may be considered a proof of quantum contextuality if, for appropriately chosen projectors Πi and a state ρ, the following noncontextuality inequality is violated [23]: (7)TrΣΓρ≤αΓ.Is contextuality needed for universality and quantum computational speed-up? For qudits (in odd dimension), only states lying outside the stabilizer polytope [28] manifest the negativity of the Wigner function and simultaneously violate the inequality (7) through appropriate two-qudit projectors; hence they display state-dependent contextuality [9, Theorem 1]. Thus the answer is yes.For even dimensions, nonstabilizer pure states of single or multiple qubits are magic. But neither the condition of negativity nor the criterion of contextuality is sufficient to promote such states to computational universality. This is because there exist (well characterized) Kochen-Specker sets of multiqubits [14]. However, it is shown in a recent paper [10] that contextuality is needed whenever two conditions are satisfied: (i) the contextuality is state-dependent and (ii) one retains a filtered set of quantum states able to ensure a full state tomography.


## 3. Magic States and State-Dependent Quantum Contextuality from Groups of Permutation Gates

We already know that permutation symmetry exists in the discrete Wigner function [12]. Our goal in this section is to shift our attention from the set of Clifford gates to a subset whose elements are permutation gates, leading to either stabilizer states or not. Classes of magic states and the related (state-dependent) contextuality will be investigated having in mind the tools described in Section 2 but by restricting to the existence of pentagons between the appropriate states (as in [27]).For dimensions larger than 4, the eigenstates of permutation gates under consideration are living in a field that may be different from the cyclotomic fieldQ[exp⁡2iπ/d]. In this paper, in order to keep this first classification short enough, for d>4, we restrict the magic states to those having entries 0 and ±1 corresponding to eigenvalues ±1.


### 3.1. Qubit Magic States

Fault tolerant quantum computing protocols based on stabilizer states have to be complemented by magic states to reach quantum universality. Two distillation protocols based on single qubit magic statesH and T are first described in [4] where (8)H=cos⁡π80+sin⁡π81,T=cos⁡β0+exp⁡iπ4sin⁡β1,cos⁡2β=13.Magic state H is the +1-eigenstate of the Hadamard matrix H=σx+σz/2 that belongs to single qubit the Clifford group. Magic state T is the ω3=exp(2iπ/3)-eigenstate of the SH matrix, where the phase gate S=100i also belongs to the Clifford group. Being not stabilizer states, they cannot be prepared by actions from the Clifford group but they can be distilled with these actions from a (dirty) mixed state to a (neat) pure state thanks to appropriate quantum codes [4, 20, 21].Matrix elements of Wootters discrete Wigner functionWρ(q,p) for a few single qubit pure states are shown in Table 1. The first three rows correspond to +1-eigenstates of Pauli spin matrices and the last two rows are for magic states. Magic state H possesses a negative entry unlike the magic state T. In the latter case, negativity of the Wigner function does not coincide with universality.Table 1
Wootters discrete Wigner function for a few pure statesρ=ψψ.
Stateψ
Eigenstate of
W
ρ
0
σ
z
1
2
1
1
0
0
1
2
(
0
+
1
)
σx
1
2
1
0
1
0
1
2
(
0
-
i
1
)
σy
1
2
0
1
1
0
H
H
=
σ
x
+
σ
z
2
1
4
1
+
2
1
1
1
-
2
T
SH
1
4
1
+
3
3
1
+
3
3
1
+
3
3
3
-
1


### 3.2. Magic States from Qutrit Permutation Gates

The smallest dimension for the occurrence of magic states associated with permutations is three. There are, up to isomorphism, two (nontrivial, i.e., with two distinct generators) two-generator permutation groups on three letters.The permutation group isomorphic toZ3 contains the permutation matrices I, X, and X2 of the Pauli group, where X is the shift matrix in (1). The eigenstates are the mutually orthogonal stabilizer states (1,1,1), (1,ω,ω2), and (1,ω2,ω), with ω being the third root of unity.The permutation group isomorphic to the symmetric groupS3 exists in three copies. One of them is generated as S3=(1,2,3),(2,3) and contains the elements found in Z3 and three extra ones 100001010≡(2,3), 001010100≡(1,3), and 010100001≡(1,2), that do not lie in Pauli group but are parts of the Clifford group. The 5 mutually orthogonal triples between the 12 eigenstates are pictured in Figure 1(a). Apart from the 6 stabilizer states, there are 6 magic states of types (0,1,1) and (0,1,-1). In [8], they are identified as the Norrell states and strange states, respectively, with Wigner function. (9)W0,1,1=162-1-1111111,W0,1,-1=16-211111111.As expected, all magic states contains some negative entries in their Wigner matrix.Figure 1
(a) Triples of mutually orthogonal rays arising from qutrit permutation gates; (b) three pentagons originating from the rays. Big black bullets are for stabilizer states; small bullets are for magic states.
(a)
(b)In Figure1(b), it is shown that three pentagons are part of the orthogonality relations. Taking the rank 1-projectors associated with the vertices/states, the exclusivity graph attached to each pentagon is also a pentagon and allows a state-dependent proof of contextuality. One observes that only magic states of the strange type are involved.


### 3.3. Magic States from Two-Qubit Permutation Gates

From now, we consider permutation groups whose two generators are magic gates. This only happens for two groups both being isomorphic to the alternating groupA4. One copy is as follows: (10)A4≅1000000101000010,0100001010000001.Looking for joined eigenstates shared by at least two commuting gates, a set of 20 states is derived whose orthogonality graph is pictured in Figure2(a).Figure 2
(a) Maximum cliques of orthogonal rays from two-qubit permutation gates: 6 4-tuples (thin lines) and 4 triples (thick lines),ω=exp⁡(iπ/3). Missing coordinates are straightforward to recover. (b) Maximum cliques of orthogonal rays from 5-dit permutation gates: 7 5-tuples (thin lines) and 5 4-tuples (thick lines). Big black bullets are for stabilizer states; small black bullets are for magic states.
(a)
(b)Wigner functions for magic states are of two types:(11)W0,1,1,1=1121-122-110020402000,W0,1,-ω,ω-1=124-1111+231-133-2313-13-231-233+233+233,with W(0,1,ω-1,-ω)=W(0,1,-ω,ω-1)t. Both types of Wigner matrices contain negative entries as for the qutrit case (in this particular case, the stabilizer states selected from permutation gates do not).It can be shown that the orthogonality graph contains 24 pentagons and thus 24 state-dependent proofs of contextuality. Surprisingly, the vertices of such pentagons either are stabilizer states or magic states of the second type, analogous to qutrit strange states.


### 3.4. Magic States from 5-Dit Permutation Gates

We again consider permutation groups whose two generators are magic gates. This happens for permutation groups isomorphic to the semidirect productZ5⋊Z4 or to the symmetric group S5, respectively.As for the first case, taking all triples of mutually commuting/compatible permutation gates, one gets a set of 30 eigenstates. They are organized into maximum cliques shown in Figure2(b) with 20 of them being magic. Missing coordinates are in the cyclotomic field Q[exp⁡(2iπ/4)].(12)W0,1,1,1,1=1204-1-1-1-13+-′-′+3-′++-′3-′++-′3+-′-′+,W0,1,-1,-1,1=1204-1-1-1-1-1-′′+′′+′′-′′-1+′′-′′-′′+′′-1+′′-′′-′′+′′-1-′′+′′+′′-′′,where the symbol “±” means ±(1+5)/2, the symbol “±′” means ±(5-1)/2, and “±′′” means (3±5)/2.As for the groupS5, one gets 50 eigenstates (shared by the 10 maximum cliques of 5 mutually compatible gates). We do not show the organization of eigenstates but only mention that one arrives at other types of magic states of the following form:(13)W0,0,0,1,±1=11000000-2±′∓∓±′000001111111111,W0,0,1,1,1=1152+′--+′2+′--+′111113-′++-′11111.As before, state-dependent contextuality may be revealed from the pentagons that are built from the states.


### 3.5. Magic States from Qubit-Qutrit Permutation Gates

The smallest permutation group generated by two magic permutation gates in dimension 6 is the alternating groupA5. There exist maximum cliques of mutually compatible permutation gates whose size is 2, 3, and 4 giving rise to shared eigenstates (stabilizer and magic) defined over the cyclotomic field Q[exp⁡(2iπ/6)]. As expected for even dimensions, the negativity in the entries of the Wigner function is not the sign of the state being magic; for example, for the stabilizer state (1,-1,1,-1,1,-1), one gets (14)W1,-1,1,-1,1,-1=118000000000-122300-122000000000-122300-122.A representative magic state is (0,1,1,1,1,1) with Wigner function (15)W0,1,1,1,1,1=1304-2-23+-3-+000-1-′′+′-1+′-′′5-1-15-′′+′5+′-′′1111+′′-′1-′+′′,where in (15) the notation “±” means (3±3)/2, “±′” means ±(3+1)/2, and “±′′” means ±(3-1)/2.Another permutation group generated by two magic permutation gates is the alternating groupA6 giving rise to magic states such as (0,0,1,1,±1,±1). One gets (16)W0,0,1,1,1,1=1241-+′1+′-222-1+-′-1-′+0004+′-4-+′4112-′+2+-′2-1-1,where in (16) the notation “±” means ±(1+3)/2 and “±′” means ±(3-1)/2.


### 3.6. Magic States from 7-Dit Permutation Gates

The smallest permutation group generated by two magic permutation gates in dimension7 is isomorphic to Z7⋊Z6. A representative magic state is (0,1,1,1,1,1,1) with Wigner function (17)W0,1,1,1,1,1,1=1426-1-1-1-1-1-15bc-a-acb5c-abb-ac5-abccb-a5-abccb-a5c-abb-ac5bc-a-acb,where a=2cos⁡(2π/7), b=-2cos⁡(4π/7), and c=-2cos⁡(6π/7) are positive so that a negative sign in front of the matrix entries is a negative entry of the Wigner function.Next, another permutation group generated by two magic gates is isomorphic toPSL(2,7), of order 168. One finds three types of magic states whose entries are 0 or ±1 with Wigner functions as follows: (18)W0,0,0,0,1,1,1=12100000002a-b-c-c-ba2a-b-c-c-ba0000000111111131-b1-c1+a1+a1-c1-b1111111,W0,0,0,0,0,1,±1=11400000000000000±2±a∓b∓c∓c∓b±a0000000000000011111111111111,W0,0,0,1,1,±1,±1=1282-a-b-c-c-ba4±b-1±c-1∓1+a∓1+a±c-1±b-12-a-b-c-c-ba11111111b∓11∓c1±a1±a1∓cb∓11b∓11∓c1±a1±a1∓cb∓11111111,where 1-b>0, 1-c<0, and 1-a<0.


### 3.7. Higher Dimensions

Table2 summarizes the magic states found from permutation gates of small dimensions d≤9. For dimensions d≥5, only magic states with entries 0 or ±1 are considered. Column 3 provides the sum of negative entries in the Wigner matrix (5). It is shown in [8] that the absolute value sn(ρ) of the sum of negative entries in the discrete Wigner matrix Wρ is a computable magic monotone. It is a quantum computing resource that does not increase under stabilizer operations. Similarly the so-called mana M(ρ)=log⁡[(2sn(ρ]) is an (easily computable) additive magic monotone. According to [8, Theorem 14], a stabilizer protocol succeeds probabilistically to produce m copies of the target state σ from at least mM(σ)/M(ρ) copies of the state ρ on average.Table 2
The magic statesρ (column 2) and the sum of negative entries in the Wigner matrix Wρ (column 3). For d>3, column 4 provides the permutation group under consideration. The group G144 is isomorphic to Z32⋊(Z2⋊D4), where D4 is the eight element dihedral group.
Dim
Magic stateρ
Sum of negative entriesWρ
Remark
2
H
(
1
-
2
)
/
4
~
-
0.1035
[4]
T
Positive
[4]
3
(
0,1
,
1
)
-
1
/
3
Norrell [15]
(
0,1
,
-
1
)
-
1
/
3
Strange [15]
4
(
0,1
,
1,1
)
-
1
/
6
A
4
(
0,1
,
-
ω
,
ω
-
1
)
(2-33)/12~-0.266
5
(
0,1
,
1,1
,
1
)
-
5
/
5
~
-
0.447
Z5⋊Z4
(
0,1
,
-
1
,
-
1,1
)
-
2
/
5
(
0,0
,
0,1
,
±
1
)
-
(
5
+
1
)
/
10
~
-
0.324
S
5
(
0,0
,
1,1
,
1
)
-
(
1
+
3
5
)
/
15
~
-
0.514
6
(
0,1
,
1,1
,
1,1
)
-
(
3
3
+
7
)
/
30
~
-
0.406
A
5
(
0,0
,
1,1
,
1,1
)
-
(
3
+
1
)
/
6
~
-
0.455
A
6
(
0,0
,
1
,
-
1
,
-
1,1
)
-
(
3
+
4
)
/
12
~
-
0.478
7
(
0,1
,
1,1
,
1,1
,
1
)
-
[
1
+
4
cos
⁡
(
2
π
/
7
)
]
/
7
~
-
0.499
Z
7
⋊
Z
6
(
0,0
,
0,0
,
1,1
,
1
)
[
2
+
8
cos
⁡
(
4
π
/
7
)
+
12
cos
⁡
(
6
π
/
7
)
]
/
21
~
-
0.504
PSL(2,7)
(
0,0
,
0,0
,
0,1
,
±
1
)
2
[
cos
⁡
(
4
π
/
7
)
+
cos
⁡
(
6
π
/
7
)
]
/
7
~
-
0.321
(
0,0
,
0,1
,
1,1
,
1
)
[
1
+
4
cos
⁡
(
4
π
/
7
)
+
10
cos
⁡
(
6
π
/
7
)
]
/
14
~
-
0.636
(
0,0
,
0,1
,
1
,
-
1
,
-
1
)
[
2
+
8
cos
⁡
(
4
π
/
7
)
+
10
cos
⁡
(
6
π
/
7
)
]
/
14
~
-
0.628
8
(
0,1
,
1,1
,
1,1
,
1,1
)
-
37
/
112
~
-
0.330
Z
2
3
⋊
Z
7
9
(
0,0
,
0,0
,
0,1
,
1,1
,
1
)
-
1
/
2
Z
3
2
⋊
Z
4
(
0,1
,
1,1
,
1,1
,
1,1
,
1
)
-
5
/
9
~
-
0.555
Z
3
2
⋊
Z
8
(
0,0
,
0,0
,
1,1
,
1,1
,
1
)
-
2
/
3
G
144
(
0,0
,
0,0
,
0,0
,
0,1
,
1
)
-
1
/
3
(
0,0
,
0,1
,
-
1,1
,
-
1,1
,
-
1
)
-
19
/
27
~
-
0.704


## 3.1. Qubit Magic States

Fault tolerant quantum computing protocols based on stabilizer states have to be complemented by magic states to reach quantum universality. Two distillation protocols based on single qubit magic statesH and T are first described in [4] where (8)H=cos⁡π80+sin⁡π81,T=cos⁡β0+exp⁡iπ4sin⁡β1,cos⁡2β=13.Magic state H is the +1-eigenstate of the Hadamard matrix H=σx+σz/2 that belongs to single qubit the Clifford group. Magic state T is the ω3=exp(2iπ/3)-eigenstate of the SH matrix, where the phase gate S=100i also belongs to the Clifford group. Being not stabilizer states, they cannot be prepared by actions from the Clifford group but they can be distilled with these actions from a (dirty) mixed state to a (neat) pure state thanks to appropriate quantum codes [4, 20, 21].Matrix elements of Wootters discrete Wigner functionWρ(q,p) for a few single qubit pure states are shown in Table 1. The first three rows correspond to +1-eigenstates of Pauli spin matrices and the last two rows are for magic states. Magic state H possesses a negative entry unlike the magic state T. In the latter case, negativity of the Wigner function does not coincide with universality.Table 1
Wootters discrete Wigner function for a few pure statesρ=ψψ.
Stateψ
Eigenstate of
W
ρ
0
σ
z
1
2
1
1
0
0
1
2
(
0
+
1
)
σx
1
2
1
0
1
0
1
2
(
0
-
i
1
)
σy
1
2
0
1
1
0
H
H
=
σ
x
+
σ
z
2
1
4
1
+
2
1
1
1
-
2
T
SH
1
4
1
+
3
3
1
+
3
3
1
+
3
3
3
-
1


## 3.2. Magic States from Qutrit Permutation Gates

The smallest dimension for the occurrence of magic states associated with permutations is three. There are, up to isomorphism, two (nontrivial, i.e., with two distinct generators) two-generator permutation groups on three letters.The permutation group isomorphic toZ3 contains the permutation matrices I, X, and X2 of the Pauli group, where X is the shift matrix in (1). The eigenstates are the mutually orthogonal stabilizer states (1,1,1), (1,ω,ω2), and (1,ω2,ω), with ω being the third root of unity.The permutation group isomorphic to the symmetric groupS3 exists in three copies. One of them is generated as S3=(1,2,3),(2,3) and contains the elements found in Z3 and three extra ones 100001010≡(2,3), 001010100≡(1,3), and 010100001≡(1,2), that do not lie in Pauli group but are parts of the Clifford group. The 5 mutually orthogonal triples between the 12 eigenstates are pictured in Figure 1(a). Apart from the 6 stabilizer states, there are 6 magic states of types (0,1,1) and (0,1,-1). In [8], they are identified as the Norrell states and strange states, respectively, with Wigner function. (9)W0,1,1=162-1-1111111,W0,1,-1=16-211111111.As expected, all magic states contains some negative entries in their Wigner matrix.Figure 1
(a) Triples of mutually orthogonal rays arising from qutrit permutation gates; (b) three pentagons originating from the rays. Big black bullets are for stabilizer states; small bullets are for magic states.
(a)
(b)In Figure1(b), it is shown that three pentagons are part of the orthogonality relations. Taking the rank 1-projectors associated with the vertices/states, the exclusivity graph attached to each pentagon is also a pentagon and allows a state-dependent proof of contextuality. One observes that only magic states of the strange type are involved.


## 3.3. Magic States from Two-Qubit Permutation Gates

From now, we consider permutation groups whose two generators are magic gates. This only happens for two groups both being isomorphic to the alternating groupA4. One copy is as follows: (10)A4≅1000000101000010,0100001010000001.Looking for joined eigenstates shared by at least two commuting gates, a set of 20 states is derived whose orthogonality graph is pictured in Figure2(a).Figure 2
(a) Maximum cliques of orthogonal rays from two-qubit permutation gates: 6 4-tuples (thin lines) and 4 triples (thick lines),ω=exp⁡(iπ/3). Missing coordinates are straightforward to recover. (b) Maximum cliques of orthogonal rays from 5-dit permutation gates: 7 5-tuples (thin lines) and 5 4-tuples (thick lines). Big black bullets are for stabilizer states; small black bullets are for magic states.
(a)
(b)Wigner functions for magic states are of two types:(11)W0,1,1,1=1121-122-110020402000,W0,1,-ω,ω-1=124-1111+231-133-2313-13-231-233+233+233,with W(0,1,ω-1,-ω)=W(0,1,-ω,ω-1)t. Both types of Wigner matrices contain negative entries as for the qutrit case (in this particular case, the stabilizer states selected from permutation gates do not).It can be shown that the orthogonality graph contains 24 pentagons and thus 24 state-dependent proofs of contextuality. Surprisingly, the vertices of such pentagons either are stabilizer states or magic states of the second type, analogous to qutrit strange states.


## 3.4. Magic States from 5-Dit Permutation Gates

We again consider permutation groups whose two generators are magic gates. This happens for permutation groups isomorphic to the semidirect productZ5⋊Z4 or to the symmetric group S5, respectively.As for the first case, taking all triples of mutually commuting/compatible permutation gates, one gets a set of 30 eigenstates. They are organized into maximum cliques shown in Figure2(b) with 20 of them being magic. Missing coordinates are in the cyclotomic field Q[exp⁡(2iπ/4)].(12)W0,1,1,1,1=1204-1-1-1-13+-′-′+3-′++-′3-′++-′3+-′-′+,W0,1,-1,-1,1=1204-1-1-1-1-1-′′+′′+′′-′′-1+′′-′′-′′+′′-1+′′-′′-′′+′′-1-′′+′′+′′-′′,where the symbol “±” means ±(1+5)/2, the symbol “±′” means ±(5-1)/2, and “±′′” means (3±5)/2.As for the groupS5, one gets 50 eigenstates (shared by the 10 maximum cliques of 5 mutually compatible gates). We do not show the organization of eigenstates but only mention that one arrives at other types of magic states of the following form:(13)W0,0,0,1,±1=11000000-2±′∓∓±′000001111111111,W0,0,1,1,1=1152+′--+′2+′--+′111113-′++-′11111.As before, state-dependent contextuality may be revealed from the pentagons that are built from the states.


## 3.5. Magic States from Qubit-Qutrit Permutation Gates

The smallest permutation group generated by two magic permutation gates in dimension 6 is the alternating groupA5. There exist maximum cliques of mutually compatible permutation gates whose size is 2, 3, and 4 giving rise to shared eigenstates (stabilizer and magic) defined over the cyclotomic field Q[exp⁡(2iπ/6)]. As expected for even dimensions, the negativity in the entries of the Wigner function is not the sign of the state being magic; for example, for the stabilizer state (1,-1,1,-1,1,-1), one gets (14)W1,-1,1,-1,1,-1=118000000000-122300-122000000000-122300-122.A representative magic state is (0,1,1,1,1,1) with Wigner function (15)W0,1,1,1,1,1=1304-2-23+-3-+000-1-′′+′-1+′-′′5-1-15-′′+′5+′-′′1111+′′-′1-′+′′,where in (15) the notation “±” means (3±3)/2, “±′” means ±(3+1)/2, and “±′′” means ±(3-1)/2.Another permutation group generated by two magic permutation gates is the alternating groupA6 giving rise to magic states such as (0,0,1,1,±1,±1). One gets (16)W0,0,1,1,1,1=1241-+′1+′-222-1+-′-1-′+0004+′-4-+′4112-′+2+-′2-1-1,where in (16) the notation “±” means ±(1+3)/2 and “±′” means ±(3-1)/2.


## 3.6. Magic States from 7-Dit Permutation Gates

The smallest permutation group generated by two magic permutation gates in dimension7 is isomorphic to Z7⋊Z6. A representative magic state is (0,1,1,1,1,1,1) with Wigner function (17)W0,1,1,1,1,1,1=1426-1-1-1-1-1-15bc-a-acb5c-abb-ac5-abccb-a5-abccb-a5c-abb-ac5bc-a-acb,where a=2cos⁡(2π/7), b=-2cos⁡(4π/7), and c=-2cos⁡(6π/7) are positive so that a negative sign in front of the matrix entries is a negative entry of the Wigner function.Next, another permutation group generated by two magic gates is isomorphic toPSL(2,7), of order 168. One finds three types of magic states whose entries are 0 or ±1 with Wigner functions as follows: (18)W0,0,0,0,1,1,1=12100000002a-b-c-c-ba2a-b-c-c-ba0000000111111131-b1-c1+a1+a1-c1-b1111111,W0,0,0,0,0,1,±1=11400000000000000±2±a∓b∓c∓c∓b±a0000000000000011111111111111,W0,0,0,1,1,±1,±1=1282-a-b-c-c-ba4±b-1±c-1∓1+a∓1+a±c-1±b-12-a-b-c-c-ba11111111b∓11∓c1±a1±a1∓cb∓11b∓11∓c1±a1±a1∓cb∓11111111,where 1-b>0, 1-c<0, and 1-a<0.


## 3.7. Higher Dimensions

Table2 summarizes the magic states found from permutation gates of small dimensions d≤9. For dimensions d≥5, only magic states with entries 0 or ±1 are considered. Column 3 provides the sum of negative entries in the Wigner matrix (5). It is shown in [8] that the absolute value sn(ρ) of the sum of negative entries in the discrete Wigner matrix Wρ is a computable magic monotone. It is a quantum computing resource that does not increase under stabilizer operations. Similarly the so-called mana M(ρ)=log⁡[(2sn(ρ]) is an (easily computable) additive magic monotone. According to [8, Theorem 14], a stabilizer protocol succeeds probabilistically to produce m copies of the target state σ from at least mM(σ)/M(ρ) copies of the state ρ on average.Table 2
The magic statesρ (column 2) and the sum of negative entries in the Wigner matrix Wρ (column 3). For d>3, column 4 provides the permutation group under consideration. The group G144 is isomorphic to Z32⋊(Z2⋊D4), where D4 is the eight element dihedral group.
Dim
Magic stateρ
Sum of negative entriesWρ
Remark
2
H
(
1
-
2
)
/
4
~
-
0.1035
[4]
T
Positive
[4]
3
(
0,1
,
1
)
-
1
/
3
Norrell [15]
(
0,1
,
-
1
)
-
1
/
3
Strange [15]
4
(
0,1
,
1,1
)
-
1
/
6
A
4
(
0,1
,
-
ω
,
ω
-
1
)
(2-33)/12~-0.266
5
(
0,1
,
1,1
,
1
)
-
5
/
5
~
-
0.447
Z5⋊Z4
(
0,1
,
-
1
,
-
1,1
)
-
2
/
5
(
0,0
,
0,1
,
±
1
)
-
(
5
+
1
)
/
10
~
-
0.324
S
5
(
0,0
,
1,1
,
1
)
-
(
1
+
3
5
)
/
15
~
-
0.514
6
(
0,1
,
1,1
,
1,1
)
-
(
3
3
+
7
)
/
30
~
-
0.406
A
5
(
0,0
,
1,1
,
1,1
)
-
(
3
+
1
)
/
6
~
-
0.455
A
6
(
0,0
,
1
,
-
1
,
-
1,1
)
-
(
3
+
4
)
/
12
~
-
0.478
7
(
0,1
,
1,1
,
1,1
,
1
)
-
[
1
+
4
cos
⁡
(
2
π
/
7
)
]
/
7
~
-
0.499
Z
7
⋊
Z
6
(
0,0
,
0,0
,
1,1
,
1
)
[
2
+
8
cos
⁡
(
4
π
/
7
)
+
12
cos
⁡
(
6
π
/
7
)
]
/
21
~
-
0.504
PSL(2,7)
(
0,0
,
0,0
,
0,1
,
±
1
)
2
[
cos
⁡
(
4
π
/
7
)
+
cos
⁡
(
6
π
/
7
)
]
/
7
~
-
0.321
(
0,0
,
0,1
,
1,1
,
1
)
[
1
+
4
cos
⁡
(
4
π
/
7
)
+
10
cos
⁡
(
6
π
/
7
)
]
/
14
~
-
0.636
(
0,0
,
0,1
,
1
,
-
1
,
-
1
)
[
2
+
8
cos
⁡
(
4
π
/
7
)
+
10
cos
⁡
(
6
π
/
7
)
]
/
14
~
-
0.628
8
(
0,1
,
1,1
,
1,1
,
1,1
)
-
37
/
112
~
-
0.330
Z
2
3
⋊
Z
7
9
(
0,0
,
0,0
,
0,1
,
1,1
,
1
)
-
1
/
2
Z
3
2
⋊
Z
4
(
0,1
,
1,1
,
1,1
,
1,1
,
1
)
-
5
/
9
~
-
0.555
Z
3
2
⋊
Z
8
(
0,0
,
0,0
,
1,1
,
1,1
,
1
)
-
2
/
3
G
144
(
0,0
,
0,0
,
0,0
,
0,1
,
1
)
-
1
/
3
(
0,0
,
0,1
,
-
1,1
,
-
1,1
,
-
1
)
-
19
/
27
~
-
0.704


## 4. Conclusion

We described the leading role played by permutations in shaping a type of universal quantum computation based on magic states, states living outside the stabilizer polytope defined by the (generalized) Pauli group. In Section3, we derived the main magic states ρ defined from eigenstates of gates in magic permutation groups (a subset of Clifford group) of small dimensions d≤9. We explicitly computed the sum negativity of the discrete Wigner matrix Wρ for estimating the value of a magic state as a resource for universal quantum computation [15]. We observed that state-dependent quantum contextuality (through building block pentagons) occurs in all dimensions d≥3 from appropriate sets of stabilizer and magic states. It is desirable to extend the calculations to higher dimensions d>9 to check a possible asymptotic trend between the dimension and the amount of magic and contextuality, to clarify the relation between magic permutation groups and unitary 2-designs (singled out in [12]) and finally to relate the derived magic states to distillation procedures and error correcting codes. A later paper will be devoted to the POVMs obtained from the Pauli group action on the magic states [29].



---

*Source: 5287862-2017-08-15.xml*