@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Physics and Astronomy, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Allard Guérin, Philippe"@en ; dcterms:issued "2015-08-24T17:01:23Z"@en, "2015"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description "We study the resources necessary for quantum computation with rebits (qubit states with real amplitudes in the standard basis). We introduce a scheme for universal quantum computation by state injection, and define a Wigner function appropriate for this scheme. We show that the Wigner function obeys a Hudson’s theorem and transforms covariantly under CSS-ness preserving unitary gates; these results allows us to establish that Wigner function negativity is necessary for quantum computation. Furthermore, we establish contextuality as another necessary computational resource. We show that in contrast with the case of qudits [M. Howard et al., Nature 510, 351 (2014)], negativity does not imply contextuality. We discuss state independent contextuality and why it does not arise in our computational scheme."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/54594?expand=metadata"@en ; skos:note "Wigner Function Negativity and Contextuality inQuantum Computation with RebitsbyPhilippe Allard Gue´rinB. Sc. Physics, Universite´ de Montre´al, 2013a thesis submitted in partial fulfillmentof the requirements for the degree ofMaster of Scienceinthe faculty of graduate and postdoctoralstudies(Physics)The University of British Columbia(Vancouver)August 2015c© Philippe Allard Gue´rin, 2015AbstractWe study the resources necessary for quantum computation with rebits(qubit states with real amplitudes in the standard basis). We introducea scheme for universal quantum computation by state injection, and definea Wigner function appropriate for this scheme. We show that the Wignerfunction obeys a Hudson’s theorem and transforms covariantly under CSS-ness preserving unitary gates; these results allows us to establish that Wignerfunction negativity is necessary for quantum computation. Furthermore, weestablish contextuality as another necessary computational resource. Weshow that in contrast with the case of qudits [M. Howard et al., Nature510, 351 (2014)], negativity does not imply contextuality. We discuss stateindependent contextuality and why it does not arise in our computationalscheme.iiPrefaceThe material presented in Chapters 2, 3 and 4 has been published as [Nico-las Delfosse, Philippe Allard Guerin, Jacob Bian, and Robert Raussendorfas Wigner Function Negativity and Contextuality in Quantum Computationon Rebits. Phys. Rev. X 5, 021003 – 2015]. My contributions to this workinclude Chapter 2, and discussions with Robert Raussendorf on the contentsof Chapter 4, which he wrote. Chapter 3 was principally the work of NicolasDelfosse, with contributions from Jacob Bian. In both previously mentionedchapters, I have slightly modified or expanded some of the proofs from theiroriginal shape in the paper. Chapter 1 is a review of the preexisting lit-erature, and it is original work that I realized for this thesis. Figures 1.3,4.1, 4.2, 4.3, as well as the circuit diagrams of Chapter 2 are taken from thepublished paper, and were produced by Robert Raussendorf. The remainingfigures were created by me for this thesis. I was closely involved in rereadingand giving feedback during the writing of the paper, as well as during thereview process.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Quantum computation in phase space . . . . . . . . . . . . . 31.1.1 Stabilizer formalism . . . . . . . . . . . . . . . . . . . 31.1.2 Phase space . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Wigner functions . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.1 The Wigner function for continuous variables . . . . . 81.2.2 The qudit Wigner function . . . . . . . . . . . . . . . 151.2.3 The qubit Wigner function . . . . . . . . . . . . . . . 191.2.4 Some properties of general Wigner functions . . . . . 231.3 Magic states and computation by state injection . . . . . . . 241.4 Hidden variable models and contextuality . . . . . . . . . . . 251.4.1 Hidden variables . . . . . . . . . . . . . . . . . . . . . 261.4.2 Algebraic constraints on the value assignments . . . . 281.4.3 Contextuality proofs . . . . . . . . . . . . . . . . . . . 291.4.4 Contextuality of subtheories of quantum mechanics . . 32iv2 Universal quantum computation by state injection withrebits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.1 Rebits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.2 Universal quantum computation . . . . . . . . . . . . . . . . 352.3 Magic state distillation . . . . . . . . . . . . . . . . . . . . . . 422.3.1 Bell states . . . . . . . . . . . . . . . . . . . . . . . . . 422.3.2 The state |B〉 . . . . . . . . . . . . . . . . . . . . . . . 453 The rebit Wigner function . . . . . . . . . . . . . . . . . . . 503.1 Definition and elementary properties . . . . . . . . . . . . . . 503.2 Hudson’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 553.2.1 Bochner’s theorem . . . . . . . . . . . . . . . . . . . . 563.2.2 Modulus and support . . . . . . . . . . . . . . . . . . 593.3 Covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.4 Efficient classical simulation of CSS-Clifford circuits . . . . . 654 Contextuality for rebits . . . . . . . . . . . . . . . . . . . . . 704.1 Hidden-variable models of rebit QCSI . . . . . . . . . . . . . 704.2 Conditions for contextuality . . . . . . . . . . . . . . . . . . . 754.2.1 A necessary condition for contextuality . . . . . . . . 754.2.2 A sufficient condition for contextuality . . . . . . . . . 774.2.3 Example: Mermin star . . . . . . . . . . . . . . . . . . 814.3 Contextuality and negativity . . . . . . . . . . . . . . . . . . 824.3.1 Negativity and contextuality are not equivalent . . . . 824.3.2 States for which negativity and contextuality coincide 834.4 Contextuality and negativity as resources for quantum com-putation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.5 Mermin square revisited . . . . . . . . . . . . . . . . . . . . . 875 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92vA Characters and Fourier transforms . . . . . . . . . . . . . . 96A.1 Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96A.2 Symplectic spaces, definitions . . . . . . . . . . . . . . . . . . 97viList of FiguresFigure 1.1 Wigner function of a coherent state |1 + 2i〉 in arbitraryunits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Figure 1.2 Wigner function of the Fock state |1〉. Units have beenchosen such that ~ = 1, and mω = 1. . . . . . . . . . . . 14Figure 1.3 Circuit for a state-injection that yields Λ(θ) |ψ〉 or Λ(−θ) |ψ〉with equal probabilities . . . . . . . . . . . . . . . . . . . 25Figure 1.4 The Mermin square.It is impossible to have a consistentvalue assignment for the observables of the square . . . . 29Figure 1.5 Observables for which it is impossible to have a consistentvalue assignment . . . . . . . . . . . . . . . . . . . . . . . 30Figure 3.1 Example of a circuit whose distribution of outcomes canbe sampled by our efficient classical algorithm. The gatesgi and the measurements Ti are CSS-ness preserving uni-taries belonging to O . . . . . . . . . . . . . . . . . . . . . 65Figure 4.1 Wigner function for the three-rebit GHZ-like state ρ =18(I−X1Z2Z3)(I−Z1X2Z3)(I−Z1Z2X3), which appearsin the state-dependent version of the Mermin star proof . 81viiFigure 4.2 Phase diagram for the space of one-rebit states ρ˜. Thedark blue area corresponds to states with positive Wignerfunction, which are non-contextual by virtue of Theorem4.5. The pale blue region shows the physical states thathave negative Wigner function. The states that are iden-tified as contextual by Theorem 4.8 fall outside the palegrey square. . . . . . . . . . . . . . . . . . . . . . . . . . . 83Figure 4.3 Phase diagram for the two-rebit states ρ(a, b) defined byequation 4.47. All states in the square are physical, andstates in the dark blue area are non-contextual. . . . . . . 84Figure 4.4 Reminder of the observables that appear in the ”Merminsquare” state-independent contextuality proof. . . . . . . 88viiiAcknowledgmentsI wish to thank my Master’s research supervisor Dr. Robert Raussendorffor his guidance and for allowing me to explore other interesting areas ofquantum information than those presented in this thesis. In particular, Iam grateful for having the opportunity to go to Paris for three months to doresearch on topological quantum computation, for which there was unfortu-nately no room in this thesis. I thank Dr. Re´my Mosseri of the Universite´Pierre et Marie Curie for his enthusiastic supervision when I was workingwith him in Paris.I acknowledge my collaborators Jacob Bian and Nicolas Delfosse, with-out whom the work presented in this thesis could not have come to fruition.I am eternally grateful to my parents Luc Gue´rin and Sylvie Allardfor supporting me throughout my life and for encouraging my passion forlearning. Finally, I wish to express gratitude to all my friends at UBC andelsewhere, for the pleasant discussions and debates that have enriched myexperience as a graduate student.ixChapter 1IntroductionQuantum computation is a field of research whose broad aim is to use thequantum properties of matter in order to acheive greater computationalpower than what is available classically. Many quantum algorithms, Shor’s[23] and Grover’s [15] being famous examples, have been devised, and thesealgorithms offer considerable speedup over their classical competitors. Weshall give the designation universal quantum computer to any machine thatcan apply any unitary operation (with arbitrary precision) to the state ofa quantum system [20]. Such theoretical machines are able to run Shor’sand Grover’s algorithms, and are thus believed to be faster than classicalcomputers. However, the reason for this faster speed is not very well under-stood.Superposition and entanglement are well known non-classical features ofquantum mechanics. However, this work will study the role of a lesser knownquantum property called contextuality, and will establish it as a necessaryresource for quantum computation. Contextuality arises in the study ofhidden variable models (HVM’s) of quantum mechanics, the attempt toassign preestablished values to the observables of a quantum system, whichare merely revealed by measurement. Bell [4] famously proved that there canbe no HVM that reproduces quantum mechanics while obeying the localitypostulate of special relativity. But there is a broader class of HVM’s thatcannot reproduce quantum mechanics: non-contextual HVM’s [18]. These1are HVM’s for which the values assigned to an observable do not depend onwhich other observables are simultaneously measured with it.In the study of quantum computation, there are many equivalent schemesthat allow universality. The paradigmatic example is the circuit model [20],but there is also measurement based quantum computation [21], and quan-tum computation by state injection (QCSI) [7]; we shall focus on the latterin this thesis. For systems with local odd prime dimension (qudits), it hasbeen discovered [16] that for the computational scheme of QCSI, contextu-ality is necessary for universal quantum computation. One of the goals ofthis thesis is to try to establish similar results for two-level systems. Wewill be lead to study systems of rebits, two-level systems with real densitymatrices in the standard basis.The result according to which contextuality is a resource for quantumcomputation draws heavily for it’s proof on a construction known as theWigner function [29]. These functions are meant to be quantum analogsof the phase space distributions that arise in classical mechanics. However,quantum mechanics is such that these distributions can sometimes take neg-ative values, which gives them the name quasi-probability distributions. Forqudits, it has been shown [27], that negativity of the Wigner function is nec-essary for universal quantum computation. Furthermore, contextuality andnegativity are equivalent for qudits [16]. In this thesis, we will define aWigner function for rebits, and study the link between contextuality, nega-tivity, and computation.In the following sections of this chapter, we will set the stage by math-ematically defining our main subjects of study: Wigner functions and con-textuality. We will give an introduction to the phase space formulationof quantum computation for continuous variables, qudits and qubits. Wealso discuss the scheme of quantum computation by state injection, whichwill be the scheme of computation studied in this thesis and especially inChapter 2. We will then give an introduction to contextuality and hid-den variable models of quantum mechanics. This introduction also presentswhat is known about the link between negativity of the Wigner function,contextuality, and quantum computation in the case of qudits. Chapter 22introduces rebits and presents the scheme that allows us universal quan-tum computation with rebits. Chapter 3 defines and characterizes the rebitWigner function, and establishes negativity of the Wigner function as a re-source for quantum computation. Chapter 4 studies contextuality of rebitquantum computation, and uses the Wigner function to find criteria for con-textuality. We finish this thesis with a conclusion in Chapter 5. There isalso an Appendix that compiles some mathematical results and definitionsabout characters and symplectic vector spaces.1.1 Quantum computation in phase spaceIn this section we study the phase space formulation for systems of qubits.We start by reviewing some definitions from the stabilizer formalism. Wethen define a Wigner function, and try to justify why we will focus on rebitsfor the rest of this thesis.1.1.1 Stabilizer formalismThe stabilizer formalism [13] is an indispensable tool in the field of quantumerror correction [20], and we give a brief introduction to the formalism herein.We start by defining the n-qubit Pauli group . Let uX ,uZ ∈ Zn2 and defineZ(u) = Zu11 ⊗Zu22 ⊗· · ·⊗Zunn , where Zi is the spin Z operator acting on qubiti, and define X(u) in an analogous way. Then the n-qubit Pauli group is thegroup generated by the local gates 〈X,Y, Z〉 for each qubit of the system.Pn = {(i)kZ(uZ)X(uX)|(uX ,uZ) ∈ Zn2 × Zn2 , k ∈ {0, 1, 2, 3}} (1.1)It will be useful to make a distinction between the n-qubit Pauli groupPn and the n-qubit Pauli operators, which we define asTn = {T(aZ ,aX) = Z(aZ)X(aX)|(uX ,uZ) ∈ Zn2 × Zn2} (1.2)Notice the absence of the factor i in this definition. In the case of a singlequbit it means that T(1,1) = ZX 6= Y , and that T(1,1) is not hermitian. Theset Tn is not a group because it is not closed under multiplication. To obtain3a group from it, we must at least include phases {±1}. The properties ofthe Pauli operators can be obtained from the well known properties of thesingle qubit Pauli matrices. For instance, all T ∈ Tn are traceless, exceptT0 = I, which has trace 2n. Also, a pair of Pauli operators either commutesor anticommutes, andTuTv = (−1)[u,v]TvTu, (1.3)where [·, ·] : Zn2 × Zn2 → Z2 is the symplectic inner product, defined as[u,v] = (uX ,vZ) + (uZ ,vX), (1.4)with (·, ·) being the usual inner product over Zn2 .The Pauli operators Tn form an orthonormal basis for the 2n dimensionalcomplex vector space of n by n square matrices, in which the inner productis defined as(A,B) =12nTr(A†B) (1.5)Indeed, it can be easily checked that with this definition,(Ta, Tb) = δa,b ∀Ta, Tb ∈ Tn (1.6)The n-qubit Clifford group Cn is defined as the subgroup of the unitarygroup that maps the Pauli group to itself under conjugation; in technicalterms, it is the normalizer of the Pauli group.Cn = {g ∈ U(n)|gPng† = Pn} (1.7)Furthermore, it is known [13] that the Clifford group is generated bythe single qubit Pauli operators, single qubit Hadarmard gates, and thetwo-qubit CNOT gates.Cn = 〈Xi, Zi, Hi, CNOT (i, j)〉 (1.8)Of course, since a global phase does not change the physical state of thesystem, all the gates in Cn may be multiplied by a complex number ofmodulus one.4We say that a state |ψ〉 is stabilized by a Pauli operator g ∈ Pn if |ψ〉 isan eigenvector of g with eigenvalue one:g |ψ〉 = + |ψ〉 (1.9)A n-qubit state that is stabilized by n independent Pauli operators (inthe sense that none of these operators can be obtained by multiplying some ofthe other n−1 operators) is called a stabilizer state. Knowing the stabilizerof a state specifies it completely, up to a phase. The group generated bythese n independent Pauli operators is called the stabilizer group of |ψ〉 andthe notation we use isS(|ψ〉) = {g ∈ Pn| g |ψ〉 = |ψ〉} (1.10)The Gottesman-Knill Theorem [13] states that the action of Cliffordunitaries on stabilizer states is efficiently classically simulable. Briefly put,the reason is because we can efficiently track the evolution of the stabilizerof the state after every Clifford unitary that appears in the computation.An important subset of stabilizer states are the Calderbank-Shor-Steane(CSS) states [8]. These are stabilizer states with the property that theirstabilizer group can be decomposed in a purely Z part and a purely X part:S(|ψ〉) = SX(|ψ〉)×SZ(|ψ〉). We also define the group of CSS-ness preservingtransformations as the subgroup of the Clifford group that preserves the setΣ of CSS states.GCSS = {g ∈ Cn| g |ψ〉 ∈ Σ ,∀ |ψ〉 ∈ Σ} (1.11)We conclude this section with a lemma characterizing GCSS that will beuseful in future chapters.Lemma 1.1. The n-rebit CSS-ness preserving group GCSS isGCSS = 〈n⊗i=1Hi, CNOT (i, j), Xi, Zi〉 (1.12)5Proof. We sketch a simple proof of this fact and refer the reader to [10]for the completely rigorous proof. Starting with the fact that GCSS is asubgroup of the Clifford group Cn, we will look at the generators of Cn andeliminate the ones that do not preserve CSS-ness, while keeping the others.Clearly, Xi and Zi preserve CSS-ness, because if S(ψ) is initially a CSSstabilzer, then XiS(ψ)Xi, will contain the same Pauli operators, with pos-sibly different signs depending on their commutation relation with Xi. Thesame thing is true for Zi.The CNOT (i, j) gate, with qubit i as control qubit, is also inGCSS , as wenow show. Without loss of generality, we consider the effect of CNOT (1, 2)on single-qubit Pauli operators.CNOT (1, 2)X1CNOT (1, 2) = X1X2CNOT (1, 2)X2CNOT (1, 2) = X2CNOT (1, 2)Z1CNOT (1, 2) = Z1CNOT (1, 2)Z2CNOT (1, 2) = Z1Z2CNOT (1, 2)XiCNOT (1, 2) = Xi if i > 2CNOT (1, 2)ZiCNOT (1, 2) = Zi if i > 2This means that conjugating a Pauli operator with CNOT does not mixX-type and Z-type operators, so we see that if we start from a CSS state,S = SX ×SZ , we end up with another CSS state after applying the CNOT.Therefore, all the CNOT gates are in GCSSThe single-qubit Hadamard is not CSS-ness preserving. Indeed, if |ψ〉 isa n-qubit CSS state with stabilizer S(|ψ〉) = 〈X1X2, Z1Z2, X3, X4, . . . , Xn〉,then acting on this state with H1 yields a new stabilizer S ′ = 〈Z1X2, X1Z2,X3, X4, . . . , Xn〉, which is not CSS. It is still possible that a subgroup of〈Hi〉 ≤ Cn is CSS-ness preserving. All such subgroups are of order 2 andconsist of multiple Hadamards acting on different qubits. It is not too hardto see that we can always construct a counterexample in a similar way asbefore, except for the subgroup that is generated by ⊗ni=1Hi. Indeed, ⊗ni=1Hitransforms all X-operators into Z-operators, and vice-versa, so it preserves6CSS-ness.1.1.2 Phase spaceThe vectorial notation we used in Section 1.1.1 suggests that there is auseful relation between the Pauli operators and a binary vector space withsymplectic structure. We define the phase space V asV = {(aZ ,aX)|aZ ,aX ∈ Zn2} ∼= Z2n2 (1.13)We can now define a mapping pi from the phase space to the Paulioperators:pi : V → T (1.14)(aZ ,aX) 7→ T(aZ ,aX) (1.15)For u,v ∈ V , we have two useful related relationsTu+v = (−1)(uX ,vZ)TuTv (1.16)TuTv = (−1)[u,v]TvTu, (1.17)where [u,v] = (uX ,vZ) + (uZ ,vX) is the symplectic product that gives asymplectic structure to V .Equation 1.16 tells us that the Pauli group is a projective representationof V . This is because that the mapping pi : V → T defined in Equation1.14 is a homomorphism of groups, up to a sign. If we consider insteadequivalence classes of T under multiplication by phases, the map inducedby pi is an isomorphism. This map is a first step towards using V as a phasespace over which we will define the discrete Wigner function.1.2 Wigner functionsIn this section, we discuss Wigner functions, which allow the phase spaceformulation of quantum mechanics. We begin by surveying the field of7continuous variables Wigner functions, and then use this insight as a guidefor understanding the discrete Wigner function of qudits and qubits.1.2.1 The Wigner function for continuous variablesWigner functions are a major tool of quantum optics and were introducedin 1932 by Wigner [29] as quantum analogues of the phase space distribu-tions that occur in classical mechanics. We will put things in place by firstdiscussing the case of the continuous variable Wigner function for a spinlessparticle. The phase space is the set of pointsV = {(x, p) ∈ R× R}. (1.18)In classical mechanics, the state of a point particle is fully specified by apoint (or Dirac delta distribution) in phase space. However, in the quantumcase, the uncertainty principle manifests itself through the impossibility ofhaving precisely defined position and momentum simultaneously. Therefore,the density matrix of a system is represented as a distribution in the phasespace. Furthermore, it turns out that for some states this distribution maytake negative values at some point; this feature is called negativity and isassociated with non-classical behavior, as we will soon see.We start by defining the Wigner-Weyl transform [28], which puts a cor-respondence between operators on a Hilbert space and functions on phasespace. The Wigner transformation takes an operator A acting on the Hilbertspace to a function on the phase space V . It is defined asA˜(x, p) =∫ ∞−∞eipy/~ 〈x−y2|A|x+y2〉 dy. (1.19)8This transformation is invertible:〈x|A|x′〉 =∫dy δ(x− x′ + y) 〈x+ x′ − y2|A|x+ x′ + y2〉=12pi~∫∫dy dp eip(x−x′+y)/~ 〈x+ x′ − y2|A|x+ x′ + y2〉=1h∫ ∞−∞eip(x−x′)/~A˜(x+ x′2, p)dp , (1.20)and the inverse transformation is known as the Weyl transform.The Wigner function for a state ρ is defined as the normalized Wignertransform of ρWρ(x, p) =1pi~∫ ∞−∞〈x+ y|ρ|x− y〉 e−2ipy/~dy (1.21)For a pure state ρ = |ψ〉 〈ψ|, the previous formula takes the formWψ(x, p) =1pi~∫ψ∗(x+ y)ψ(x− y)e−2ipy/~dy, (1.22)where ψ(x) = 〈x|ψ〉.For the purpose of future comparison with the discrete case, we introducedisplacement operators T (u, v) with (u, v) ∈ R2T (u, v) = ei(vXˆ−uPˆ )/~ = e−iuv2~ eivXˆ/~e−iuPˆ /~ = eiuv2~ e−iuPˆ /~eivXˆ/~, (1.23)where Xˆ, Pˆ are the position and momentum operators, and the above in-equalities were obtained by use of the Baker-Campbell-Hausdorff formula,which states that for two operators A,B such that [[A,B], A] = [[A,B], B] =0, theneA+B = e−[A,B]/2eAeB = e[A,B]/2eBeA. (1.24)The operators T (u, v) earn their name because of their action on position9eigenstates:T (u, v) |x〉 = eiuv/(2~)e−iuPˆ /~eivXˆ/~ |x〉 (1.25)= eiuv/(2~)eivx/~e−iuPˆ /~ |x〉 (1.26)= eiv(u/2+x)/~ |x+ u〉 (1.27)Furthermore, we can check that the displacement obey the followingcomposition lawT (u, v)T (y, z) = exp(−i~2(uv + yz))eivXˆe−iuPˆ eizXˆe−iyPˆ= exp(−i2~(uv + yz + 2uz))eivXˆ/~eizXˆ/~e−iuPˆ /~e−iyPˆ /~= exp(i2~(vy − uz))T (u+ y, v + z)= exp(−i2~[(u, v), (y, z)])T (u+ y, v + z), (1.28)where [·, ·] is the symplectic product over R2. In the discrete case, we willfind analogues of the displacement operators, and we will see that theircomposition reveals a similar symplectic structure.It is possible to express the Wigner function in a more concise form bydefining defining point operators A(x, p) asA(0, 0) =12pi~∫∫du dv T (u, v) (1.29)10andA(x, p) = T (x, p)A(0, 0)T (x, p)† (1.30)=12pi~∫∫du dv T (x, p)T (u, v)T (−x,−p)=12pi~∫∫du dv exp(i2~(pu− xv))T (u+ x, v + p)T (−x,−p)=12pi~∫∫du dv exp(i2~[(pu− xv) + (v + p)(−x)− (u+ x)(−p)])T (u, v)=12pi~∫∫du dv exp(i~(pu− xv))T (u, v). (1.31)Then,12pi~Tr(A(x, p)ρ) =12pi~∫dy 〈y| ρA(x, p) |y〉=1(2pi~)2∫∫∫du dv dy ei(pu−vx)/~ 〈y| ρT (u, v) |y〉=1(2pi~)2∫∫∫du dv dy eipu/~eiv(y−x+u/2)/~ 〈y| ρ |y + u〉=12pi~∫∫du dy eiup/~δ(y − x+ u/2) 〈y| ρ |y + u〉=12pi~∫du eiup/~ 〈x− u/2| ρ |x+ u/2〉=1pi~∫dy e−2iyp/~ 〈x+ y| ρ |x− y〉 .Thus we see thatWρ(x, p) =12pi~Tr (A(x, p)ρ) . (1.32)This is the form of the Wigner function that we will try to reproduce in thediscrete finite dimensional setting.We now present some elementary properties of the continous Wignerfunction, and refer the interested reader to the review [9] for the proofs.1. Wρ is real112. The Wigner function sums to one:∫∫dx dpWρ(x, p) = Tr(ρ) = 1 (1.33)3. The probability distributions for x and p are given by the marginalsof the Wigner function:〈x|ρ|x〉 =∫dpWρ(x, p) (1.34)〈p|ρ|p〉 =∫dxWρ(x, p) (1.35)4. If an observable B = B(Xˆ) is purely a function of the position operatorXˆ, then〈A〉 =∫∫dx dpW (x, p)A(x), (1.36)and similarly for observables that are pure functions of Pˆ .To better understand the properties of the Wigner function, we lookat some important examples of quantum optics: coherent states and Fockstates.Coherent states [30] are eigenstates of the annihilation operatora =√mω2~(xˆ+imωpˆ). (1.37)These states minimize the uncertainty principle, and are often thought asthe states whose dynamic is the most similar to that of a classical harmonicoscillator. They are labeled by the complex number α such thata |α〉 = α |α〉 . (1.38)12Figure 1.1: Wigner function of a coherent state |1 + 2i〉 in arbitraryunits.The wave function of a coherent state |α〉 isψ(α)(x) =(mωpi~)1/4e−mω2~(x−√2~mω<[α])2+i√2mω~ =[α]x. (1.39)With this, we can directly use Equation 1.22 to calculate the Wigner functionof a coherent state. Figure 1.1 shows the Wigner function of coherent state,using natural units such that mω = 1. The Wigner function of a coherentstate is a Gaussian centered in (x, p) = (<[α],=[α]). Note that the Wignerfunction of a coherent state is non-negative over all the phase space. Thisproperty allows us to identify these states as classical states, because theWigner function can be interpreted as a classical probability distribution.Another important class of states in quantum optics is the Fock states.These states are eigenstates of the number operator N = a†a. Figure 1.2shows the Wigner function of the state |1〉. Notice that the Wigner functionfor this state takes negative values, with maximal negativity occurring atthe origin.A positive Wigner function can be interpreted as a probability distribu-tion, an thus as a hidden variable model (more about this in section 1.4). It13Figure 1.2: Wigner function of the Fock state |1〉. Units have beenchosen such that ~ = 1, and mω = 1.is therefore common to interpret negativity of the Wigner function as a non-classical feature. This agrees with the previous observation that Fock stateshave negativity in their Wigner function, and with the typical interpretationof these states as particle-like, a distinctively quantum feature.However, we must be careful when identifying non-negativity of theWigner function with classicality. It has been shown [2], that the EPRstate [11] has non-negative Wigner function, but it can nonetheless be usedto violate a Bell inequality.The previous discussion shows that some pure states have non-negativeWigner functions, while others can take negative values at some points inthe phase space. The complete set of pure states with non-negative Wignerfunction is identified by Hudson’s theorem [17] and it’s multi-particle gen-eralization by Soto and Claverie [24].Theorem 1.2. (Hudson’s Theorem) The Wigner function of a pure stateψ ∈ L2(Rn) is non-negative if and only if ψ is Gaussian, that is, if its wavefunction has the formψ(x) ∝ e2pii(xθx+ωx), (1.40)where x, ω ∈ Rn and θ is a complex symmetric matrix.A positive Wigner function can also be interpreted as classical in thesense of computation. Indeed, there exists [3] an equivalent of the Gottesman-Knill theorem for continuous variables. Any computing machine acting on14an initial unentangled Gaussian state (whose Wigner function is positive byHudson’s theorem) with gates generated by Hamiltonians that are quadraticin the canonical operators Xˆ and Pˆ (these gates send Gaussian states toGaussian states), and where the allowable measurements are canonical op-erators can be efficiently classically simulated.The question of whether there exists equivalent theorems in the case ofdiscrete phase spaces is the starting point for what follows.1.2.2 The qudit Wigner functionIn this chapter, we survey the previously known results for the case of qu-dits: d-level systems, where d is an odd prime. We give the statement of thediscrete Hudson’s theorem, and detail the link between universality, contex-tuality and Wigner function negativity. These results are valid for virtuallyall discrete quantum systems, except the most paradigmatic one in quantumcomputation, systems of qubits. The remaining chapters of this thesis arelargely motivated by what is know for qudits, and we shall make frequentreference to the results presented here.For the remaining of this section, we will assume that d is an odd primenumber. The definition of the Wigner function we present here is that ofGross [14], with a somewhat adapted notation. For systems of dimension d,the standard basis vectors are {|0〉 , |1〉 , . . . , |d− 1〉}. Here {0, . . . , d−1} areelements of the field Zd, in which addition and multiplication are definedmodulo d. The analogs of the Pauli operators in dimension d are defined bytheir action on the standard basis vectors asX |x〉 = |x+ 1〉 Z |x〉 = ωx |x〉 , (1.41)where ω = e2pii/d is the d-th root of unity. Using the X and Z operators asbuilding blocks, we define the Weyl (or Heisenberg-Weyl operators) asT(az ,ax) = ω2−1azaxZazXax . (1.42)The set {T(az ,ax)} is only closed under multiplication up to phases, it is15therefore not a group.Note the appearance of 2−1, the inverse of 2 in the above expression.This quantity does not exist in dimension 2, and it is the source of most ifnot all of the mathematical complications that occur for qubits. Althoughthis “detail” might seem surprising to the eyes of a physicist, fields of charac-teristic two are well known by mathematicians to be pathological in variousways. The characteristic of a field F is the smallest integer n such that1 + 1 + · · ·+ 1 = 0, with the sum on the left containing n terms. Two simpleproperties of fields of characteristic two that do not apply for other fieldsare that x−1 = −x, ∀x ∈ F and the fact that 1 only has one square root.The construction of the Heisenberg-Weyl operators is readily generalizedto systems of multiple qudits. In this case, the phase space V = Znd × Zndconsists of the vectors a = (az,ax) = (a1z, a2z, . . . anz , a1x, . . . , anx), and theHeisenberg-Weyl operators are defined asTa = T(az1 ,ax1 ) ⊗ T(az2 ,ax2 ) ⊗ · · · ⊗ T(azn ,axn ). (1.43)The phase space Znd × Znd naturally inherits a symplectic structure fromthe composition of the Weyl operators, becauseTuTv = ω2−1[u,v]Tu+v, (1.44)where[u,v] = (uz,vx)− (uz,ux) (1.45)is the symplectic product with addition and multiplication modulo d.From Equation 1.44 and the antisymmetry of the symplectic product,we haveTuTv = ω[u,v]TvTu. (1.46)The Wigner function for a density operator ρ is the symplectic Fouriertransform of the coefficients of ρ in the basis of the Heisenberg operators.More concretely, it’s the coefficient of the expansion of ρ in terms of point-16operators Au, defined asA0 =1dn∑a∈VTa (1.47)Au = TuA0T†u. (1.48)Therefore, the Wigner function Wρ of ρ isWρ(u) =1dnTr(ρAu). (1.49)Properties of the qudit Wigner functionIt can be shown [14] that the Wigner function has the following properties1. Wρ is real and sums to one:∑uWρ(u) = 1.2. For all density matrices ρ and σ, Wρ⊗σ = Wρ ·Wσ.3. W is informationally complete: since ρ =∑uWρ(u)Au, knowing theWigner function for a state is equivalent to knowing the state4. A0 |x〉 = |−x〉 , ∀x ∈ Z2nd .5. Discrete Hudson’s Theorem: the only pure states with non-negativeWigner function are stabilizer statesRemark. In dimension d = 2, all vectors of the phase space obey |x〉 =|−x〉. Therefore Property 4 does not hold for qubits since it would implyA0 = I.Clifford covarianceSome unitary gates have a relatively simple effect on the quantum state ofa system. This is captured in the definition of Wigner function covariance.Definition 1.3. A Wigner function Wρ is covariant under a group G if forany g ∈ G and for all states ρ, there exists a permutation map θg : V → V17such thatWgρg†(u) = Wρ(θg(u)). (1.50)We will use this definition to study stabilizer quantum computation forqudits. The stabilizer formalism of Section 1.1.1 generalizes readily to qu-dits, by defining the Clifford group as the group that preserves generalizedPauli operators (Weyl operators). If U belongs to the Clifford group,UTuU† = c(u)TSu, (1.51)where c : V → C is a map whose image has values ωx for x ∈ Zd, andS : V → V is a permutation of the phase space. It is a fact [14], that for anyClifford unitary U , there exists a symplectic matrix F and a vector a ∈ Vsuch thatUTuU† = TFu+a. (1.52)For qubits, this property only holds up to a sign ±1. It possible to use Equa-tion 1.52 to show that the Wigner function is covariant under the Cliffordgroup. Let U be a Clifford operation, then there exists [14] a symplecticmatrix F and a vector a such thatWUρU†(u) = Wρ(F−1(v − a)). (1.53)The Clifford covariance of the Wigner function shows that it has a highlevel of symmetry. It is possible, as was pointed out by Gibbons et al. [12],to define many different Wigner functions. However there is an importanttheorem, proved by Gross [14] that shows that the definition we have chosenis the only Wigner function possessing Clifford covariance. We give it’s fullcontent here for clarityTheorem 1.4. Consider another Wigner function W ′ that satisfies the fol-lowing properties1. W’ is a linear mapping on the space of density matrices: W ′ρ+σ =W ′ρ +W′σ.182. W’ is covariant under the action of the Clifford group.3. W’ gives the correct marginal probabilities.Then W ′ = W .In this sense, it can be said that the definition of the Wigner that wehave presented here is the most natural one.Negativity as a resourceIt is known through the Gottesman-Knill theorem that quantum circuitsconsisting of only Clifford gates acting on stabilizer states can be simulatedclassically. Veitch et al. [27] have expanded this result to all (pure andmixed) states that have positive Wigner functions.Theorem 1.5. Quantum circuits consisting of Clifford gates acting on aninitial state of qudits with positive Wigner function can be efficiently simu-lated by a classical computerThe proof of the previous is very similar to the efficient simulation proofthat we will give in Chapter 3, so we do not review it here. The proofrelies crucially on the property that the Wigner function is covariant underClifford gates. This covariance allows us to classically track the evolutionof the quantum state by calculating the associated phase space permutationafter each gate in the computation.This theorem identifies negativity as a resource in qudit stabilizer quan-tum computation, since it cannot be created using the allowed gate set. Inorder to acheive computational, negatively represented “magic states” needto be introduced; we shall have more to say about this process in Section1.31.2.3 The qubit Wigner functionWe will now go through a heuristic ”derivation” of the qubit Wigner func-tion, and attempt to show why some desirable properties, such as Cliffordcovariance, fall short in this case. For qubits, the phase space is discrete,19and it is the V that was described in equation 1.13. Our goal is to describethe density matrix of our system as a real-valued distribution on V . Usingthe fact that Pauli operators T are a basis for the complex space of matrices,we can write the density matrix of the system asρ =∑uρuTu, (1.54)where the ρu are generally complex coefficients if we consider states of qubits.The idea behind the Wigner function is to find another basis (Au) for ρ,whose coefficients are real and whose total sum over the phase space is one.The expansion coefficients of ρ in this basis are taken to be the definition ofthe Wigner function Wρρ :=∑uWρ(u)Au. (1.55)The requirement that Wρ is real and ρ hermitian forces the operators Auto be hermitian. The Au’s are called point operators. If we further requirethat the Au’s are orthonormal, we can invert equation 1.55 to obtainWρ(u) = Tr(Auρ). (1.56)One possible way to define the point operators isA0 =12n∑u(i)auTu Au = TuA0T†u. (1.57)The multiplicative factor (i)au is there to enforce hermiticity of the pointoperators. It is defined asau =0 if (uX ,uZ) = 01 if (uX ,uZ) = 1(1.58)We stress that there are many different ways to define a Wigner function,corresponding to different choices of A0, and they have been characterized by20Gibbons et al. [12]. For certain applications, however, we will be interestedin using Wigner functions that are particularly ”symmetrical” in the senseof covariance, a property that we have already seen in the context of thequdit Wigner function.The qubit Wigner function that we have defined enjoys the nice propertyof covariance under Pauli operations. In fact, elements of T have the effectof translating the phase space:WTvρT †v(u) =12nTr(TuA0T†uTvρT†v)=12nTr(T †vTuA0(T†vTu)†ρ)=12nTr(TvTuA0(TvTu)†ρ)=12nTr(Tu+vA0(Tu+v)†ρ)= Wρ(u + v),where in the second to third line of the previous calculation we used thatT †v = ±Tv.There is a more powerful and desirable kind of covariance, called Cliffordcovariance which is possessed by the qudit Wigner function, as we haveseen in Section 1.2.2. Clifford gates send Pauli operators to other Paulioperators, and furthermore they preserve the commutation relations. Inlight of Equation 1.17, preserving the commutation relations of the Paulioperators is equivalent to preserving the symplectic product over the phasespace. Therefore, for any g ∈ Cn, there exists a symplectic matrix F suchthatgTug† = ±TFu . (1.59)Symplectic matrices are matrices that preserve the symplectic product:[Fu, Fv] = [u,v]. (1.60)We are led to wonder if there exists a permutation of the phase spacethat describes the action of Clifford operations, as it was the case for qudits21in Section 1.2.2. In that section we established that Clifford covariancewas a desirable property for the Wigner function, because it leads to anefficient classical simulation method. However, it is a mathematical factthat there exists no definition of the Wigner function that is covariant underthe Clifford group for systems of qubits [31]. We can show this easily forthe function Wρ that we have defined.Lemma 1.6. The qubit Wigner function Wρ of Equation 1.56 is not Clifford-covariantProof. The proof proceeds through counterexample, by considering a one-qubit state ρ undergoing transformation by the Clifford unitary H. Themost general form of a one qubit state isρ =14(1 + rxX + iryZX + rzZ), (1.61)with r2x + r2y + r2z < 1. After the Hadamard gate, the state isρ→ HρH =14(1 + rzX − iryZX + rxZ). (1.62)We can compute the Wigner function of the state before and after theHadamard gateWρ(0, 0) =14(1 + rx + ry + rz) WHρH(0, 0) =14(1 + rx − ry + rz)Wρ(1, 0) =14(1 + rx − ry − rz) WHρH(1, 0) =14(1− rx + ry + rz)Wρ(0, 1) =14(1− rx + ry + rz) WHρH(0, 1) =14(1 + rx + ry − rz)Wρ(1, 1) =14(1− rx + ry − rz) WHρH(1, 1) =14(1− rx − ry − rz).Looking at the above equations for Wρ and WHρH , we see that for generalone qubit states, there is no permutation of the phase space that sends thefirst function to the other. Indeed, the function for WHρH(1, 1) containsthree minus signs, while there is no phase space point such that has this22property for Wρ.Is there a way to obtain some limited form of covariance? We can achievethis by setting one of the ri = 0 in Equation 1.61. In this thesis, we willchoose to set ry = 0, in which case ρ is a real state, or rebit. If we considera general states of n rebits, it’s expansion in terms of the Pauli operators isρ =∑a∈AρaTa, (1.63)with ρa ∈ R∀a and A = {u ∈ V | (uX ,uZ) = 0}. Therefore, we can dropsome terms from the definition of A0 in Equation 1.64 without consequence,and obtainA0 =12n∑a∈ATa Au = TuA0T†u. (1.64)This definition for the point operators will be the starting point for ourdiscussion of the rebit Wigner function in Chapter 3. In particular, we willestablish that this Wigner function is covariant under the subgroup GCSSof the Clifford group.1.2.4 Some properties of general Wigner functionsWe list here some properties held generally by Wigner functions Wρ : V → R1. The Wigner function is a quasi-probability distribution, so it sums toone∑u∈VWρ(u) = 1. (1.65)2. Wρ is informationally complete, in the sense that ρ =∑uWρ(u)Aue´3. For two state ρ and σ, their overlap (trace inner product) isTr(ρσ) = 2n∑uWρ(u)Wσ(u). (1.66)23If σ = |ψ〉 〈ψ| is a stabilizer state associated to a line L, this equationreduces to the probability that ρ is in the state |ψ〉Tr(ρ |ψ〉 〈ψ|) =∑u∈LWρ(u). (1.67)We will prove these properties, and some others, for the rebit Wignerfunction in Chapter 3.1.3 Magic states and computation by stateinjectionAs we have mentioned in Section 1.1.1, the set of Clifford gates acting onstabilizer states is classically simulable. If we hold the typical assumptionthat a general purpose quantum computer is not simulable classically, weare naturally lead to wonder how we can supplement this operational re-striction and achieve universal quantum computation. One possible way isto introduce a single qubit gate that does not belong to the Clifford group,such as the T gate [20]. Here we will focus on another road to universalityknown as quantum computation by state injection (QCSI), and the closelyrelated idea of magic state distillation.This approach is twofold. First we show that given a supply of perfectcopies of a certain quantum state as ancillas, and by only using Cliffordgates, we can realize a non-Clifford single qubit gate. These states have theproperty of “unlocking” universal quantum computation, which is why theyare called magic states in the literature. Then, we show that some magicstates have the other desirable property that a large number of imperfectcopies of a target magic state can be purified to obtain a smaller number ofbetter copies of that target.We first review a familiar construction in the quantum computation com-munity [20] that allows to realize the family of gatesΛ(θ) =(1 00 eiθ)(1.68)24Figure 1.3: Circuit for a state-injection that yields Λ(θ) |ψ〉 orΛ(−θ) |ψ〉 with equal probabilitiesby state injection using the magic state |Aθ〉 = 1√2(|0〉+ eiθ |1〉). This familyof gates contains |Api/4〉 := |H〉 and |Api/8〉 := |T 〉, which allow to realize theH and T gates, and obtain universal quantum computation. The circuit forstate injection is shown in figure 1.3, and can easily be shown to produceΛ(θ) |ψ〉 or Λ(−θ) |ψ〉 with equal probabilities.A question that naturally occurs in the context of fault-tolerant quantumcomputation is: can this scheme work if our ancilla states are not perfect?Bravyi and Kitaev answered this question positively by inventing the schemeof magic state distillation. Broadly, the scheme proceeds as follows.1. Start with a large number of imperfect states ρ⊗n2. Perform Clifford gates and measurements3. Obtain a smaller number of states ρ′⊗m with improved fidelity.It has been shown that |T 〉 and |H〉 states are distillable efficiently, butas the constructions rely heavily on the theory of quantum error correction,we will refer the interested reader to their original paper [7].Does magic state distillation also work for rebits? We address this ques-tion in Section 2.31.4 Hidden variable models and contextualityMany of the insights on the peculiar nature of quantum mechanics havebeen obtained by the study of hidden variable models. These ideas go back25to the Einstein-Podolsky-Rosen paradox [11] in which the authors famouslyargued that quantum mechanics was incomplete; their assumption of a localhidden variable model describing quantum theory led to ”spooky action ata distance”. It was latter proved by Bell in a seminal paper [4], that no localhidden variable model can reproduce the predictions of quantum mechanics.Subsequent experimental work has largely (but as of now not completely)concluded in favor of the formalism of quantum mechanics over local hiddenvariable models. However, there is another feature that we would expectreasonable hidden variable models to exhibit, but that is also violated byquantum mechanics: contextuality. This section aims to be a quick butself-contained introduction to the aspects of hidden variable models andcontextuality that are relevant for the content of this thesis.1.4.1 Hidden variablesContrary to the usual Copenhagen interpretation of quantum mechanics,in which measurements outcome are brought into being by the act of mea-surement, hidden variable models (HVMs) work under the reasonable as-sumption that physical systems have well-defined values of their propertiesbefore a measurement is performed on the systems. Thus, in such mod-els we assume quantum mechanics to be incomplete, and augment it withhidden-variables: a set of values {λi} that describe the definite outcome ofany measurement that can be performed on the system. In what followsthe values {λi} describing a particular system will sometimes be referred toas the ontic state of the system. To account for the fact that the standardformalism of quantum mechanics has always been vindicated by experiment,we require that on a set of identically prepared particles, the values λi aresampled from a probability distribution such that all statistical predictions(expectation values of observables, correlations between observables, etc.)agree with quantum mechanics.In quantum mechanics, as measurable quantity is represented as a her-mitian operator, and the possible outcomes of the measurement are theeigenvalues of the operator. The state of the system after a measurement26is given by the projection postulate; it is the (normalized) projection of theoriginal state onto the eigenspace corresponding to the measurement result.Mutually commuting operators are said to be simultaneously measurable,because they have simultaneous eigenvectors. For our purposes, we definea context to be a set {Mi} of mutually commuting observables. A contextcan therefore physically be identified with a possible measurement appara-tus, which yields a set of compatible measurement outcomes. We note thatthere exists more general definitions of contexts [25], which include ours asa special case. This discussion has set the stage for some definitionsDefinition 1.7. A physical setting is a pair (ρ,M), where ρ is the den-sity operator describing system and M is a set of measurement contextssuch that all observables O belonging to a context M ∈ M are mutuallycommuting and can be simultaneously measured.Definition 1.8. A hidden variable model for a physical setting (ρ,M) isa set of internal states S, together with a set value assignment functions{λu : O → R|u ∈ S}, where O is the set of observables that appear inM. The internal states should follow a probability distribution such thatall statistical prediction of quantum mechanics are reproduced by the HVM.Definition 1.9. A non-contextual hidden variable model (NCHVM) is aHVM such that for two contexts C1 and C2, the values associated to anobservable A such that A ∈ C1 and A ∈ C2 is independent on which of thetwo contexts is measured.Definition 1.10. A physical setting is contextual if it cannot be describedby a non-contextual hidden variable model.As a more concrete example, suppose we have three observables A, B,C such that [A,B] = [A,C] = 0, but [B,C] 6= 0. Then C1 = {A,B} ,C2 = {A,C} are two contexts, and a hidden variable model for this systemwill be non-contextual if the value assigned to A is independent of whetherA is measured jointly with B or with C. We note that our definition makesexplicit reference to quantum theory, and that it has been substantially gen-eralized by Spekkens [25]. Using the language introduced by that paper, we27make the assumption of outcome determinism, meaning that the a physicalsystem is in a well-defined ontic state, in opposition with it being given bya probability distribution over ontic states.The Definition 1.7 of a physical setting has the virtue of further restrict-ing the measurement contexts that need to be replicated by the HVM than tothe requirement that contexts are sets of mutually commuting observables.Indeed, if for some operational reason we are unable to simultaneously mea-sure a pair of commuting observables A and B, then we will not require ourNCHVM to account for measurements containing A and B.1.4.2 Algebraic constraints on the value assignmentsA HVM comes with a set of value assignment functions λu : O → R, whereu ∈ S is an internal state of the system and O is the set of observableson the Hilbert space of the system. Since the only possible outcomes fora measurement of an observable O ∈ O are eigenvalues of that observable,this limits the value assignments to λu(O) ∈ Eig(O). Furthermore, if twoobservables A and B commute, and if |ψ〉 is a simultaneous eigenvector ofboth operators with eigenvalues a and b, then AB |ψ〉 = ab |ψ〉. This imposesa consistency constraint on the value assignments:λu(AB) = λu(A)λu(B). (1.69)By the same reasoning, for any set of commuting observables, functionalidentities of operators f(A,B,C, ...) = 0 carry on to the value assignmentsso that f(λu(A), λu(B), λu(C), ...) = 0.Commuting observables are said to be simultaneously measurable be-cause they have simultaneous eigenvectors, and because the formalism ofquantum mechanics gives the same predictions no matter what the order ofthe measurements in the set is. However, it is not immediately obvious whatthis requirement of simultaneous measurability means when considering aHVM. It is conceivable that the ontic state of the system might change afterthe measurement of one of the observables in the setting, such that relation1.69 would not necessarily hold at the beginning of the measurement proce-28Figure 1.4: The Mermin square.It is impossible to have a consistentvalue assignment for the observables of the squaredure. However, the usefulness of this constraint is saved by noticing that forfinite contexts containing observables with a finite number of eigenvalues,it is always possible to construct a single observable whose measurementwould unambiguously determine the eigenvalues of all the other observablesin the context. Namely, if the context consists of observables {Ai}i=1..n witheigenvalues ranging for 1 to N , then we can construct the observableO =n∑i=1N iAi, (1.70)whose eigenvalue is an N-ary number that represents the set of eigenvaluesfor the context.1.4.3 Contextuality proofsIf we consider a system consisting of a single qubit, then it is possible toexplicitly construct a NCHVM that reproduces all predicitons of quantummechanics [4]. Contextuality first arises in systems of dimension 3, as wasfirst demonstrated by Kochen and Specker [18]. The proof is relativelycomplicated and we do not reproduce it here.There exists a very simple proof of contextuality due to Mermin [19]which considers a system formed by two qubits. We present this proof29Figure 1.5: Observables for which it is impossible to have a consistentvalue assignmentin a slightly modified version, to make it more readily applicable to thearguments of Chapter 4. The proof is purely algebraic and reaches a con-tradiction by showing that it is impossible to satisfy the value constraintsof Equation 1.69 for the set of nine observables shown in Figure 1.4, knownherein as the Mermin square. It can be easily checked that every row andcolumn is formed of mutually commuting observables, and that the prod-uct of the observables in every row and column is +I, except for the rightcolumn which multiplies to −I. Consistency of the value assignments givesus 6 equations of the form λ(X1)λ(X2)λ(X1X2) = 1, etc. constraining thevalues in the HVM. Multiplying these six equations together and noticingthat each observable appears in exactly two equations, we get∏A∈Oλ(A)2 = −1. (1.71)This is a contradiction, because the fact that Pauli operators have eigen-values ±1 implies that λ(A)2 = 1 for every observable. We remark thatthis proof made no mention of a particular state, it is thus an example ofsomething called state-independent contextuality.The previous argument uses some non-local observables, for instance30X1Z2, but there exists another proof of the Kochen-Specker theorem whichrelies only on local observables. In such a proof the assumption of non-contextuality might be more convincing, because it is guaranteed by local-ity. Indeed, if the individual particles are space-like separated, then it isimpossible for a measurement at one site to affect the values at another site.Consider the observables of the Mermin star in Figure 1.5, and assume thatthe state of the system is in an eigenstate of the (commuting) observablesbelonging to the horizontal row. Since the state is an eigenstate, the fourvalue assignments for the operators on the horizontal row are fixed to theassociated eigenvalue. All the other observables, whose properties undermeasurement need to be replicated by the HVM, are local Pauli operators.The rest of the proof proceeds in an analogous way as Mermin’s square. Wecan check that the five lines of the star are formed of commuting observ-ables, and that the product of the observables on every line is +1, exceptfor the horizontal line whose product is −1. Multiplying the five equationstogether yields a similar contradiction as in the Mermin square. The pricewe had to pay for the limitation to local observables is that this proof isconstructed to work only for one state, hence it is called state-dependentcontextuality. Note that if we allow ourselves to measure non-local observ-ables, we can directly get a state-independent proof of contextuality fromthe Mermin star.We conclude this brief introduction to HVM’s by pointing out that hid-den variable models that reproduce quantum mechanics are indeed possible,if one drops the assumption of non-contextuality. A well-known early exam-ple of such a model is Bohm’s pilot wave theory [6].The discussion of the two Mermin proofs shows that there is a fine linebetween state-independent and state-dependent contextuality, and that thisdemarcation has to do with the operations we allow ourselves to carry onthe physical system. We discuss these issues further in following section.311.4.4 Contextuality of subtheories of quantum mechanicsIn the previous paragraphs we saw that quantum theory exhibits state in-dependent contextuality. The arguments given above are quite general, asfor any system with total dimension higher than four, we can pick a 4-dimensional subspace on which the Mermin square proof applies directly.However, if for a reason or another we have an operational restriction (onlya certain subset of gates, states or measurements are allowed), we might beable to construct a non-contextual hidden variable model describing everypossible measurement outcome. As a trivial example of such a situtation,consider a system of qubits, initially in state |000 · · · 0〉 on which we are onlyable to perform X and Z gates, and Z measurements. Since we do not havethe capability to perform entangling gates, every qubit can be independentlydescribed by the non-contextual HVM of Bell [4] to which we have alreadyreferred to.In the field of fault-tolerant quantum computation [20], certain quan-tum gates are considered ”cheap” because they can be implemented fault-tolerantly in a relatively simple way. One prominent example of such a setof gates occurs in stabilizer quantum computation, which we have discussedin Section 1.1.1, and where the cheap gates are 〈Xi, Zi, Hi, CNOT (i, j)〉. Asnow know, stabilizer quantum computation is not universal, and in order toachieve universality, we need to resort the scheme of QCSI.Restricting ourselves to a such a subtheory of quantum mechanics, it isconceivable that the subtheory could be described by a NCHVM. Supposefor the following that we have an operational restriction that yields a non-contextual subtheory of quantum mechanics. Then it is immediate thatour restricted set of gates will not allow universal quantum computation.Indeed, if it did, we could achieve exactly the measurements of the Merminsquare proof and contradict our assumption of non-contextuality.Howard et al. [16] have expanded on the previous results of Veitch et al.[27] by considering the role of contextuality as a resource in qudit QCSI. Intheir paper, drawing from an earlier result of Spekkens [26], they show thatnegativity and contextuality are equivalent notions. Therefore they establish32contextuality of the magic state as a resource for quantum computation. Animportant point to note is that for qudits, there exists no state-independentcontextuality proof involving only measurements of generalized Pauli oper-ators. This is clearly not the case for qubits, as evidenced by the Merminsquare and star.The advantage of the QCSI scheme for fundamental study of the re-sources of quantum computation is that we put the computational power onthe magic states. Whether a state is contextual or not completely dependson the operational restriction we impose on ourselves. One of the main ques-tions we shall ask in Chapter 4 is: ”does contextuality imply universality inrebit QCSI?”, and the answer will be positive.33Chapter 2Universal quantumcomputation by stateinjection with rebits2.1 RebitsJust as real numbers can ben seen as a subset of the complex numbers, it ispossible to define rebits as the subset of quantum states of qubits that havedensity matrices with real entries in the computational basis. If ρ is a n-rebitstate, then for every computational basis states |x〉 , |y〉 ( ±1 eigenstates ofZ1 ⊗ · · · ⊗ Zn), it will obey〈x|ρ|y〉 ∈ R. (2.1)The full Clifford group does not preserve rebit states, as can be easilyseen from Y |0〉 = i |1〉. The subgroup of the Clifford group that preservesrealness is GCSS , which we defined in Equation 1.11.342.2 Universal quantum computationUniversal quantum computation, in the more traditional case of qubits,refers to the ability to approximate any unitary gate using number of el-ementary gates that scales polynomially with the desired accuracy [20]. Ithas been shown [22], that through the use of a simple encoding, that rebitsare universal for quantum computation. The encoding consists of mappinga n-qubit state to a state of n+1 rebits, with the additional rebit coding forthe real and imaginary parts of the initial state. More explicitly, startingfrom a general n-qubit state|ψ〉 =∑v∈Zn2rveiθv , |v〉 (2.2)the corresponding encoded state is|ψ〉 =∑v∈Zn2(rv cos θv |v〉 ⊗ |R〉+ rv sin θv |v〉 ⊗ |I〉). (2.3)Here |R〉 = |0〉 and |I〉 = |1〉 is just notation that makes explicit the realand imaginary parts in the encoding. The fact that changing a qubit stateby a global phase is reflected by the existence of infinitely many rebit statesencoding the same qubit state. As a simple example, |0〉 |R〉 and |0〉 |1〉 areboth encodings of the qubit state |0〉.We will now exhibit a set of gates acting on encoded rebit states thatis universal and preserves realness of the states. One common choice for auniversal gate set [20] isGuniversal = 〈CNOT(i, j), Hi, exp(ipi/8Zi)〉. (2.4)We will restrict our allowed gates to the CSS-ness preserving groupGCSS , so thatGrestricted = 〈CNOT(i, j),⊗ni=1Hi, Zi, Xi〉, (2.5)where ⊗ni=1Hi := Hall is the Hadamard on all rebits. Our goal is now to35show that, assuming that we have access to a reservoir of ”magic states”,we can performed encoded versions of the gates Hi and exp (ipi/8Zi). Ourmethod closely follows the scheme of universal quantum computation bystate injection of Bravyi and Kitaev [7]. The two magic states we will needare|A〉 =1√2(|0〉+ eipi/4 |1〉)(2.6)=1√2(|0〉 |R〉+ cospi4|1〉 |R〉+ sinpi4|1〉 |I〉)(2.7)and|B〉 =1√2(|0〉 |+〉+ |1〉 |−〉) , (2.8)where |±〉 is the ±1 eigenstate of the Pauli operator X.In the following we demonstrate how to obtain Guniversal, using onlygates from Gresricted, the states |A〉 and |B〉, and measurements in the com-putational basis. Said differently, for all g ∈ Guniversal, we show how torealize the transformation |ψ〉 → g |ψ〉 using only gates from GCSS and themagic states |A〉, |B〉.1. Pauli Y on qubit iThe Y = iXZ gate has imaginary components, so it’s encoding forrebits has to affect the ancilla A. We will show that the encoded gateY¯i isY¯i = Yi ⊗ YA = −XiZiXAZA. (2.9)Indeed, starting from the initial encoded rebit state¯|ψ〉 =∑vrv |v〉 (cos θv |0〉A + sin θv |1〉A) (2.10)and applying Yi ⊗ YA gives (up to an overall minus sign)∑v(−1)virv |v + ei〉 (cos θv |1〉A − sin θv |0〉A) , (2.11)36where ei ∈ Zn2 is the basis vector that has value 1 in position i and 0elsewhere. This state the same as the encoding of the stateYi |ψ〉 =∑v(−1)virvei(θv+pi/2) |v + ei〉 , (2.12)proving our initial claim.2. Measurement of ZiThe Pauli operator Zi is real in the computational basis, so it doesnot mix the real and imaginary parts of the encoded state. Thereforethe encoded version Zi is the same as Zi(2.13)3. CNOT gate between qubits i and jThe CNOT gate between qubits i and j gate belongs to GCSS , andit is real in the computational basis. Therefore it does not mix thereal and imaginary parts of the state it is applied to, so CNOT (i, j) =CNOT (i, j)(2.14)4. Hadamard gateWe will show that the following circuit, using one copy of the magicstate |B〉 realizes an encoded Hadamard on the state |ψ〉37(2.15)The initial state is(r0 cos θ0 |0〉 |R〉+ r1 sin θ1 |1〉 |I〉) |B〉 . (2.16)After the CNOT gate, the state of the system is1√2(r0 cos θ0 |0〉 |R〉+ r1 sin θ1 |1〉 |I〉) |0〉 |+〉 (2.17)+1√2(r0 cos θ0 |1〉 |R〉+ r1 sin θ1 |0〉 |I〉) |1〉 |−〉 . (2.18)After the X measurement and the conditional X gate associated withit, we discard the third qubit and the state is1√2(r0 cos θ0 |0〉 |R〉+ r1 sin θ1 |1〉 |I〉) |+〉 (2.19)+1√2(r0 cos θ0 |1〉 |R〉+ r1 sin θ1 |0〉 |I〉) |−〉 . (2.20)After the Z measurement and the conditional Z gate associated withit, we discard the first qubit. We also swap the two remaining qubitsso that the I/R ancilla ends up in the right position. The final state isr0 cos θ0 |+〉 |R〉+ r1 sin θ1 |−〉 |I〉 = H |ψ〉, (2.21)as claimed.5. Conditional phase gateIn order to make the next point of state-merging easier to follow, we38demonstrate a state injection circuit for the conditional phase gate.This two-qubit gate leaves all standard basis states invariant, exceptfor |11〉 → − |11〉. We show that(2.22)The initial state is1√2(|0〉 |+〉+ |1〉 |−〉)(a |00〉+ b |01〉+ c |10〉+ d |11〉). (2.23)The two CNOT gates send the state to1√2[a(|0〉 |+〉+ |1〉 |−〉)|00〉+ b(|0〉 |+〉 − |1〉 |−〉)|01〉+ c(|1〉 |+〉+ |0〉 |−〉)|10〉+ d(|1〉 |+〉 − |0〉 |−〉)|11〉]. (2.24)The measurement of Z on the first qubit, followed by a conditionalZ gate on the third qubit yields (after discarding the measured qubitfrom the notation) the state |ψ±〉. We have + if the measured spinwas in the state |0〉, and − if the spin was in state |0〉. This state is|ψ±〉 = a |±〉 |00〉+ b |±〉 |01〉+ c |∓〉 |10〉 − d |∓〉 |11〉 . (2.25)And finally, measuring Z and the first remaining qubit and applying aconditional Z on the last qubit produces the transformation|ψ±〉 → ±(a |00〉+ b |01〉+ c |10〉 − d |11〉), (2.26)where we have suppressed the measured qubit from the notation. Thisis exactly the outcome of a conditional phase gate, up to an irrelevant39global phase.6. State-mergingSuppose that we have two multiqubit states |ψ〉 and |φ〉 in their rebit-encoded form |ψ〉 and |φ〉. We would like to get the encoded state fortheir direct product: |ψ〉 ⊗ |φ〉. It is obvious that we need to get rid ofone of the ancillas, and we will show that the following circuit realizesthe adequate transformation.(2.27)Let our initial encoded states be|ψ〉 =∑v∈Zn2(rv cos θv |v〉 |R〉+ rv sin θv |v〉 |I〉) (2.28)and|φ〉 =∑u∈Zm2(su cosκu |u〉 |R〉+ su sinκu |u〉 |I〉) (2.29)Taking the product of these two states gives|ψ〉 ⊗ |φ〉 =∑v,urvsu(cos θv cosκu |v, R〉 |u, R〉+ cos θv sinκu |v, R〉 |u, I〉+ sin θv cosκj |v, I〉 |u, R〉+ sin θv sinκu |v, I〉 |u, I〉).It should be noted that this state is not equal to (|ψ〉 ⊗ |φ〉). Wenow detail the effect of the circuit on this state. Applying the CNOTgate and the conditional phase gate (preserves basis stats except for40|11〉 → − |11〉) on the ancillas yields∑v,urvsu(cos θv cosκu |v, R〉 |u, R〉 − cos θv sinκu |v, I〉 |u, I〉+ sin θv cosκu |v, I〉 |u, R〉+ sin θv sinκu |v, R〉 |u, I〉). (2.30)We now perform the X measurement on the last qubit and discard themeasured qubit. We also swap the remaining ancilla qubit so it is atthe last position in our notation. Let |Ψa〉 be the two possible outputstates after measurement, with a = 0 denoting the positive outcome,and a = 1 the negative outcome. This state is|Ψa〉 =∑v,u(rvsu(cos θv cosκu + (−1)a sin θv sinκu) |v,u, R〉+ (sin θv cosκu + (−1)a+1 cos θv sinκu) |v,u, I〉)=∑v,urvsu[cos(θv + (−1)a+1κu)|v,u, R〉+ sin(θv + (−1)a+1κu)|v,u, I〉]. (2.31)We see that |Ψ0〉 = |ψ〉 ⊗ |φ〉∗, where |φ〉∗ is the state obtained from|φ〉 by complex conjugation of the coefficients in the standard basis.Also, we have that |Ψ1〉 = |ψ〉 ⊗ |φ〉. We have thus shown that itis possible to merge encoded states, modulo a probabilistic complexconjugation. We will return to this issue of complex conjugation later,where we shall see that it affects neither the computational power northe efficiency of state state injection.7. The gate exp ipi/8ZiAs we showed in Section 1.3, the following qubit circuit is a validstate-injection circuit for the exp ipi/8Zi gate.41(2.32)To realize an encoded version of this circuit on rebits, it suffices toperform a state merging routine between the magic state |A〉 and theinput state, followed by the necessary CNOT and measurement.While the magic state |A〉 certainly allows us to perform this task, anytwo-rebit state that encodes for the qubit state 1√2(|0〉+ eipi/4 |1〉) willalso work.2.3 Magic state distillation2.3.1 Bell statesWe first show, following Bennett et al. [5], that it is possible to take multiplecopies of an impure Bell state and perform manipulations on them to geta state with higher purity. Consider an initial mixed state that is mostlycomposed of |Φ+〉 = 1√2(|00〉+ |11〉),ρin = (1− )ρ00 +3(ρ01 + ρ10 + ρ11), (2.33)where for notational simplicity, we describe the Bell basis in the stabilizerformalism so that ρij is the pure state stabilized by 〈(−1)iZ1Z2, (−1)jX1X2〉.This state has fidelity F = 〈Φ+|ρin|Φ+〉 = 1− .The first step of the protocol isStep 1 on qubits 1 and 21. Start in state ρin ⊗ ρin2. Apply a CNOT gate with qubit 1 as control and qubit 3 as target3. Apply a CNOT gate with qubit 2 as control and qubit 4 as target424. Measure the two-qubit Pauli observable Z3Z4. If the result is +1,continue; otherwise reject the state and start over. A mixed stateconsisting of mostly the |Φ+〉 Bell state is now located on the first twoqubitsWe show, using the stabilizer formalism, how this protocol improves thefidelity. The initial state can be written asρin ⊗ ρin =∑e∈Z42f(e)ρe1e2 ⊗ ρe3e4 , (2.34)withf(e) =(1− )2 if (e = 03(1− ) if e 6= 0 and e1 = e2 = 0 or e3 = e4 = 029 otherwise(2.35)Now let us see how the stabilizer of a state ρe1e2 ⊗ ρe3e4 evolves at eachstep in the circuit.1. Initial state: 〈(−1)e1Z1Z2, (−1)e2X1X2, (−1)e3Z3Z4, (−1)e4X3X4〉2. First CNOT:〈(−1)e1Z1Z2, (−1)e2X1X2X3, (−1)e3Z1Z3Z4, (−1)e4X3X4〉3. Second CNOT:〈(−1)e1Z1Z2, (−1)e2X1X2X3X4, (−1)e3Z1Z2Z3Z4, (−1)e4X3X4〉= 〈(−1)e1Z1Z2, (−1)e2+e4X1X2, (−1)e1+e3Z3Z4, (−1)e4X3X4〉4. The Z3Z4 measurements discards all e such that e1+e3 = 1, and keepsthe other half. If the measurement was a success, we remove qubits 3and 4, and the result is a two qubit state with stabilizer〈(−1)e1Z1Z2, (−1)e2+e4X1X2〉 .43With the previous information it is possible to calculate that the outputstate after the first step of the protocol isρ1step ∝((1− )2 +29)ρ00 +229ρ10 +23(1− )ρ01 +229ρ11. (2.36)This form of the density matrix after one step of purification reveals why itis interesting to have a two step protocol. Indeed, we see that the coefficientof ρ01 is of order , while the coefficients for ρ10 and ρ11 are of order 2.There has thus been no significant improvement in the ρ01 portion of thestate, and we would like to fix this.The goal of the second step of the protocol is to take to copies of ρ1stepand to correct the ρ01 errors. This is achieved by a slight modification ofthe first step.Step 21. Start with input state ρ1step ⊗ ρ1step2. Apply a CNOT gate with qubit 1 as control and qubit 3 as target3. Apply a CNOT gate with qubit 2 as control and qubit 4 as target4. Measure the two-qubit Pauli observable X1X22. If the result is +1,continue; otherwise reject the state and start over. A mixed stateconsisting of mostly the |Φ+〉 Bell state is now located on the last twoqubitsThe outcome of this procedure can be calculated as previously, and theresult isρout ∝[((1− )2 +29)2+(229)2]ρ00 +429((1− )2 +29)ρ10+[23(1− ) +(229)2]ρ01 +8327(1− )ρ11. (2.37)44This expression shows that the two step protocol allows for all of the errorsto be reduced to order 2 or more. Assuming   1, we can expand theoutput state asρout = (1− out)ρ00 + . . . , (2.38)without =829+O(3). (2.39)If we apply the protocol recursively, and let out(k, ) be the error afterk recursion levels starting with initial error , then the efficiency of thedistillation is characterized byout(k, ) =√98(√89)2k, (2.40)in the limit where  1.2.3.2 The state |B〉The Bell state distillation method that we just presented can be straight-forwardly modified to allow distillation of the magic state|B〉 =1√2(|0〉 |+〉+ |1〉 |−〉) = H2 |Φ+〉 . (2.41)As the previous equation shows, |B〉 is related to |Φ+〉 through the appli-cation of a Hadamard gate. For what follows, we need the following circuitidentity(H1H2)CNOT (1, 2)(H1H2) = CNOT (2, 1), (2.42)whose validity can be easily verified. Therefore, we only need to invert thedirection of one CNOT, and change one measurement, to adapt the Bellstate distillation scheme to our needs. Explicitly, we haveStep 11. Start in state ρin ⊗ ρin452. Apply a CNOT gate with qubit 1 as control and qubit 3 as target3. Apply a CNOT gate with qubit 4 as control and qubit 2 as target4. Measure the two-qubit Pauli observable Z3X4. If the result is +1,continue; otherwise reject the state and start over. A mixed stateconsisting of mostly the |B〉 state state is now located on the first twoqubitsStep 21. Start with input state ρ1step ⊗ ρ1step2. Apply a CNOT gate with qubit 1 as control and qubit 3 as target3. Apply a CNOT gate with qubit 4 as control and qubit 2 as target4. Measure the two-qubit Pauli observable Z1X22. If the result is +1,continue; otherwise reject the state and start over. A mixed stateconsisting of mostly the |B〉 state is now located on the last two qubitsThe above described scheme allows us to distill |B〉 with the same effi-ciency of distillation as we calculated in the case of |Φ+〉 Bell states.We are now in possession of a reliable supply of |B〉 magic states. Re-ferring back to the rebit encoding scheme of Section 2.2, this allows us toperform encoded controlled-phase gates, encoded Hadamard gates, and statemergingThe state |A〉The magic state that we need for universal quantum computation is|A〉 =1√2(|0〉 |R〉+1√2|1〉 |R〉+1√2|1〉 |I〉). (2.43)It is the rebit encoding of the qubit state|A0〉 =12(|0〉+ eipi/4 |1〉), (2.44)46for which a distillation scheme relying on an intricate CSS-code constructionwas first presented by Bravyi and Kitaev [7]. Their qubit scheme takes 15copies of |A0〉 and outputs a copy with higher fidelity. The only operationsneeded for the scheme are Clifford gates (which we can now do using themagic state |B〉), X and Z Pauli measurements, and the single qubit gateA =1√2(X + Y ) = e−ipi/4SX, (2.45)whereS =(1 00 i). (2.46)We refer the reader to the original paper for the details of the construc-tion. Our strategy will be to implement the same method on encoded rebitstates.The action of an S-gate on an encoded rebit state isS |ψ〉 = CZ(|ψ〉), (2.47)where CZ is a conditional phase gate, which is possible to realize using amagic states |B〉 as we have already demonstrated in Section 2.2We now show how we can perform this scheme on impure copies of thetwo-rebit state |A〉. We first need to address the issue of how to deal witherrors in the larger Hilbert space of two rebits. Consider the following basisfor the real vector space of two rebits|A〉 =1√2(|0〉 |R〉+1√2|1〉 |R〉+1√2|1〉 |I〉)|A1〉 =1√2(|0〉 |R〉 −1√2|1〉 |R〉 −1√2|1〉 |I〉)= Z1 |A0〉|A′〉 =1√2(|0〉 |I〉 −1√2|1〉 |R〉+1√2|1〉 |I〉)|A′1〉 =1√2(|0〉 |I〉+1√2|1〉 |R〉 −1√2|1〉 |I〉)= Z1 |A1〉.47The important thing to notice here is that |A〉 and |A′〉 encode from thesame one qubit state, and similarly for |A1〉 and |A′1〉. Indeed,|A1〉 = i |A0〉|A′1〉 = iZ |A0〉.Therefore, since our rebit quantum computer realizes all its computationby operating on encoded qubit states, the primed states will yield exactlythe same outputs as the unprimed states. This allows us to regard them asequivalent for computational purposes. We take the following state as ourinitial impure stateρ = (1− )|A〉 〈A|+ |A1〉 〈A1|. (2.48)The Bravyi-Kitaev protocol requires 15 copies of this state:ρin = ρ⊗15. (2.49)We perform the state-merging routine which we described in the previoussection. We must attend to the potential complex conjugation of states afteran encoded conditional-phase gates, which we saw happens with probabilityone half. The results of a complex conjugation are either|A0〉∗ =12(|0〉+ e−ipi/4 |1〉) =12(|0〉 − ieipi/4 |1〉) = S† |A0〉 (2.50)or|A1〉∗ =12(|0〉 − e−ipi/4 |1〉) =12(|0〉+ ieipi/4 |1〉) = S† |A1〉 . (2.51)Therefore, if we know that a conjugation has happened, applying the en-coded S gate will correct the state to it’s non-conjugated form. The resultof these manipulations is the state ρ⊗15qubit, where ρqubit = (1− ) |A0〉 〈A0|+Z |A0〉 〈A0|Z, for which Bravyi and Kitaev demonstrated their distillation48method. Following their method step by step in an encoded fashion, weobtain ρout ⊗ ρjunk, with ρjunk a 14-qubit state which is unentangled fromthe purified state ρ0. Tracing out these junk states gives us our purifiedstate.49Chapter 3The rebit Wigner functionThe goal of this Chapter is to define and characterize a rebit Wigner func-tion that has properties that are as similar as possible to the qudit Wignerfunction described in Section 1.2.2. We will state and prove a number ofproperties about this Wigner function, the most important of which beinga discrete Hudson’s theorem for rebits. We will also study covariance of theWigner function under a subgroup of the Clifford group, the CSS-ness pre-serving Clifford group. We will also give a theorem analogous pertaining tothe classical simulability of circuits consisting of CSS-ness preserving Clif-ford unitaries acting on states with positive Wigner functions. This chapteris rather technical; the reader is advised to skip over the proofs on a firstreading, and to consult the appendices for some mathematical background.3.1 Definition and elementary propertiesIn this section we revisit the phase space formalism and Wigner function ofSection 1.1, this time for rebits. The Wigner function W of a rebit state ρis defined over the phase spaceV = {a = (aZ ,aX)|aZ ,aX ∈ Zn2} ∼= Z2n2 . (3.1)With each of the phase space points a ∈ V is associated a Pauli operator50Ta defined asT(aZ ,aX) = Z(aZ)X(aX), (3.2)where Z(a) = Za11 ⊗ Za22 ⊗ · · · ⊗ Zann , and equivalently for X(aX). Notethat the Pauli operators defined in this way are not all Hermitian. Theseoperators form a basis for the complex vector space of n by n square matrices,with the trace inner product (A,B) = 12nTr(A†B). Indeed, it can be checkedthatTr(T †aTb) = 2nδa,b. (3.3)In this chapter we will be restricting ourselves to real density matrices.The requirement that density matrices should be Hermitian and real forcesthat their expansion in terms of Ta’s is restricted to the subsetA = {a ∈ V | (az,ax) = 0}. (3.4)By abuse of notation, A will sometimes be taken to denote the set {Ta|a ∈A}, but the meaning will always be clear from the context.In analogy with the qudit situation, we define a family of operators(Au)u∈V asA0 =12n∑a∈ATa (3.5)Au = TuA0T†u. (3.6)Using the commutation relations for the Pauli operators, we can also writeAu into the following form, of which we will make frequent use in this thesisAu =12n∑a∈A(−1)[u,a]Ta, (3.7)where [u,v] = (uX ,uZ) − (uZ ,uX) is the symplectic product, for whichaddition and multiplication is modulo two. The Au operators do not forma basis for the space of real density matrices, because it is overcomplete.We can nonetheless obtain an informationally complete Wigner function51Wρ : V → R, by definingWρ(u) =12nTr(Auρ) (3.8)We now turn to proving a list of properties concerning the rebit Wignerfunction Wρ. We encourage the reader to compare this list with the list ofproperties for the qudit Wigner function appearing in Section 1.2.2.1. Wρ is real and sums to one:∑uWρ(u) = 1.Proof. For a rebit state ρ, the expansion of its density matrix in termsof Pauli operators can be written asρ =12n∑a∈AρaTa, (3.9)with ρ0 = 1 for the trace condition, and other conditions on the co-efficients ρa ∈ R to ensure that the state is physical, but that we willnot need to consider. The Wigner function is thusWρ(u) =122n∑a∈AρaTr (AuTa)=122n∑a∈Aρa(−1)[u,a], (3.10)where in the first to second line we used Equation 3.7 and the orthog-onality relation of the Paulis. Therefore, Wρ(u) is clearly real for allu ∈ V because of the realness of the coefficients ρa.To prove that Wρ sums to one, we take Equation 3.10 and sum it upover V :∑u∈VWρ(u) =122n∑a∈Aρa∑u∈V(−1)[u,a]=∑a∈Aρaδa,0= ρ0 = 1,52where in going to the second line we used the character orthogonalityrelations,∑u∈V (−1)[u,a] = 22nδa,0. The basics of character theory arereviewed in Appendix A.1.2. W is informationally complete: ρ =∑uWρ(u)AuProof. We start from the expression 3.10 for Wρ(u)∑u∈VWρ(u)Au =122n∑u∈V∑a∈A(−1)[u,a]ρaAu=123n∑u∈V∑a,b∈A(−1)[u,a+b]ρaTb=12n∑a,b∈Aδa,bρaTb=12n∑a∈AρaTa= ρ.We have again used the ever useful character orthogonality relation ingoing from the second to the third line.3. For all real density matrices ρ and σ, Wρ⊗σ = Wρ ·WσProof. Let Wρ : VA → R and Wσ : VB → R be the Wigner functionsfor ρ and σ, defined on phase spaces of possibly different size |VA| = 2nand |VB| = 2m. Then the domain of Wρ⊗σ is VA ⊗ VB, andWρ⊗σ(u) =12n+mTr(Auρ)=122(n+m)∑a∈AA,B(−1)[u,a]Tr(Taρ⊗ σ).By definition of the direct sum, we can decompose any v ∈ VA ⊗ VBas v = vA + vB, with vA having trivial projection over the subspaceVB and vice versa.53If a ∈ VA ⊗ VB, then Ta = TaATaB , where TaA and TaB commutebecause they act on different systems. If we further wish to ensurethat a ∈ AA,B, it is necessary that either (aA,aB) ∈ AA ⊗ AB, or(aA,aB) ∈ A¯A ⊗ A¯B, where A¯A = VA − AA, and similarly for A¯B.With the observations just made,Wρ⊗σ(u) =122(n+m)∑aA∈AA∑aB∈AB(−1)[uA,aA](−1)[uB,aB]TrA(TaAρ)TrB(TaBσ)+122(n+m)∑aA∈A¯A∑aB∈A¯B(−1)[uA,aA](−1)[uB,aB]TrA(TaAρ)TrB(TaBσ).The second sum is zero because ρ and σ are real. We can now factorizethe Wigner function, as claimedWρ⊗σ(u) =122n∑aA∈AA(−1)[uA,aA]TrA(TaAρ)×12m∑aB∈AB(−1)[uB,aB]TrB(TaBσ)= Wρ(uA)Wσ(uB).4. The trace inner product isTr(ρσ) = 2n∑u∈VWρ(u)Wσ(u) (3.11)Proof. Using Property 2, we obtain54Tr(ρσ) =∑u,v∈VWρ(u)Wσ(v)Tr(AuAv)=122n∑u,v∈VWρ(u)Wσ(v)∑a,b∈A(−1)[u,a]+[v,b]Tr(TaTb)=12n∑u,v∈VWρ(u)Wσ(v)∑a∈A(−1)[u+v,a]= 2n∑u∈VWρ(u)Wσ(u),where in the previous calculation we have used the orthogonality ofthe Pauli operators and the character orthogonality relation.5. Hudson’s theorem: The only pure states with positive Wigner functionare CSS-stabilizer states. The next section is dedicated to proving thistheorem.3.2 Hudson’s theoremThe goal of this section is to prove Hudson’s theorem:Theorem 3.1. A pure rebit state has a non-negative Wigner function ifand only if it is a CSS state.To prove this, we will need to collect a significant chain of lemmas. Westart by provingLemma 3.2. A state ρ has Wigner functionWρ =12nδt+N⊥×N (u), (3.12)where t ∈ V and N is a subspace of Zn2 , if and only if ρ is a pure CSS state.55Proof. A CSS state |ψ〉 has a stabilizer that is the direct product of an Xpart and a Z part: S(|ψ〉) = SX × SZ . Taking N ⊂ V to be the subspaceassociated with SX , then its orthogonal complement N⊥ = {u ∈ V | [u,v] =0, ∀v ∈ N} will be the subspace associated with SZ . Therefore, any Paulioperator in S has the form ±TaX+aX , with aX ∈ N and aZ ∈ N⊥. By thecompleteness of characters, there exists a t ∈ V such thatρ = |ψ〉 〈ψ| =12n∑u∈N⊥×N(−1)[t,u]Tu. (3.13)Then the Wigner function Wρ isWρ(u) =122n∑v∈N⊥×N(−1)[t,v]Tr(AuTa)=123n∑u∈N⊥×N∑a∈A(−1)[t,v](−1)[a,u]Tr(TaTv)=122n∑u∈N⊥×N∑a∈A(−1)[t,v](−1)[u,a]δa,v=12n∑u∈N⊥×N(−1)[v,t+u]=12nδt+(N⊥×N)(u)This proves one direction of the claim. For reverse implication, we usethe fact the the Wigner function is informationally complete. Starting fromWρ(u) = 12n δt+(N⊥×N)(u), we do the inverse Fourier transform to get ρ =∑u∈(N⊥×N)(−1)[t,u]Tu, and such a state is a CSS state.We have thus proved that all CSS states have positive Wigner function.We now set out for the nontrivial task of proving that all pure states withpositive Wigner function are stabilizer states3.2.1 Bochner’s theoremHere we prove a very limited form of a theorem in harmonic analysis knownas Bochner’s theorem. It will allow us to better understand the Wigner56function of a pure state by looking at it’s Fourier transform.The Wigner function of a pure rebit state |ψ〉 =∑x∈Zn2ψ(x) |x〉, evalu-ated at u = (p,q) ∈ V isWψ(u) =12n∑x,y∈Zn2ψ(x)ψ(y)Tr (Au |x〉 〈y|)=122n∑x,y∈Zn2∑a∈Aψ(x)ψ(y)(−1)[u,a]Tr (Ta |x〉 〈y|) .Because the state is real, the sum over A can be extended to a sum over thefull phase space without changing the result. This givesWψ(u) =122n∑x,y∈Zn2∑a∈Vψ(x)ψ(y)(−1)[u,a]Tr (Ta |x〉 〈y|)=122n∑x,y∈Zn2∑a∈Vψ(x)ψ(y)(−1)[u,a](−1)(aZ ,y)Tr (|x + aX〉 〈y|)=122n∑x,y∈Zn2∑a∈Vψ(x)ψ(y)(−1)[u,a](−1)(aZ ,y)δx+aX ,y=122n∑y∈Zn2∑a∈Vψ(y + aX)ψ(y)(−1)[u,a](−1)(aZ ,y)=122n∑y∈Zn2∑aX∈Zn2(−1)(uZ ,aX)ψ(y + aX)ψ(y)∑aZ∈Zn2(−1)(aZ ,y+uX)=12n∑y∈Zn2∑aX∈Zn2(−1)(uZ ,aX)ψ(y + aX)ψ(y)δy,uX=12n∑aX∈Zn2(−1)(uZ ,aX)ψ(uX + aX)ψ(uX)=12n∑x∈Zn2(−1)(uZ ,x)ψ(uX + x)ψ(uX).We are inspired to define the functionKψ(q,x) = ψ(q)ψ(q + x) (3.14)57So that the Wigner function for fixed q, Wψ(·,q), is the Fourier transformof Kψ(q, ·)Wψ(p,q) =12n∑x∈Zn2(−1)(p,x)Kψ(q,x). (3.15)We can also do the inverse Fourier transform (in dimension two it is thesame as the Fourier transform up to a multiplicative factor), to get∑p∈Zn2(−1)(p,x)Wψ(p,q) =12n∑p,y∈Zn2(−1)(p,x+y)Kψ(q,y)=∑y∈Zn2δx,yKψ(q,y)= Kψ(q,x),where in the first to second line we have used the character orthogonalityrelation. We restate the previous equation for future reference:Kψ(q,x) =∑x∈Zn2(−1)(p,x)Wψ(p,q). (3.16)Theorem 3.3. (Bochner’s theorem) The matrix Axy = K(q,x− y) is pos-itive semi-definite if and only if Wψ(y,q) ≥ 0 ∀y ∈ Zn2 . A real matrix Awith entries Axy is positive semi-definite if∑x,y∈Zn2bxbyAxy ≥ 0 for all realvectors b with coefficients indexed by Zn2 .Proof. Let b be a real vector with coefficients indexed by Zn2 . Then∑x,y∈Zn2bxbyK(q,x− y) =12n∑x,y,pbxby(−1)(p,x−y)Wψ(p,q)=12n∑pWψ(p,q)(∑x(−1)(p,x)bx)2Therefore, if Wψ(p,q) ≥ 0 for all p ∈ Zn2 , the right hand side is greaterthan zero, showing that K(q,x− y) is positive semi-definite.Conversely, suppose there exists an r such that Wψ(r,q) < 0. Then,58recalling that the characters are a basis for the space of functions over Zn2 ,we can choose a vector a ∈ Zn2 such that(∑x(−1)(p,x)ax)2= δp,r, (3.17)showing that K(q,x− y) is not positive semi-definite in this case.3.2.2 Modulus and supportLemma 3.4. For a pure rebit state |ψ〉 =∑x ψ(x) |x〉, non-negativity ofWψ implies that the function ψ has constant absolute value over its support.Proof. It is a known fact about positive semi-definite matrices that allof their principal minors are non-negative. Applied to the matrix Axy =K(q,x− y), this means that the determinant∣∣∣∣∣A00 A0xAx0 Axx∣∣∣∣∣=∣∣∣∣∣ψ(q)2 ψ(q)ψ(q + xψ(q)ψ(q + x) ψ(q)2∣∣∣∣∣≥ 0. (3.18)Expanding this equation givesψ(q)4 ≥ ψ(q)2ψ(q + x)2. (3.19)Let q,q′ ∈ supp(ψ) and use x = q + q′ in Equation 3.19. Then,ψ(q)4 ≥ ψ(q)2ψ(q′)2|ψ(q)| ≥ |ψ(q′)|. (3.20)Going through the same reasoning, but exchanging q and q′ we get |ψ(q′)| ≥|ψ(q)|, and thus|ψ(q)| = |ψ(q′)| ∀q,q′ ∈ supp(ψ) (3.21)59Lemma 3.5. For a pure rebit state |ψ〉 =∑x ψ(x) |x〉, non-negativity ofWψ implies that the support of ψ is an affine subspace of Zn2 . This meansthat supp(ψ) = q0 +N where q0 ∈ Zn2 and N is a subspace of Zn2 .Proof. Let q0 ∈ supp(ψ). To show that supp(ψ) is an affine subspace,we must show that if (q0 + x) ∈ supp(ψ) and (q0 + y) ∈ supp(ψ), thenq0+x + y ∈ supp(ψ). From Bochner’s theorem, Axy is positive semi-definite,so every principal minor is non-negative. In particular,∣∣∣∣∣∣∣A00 A0x A0yAx0 Axx AxyAy0 A0y Ayy∣∣∣∣∣∣∣≥ 0. (3.22)Expanding this determinant yieldsψ(q0)3[ψ(q0)3 + 2ψ(q0 + x)ψ(q0 + y)ψ(q0 + x + y)]− ψ(q0)4[ψ(q0 + x)2 − ψ(q0 + y)2 − ψ(q0 + x + y)2] ≥ 0. (3.23)We will now suppose that (q0 + x + y) /∈ supp(ψ), and reach a contra-diction. If this is the case, thenψ(q0)6 − ψ(q0)4[ψ(q0 + x)2 − ψ(q0 + y)2] ≥ 0. (3.24)But that’s impossible, since by the constant modulus property, ψ(q0 +x)2−ψ(q0 + y)2 = 0. This proves the claim that q0 + x + y ∈ supp(ψ), andtherefore that supp(ψ) = q0 +N for some subspace N ⊂ Zn2 .Lemma 3.6. If it is non-negative, the Wigner function of a pure real state|ψ〉 =∑x ψ(x) |x〉 isWψ(p,q) =12nδ(p0+N⊥)×(q0+N), (3.25)with q0 +N = supp(ψ) as given by Lemma 3.5, and p0 ∈ Zn260Proof. Suppose that p,q ∈ supp(Wψ). ThenWψ(p,q) =12n∑x∈Zn2(−1)(p,x)ψ(q)ψ(q + x) (3.26)is non zero by assumption, implying that ψ(q) 6= 0. Therefore, by Lemma3.5, q ∈ q0 +N . Furthermore, ψ(q + x) is zero unless x ∈ N . This givesWψ(p,q) =12n∑x∈N(−1)(p,x)ψ(q)ψ(q + x). (3.27)By the constant modulus property of Lemma 3.4,ψ(q)ψ(q + x) = ψ(q)2χ(x), (3.28)where χ is a character of N . Because it is a character, χ(x) = (−1)(p0,x) forsome p0 ∈ N . Plugging this in Equation 3.27, we getWψ(p,q) =12nψ(q)2∑x∈N(−1)(p+p0,x). (3.29)We would like to use the character orthogonality relation. Using thefact that Zn2 = N ⊕ N⊥ we see that the sum will be non-zero if and onlyif p ∈ p0 + N⊥. Combining this with the earlier established fact thatq ∈ q0 +N , we getWψ(p,q) = cδ(p0+N⊥)×(q0+N), (3.30)where c is an undetermined positive constant, which we now fix through therequirement that Wψ sums to one. The dimension of the support of Wψ is|supp(Wψ)| = |N | · |N⊥| = |Zn2 | = 2n. (3.31)We thus obtain the desired resultWψ =12nδ(p0+N⊥)×(q0+N). (3.32)61We have now collected all the lemmas needed to prove Hudson’s TheoremProof of Theorem 3.1. The content of Lemma 3.2 is thatWψ =12nδt+(N⊥×+N) ⇐⇒ |ψ〉 is a pure CSS state. (3.33)Combining this with Lemma 3.6, and identifying t = (p0,q0), we get thatevery non-negative pure state is a pure CSS state, which proves the theorem.3.3 CovarianceIn this section we show that CSS-ness preserving unitaries have a very simpleaction on the Wigner function, in that they can be interpreted as permuta-tions on the phase space. This property will be crucial in establishing thesimulability results of section 3.4. We start by proving the following lemmaLemma 3.7. Let g ∈ GCSS. Then there is a unique pair (F,x), composedof a symplectic matrix F ∈ Sp2n(Z2) and a vector x ∈ V such that for alla ∈ A,gTag† = (−1)[x,a]TFa. (3.34)Proof. Since g is a member of GCSS , we havegTag† = χ(a)Tφ(a) (3.35)for some functions χ : V → {±1} and φ : V → V . Using this observationon Ta+b yieldsgTa+bg† = χ(a + b)Tφ(a+b). (3.36)62But the following also holdsgTa+bg† = (−1)[a,b]gTag†gTbg†= (−1)[a,b]χ(a)χ(b)Tφ(a)Tφ(b)= (−1)[a,b](−1)[φ(a),φ(b)]χ(a)χ(b)Tφ(a)+φ(b).Comparing with Equation 3.36, this tells us thatφ(a + b) = φ(a) + φ(b) (3.37)andχ(a + b) = (−1)[a,b](−1)[φ(a),φ(b)]χ(a)χ(b). (3.38)Furthermore, conjugation by g preserves the commutation relations of Paulioperators, and these commutation relations are given by the symplecticproduct. Therefore, [a,b] = [φ(a), φ(b)]. This observation, combined withthe linearity of Equation 3.37 proves that φ is a symplectic transformationφ = F ∈ Sp2n(Zn2 ). It also allows us to deduce thatχ(a + b) = χ(a)χ(b), (3.39)so χ is a character. By a property of characters, there exists x ∈ V suchthat χ(a) = (−1)[x,a]. This proves the claim.We note in passing that the matrix F appearing in Lemma 3.7 is injective(has trivial kernel), because Clifford unitaries have a bijective action overthe Paulis under conjugation.Here is the statement of the theorem that establishes the conditions forcovariance of the rebit Wigner function.Theorem 3.8. For a n-rebit state ρ, Wρ is covariant under GCSS, in thesense that for all g ∈ GCSS,Wgρg†(u) = Wρ(Fu + t), (3.40)for a unique symplectic transformation F and unique vector t ∈ V63Proof. For any g ∈ GCSS , let (Fg,xg) be the symplectic transformation andvector appearing in Lemma 3.7. We start by using the latter lemma todetermine the action of g ∈ GCSS on the point operators.gAug† =12n∑a∈A(−1)[u,a]gTag†=12n∑a∈A(−1)[u+xg ,a]TFga=12n∑a∈A(−1)[Fg(u+xg),Fga]TFga=12n∑a∈A(−1)[Fg(u+xg),b]Tb= AFg(u+xg)= AFgu+tg ,where in the last line we defined the vector tg = Fgxg. It only remains toplug this in the expression for the Wigner functionWgρg†(u) =12nTr(Augρg†)=12nTr((g−1)Au(g−1)†ρ)=12nTr(AFg−1u+tg−1ρ)= Wρ(Fg−1u + tg−1).As we remarked in Section 1.2.3, it is impossible to have a Wigner func-tion that is covariant under all (real) Clifford operations. As another exam-ple, g = H1 acting on a state of two rebits does not transform the Wignerfunction covariantly, because it does not preserve positivity. Indeed,H1|00〉+ |11〉√2=|10〉+ |01〉√2. (3.41)64Figure 3.1: Example of a circuit whose distribution of outcomes canbe sampled by our efficient classical algorithm. The gates giand the measurements Ti are CSS-ness preserving unitaries be-longing to OIt can be checked that the initial state has positive Wigner function, whilethe final state has a negative Wigner function.3.4 Efficient classical simulation of CSS-CliffordcircuitsIn this section we prove the analog of Theorem 1.5 in the case of rebits. Here,instead of considering the full set of Clifford gates acting on stabilizer statesas in Chapter 1.2.2, we will consider the smaller set of CSS-ness preservingClifford gates and CSS measurements acting of CSS states, and we will callsuch circuits CSS-Clifford circuits. This restriction comes in play becausethe covariance of the Wigner function under our restricted set of gates is thecrucial property to establish an efficient classical simulation method. Theremainder of this section is dedicated to the proof of the following theoremTheorem 3.9. Every CSS-Clifford circuit acting on an initial product stateρ = ⊗ni=1ρi with non-negative Wigner function can be efficiently classicallysimulated.We prove this by explicitly giving a classical simulation algorithm. Typi-cal quantum circuits have probabilistic outcomes for the final measurements,a particular run of the circuit giving a string of outputs with some probabil-65ities. A classical simulation algorithm is an algorithm that allows efficientsampling from the probability distribution for the outcomes of the quantumcircuit.The algorithm we present is inspired from the interpretation of a positiveWigner function as being equivalent to a hidden variables model, and is verysimilar to the qudit algorithm of Veitch et al. [27]. Considering the phasespace as the hidden variable, we can update our ontic state at each step ofthe quantum circuit according to the covariance of the Wigner function.Classical simulation algorithm1. Sample a phase point u ∈ V according to the initial Wigner functionWρ(0)(u) = Wρ1(u1)Wρ2(u2) . . .Wρn(un). (3.42)2. For every unitary gate g ∈ GCSS, update the phase point according tou→ Fgu + tg, (3.43)where Fg is the symplectic matrix and tg is the vector in V thatdescribe the covariant action of g on Wρ such thatWgρg†(Fgu + tg) = Wρ(u). (3.44)3. For every measurement of a CSS-ness preserving Clifford unitary Ta ∈O, report the measurement outcome s ∈ {±1} with probabilityWE(s)(u),where E(s) = 12(I + sTa) is the POVM element corresponding to out-come s and u is the phase point as it was before the measurement.Then update u in a probabilistic manner according tou→u with probability Wρ(u)Wρ(u+a)u + a with probability 1− Wρ(u)Wρ(u+a) .(3.45)It is possible to condition further steps of the computation according66to the outcome of this measurement.To show that this algorithm is valid, we need to prove the followinglemma about the Wigner function of the post-measurement stateLemma 3.10. The Wigner function Wρ of the state obtained after measur-ing Ta ∈ O with outcome s ∈ {±1} on state ρ isWρ′(u) = kWρ(u)+Wρ(u+a)2 if s(−1)[u,a] = 10 otherwise,(3.46)where k is a constant independent of u.Proof. The proof is by explicit calculation. After the measurement, the stateof the system isρ′ =(I + sTa)ρ(I + sTa)Tr((I + sTa)ρ(I + sTa)). (3.47)67So the Wigner function of the post-measurement state isWρ′(u) ∝12nTr(AuI + sTa2ρI + sTa2)=122nTr(I + sTa2Tu[∑v∈ATv]T †uI + sTa2ρ)=122nTr(TuI + s(−1)[u,a]Ta2[∑v∈ATv]I + s(−1)[u,a]Ta2T †uρ)=122n∑v∈ATr(TuTvI + s(−1)[u+v,a]Ta2I + s(−1)[u,a]Ta2T †uρ)=122n∑v∈ATr(Tu1 + (−1)[v,a]4Tv[I + s(−1)[u,a]Ta]T †uρ)=122n+1∑v|[v,a]=0Tr(TuTv[I + s(−1)[u,a]Ta]T †uρ)=122n+1∑v|[v,a]=0Tr(TuTvT†uρ)+ s(−1)[u,a]∑v|[v,a]=0Tr(TuTv+aT†uρ)=122n+1∑v|[v,a]=0Tr(TuTvT†uρ)+ s(−1)[u,a]∑v|[v,a]=0Tr(TuTvT†uρ)=122n+1(1 + s(−1)[u,a])∑v|[v,a]=0Tr(TuTvT†uρ)=122n+2(1 + s(−1)[u,a])∑v∈ATr(Tu [Tv + TaTvTa]T†uρ)=14(1 + s(−1)[u,a])Tr ([Au +Au+a] ρ)=12δs,(−1)[u,a]Tr ([Au +Au+a] ρ)=12δs,(−1)[u,a] (Wρ(u) +Wρ(u + a)) .The normalization for W ′ρ is not obvious to calculate, but it is of no im-portance for the validity of the classical simulation, as the transition prob-abilities only depend on the ratio Wρ(u)Wρ(u+a) .68The previous lemma guarantees that the non-negativity of the Wignerfunction is preserved under measurements of observables in O. However,in contrast with the qudit case, non-negativity of the POVM and of theWigner function is not enough to guarantee that the output state has anon-negative Wigner function. For instance, both ρ = (I + X1Z2)/4 andthe POVM element E = (1 + Z1X2)/4 are positively represented, but thestate after measurement is ρ′ = (1+X1Z2)(1+Z1X2)/4, which has negativeWigner function. Indeed,A((1,1),(0,0)) =14(I −X1Z2 − Z1X2 + Z1Z2X1X2 + irrelevant terms) ,soWρ′((1, 1), (0, 0)) =12n(1− 1− 1− 1) < 0.69Chapter 4Contextuality for rebitsIn this chapter, we prove that there is a link between contextuality and uni-versal quantum computation. We find that negativity of the Wigner func-tion is necessary for contextuality of the state, but that it is not sufficient.We prove the existence of a condition that guarantees contextuality of thestate, provided its Wigner function is sufficiently negative, in a well-definedsense. We study a couple of examples that illustrate the situation, and howit differs from the case of qudits. Finally, we address a reasonable objectionconcerning the Mermin square and state-independent contextuality in rebitQCSI.4.1 Hidden-variable models of rebit QCSIIn Section 1.4.4 we discussed that some subtheories of quantum mechanicsmay or may not be contextual. In particular, some subtheories exhibitstate-dependent contextuality. As our scheme of rebit quantum computationis indeed a subtheory of quantum mechanics, we should first endeavor toidentify what are the features that should be reproduced by a non-contextualhidden variable model (NCHVM). First, we want our HVM to reproducethe correct measurement statistics for any rebit quantum state, but it is notimmediately obvious what set of measurements should be reproduced by theHVM.70Recall that in the scheme of rebit QCSI, the allowed measurements werethe CSS Pauli operatorsO = {X(ax), Z(az)|ax,az ∈ Zn2 }. (4.1)We thus want our HVM to reproduce the measurement statistics for allobservables in O, and to obey the value consistency condition on commutingobservablesλ(A)λ(B) = λ(AB) ∀A,B ∈ O such that [A,B] = 0. (4.2)Can we perform a measurement of observables in A that do not belong toO? Yes, for instance, if we want to measure X1Z2 on a system of two rebits,we can first measure X1 ∈ O ,then measure Z2 ∈ O, and finally multiplythe two outcomes together. The key point here is that set of observables forour measurement M = {X1Z2} can be decomposed into a set of commutingobservables in O as M ′ = {X1, Z2}.Let’s see what happens in an example where this decomposition fails tohold. For instance, the observables in M = {X1Z2, Z1X2} commute, so reg-ular quantum mechanics states that simultaneous measurement is possible.But if as previously, we attempt to decompose M into observables of O, weget M ′ = {X1, Z1, X2, Z2}, which clearly is not a commuting set of observ-ables. These observables cannot be measured without changing the state ofthe system, and therefore M = {X1Z2, Z1X2} is not a possible measurementin rebit QCSI.Let us formalize the above discussion with the following definitions.Definition 4.1. (Allowable measurements) The set of commuting observ-ables M ⊂ A is an allowable measurement if there exists a commuting setof observables M ′ ⊂ O such that the outcomes of M can be computed byknowing the outcomes of M ′. The set of all allowed measurement settingsis denoted by M71Given two operators Ta and Tb, we already know thatTaTb = (−1)(ux,bz)Ta+b.The following lemma gives a simplification of this property for observablesin M that will be very useful in the next sections.Lemma 4.2. Let M ⊂ A be a set of commuting observables. Then M ∈Mif and only if TaTb = Ta+bProof.Ta, Tb ∈M ⊂M ⇐⇒ {X(a), X(b), Z(a), Z(b)} all commute⇐⇒ (ux,bz) = (uz,bx) = 0⇐⇒ TaTb = +Ta+b (and [Ta, Tb] = 0)Applying this lemma to an example we previously considered, {X1, Z2, Z1X2} /∈M because if Ta = X1Z2 and Tb = Z1X2, thenTaTb = −Y1Y2 = −Ta+b. (4.3)We now give a mathematical description of the features that are requiredto be present in a NCHVM of rebit QCSI.Definition 4.3. (Non-contextual hidden variables model) A HVM describ-ing the quantum state ρ and the set of measurement settings M consistsof:• A set of internal (ontic) states S.• A probability distribution qρ over S.• Conditional probabilities p(sM |u),u ∈ S that describe the proba-bilities of the outcome sM = (s1, s2, . . . , s|M |) of a measurement inM ⊂M.72These objects are required to obey the following conditions1. There is a value assignment function λ, which assigns for every u ∈ S adefinite value to all observables O ∈ A, λu(O) = ±1. For all M ∈M,the conditional probabilities take the simple formp(sM |u) =∏i|Oi∈Mδsi,λu(Oi). (4.4)2. (Consistency of value assignments) For all M ∈ M, and all pairs ofobservables A,B ∈M such that AB ∈M ,λu(A)λu(B) = λu(AB) ∀u ∈ S. (4.5)3. (Reproduces quantum mechanics) Let pM,ρ be the probability distribu-tion that quantum mechanics predicts for the measurements outcomesin M , given an initial state ρ. Then the probabilities of the HVM aresuch that for all M ⊂M and all possible measurement outcomes sM,pM,ρ(sM ) =∑u∈Sp(sM|u)qρ(u). (4.6)Lemma 4.4. For any NCHVM of a n-rebit setting (ρ,M), S = Z2n2 , andfor all u ∈ S,λu(Ta) = (−1)[u,a] ∀Ta ∈ A, (4.7)so thatλu(Ta+b) = λu(Ta)λu(Tb) ∀Ta, Tb, Ta+b ∈ A, (4.8)or equivalentlyλu(Ta+b) = λu(Ta)λu(Tb) ∀Ta, Tb ∈ A such that [Ta, Tb] = 0. (4.9)Proof. Both sets of observables MX = {X(aX)|aX ∈ Zn2} and MZ ={Z(aZ)|aZ ∈ Zn2} are allowable sets of measurements, so the consistencycondition (2) of Definition 4.3 requires that the values of these observables73are determined by the single rebit observables:λu(Z(aZ)) =n∏i=1λu(Zi) (4.10)λu(X(aX)) =n∏i=1λu(Xi). (4.11)Furthermore, for any T(aX ,aZ) ∈ A, the set of observablesM = {Z(aZ), X(aX), T(aX ,aZ)} (4.12)is an allowable measurement, because [X(aX), Z(aZ))] = 0, by the defi-nition of A. Since also Z(aZ)X(aX) = T(aX ,aZ), consistency of the valueassignment givesλu(T(aX ,aZ)) = λu(Z(aZ))λu(X(aX)). (4.13)Using this equation in conjunction with equations 4.10 and 4.11, we see thatfor all observables in A their value is determined by the product of individuallocal observables Xi and Zi. Since these local observables take values ±1,the set of internal states S has dimension 22n and is isomorphic (as a set) toZ2n2 . Also, characters span the space of linear functions from Z2n2 to {±1},so we conclude that we can writeλu(Ta) = (−1)[u,a] ∀u ∈ S. (4.14)To finish the proof, we can see that Equation 4.8 follows directly fromthis form for the λu. Equation 4.9 also follows by noticing that if Ta, Tb ∈ A,then [Ta, Tb] ⇐⇒ Ta+b ∈ A.744.2 Conditions for contextuality4.2.1 A necessary condition for contextualityAs it was the case for qudits, the Wigner function is a valid NCHVM whenit is non-negative. We therefore have the following necessary condition forcontextualityTheorem 4.5. The physical setting (ρ,M) is contextual only if Wρ(u) < 0for some u ∈ V .Proof. The proof proceeds by showing that if the Wigner function is non-negative, then it satisfies all the points in Definition 4.3 of a NCHVM. Wetake the set of internal states as equal to the phase space: S = V , and theprobability distribution qρ over S is the Wigner function Wρ, which is a validprobability distribution because it is non-negative by our assumption. Themeasurement of a set M = {Ta(i)} ∈ M is represented by POVM elementsE(sM ) associated with the measurement outcomes. Their general form isE(sM ) =∏iI + siTa(i)2. (4.15)For simplicity, let us first consider the POVM element E(s) correspondingto the measurement of Ta with outcome s ∈ {±1}E(s) =12(I + sTa) . (4.16)ThenWE(s)(u) =12n+1Tr (Au(I + sTa)) (4.17)=122n+1∑b∈ATr((−1)[u,b]Tb(I + sTa))(4.18)=12n+1(1 + s(−1)[u,a])(4.19)=12nδs,(−1)[u,a](u). (4.20)75We can directly check that by defining p(sM|u) = 2nWE(s)(u), andλu(Ta) = (−1)[u,a], we satisfy points 1 and 3 of Definition 4.3.For a general POVM E(sM ) = E1(s1)E2(s2) . . . E|M |(s|M |), the Wignerfunction factorizes as2nWE(sM ) = 2n|M |WE1(s1)WE2(s2) . . .WE|M|(s|M|). (4.21)This can be proved recursively by using Lemma 4.2:WE1(s1)E2(s2)(u) =12n+2Tr (Au(I + s1Ta)(I + s2Tb))=122n+2∑c∈ATr((−1)[u,c]Tc(I + s1Ta)(I + s2Tb))=12n+2(1 + s1(−1)[u,a])(1 + s2(−1)[u,b])=12nδs1,(−1)[u,a](u)δs2,(−1)[u,b](u).Therefore, we obtain that2nWE(sM )(u) =∏i|Ta(i)δsi,(−1)[u,a(i)] . (4.22)Furthermore,pM,ρ(sM ) = Tr(E(sM )ρ) = 2n∑u∈VWE(sM )(u)Wρ(u). (4.23)And we see that p(sM |u) = 2nWE(sM )(u) is indeed a valid conditional prob-ability in the sense of Definition 4.3. It only remain to check point 2 ofthe definition, concerning the consistency of the assignment. Since we haveλu(Ta) = (−1)[u,a] and TaTb = Ta+b for all allowable measurements,λu(TaTb) = λu(Ta+b) = (−1)[u,a+b] = λu(Ta)λu(Tb). (4.24)We thus see that a non-negative Wρ fulfills all requirements of a NCHVM.764.2.2 A sufficient condition for contextualityWe now turn to the proof of a sufficient condition for contextuality. Perhapssurprisingly, the necessary condition of the previous section and the sufficientcondition do not coincide. Indeed, as will be shown in Section 4.3.1, thereexists states with negative Wigner function that are non-contextual.Our derivation of the sufficient condition will first require constructinga family of contextuality witnesses. Contextuality witnesses are linear func-tions of the quantum state ρ that take positive values for all NCHVMs, butthat are allowed by quantum mechanics to take negative values. To motivatethe construction of the witnesses, let us got back to an example we previ-ously considered of a system of two rebits and the observables Ta = X1Z2and Tb = Z1X2. We know already from Section 4.1 that these two operatorscannot be simultaneously measured in rebit QCSI, but we are still allowedto calculate their expectation values. Define the witnessWρ = 〈I + Ta + Tb + Ta+b〉ρ = 〈I +X1Z2 + Z1X2 − Y1Y2〉ρ. (4.25)This function can take negative values. Indeed, if ρ = |K2〉 〈K2|, where |K2〉is the stabilizer state with stabilizer 〈−X1Z2,−Z1X2〉, then Wρ = −2. Butnow consider the values thatW can take if we restrict ourselves to NCHVMs.The compatibility condition for the value assignments requires thatλ(X1Z2) = λ(X1)λ(Z2)λ(Z1X2) = λ(Z1)λ(X2)λ(Y1Y2) = λ(X1)λ(X2)λ(Z1)λ(Z2).Therefore, for any internal state in S, the witness evaluates to (1+λ(X1)λ(Z2))(1+λ(Z1)λ(X2)) ≥ 0. This is why W is a contextuality witness; in particular itidentifies |K2〉 as possessing state dependent contextuality.We can generalize this construction to create a large family of witnessfunctions. Looking back, we see that the important necessary property isthat we find a subspace U such that for all a,b ∈ U , λ(Ta+b) = λ(Ta)λ(Tb).Lemma 4.4 tells us that this will be the case if all [Ta, Tb] = 0 ∀a,b ∈ U , i.e.77if U is an isotropic subspace of V . We have thus motivated the statementof the following lemma.Lemma 4.6. The n-rebit setting (ρ,M) is contextual if there exists anisotropic subspace U ⊂ V with a basis B(U) = {a(1),a(2), . . . ,a(m)} suchthat the associated witness functionWB(U)ρ (x) =〈∑z∈Zm2[m∏i=1(−1)zixi]T∑i zia(i)〉ρ, (4.26)which is defined for arguments x ∈ Zm2 , takes at least one negative value.The factors (−1)zixi are there to allow all possible signs in the sum ofoperators that defines the witness.Proof. We show that the witness WB(U)ρ is indeed a contextuality witness,by assuming a NCHVM and showing that it can only take non-negativevalues. Evaluating the witness function for one particular state u ∈ S, wegetWB(U)λu (x) =∑z∈Zm2[m∏i=1(−1)zixi]λu(T∑i zia(i)). (4.27)Applying the fact that U is isotropic with Lemma 4.4 allows us to factorizethe witness asWB(U)λu (x) =∑z∈Zm2m∏i=1[(−1)xiλu(Ta(i))]zi (4.28)=m∏i=1[(−1)xiλu(Ta(i))](4.29)≥ 0. (4.30)Since the witness is positive for all u ∈ S, but can take negative values inquantum mechanics, this concludes the proof.The following lemma establishes a relationship between the witnessesand the Wigner function78Lemma 4.7. Let U be an isotropic subspace of Z2n2 with basis B(U) ={a(1),a(2), . . . ,a(m)}. Then there exists a set B˜ = {b(1),b(2), . . . ,b(m)}of vectors of Z2n2 such that [a(i),b(j)] = δij ∀i, j ∈ {1, ...,m}. For everyη(x) =∑i xia(i) ∈ U , define the vector η¯(x) =∑i xib(i). ThenWB(U)ρ (η(x)) = 2m∑v∈U⊥Wρ(v + η¯(x)). (4.31)Proof. We can use the operators Tη to reproduce the factor∏i(−1)xizi inEquation 4.26, and obtainWB(U)ρ (η(x)) =〈Tη¯(∑u∈UTu)T †η¯〉ρ. (4.32)We can simplify the above expression by noticing that∑u∈UTu =∑u∈Z2n2δu,UTu (4.33)=1|U⊥|∑u∈Z2n2∑v∈U⊥(−1)[u,v]Tu (4.34)=2m22n∑u∈Z2n2∑v∈U⊥TvTuT†v (4.35)=2m22n∑v∈U⊥TvA0T†v. (4.36)Substituting into the expression for the witness W, this givesWB(U)ρ (η(x)) =2m22n〈∑v∈U⊥Tη¯TvA0T†vT†η¯〉ρ(4.37)=2m2n∑v∈U⊥Tr (Aη¯+vρ) (4.38)= 2m∑v∈U⊥Wρ(v + η¯). (4.39)79We can finally prove the following theorem that gives a sufficient condi-tion for contextualityTheorem 4.8. The n-rebit setting (ρ,M) is contextual if there exists avector t ∈ V and a maximally isotropic U ⊂ V such that∑v∈UWρ(v + t) < 0. (4.40)Proof. Putting Lemmas 4.6 and 4.7 together, we obtain that (ρ,M) is con-textual if there exists an isotropic subspace U ⊂ V , and a vector t ∈ V suchthat∑v∈U⊥Wρ(v + t) < 0. (4.41)We are almost done, but we can make the condition stronger by con-sidering maximally isotropic subspaces. Every isotropic space U can beembedded in a maximally isotropic subspace, UM = U⊥M , and furthermorethere exists a space U¯ ⊂ V such thatU⊥ = UM ⊕ U¯ . (4.42)Therefore,∑v∈U⊥Wρ(v + t) =∑u∈U¯∑w∈UMWρ(u + w + t) . (4.43)In order for the left hand side to be negative, the bracketed terms in theabove equation need take negative values. This means that there exists at′ ∈ V such that∑w∈UMWρ(w + t′) < 0, (4.44)which proves the claim80Figure 4.1: Wigner function for the three-rebit GHZ-like state ρ =18(I−X1Z2Z3)(I−Z1X2Z3)(I−Z1Z2X3), which appears in thestate-dependent version of the Mermin star proof4.2.3 Example: Mermin starAs an example of Theorem 4.8, we use it to prove the state-dependent con-textuality of the Mermin star, which we have discussed already in Section1.4.3. Consider the three-rebit GHZ-like stateρ =18(I−X1Z2Z3)(I−Z1X2Z3)(I−Z1Z2X3) :=18(I−Ta)(I−Tb)(I−Tc),(4.45)whose Wigner function is shown in Figure 4.1.Let us take the maximally isotropic subspace U = span({a,b, c)} andthe vector t = 0. The following relations can be easily checked to holdTaTb = −Ta+b TaTc = −Ta+cTbTc = −Tb+c TaTbTc = Ta+b+c.These relations allow us to write ρ = 18(I−Ta−Tb−Tc−Ta+b−Ta+c−81Tb+c − Ta+b+c). With this, we obtain that∑u∈UWρ(u) =122n∑u∈U∑v∈A(−1)[u,v]Tr(Tvρ)=122n∑u∈U∑v∈ATr(Tvρ)=122n(−68)< 0,so the setting is contextual by virtue of Theorem 4.8.4.3 Contextuality and negativity4.3.1 Negativity and contextuality are not equivalentThe necessary condition for contextuality of Theorem 4.5 and the sufficientcondition of Theorem 4.8 do not match, as we have already alluded to.Theorem 4.5 establishes that all contextual setting have states with neg-ative Wigner function. However, if we know the Wigner Wρ of a state,merely possessing negativity is not enough to guarantee contextuality, andTheorem 4.8 tells us how much negativity we need. The necessary conditionfor contextuality of Theorem 4.5 and the sufficient condition of Theorem 4.8do not match, but is it only because of our failure to find a stronger sufficientcondition? It turns out that it is not the case, and we will illustrate this bystudying family of all one-rebit statesρ˜(x, z) =I + xX + zZ2. (4.46)The requirement that Tr(ρ) ≤ 1 for physical states enforces gives a con-straint x2 + z2 ≤ 1 on the range of the parameters x and z. Figure 4.2is a phase diagram for the states ρ˜(x, y), showing the regions of in param-eter space that Theorems 4.5 and 4.8 single out, as well as set of stateswith negative Wigner function. State with |x| + |z| ≤ 1 have non-negative82Figure 4.2: Phase diagram for the space of one-rebit states ρ˜. Thedark blue area corresponds to states with positive Wigner func-tion, which are non-contextual by virtue of Theorem 4.5. Thepale blue region shows the physical states that have negativeWigner function. The states that are identified as contextualby Theorem 4.8 fall outside the pale grey square.Wigner functions, so Theorem 4.5 identifies these as non-contextual. How-ever, states falling in the pale blue region have negative Wigner function,but are not identified as contextual by Theorem 4.8. Indeed, the latter the-orem does not identify any one-rebit state as contextual. This should notbe as surprise, since in Section 1.4.3, we pointed out the fact that singlequbits can be described by a NCHVM. The take home message from thisdiscussion is that for rebits, Wigner function negativity and contextualityare not equivalent.4.3.2 States for which negativity and contextuality coincideLet us consider the family of two-rebit states defined byρ(a, b) =(I + aX1Z2)(I + bZ1X2)4. (4.47)83Figure 4.3: Phase diagram for the two-rebit states ρ(a, b) defined byequation 4.47. All states in the square are physical, and statesin the dark blue area are non-contextual.Let a,b ∈ V be such that Ta = X1Z2 and Tb = Z1X2. Then, thenecessary condition for contextuality, that Wρ be negative, reads asWρ(u) =122n∑c∈ATr((−1)[u,c]Taρ)=12n(1 + (−1)[u,a]a+ (−1)[u,b]b− (−1)[u,a+b]ab)=12n(1 + (−1)[u,a]a+ (−1)[u,b]b− (−1)[u,a](−1)[u,b]ab)(4.48)=12n(1 + α(u)a+ β(u)b− α(u)β(u)ab) < 0, (4.49)where in the last line we have defined α(u) = (−1)[u,a] and β(u) = (−1)[u,b],functions that can take values ±1.Now let U = span({a,b}) and t ∈ V , and let us calculate the sufficientcondition of Theorem 4.8. Because of the isotropicity of U , all the characters84in Equation 4.48 will be of the form (−1)[u1+t,u2] = (−1)[t,u2]. Therefore,∑v∈UWρ(v + t) =(1 + (−1)[t,a]a+ (−1)[t,b]b− (−1)[t,a](−1)[t,b]ab).Depending on the value of t, the characters in the previous equation cantake any value in {±1}. Comparing the two conditions, we see that they arethe same, and we conclude that ρ(a, b) is contextual if1 + αa+ βb− αβab < 0 (4.50)for any possible value of α, β = ±1.It remains to determine what values of (a, b) describe physical states.Physical density matrices are positive semidefinite, meaning that〈ψ|ρ|ψ〉 ≥ 0 for all states |ψ〉 . (4.51)Due to the following easily verified relations,〈+, 0|ρ(a, b)|+, 0〉 =1 + a2〈+, 1|ρ(a, b)|+, 1〉 =1− a2〈0,+|ρ(a, b)|0,+〉 =1 + b2〈1,+|ρ(a, b)|1,+〉 =1− b2,we have that physical states obey |a| ≤ 1, |b| ≤ 1.Figure 4.3 shows the phase diagram for the family of states ρ(a, b) Thephysical states fill the unit square, while the non-contextual states are lo-cated in the dark blue area. The corners of the square represent the purestates that are joint eigenstates of X1Z2 and Z1X2, these states are locatedin the contextual phase at the points that are the furthest from the boundarywith the non-contextual phase.4.4 Contextuality and negativity as resources forquantum computationTheorem 4.9. In order to achieve computational universality in the schemeof QCSI with rebits, the resource states need to be contextual.85Remark. Contextuality of the resource states implies that they have neg-ative Wigner function, using Theorem 4.5.Proof. First, we show that if our scheme is capable of universal quantumcomputation, it is able to create a state that maximally reveals contextu-ality, i.e has WB(U)ρ (x) = −2 for some x. In section 4.2.2 we have alreadydemonstrated that the state ρ˜ = 14(I −X1Z2)(I −Z1X2) maximally revealscontextuality. Therefore, any universal scheme of computation with rebitsshould be able to create the encoded version of the state ρ˜, for whichWB(U)ρ˜ (0) = −2. (4.52)The second part of the proof is to show that if a quantum circuit createsρ˜, the state at every previous step of the computation also maximally revealscontextuality. Suppose that the state after the m-th step of a circuit, ρ(m) =ρ˜. We show that the state at the step just before ρ(m− 1) must also revealcontextuality maximally. There are two cases to consider:1. Step m of the circuit is a unitary gate.Because the witness function obeys Equation 4.31, the covariance un-der CSS-ness preserving unitaries of the Wigner function carries on toWB(U)ρWB(U)ρ (η) =WF−1B(U)g−1ρg (η + a¯). (4.53)This covariance guarantees that the state ρ(m − 1) also maximallywitnesses contextuality.2. Step m of the circuit is a projective measurement of an observableTc ∈ O. There are two possible situations(a) Tc commutes with all elements of the stabilizer of ρ˜.Then the measurement does not change the state. Indeed, if |ψ〉is stabilized by U , thenU(1± Tc) |ψ〉 = (I ± Tc)U |ψ〉 = (I ± Tc) |ψ〉 , (4.54)86so |ψ〉 still has the same stabilizer, and is therefore unchanged.(b) Tc does not commute with all elements of the stabilizer of ρ˜.Then Tc commutes with two of the non-trivial stabilizers of ρ˜, andanticommutes with the other. Let Ta and Tb be the two stabilizersthat commute with Tc, with Ta+b being the anticommuting one.Then〈Ta〉ρ˜ = 〈Tb〉ρ˜ = 0, (4.55)which reduces the expression for the witness function toWa,bρ˜ (η) = 〈I ± Ta+b〉ρ˜ ≥ 0. (4.56)But this contradicts our assumption 4.52. Therefore, case b)impossible.We have thus established that any circuit that creates a state that maxi-mally witnesses contextuality, must have an initial state that also maximallywitnesses contextuality.4.5 Mermin square revisitedAt first glance, the Mermin square proof of contextuality that was discussedin Section 1.4.3 only uses real observables, and should therefore be alsoapplicable to rebit quantum mechanics. If state-independent contextualityis present, this would pose serious problems for the interpretation of ourprevious result that contextuality of the intial state is necessary for quantumcomputation. The square is reproduced again here in Figure 4.4 for theconvenience of the reader.The key feature of rebit QCSI that allows us to avoid the conclusions ofthe Mermin proof is that not all commuting observables can be simultane-ously measured. Indeed, by the definition 4.1 of an allowable measurement,{X1Z2, Z1X2,−Y1Y2} /∈M. (4.57)87Figure 4.4: Reminder of the observables that appear in the ”Merminsquare” state-independent contextuality proof.The lower row of the diagram is thus removed, and we can no longer producethe algebraic contradiction necessary for the original Mermin proof. Wegeneralize these observations in the following lemmaLemma 4.10. Consider a system of n rebits with measurements restrictedto the set of observables O. Then there exists a consistent non-contextualvalue assignment λu : A → ±1, ∀u ∈ S. This means that there is nostate-independent contextuality in the scheme of rebit QCSI.Proof. We prove this by collecting the results of previous lemmas about thepossible value assignments and the commutation properties of observables.Lemma 4.4 requires that the value assignments λu : A → {±1},u ∈ V takethe formλu(Ta) = (−1)[u,a], (4.58)and satisfy the consistency conditionλu(Ta+b) = λu(Ta)λu(Tb) ∀Ta, Tb ∈ A such that [Ta, Tb] = 0. (4.59)Furthermore, for all allowable measurements M ∈M, Lemma 4.2 guar-antees that for all Ta, Tb ∈M ,Ta+b = TaTb. (4.60)So we see that all λu are valid value assignments for a NCHVM that describes88rebit QCSI with measurable observables restricted to O.We conclude this section with some general comments about Mermin-type proofs of contextuality, also known as parity proofs. The key ingredientfor these proofs is that there be a measurement M ∈ M such that forTa, Tb ∈M ,TaTb = −Ta+b. (4.61)Then, using Ta, Tb, Ta+b, and local Pauli observables Xi, Zi, it is possibleto formulate a state-independent proof of contextuality.According to the proof of Lemma 4.6, a witness functionWB(U) will onlybe able to take negative values if the isotropic subspace U ⊂ V containsTa, Tb such that TaTb = −Ta+b. In this way, we see that the existenceof a contextuality witness is very closely linked to the existence of a state-independent parity proof. What our operational restriction of rebit QCSIdoes is to prevent any measurement that has TaTb = −Ta+b. Indeed, if weallowed all real Clifford operations in our scheme, then the Mermin squareproof would apply, and it would be impossible to assert that contextualityis a resource for quantum computation.89Chapter 5ConclusionLet us summarize what have been the results of this work. We have seenthat two-dimensional systems are different from odd-prime dimensional inways that manifest themselves in the properties of the Wigner function. Inorder to have a useful covariant Wigner function for two level systems, wehad to restrict ourselves to systems of rebits, and we described a universalscheme of quantum computation for them. We have been able to define arebit Wigner that is covariant under CSS-ness preserving unitaries, and forwhich CSS states are positively represented. This allowed us to devise anefficient simulation method for positive states undergoing CSS-Clifford cir-cuits, and therefore establish negativity of the Wigner function as a resourcefor quantum computation.We have also studied contextuality, and found necessary and sufficientconditions that were based on the Wigner function. We found that thelimited gate set in our QCSI scheme prevented state-independent contextu-ality to occur. We could thus establish contextuality of the magic state asa resource for universal quantum computation. The previous observationsshow that we have managed to recover virtually all the properties enjoyedby the qudit case, with the exception that contextuality and negativity arenot equivalent: some states are negative but non-contextual.This research bridges some of the gap of understanding that was presenton the literature, as most of the preexisting work on negativity and contex-90tuality had been made on qudits, while quantum computation is typicallythought in terms of qubits. A limitation of this work is that we use rebits,which are relatively esoteric, and on which there has been virtually no ex-perimental work. We also have not addressed very deeply the reasons forthe differences between qubits, qudits, and rebits, but there are already ef-forts (not involving the author of this thesis) to use the machinery of groupcohomology to better understand the particularities of each case, and to ex-tend the results of this thesis from rebits to qubits. Another possible futureresearch direction would be to use Wigner functions to study measurementbased quantum computation (MBQC) [21]. It has been established [1] thatcontextuality in MBQC is necessary for classical universal computation. Itwould be interesting to use some of the insights from our research to under-stand the reason of this apparent difference.91Bibliography[1] J. Anders and D. E. Browne. Computational power of correlations.Phys. Rev. Lett., 102:050502, Feb 2009.doi:10.1103/PhysRevLett.102.050502. URLhttp://link.aps.org/doi/10.1103/PhysRevLett.102.050502. → pages 91[2] K. Banaszek and K. Wo´dkiewicz. Nonlocality of theeinstein-podolsky-rosen state in the wigner representation. Phys. Rev.A, 58:4345–4347, Dec 1998. doi:10.1103/PhysRevA.58.4345. URLhttp://link.aps.org/doi/10.1103/PhysRevA.58.4345. → pages 14[3] S. D. Bartlett, B. C. Sanders, S. L. Braunstein, and K. Nemoto.Efficient classical simulation of continuous variable quantuminformation processes. Phys. Rev. Lett., 88:097904, Feb 2002.doi:10.1103/PhysRevLett.88.097904. URLhttp://link.aps.org/doi/10.1103/PhysRevLett.88.097904. → pages 14[4] J. S. Bell. On the Einstein-Podolsky-Rosen Paradox. Physics, 1(3):195–200, 1964. ISSN 00653276. → pages 1, 26, 29, 32[5] C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin,and W. K. Wootters. Purification of noisy entanglement and faithfulteleportation via noisy channels. Phys. Rev. Lett., 76:722–725, Jan1996. doi:10.1103/PhysRevLett.76.722. URLhttp://link.aps.org/doi/10.1103/PhysRevLett.76.722. → pages 42[6] D. Bohm. A suggested interpretation of the quantum theory in termsof ”hidden” variables. ii. Phys. Rev., 85:180–193, Jan 1952.doi:10.1103/PhysRev.85.180. URLhttp://link.aps.org/doi/10.1103/PhysRev.85.180. → pages 31[7] S. Bravyi and A. Kitaev. Universal quantum computation with idealClifford gates and noisy ancillas. Physical Review A, 71(2):022316,2005. → pages 2, 25, 36, 4792[8] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane.Quantum error correction and orthogonal geometry. Phys. Rev. Lett.,78:405–408, Jan 1997. doi:10.1103/PhysRevLett.78.405. URLhttp://link.aps.org/doi/10.1103/PhysRevLett.78.405. → pages 5[9] W. B. Case. Wigner functions and weyl transforms for pedestrians.American Journal of Physics, 76:937–946, 2008.doi:10.1119/1.2957889. → pages 11[10] N. Delfosse, P. A. Guerin, J. Bian, and R. Raussendorf. WignerFunction Negativity and Contextuality in Quantum Computation onRebits. Physical Review X, 021003(5):1–23, 2015.doi:10.1103/PhysRevX.5.021003. → pages 6[11] A. Einstein, B. Podolsky, and N. Rosen. Phys. Rev. 47, 777 (1935):Can Quantum-Mechanical Description of Physical Reality BeConsidered Complete? Phys. Rev., 47:777–780, 1935. ISSN0031-899X. → pages 14, 26[12] K. S. Gibbons, M. J. Hoffman, and W. K. Wootters. Discrete phasespace based on finite fields. Physical Review A, 70(6):60, 2004. ISSN1050-2947. → pages 18, 21[13] D. Gottesman. Stabilizer Codes and Quantum Error Correction. PhDthesis, 1997. URL http://arxiv.org/abs/quant-ph/9705052. → pages 3, 4, 5[14] D. Gross. Hudson’s theorem for finite-dimensional quantum systems.Journal of Mathematical Physics, 47:1–17, 2006. ISSN 00222488. →pages 15, 17, 18[15] L. K. Grover. A fast quantum mechanical algorithm for databasesearch. 28th Annual ACM Symposium on the Theory of Computing,1996. → pages 1[16] M. Howard, J. Wallman, V. Veitch, and J. Emerson. Contextualitysupplies the ’magic’ for quantum computation. Nature, 510:351–355,2014. ISSN 0028-0836. → pages 2, 32[17] R. Hudson. When is the wigner quasi-probability densitynon-negative? Reports on Mathematical Physics, 6(2):249 – 252, 1974.ISSN 0034-4877. doi:http://dx.doi.org/10.1016/0034-4877(74)90007-X.URL http://www.sciencedirect.com/science/article/pii/003448777490007X.→ pages 1493[18] S. Kochen and E. P. Specker. The problem of hidden variables inquantum mechanics. Journal of Mathematics and Mechanics, 17:59–87, 1967. → pages 1, 29[19] N. D. Mermin. Hidden variables and the two theorems of John Bell.Reviews of Modern Physics, 65:803–815, 1993. ISSN 00346861. →pages 29[20] M. A. Nielsen and I. L. Chuang. Quantum Computation andQuantum Information: 10th Anniversary Edition. CambridgeUniversity Press, New York, NY, USA, 10th edition, 2011. ISBN1107002176, 9781107002173. → pages 1, 2, 3, 24, 32, 35[21] R. Raussendorf and H. J. Briegel. A one-way quantum computer.Phys. Rev. Lett., 86:5188–5191, May 2001.doi:10.1103/PhysRevLett.86.5188. URLhttp://link.aps.org/doi/10.1103/PhysRevLett.86.5188. → pages 2, 91[22] T. Rudolph and L. Grover. A 2 rebit gate universal for quantumcomputing. arXiv, page 2, 2002. URLhttp://arxiv.org/abs/quant-ph/0210187. → pages 35[23] P. Shor. Polynomial-time algorithms for prime factorization anddiscrete logarithms on a quantum computer. SIAMJ.Sci.Statist.Comput., 26, 1997. → pages 1[24] F. Soto and P. Claverie. J. Math. Phys., 24, 1983. → pages 14[25] R. W. Spekkens. Contextuality for preparations, transformations, andunsharp measurements. Physical Review A - Atomic, Molecular, andOptical Physics, 71(5), 2005. ISSN 10502947. → pages 27[26] R. W. Spekkens. Negativity and contextuality are equivalent notionsof nonclassicality. Phys. Rev. Lett., 101:020401, Jul 2008.doi:10.1103/PhysRevLett.101.020401. URLhttp://link.aps.org/doi/10.1103/PhysRevLett.101.020401. → pages 32[27] V. Veitch, C. Ferrie, D. Gross, and J. Emerson. Negativequasi-probability as a resource for quantum computation. NewJournal of Physics, 14:1–15, 2012. ISSN 13672630. → pages 2, 19, 32,6694[28] H. Weyl. Quantenmechanik und gruppentheorie. Zeitschrift fu¨rPhysik, 46(1-2):1–46, 1927. ISSN 0044-3328. doi:10.1007/BF02055756.URL http://dx.doi.org/10.1007/BF02055756. → pages 8[29] E. Wigner. On the quantum correction for thermodynamicequilibrium. Phys. Rev., 40:749–759, Jun 1932.doi:10.1103/PhysRev.40.749. URLhttp://link.aps.org/doi/10.1103/PhysRev.40.749. → pages 2, 8[30] W.-M. Zhang, D. H. Feng, and R. Gilmore. Coherent states: Theoryand some applications. Rev. Mod. Phys., 62:867–927, Oct 1990.doi:10.1103/RevModPhys.62.867. URLhttp://link.aps.org/doi/10.1103/RevModPhys.62.867. → pages 12[31] H. Zhu. Permutation symmetry determines the discrete Wignerfunction. arXiv, page 6, 2015. URL http://arxiv.org/abs/1504.03773. →pages 2295Appendix ACharacters and FouriertransformsThis appendix some of the mathematical concepts necessary to make senseof some sections of this thesis. References have been omitted, but it is allstandard material. We have tried at all times to avoid excessive generalityso as to be readily applicable to the body of this thesis.A.1 CharactersGiven a finite abelian group G with the group operation written in additivenotation, a character of G is a functionχ : G→ C (A.1)such that χ(g + h) = χ(g)χ(h). In other words, it is a one dimensionalrepresentation of G. The set of characters of G is denoted G∗, and it is afact about finite groups that they are isomorphicG ∼= G∗. (A.2)In the context of phase-space distributions, G = Znd , and the charactersare of the form χ : x 7→ ei2pixy/d for some y ∈ Znd .96Lemma A.1. Given a group G and any character χ of G,∑gχ(g) = 0 (A.3)for any character other that χ0 : g 7→ 1, in which case∑g χ0(g) = |G|Proof. If χ 6= χ0, then there exists an h ∈ G such that χ(h) 6= 1. Thenχ(h)∑gχ(g) =∑gχ(h)χ(g) =∑gχ(h+ g) =∑gχ(g). (A.4)Comparing the right-most side of the equation with the left-most side, weconclude that χ(h) = 1, a contradiction.Given two character χ, η ∈ G∗, we can use this property to define aninner product on the space of characters of G(χ, η) =1|G|∑g∈Gχ(g)η(−g). (A.5)This inner product makes the characters an orthonormal basis for theset of functions G→ Cn, where Cn = {ei2pix/n|x ∈ {0, 1, . . . , n− 1}}.A.2 Symplectic spaces, definitionsFor the following section, let V = Z2nd . We will use the notation SpN (F )for the space of symplectic matrices of dimension N ×N with entries in thefield F . Symplectic matrices preserve the symplectic form over the vectorspace that they act on:[Fu, Fv] = [u,v]. (A.6)Definition A.2. (Nondegenerate bilinear form) A bilinear form [·, ·] over Vis non degenerate if [u,v] = 0 ∀v implies that u = 0The usual symplectic product over V defined as [u,v] = uz ·vx−ux ·vzis a nondegenerate bilinear form.97Definition A.3. (Isotropic subspace) A subspace U of V is isotropic if∀u,v ∈ U, [u,v] = 0Definition A.4. (Maximally isotropic subspace) An isotropic subspace Uof V is maximally isotropic if it has the maximal dimension for which asubspace of V can be isotropic. This happens if and only if dim(U) = nLemma A.5. Any character χ of a non-degenerate symplectic space V canbe written as χ(u) = e2pii[u,w]/d for some w ∈ VProof. Using the fact that |V ∗| = |V | = 2n, we only need to prove that theset of characters {χw = e2pii[·,w]/d|w ∈ V } contains 2n different characters.Suppose ∃w,w′ such that χw = χw′ . Then we havee2pii[u,w]/d = e2pii[u,w′]/d =⇒ [u,w −w′] = 0. (A.7)But by the nondegeneracy of the symplectic product, this implies that w =w′.98"@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "2015-09"@en ; edm:isShownAt "10.14288/1.0166620"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Physics"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "Attribution-NonCommercial-NoDerivs 2.5 Canada"@en ; ns0:rightsURI "http://creativecommons.org/licenses/by-nc-nd/2.5/ca/"@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Wigner function negativity and contextuality in quantum computation with rebits"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/54594"@en .