Cli ord group - LU

1 clifford groupMaris OzolsJuly 31, 2008 AbstractThis is a survey on the clifford group onnqubits. I will discuss its properties andapplications in quantum Pauli matricesThePauli matriceson a single qubit areI=(1 00 1),X=(0 11 0),Y=(0 ii0),Z=(1 00 1). Onnqubits the set of Pauli matrices isPn={ 1 n| i {I,X,Y,Z}},|Pn|= 4n. ThegroupPn/U(1) is isomorphic to a vector space overF2with dimension 2nvia identification:ZY| |IX (0,1)(1,1)| |(0,0)(1,0)(1)where the multiplication of matrices corresponds to the addition of clifford DefinitionTo define the clifford group , we do not have to turn the Pauli matrices into a group .

2 Weneed just non-identity Pauli matricesP n=Pn\{I n}(their eigenvalues are 1 with equalmultiplicity). We can ignore the global phase, sinceUandei Uact in the same groupCnonnqubits isCn={U U(2n)| P n U U P n}/U(1).(2) Single qubit caseWe have P 1={ X, Y, Z}. Conjugation must preserve the structure ofP 1, thus theaction ofU C1is completely determined by the images ofXandZ. Moreover,UXU andUZU must anti-commute. ThusXcan go to any element of P 1, butZcan only go to P 1\{ UXU }. Hence|C1|= 6 4 = can think ofC1as rotations of the Bloch sphere that permute x, y, and zdirections. There are 6 possibilities where thexaxis can go.

3 Once we have fixed thexaxis,we can still rotate around it and thus there are 4 possibilities where thezaxis can to the group of rotational symmetries of the Number of elementsTo fix an elementU Cn, it is enough to specify how it transformsXiandZifor alli {1,..,n}, since they form a basis of the vector space (1). AllX s andZ s commute,exceptXiandZithat anti-commute (elements that anti-commute are joined by edges):X1X2..Xn 1Xn| || |Z1Z2..Zn 1Zn(3)Conjugation byUcertainly must preserve this structure. Moreover, it can be shown thatthere are no other restrictions, , each mapping that sends (3) to distinct elements of P nand preserves their structure, determines a uniqueU Cn.

4 Let us find all such are the possible images of the last pair (Xn,Zn)?Xncan go to any element of P n, butZncan only go to elements of P nthat anti-commute withUXnU . Thus thereare| P n|= 2(4n 1) choices forXn. Observe that each matrix in P nanti-commutes withexactly half1of Pauli matricesPn(this half is clearly inP n). Thus, there are 2|Pn|/2 = 4nchoices forZn. The elements ofCnthat leave bothXnandZnfixed form a group isomorphictoCn 1with the number of cosets equal to 2(4n 1)4n. Hence|Cn|= 2(4n 1)4n|Cn 1|.Therefore,|Cn|=n j=12(4j 1)4j= 2n2+2nn j=1(4j 1).(4)The first few values of|Cn|are given in Table 1. Equation (4) does not agree with [1], since in[1] it is assumed thatH,P Cn, ,Cnis implicitly defined as the group generated byH,P,andCNOT(see the next section) without ignoring the global phase.

5 Since (PH)3=e2 i8I,this way each clifford group operation is obtained 8 times with different global |Cn|241152092897280121286688768002541082 2678459187200 Table 1: The order the clifford groupCnonnqubits (18 Sloane s A003956 ). Hi,Pi,CNOTij /U(1), whereH=1 2(1 11 1), P=(1 00i), CNOT=(1 0 0 00 1 0 00 0 0 10 0 1 0).(5)1 Let P n. Letkbe a position where does not contain identityI. Then all Pauli matrices thatanti-commute with can be constructed as follows: put any ofI,X,Y,Zat each position other thank;then fill thekth position in any of two possible ways so that the obtained matrix anti-commutes with .2 See [2, p.]

6 13] or [3, Section ] for the proof. Note that forn= 1 we need onlyHandP. It can be easily verified that they generate the rotational symmetry group of a we have to use induction onn. The main idea is to show that any clifford operationonn+ 1 qubits can be implemented using only those on at Gottesman - Knill theoremQuantum circuits that involve only clifford group operations are not universal for quantumcomputing. In fact, one can efficiently simulate such circuits on a classical quantum computation involving only: state preparation in the computational basis, clifford group operations, measurements in the standard basis, any classical control conditioned on the measurement outcomescan be perfectly simulated in polynomial time on a probabilistic classical main idea is to use thestabilizer formalismto see how the stabilizer of the quantumstate evolves instead of following the evolution of the state directly [4].

7 Aaronson andGottesman have written a program in C calledCHPthat can simulate such circuits [5]. Itcan easily handle up to 3000 qubits! Universal set of quantum gatesAssume we can implement all operations inCn( , it means that we can permute qubitsin arbitrary way). If we could implement any other fixed gate, that is not (a multiple of agate) inCn, we could apply it on any ordered tuple of qubits. It turns out that this wouldallow us to perform any quantum computation (Theorem in [6]) with any other gate not inCnform a universal set of quantum , there is noelementaryproof available for this theorem.

8 However, forn= 1 it is not that hard to prove it. Recall the geometrical meaning ofC1discussed inSect. it is the rotational symmetry group of a cube. A classical result says that allfinite groups of rotations inR3that do not have an invariant 2-dimensional subspace arerotational symmetry groups of Platonic solids. Since there is no other Platonic solid, whoserotational symmetry group properly contains that of a cube, the group obtained by addingany gate toC1must be infinite. Moreover, it can be shown that it is dense inO(3) [7].3 References[1] Calderbank , Rains , Shor , Sloane , Quantum Error CorrectionVia Codes Over GF(4),arXiv:quant-ph/9608006v5.

9 [2] Gottesman D., A Theory of fault-tolerant quantum computation,arXiv:quant-ph/9702029v2.[3] Gottesman D., Stabilizer Codes and Quantum Error Correction, PhD thesis,arXiv:quant-ph/9705052v1.[4] Gottesman D., The Heisenberg Representation of Quantum Computers,arXiv:quant-ph/9807006v1.[5] Aaronson S., Gottesman D., Improved Simulation of Stabilizer Circuits,arXiv:quant-ph/0406196v5.[6] Nebe G., Rains , Sloane , The Invariants of the clifford Groups,arXiv:math/0001038v2.[7] Ozols M., Mancinska L., Childs A., Leung D., Universal Pairs of Rotations,available