Science, Faculty of
Physics and Astronomy, Department of
DSpace
UBCV
Herringer, Paul
Master of Science - MSc
University of British Columbia
Certain symmetry-protected topological (SPT) phases also possess the property that every state in the phase is a universal resource for measurement-based quantum computation (MBQC). These phases are called computational phases of quantum matter. Computational phases have been classified in 1D, and several examples are known in 2D. 2D computational phases are of interest because we can simulate any quantum computation using a 2D phase. Therefore, the classification of 2D phases may lead to a better understanding of the relationship between symmetry and quantum computation. Many known 2D phases have a projected entangled pair state (PEPS) representation where the local tensor symmetries define a quantum cellular automaton (QCA) acting on correlation space. However, not every tensor symmetry defines a QCA, which motivates the definition and study of a larger class of PEPS tensors called stabilizer tensors. Stabilizer tensors have symmetries that act as a tensor product of Pauli operators on correlation space but do not necessarily define a QCA. In this thesis, I present a classification of stabilizer tensors by their channel capacity for quantum wire. In particular, I consider the quantum wire capacity of translationally invariant, cylindrical PEPS constructed from stabilizer tensors and find that it falls into one of 13 classes. Furthermore, I prove that no other types of channel capacity exist for stabilizer tensors, regardless of the size of the cylinder. I also discuss the significance of this result for the classification of 2D computational phases along with possible next steps.
Classification of Quantum Wire inTensor Network States with a LocalPauli SymmetrybyPaul HerringerB.Sc. Honours in Physics, University of Calgary, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Physics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)October 2021© Paul Herringer 2021The following individuals certify that they have read, and recommend tothe Faculty of Graduate and Postdoctoral Studies for acceptance, the thesisentitled:Classification of Quantum Wire in Tensor Network States with aLocal Pauli Symmetrysubmitted by Paul Herringer in partial fulfillment of the requirements forthe degree of Master of Science in PhysicsExamining committee:Robert Raussendorf, Physics and Astronomy, UBCSupervisorMark van Raamsdonk, Physics and Astronomy, UBCSupervisory Committee MemberiiAbstractCertain symmetry-protected topological (SPT) phases also possess the prop-erty that every state in the phase is a universal resource for measurement-based quantum computation (MBQC) [21]. These phases are called com-putational phases of quantum matter. Computational phases have beenclassified in 1D, and several examples are known in 2D [21, 22, 26]. 2Dcomputational phases are of interest because we can simulate any quantumcomputation using a 2D phase. Therefore, the classification of 2D phasesmay lead to a better understanding of the relationship between symmetryand quantum computation.Many known 2D phases have a projected entangled pair state (PEPS)representation where the local tensor symmetries define a quantum cellularautomaton (QCA) acting on correlation space [26]. However, not every ten-sor symmetry defines a QCA, which motivates the definition and study of alarger class of PEPS tensors called stabilizer tensors. Stabilizer tensors havesymmetries that act as a tensor product of Pauli operators on correlationspace but do not necessarily define a QCA.In this thesis, I present a classification of stabilizer tensors by their chan-nel capacity for quantum wire. In particular, I consider the quantum wirecapacity of translationally invariant, cylindrical PEPS constructed from sta-bilizer tensors and find that it falls into one of 13 classes. Furthermore, Iprove that no other types of channel capacity exist for stabilizer tensors,regardless of the size of the cylinder. I also discuss the significance of thisresult for the classification of 2D computational phases along with possiblenext steps.iiiLay SummaryQuantum computers are widely expected to solve problems that classicalcomputers find intractable. The evidence for this claim rests on a rela-tively small number of examples where we have a quantum algorithm thatoutperforms the best classical algorithm. However, there is no general un-derstanding of why a quantum computer should be better than a classicalcomputer. One way to address this problem is through the dual lenses ofsymmetry and measurement-based quantum computing (MBQC). MBQCuses entangled states of quantum matter as the fuel for computations. Weknow that symmetry affects MBQC because when certain families of entan-gled states share symmetries, they also have the same degree of power forMBQC. These symmetric families of states are called computational phases.In my thesis, I study the amount of information that different computationalphases can process, which helps to clarify the role of symmetry in quantumcomputation.ivPrefaceThis thesis is the original, unpublished work of the author, Paul Herringer,in collaboration with Robert Raussendorf. The original research direction isdue to Robert Raussendorf. Some of the text in Chapters 1 and 7 previouslyappeared in my application to the 2022 NSERC Post-Graduate Scholarships(Doctoral) program.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Mathematical Methods . . . . . . . . . . . . . . . . . . . . . . 42.1 The Stabilizer Formalism . . . . . . . . . . . . . . . . . . . . 42.1.1 Symplectic Representation . . . . . . . . . . . . . . . 62.2 Tensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . 82.2.1 Tensor Diagrams . . . . . . . . . . . . . . . . . . . . . 82.2.2 Matrix Product States and Matrix Product Operators 92.2.3 Examples of MPS . . . . . . . . . . . . . . . . . . . . 102.2.4 Projected Entangled Pair States . . . . . . . . . . . . 113 Computation with Quantum States . . . . . . . . . . . . . . 123.1 The Circuit Model . . . . . . . . . . . . . . . . . . . . . . . . 123.2 The Measurement-Based Model . . . . . . . . . . . . . . . . 123.2.1 Quantum Wire . . . . . . . . . . . . . . . . . . . . . . 133.2.2 Single-Qubit Gates . . . . . . . . . . . . . . . . . . . 153.2.3 Universal MBQC . . . . . . . . . . . . . . . . . . . . 15viTable of Contents3.2.4 Resource States as Tensor Networks . . . . . . . . . . 154 Computation with Quantum Phases . . . . . . . . . . . . . . 184.1 Symmetry-Protected Topological Phases . . . . . . . . . . . 184.2 Computation in 1D SPT Phases . . . . . . . . . . . . . . . . 194.2.1 Tensor Symmetries . . . . . . . . . . . . . . . . . . . 194.2.2 Logical Tensors . . . . . . . . . . . . . . . . . . . . . 204.3 Computation in 2D SPT Phases . . . . . . . . . . . . . . . . 224.3.1 Quantum Cellular Automata . . . . . . . . . . . . . . 224.3.2 Logical Tensors in 2D . . . . . . . . . . . . . . . . . . 235 Beyond Quantum Cellular Automata . . . . . . . . . . . . . 265.1 GHZ Tensors . . . . . . . . . . . . . . . . . . . . . . . . . . . 265.2 Channel Capacity . . . . . . . . . . . . . . . . . . . . . . . . 275.3 Stabilizer Tensors and Stabilizer MPOs . . . . . . . . . . . . 285.3.1 Symmetry Inheritance . . . . . . . . . . . . . . . . . . 295.3.2 Canonical Form of a Bipartite Stabilizer . . . . . . . 305.4 Computing Channel Capacity Numerically . . . . . . . . . . 306 Classification of Channel Capacity . . . . . . . . . . . . . . . 336.1 Non-unitary Update Rules . . . . . . . . . . . . . . . . . . . 336.2 Chains of Symmetry . . . . . . . . . . . . . . . . . . . . . . . 346.3 Local Generators . . . . . . . . . . . . . . . . . . . . . . . . . 396.3.1 Bipartite Local Generators . . . . . . . . . . . . . . . 456.3.2 Periodic Boundary Conditions . . . . . . . . . . . . . 476.4 Removing the Bounds on n and d . . . . . . . . . . . . . . . 497 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.1 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54viiList of Tables6.1 Standard local generating sets of SL. . . . . . . . . . . . . . . 466.2 Correspondence between throughput classes and equivalenceclasses of Φ1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.3 Generators of ZL for each standard local generating set of SL. 49viiiList of Figures3.1 Example of a circuit model computation. Each qubit is pre-pared in a known state, acted on by unitary gates, and readout by projective measurement. . . . . . . . . . . . . . . . . . 134.1 Cone-shaped symmetries formed by the QCA of the cluster-like tensors (Eq. 4.17). . . . . . . . . . . . . . . . . . . . . . . 255.1 Heatmaps of channel capacity fall into 12 non-trivial classes. . 32ixList of Algorithms1 Channel Capacity from Lattice Symmetries . . . . . . . . . . 312 Channel Capacity from Chains of Symmetry . . . . . . . . . . 363 Standard form of Ω1 . . . . . . . . . . . . . . . . . . . . . . . 38xAcknowledgementsI am deeply grateful to my supervisor, Robert Raussendorf, for giving mefreedom and guidance in just the right amounts to help me grow as a physi-cist. His knowledge, patience, kindness, and enthusiasm have been essentialto navigating my degree and completing this thesis. I am also thankful to thecurrent and former members of the Quantum Information Group at UBC,especially Arnab Adhikary, Oleg Kabernik, Cihan Okay, and Michael Zurel,for making me feel welcome and sharing many interesting conversations.Finally, I wish to thank my family and friends for being a constant sourceof laughter, love, and support.xiChapter 1IntroductionQuantum mechanics describes the physics of light and matter at tiny scaleswith great accuracy. Unfortunately, the price to be paid for accuracy is scal-ability because the amount of information required to describe a quantumsystem scales exponentially in the system size. However, along with thiscurse of dimensionality comes a promise: that the very difficulty of simu-lating quantum systems may point to their usefulness for solving specificclassically intractable problems. It is this promise that drives the field ofquantum computation.This thesis deals with a scheme for quantum computation called mea-surement based quantum computation (MBQC) [20]. The central tenet ofMBQC is that it is possible to perform any quantum computation usingonly local measurements on a many-body quantum system, provided thatthe system has been prepared in a particular type of entangled state calleda resource state. Thus in the context of MBQC, computational power isassociated with resource states, and resource states alone.This focus on resource states puts the study of MBQC at the crossroadsof quantum information theory and condensed-matter physics. It turns outthat resource states are exceedingly rare in Hilbert space for the surprisingreason that most states are too entangled to be useful [10]. However, in thepresence of symmetry, resource states are more prevalent; at zero tempera-ture, there are symmetry-protected phases of quantum matter where everystate in the phase is a resource state for MBQC [21, 22]. Such phases arecalled computational phases.Over the last decade, there has been a push to understand and clas-sify resource states using symmetry. For 1D spin systems, this has led toa relatively mature classification of computational phases that adopts thetools of group cohomology from condensed-matter physics [3, 5, 16, 19, 24].Unfortunately, 1D is not so attractive from a practical standpoint becausethe MBQC protocol requires two spatial dimensions to perform arbitraryquantum computations.To date, there are several examples of 2D computational phases but noclassification scheme [21, 26]. However, many of the known 2D computa-1Chapter 1. Introductiontional phases can be understood via tensor networks and quantum cellularautomata (QCA) [26].A tensor network is a way of writing a large tensor – for instance, thestate of a many-body quantum system – as the contraction of many smaller“local” tensors. In 2D computational phases, these local tensors may bedescribed by their symmetries. For many known computational phases,these symmetries are associated with a QCA: a local, unitary update rule.The QCA encodes the effect of local measurements on the tensor networkand ensures that local measurements induce a local, unitary evolution ofthe tensor network. It turns out that this is precisely the type of evolutionrequired for MBQC, thus a tensor network whose symmetries define a QCAis a resource state [26].Furthermore, within a symmetry-protected computational phase, thesame QCA persists as long as the global symmetry remains unbroken. Themajority of 2D computational phases that we know of are associated with aQCA in this manner [26]. However, while every QCA may be constructedfrom a local tensor symmetry, it is not the case that every local tensorsymmetry gives rise to a QCA, and therefore QCA are not sufficient toclassify 2D computational phases.To understand what happens when there is no QCA, I studied the moststraightforward MBQC protocol, quantum wire. To implement quantumwire means to shuttle quantum information across a resource state usinglocal measurements – in other words, quantum teleportation. Quantumwire is a prerequisite for full MBQC but has the advantage of simplicity.To be precise, I consider a 2D square lattice of spin-1/2 particles on acylinder with circumference n and depth d. This system can be describedby a tensor network where the local tensors obey symmetry constraints.Given the local tensor symmetries, one can construct the state of the entirecylinder and determine the number of qubits of information that can beshuttled from one end to the other. This quantity is called the channelcapacity of the quantum wire. If the tensor symmetries define a QCA, thenthe channel capacity is maximal and equal to n for any value of d. If thereis no QCA, then different forms of channel capacity as a function of n andd may arise.In the early stages of research for this thesis, I wrote a program tocompute the channel capacity for every local tensor symmetry that acts bythe Pauli operators. I call these tensors stabilizer tensors; they include sometensors that define QCA, along with many others that do not. The output isinteresting because there are many possible symmetries, yet there are only 12non-trivial types of channel capacity. This result suggests that the tensor2Chapter 1. Introductionsymmetries – and the corresponding quantum states – may be classifiedby their channel capacity for quantum wire. However, the computation islimited to relatively small lattice sizes. The main result of this thesis is aproof that this classification is complete, that is, no other forms of channelcapacity exist regardless of the lattice size.The thesis is organized into seven chapters as follows. Chapter 2 reviewssome mathematical methods used for the description of many-body quantumstates. Chapters 3 and 4 explain measurement-based quantum computation,resource states, quantum cellular automata, and computational phases ingreater detail. Chapter 5 outlines the research program and includes apresentation of my numerical results. In Chapter 6, I develop a formalismto describe the numerical results and prove that the classification impliedby the numerics is complete. Finally, Chapter 7 discusses the significance ofthis classification scheme and highlights the possible next steps.3Chapter 2Mathematical Methods2.1 The Stabilizer FormalismThe stabilizer formalism is a powerful technique that leverages symmetry toefficiently describe quantum states, unitary dynamics, and projective mea-surements. However, efficiency often comes at the cost of generality, and thestabilizer formalism is no exception: it applies exclusively to states whosesymmetries are tensor products of the Pauli operators.Definition 1. The single-qubit Pauli group is the group of observables gen-erated by the Pauli X and Z operators:P1 = ⟨X,Z⟩ . (2.1)The n-qubit Pauli group Pn is the n-fold tensor product of P1.Let |ψ⟩ be any n-qubit quantum state, then the Hilbert space where|ψ⟩ lives is Hn = (C2)⊗n with dimension 2n. Now suppose we give |ψ⟩ asymmetry g1 ∈ Pn. The eigenvalues of g1 are ±1, so the eigenspaces of g1divide Hn into two pieces, each with dimension 2n−1. Clearly |ψ⟩ lies in the+1 eigenspace, because g1 |ψ⟩ = |ψ⟩. Already we can see that the presenceof symmetry has a significant effect, because a single symmetry has halvedthe state space of |ψ⟩.Next, let us give |ψ⟩ another, independent symmetry g2 ∈ Pn. To besymmetries of the same state, g1 and g2 must commute, so they generate anabelian subgroup of Pn. Recall that commuting operators can be simultane-ously diagonalized, so it is perfectly fine for |ψ⟩ to be in the +1 eigenspaceof both g1 and g2. This halves the state space of |ψ⟩ again; now it hasdimension 2n−2.Continuing the pattern, we could keep adding independent and com-muting elements of Pn to the symmetry group of |ψ⟩. Each addition woulddecrease the state space of |ψ⟩ by a factor of two, and eventually, the sym-metries would specify a unique quantum state. Note that it would onlytake n independent symmetries to get to this point, which is a considerable42.1. The Stabilizer Formalismimprovement over the 2n parameters required to specify a general n qubitquantum state.Alternatively, we could have stopped short of specifying a unique stateby letting |ψ⟩ have only n − k independent symmetries. In that case, thesymmetry constraints would describe a vector space V ⊂ Hn with dimension2k. Regardless of how many symmetries there are, they form a group S =⟨g1, . . . , gn−k⟩ such that g |ψ⟩ = |ψ⟩ for all g ∈ S and |ψ⟩ ∈ V . This groupis called the stabilizer of |ψ⟩ if |ψ⟩ is a unique state, and the stabilizer of Votherwise. Individual elements of S are called stabilizers of |ψ⟩ or V . Moreformally, we have the following definitions.Definition 2. An n-qubit stabilizer group is an abelian subgroup S ⊂ Pnwith 1 < rank(S) ≤ n.Definition 3. An n-qubit stabilizer state is an n-qubit quantum stateuniquely specified by a stabilizer group S ⊂ Pn.Stabilizer states capture a single point in the evolution of a quantumsystem, but the stabilizer formalism also includes the unitary evolution ofstabilizer states. To understand how, consider a unitary operator U actingon a stabilizer state |ψ⟩, and let g ∈ S be any stabilizer of |ψ⟩:U |ψ⟩ = Ug |ψ⟩ = UgU †U |ψ⟩ . (2.2)A more suggestive form of Eq. 2.2 is UgU †(U |ψ⟩) = U |ψ⟩, which says thatthe stabilizers of U |ψ⟩ are simply the stabilizers of |ψ⟩, conjugated by U .If U |ψ⟩ is to be a stabilizer state as well, then we must have UgU † ∈ Pnfor all g ∈ S. The set of unitary operators that satisfy this property forma group called the Clifford group. In other words, the Clifford group is thenormalizer of Pn in the unitary group U(2n). However, in the context ofquantum states a global phase is irrelevant, therefore the Clifford group issometimes defined modulo phases [14]. In this thesis, I will adopt the latterdefinition.Definition 4. The n-qubit Clifford group isCn = {U : UPnU † = Pn}/U(1). (2.3)Projective measurement of stabilizer states is not directly relevant tothis thesis. Therefore, we will not discuss measurement in the stabilizerformalism in great detail. Suffice it to say that if we have a stabilizer state|ψ⟩ and wish to describe the measurement of some observable h ∈ Pn, thenthe stabilizer of the post-measurement state |ψ′⟩ is given by a simple set ofupdate rules for the stabilizers of |ψ⟩. For a full explanation, see [7] or [18].52.1. The Stabilizer Formalism2.1.1 Symplectic RepresentationThe Pauli group has a useful representation as a vector space over the finitefield F2. In this representation, the elements of Pn (up to phase) are mappedto binary vectors ξ = (ξX , ξZ) ∈ F2n2 . The vector ξ corresponds to anoperator g(ξ) ∈ Pn as follows [26]:g(ξ) =n⊗i=1XξXii ZξZii . (2.4)In other words, ξX lists the sites where there is an X, and ξZ lists the siteswith a Z. For example,g(0, 0) = I, g(1, 0) = X, g(1, 1) = Y, g(0, 1) = Z. (2.5)Multiplication of Pauli operators corresponds to addition of binary vectors,that isg(ξ)g(η) ∼ g(ξ + η mod 2), (2.6)where ∼ denotes equality up to phase. Note that Eq. 2.6 ignores an impor-tant aspect of the Pauli group, namely the commutation relations. Theserelations are recaptured by defining a symplectic formω(ξ, η) =n∑i=1ξXi ηZi + ξZi ηXi mod 2 (2.7)such thatg(ξ)g(η) = (−1)ω(ξ,η)g(η)g(ξ). (2.8)In matrix form, Eq. 2.7 becomesω(ξ, η) = ξTΛη mod 2, (2.9)whereΛ =(0 InIn 0). (2.10)As a vector space equipped with a symplectic form, F2n2 is called a symplecticvector space. From the above discussion, we can see that F2n2 is isomorphicto the Pauli group up to phase, that is F2n2 ∼= Pn/U(1).Every symplectic vector space has a symplectic basis, and the propertiesof symplectic bases reveal much about the properties of symplectic vectorspaces. A symplectic basis has the defining property that each basis vectorhas a nonzero symplectic product with exactly one other basis vector.62.1. The Stabilizer FormalismDefinition 5. A symplectic basis {e1, . . . , en, e¯1, . . . , e¯n} is a basis that sat-isfies ω(ei, e¯j) = δij and ω(ei, ej) = ω(e¯i, e¯j) = 0.Definition 5 implies that the dimension of a symplectic vector space mustbe even because symplectic basis vectors come in pairs. It is also helpfulto know that the symplectic group acts transitively on the set of symplecticbases, i.e., there is a symplectic transformation that maps between any twosymplectic bases [1].Definition 6. A subspace V ⊂ F2n2 is isotropic if it satisfies ω(ξ, η) = 0 forall ξ, η ∈ V .An isotropic subspace with dimension n is called maximally isotropicbecause no isotropic subspace has dimension larger than n. To see this,note that the basis for any maximally isotropic subspace is exactly one-halfof a symplectic basis, thus it is impossible to add another basis vector thatsatisfies Definition 6. Another way to think about isotropic subspaces is interms of the orthogonal complement of V :V ⊥ = {ξ ∈ F2n2 : ω(ξ, η) = 0 for all η ∈ V }. (2.11)With this definition, we can see that V is isotropic if V ⊆ V ⊥, and maximallyisotropic if V = V ⊥.Isotropic subspaces of F2n2 represent stabilizer groups because they cor-respond to abelian subgroups of Pn, and maximally isotropic subspaces rep-resent stabilizer states because they correspond to rank n stabilizer groups.Note that the symplectic representation disregards relative phases betweenelements of a stabilizer group. For example, an isotropic subspace with ba-sis {ξ, η} is the symplectic representation of four different stabilizer groupsgenerated by {g(ξ), g(η)} with relative phases {±1,±i}.If stabilizer states correspond to isotropic subspaces of F2n2 , what is theequivalent of a Clifford unitary? Clifford unitaries map Pauli operators toPauli operators under conjugation and leave commutation relations invari-ant, i.e.[UgU †, UhU †]= [g, h] for g, h ∈ Pn. In the symplectic represen-tation, conjugation of g(ξ) by a Clifford unitary U corresponds to a linearoperator M(U) : F2n2 → F2n2 acting on ξ:Ug(ξ)U † ∼ g(Mξ). (2.12)The action ofM on any pair of vectors ξ and η must preserve the symplecticform, i.e. ω(Mξ,Mη) = ω(ξ, η). In matrix form,ξTMTΛMη = ξTΛη =⇒ MTΛM = Λ. (2.13)72.2. Tensor NetworksMatrices that satisfy Eq. 2.13 are called symplectic matrices or symplec-tic transformations. The set of symplectic matrices forms the binary sym-plectic group Sp2(2n). This group plays the role of the Clifford group inthe symplectic representation, in the sense that for any U ∈ Cn there ex-ists M ∈ Sp2(2n) that satisfies Eq. 2.12 [1]. However, neglecting phaseimplies that Ug(ξ)U † ∼ g(ξ) for any U ∈ Pn, so to be precise we haveSp2(2n)∼= Cn/Pn.2.2 Tensor NetworksAnother tool for the efficient description of many-body quantum states isthe tensor network formalism. Like the stabilizer formalism, it achieves thisefficiency at the cost of specializing to a particular class of quantum states.However, unlike the stabilizer formalism, this class of states does not have aparticular type of symmetry but rather a particular entanglement structure.Specifically, tensor networks are efficient at representing short-range en-tangled states [4]. Physically, short-range entangled states are associatedwith local Hamiltonians, that is, Hamiltonians where any site interacts witha finite set of its neighbors, independently of the system size. Locality isa reasonable assumption for Hamiltonians that occur in nature or can beengineered in the lab. Consequently, the use of tensor networks has becomewidespread in condensed-matter physics [2, 4]. This section will review ten-sor network notation and introduce some relevant tensor network structures.2.2.1 Tensor DiagramsIn the tensor network formalism, a tensor of rank r is represented by a shapewith r “legs” branching off. Each leg denotes one index of the tensor. Whentwo indices are set equal to each other and summed over, the correspondinglegs are joined. I will also adopt the convention that the leg of a vector |v⟩points to the right, while the leg of a dual vector ⟨v| points to the left. SeeFig. 2.1 for some examples of tensors and tensor operations in graphicalform.82.2. Tensor Networks(i) (ii) (iii) (iv)(v) (vi) (vii)Figure 2.1: Tensor diagrams for (i) |ψ⟩. (ii) ⟨ψ|. (iii) Matrix. (iv) Rank 3tensor. (v) A |ψ⟩. (vi) ⟨ψ|A |ψ⟩. (vii) Tr(A).2.2.2 Matrix Product States and Matrix Product OperatorsConsider an open 1D chain of n qudits, each living in a d-dimensional Hilbertspace Hi = Cd. The quantum state of this system can be written as a unitvector in the dn-dimensional Hilbert space Hn =⊗ni=1Hi. That is,|ψ⟩ =d∑s1,...,sn=1As1,...,sn |s1 . . . sn⟩ , (2.14)where {|si⟩} is an orthonormal basis for Hi, and As1,...,sn is a rank n ten-sor containing the normalized amplitudes of |ψ⟩ with respect to this basis.Graphically, we represent |ψ⟩ by the amplitude tensor A:|ψ⟩ = . (2.15)As1,...,sn can be decomposed into the product of n matrices using thesingular value decomposition (SVD). This form of |ψ⟩ is called a matrixproduct state (MPS):|ψ⟩ =d∑s1,...,sn=1⟨R|An[sn]An−1[sn−1] . . . A1[s1] |L⟩ |s1 . . . sn⟩ , (2.16)where Aj are rank-3 tensors containing one D × D matrix Aj [si] for eachvalue of si, and the vectors |L⟩ and |R⟩ encode the boundary conditions. If|ψ⟩ is translation-invariant then the tensors are all equal, i.e. Aj = A. Thedimensions d and D are called the physical dimension and bond dimension92.2. Tensor Networksof the MPS, respectively. These names are motivated by the tensor diagramof an MPS:|ψ⟩ = . (2.17)In the diagram, the legs pointing upwards represent the indices si. They arecalled physical legs because each si indexes the eigenvalues of a local observ-able. The contracted legs which form “bonds” between matrices at neighbor-ing sites are called virtual legs because the matrices A[si] are mathematicalconstructs rather than physical observables. However, this observation doesnot mean that A[si] are not helpful; among other things, they encode thequantum correlations between sites. Therefore, the D-dimensional vectorspace where A[si] act is called correlation space.Operators acting on MPS are called matrix product operators (MPOs).Graphically, MPOs are similar to MPS, except that MPOs have two physicallegs at each site. Contracting an MPO with an MPS yields a new MPS, asshown in Eq. 2.18:= . (2.18)2.2.3 Examples of MPSTwo well-known MPS have particular importance for this thesis: the clus-ter state [20] and the GHZ state [8]. Both are entangled states, but thecluster state is a universal resource for MBQC1 while the GHZ state is not.Unraveling the reasons behind this observation is part of the motivation forthis thesis. Here are the 1D versions of these states in MPS form, partly toprovide concrete examples of the tensor network formalism and partly as apreview for later sections.The 1D cluster state |CL⟩ is stabilized by S = ⟨Zi1XiZi+1⟩. On twoqubits, we have|CL⟩ = 12(|00⟩+ |01⟩+ |10⟩ − |11⟩). (2.19)The MPS form of the cluster state has the following matrices in the compu-tational basis {|0⟩ , |1⟩} [9]:A[0] = |+⟩⟨0| A[1] = |−⟩⟨1| , (2.20)1In fact, the cluster state is the original resource state [20].102.2. Tensor Networkswhere |±⟩ = (|0⟩ ± |1⟩)/√2 are the eigenstates of X. Taking the boundaryconditions to be |L⟩ = |0⟩ and ⟨R| = ⟨1|, it is straightforward to verify thatEq. 2.16 reproduces the 2-qubit cluster state (Eq. 2.19).The 1D GHZ state is stabilized by S = ⟨∏iXi, ZiZi+1⟩, and on n qubitsit has the state vector|GHZ⟩ = 1√2(|0⟩⊗n + |1⟩⊗n). (2.21)The MPS form of the GHZ state is given by the matrices [4]A[0] = |0⟩⟨0| A[1] = |1⟩⟨1| , (2.22)with boundary conditions |L⟩ = |+⟩ and ⟨R| = ⟨+|.2.2.4 Projected Entangled Pair StatesThe extension of MPS to two dimensions are called Projected Entangled PairStates (PEPS)2. Dealing with PEPS is where the tensor diagram notationcomes into its own, for drawing a PEPS tensor is as easy as adding someextra virtual legs to an MPS tensor. Eq. 2.23 shows the tensor diagram of aPEPS on a square lattice with periodic boundary conditions in the verticaldirection:(2.23)One difference between MPS and PEPS is the class of states which theycan represent. In 1D, it has been shown that every MPS is the ground stateof a local, gapped Hamiltonian, and vice versa [4]. In 2D, there is no suchguarantee. However, both PEPS and resource states exhibit strong localcorrelations and an area law for entanglement entropy, and many states innature and the lab have a PEPS representation [4]. Furthermore, under theassumption of translation invariance, the properties of a PEPS are encodedin a single tensor, which is a very efficient representation.2It might be more accurate to say that the restriction of PEPS to 1D yields MPS [2],but I find it easier to start with 1D.11Chapter 3Computation with QuantumStates3.1 The Circuit ModelThere are two types of processes in quantum mechanics: unitary evolu-tion and projective measurement. Unitary evolution is deterministic andreversible, while a projective measurement is probabilistic and irreversible.The circuit model of quantum computation requires both types of processes.A circuit model computation separates into three steps: initialization,manipulation, and readout. In the first step, we prepare several qubitsin a known state. Usually, each qubit is prepared separately in the +1eigenstate of the Pauli Z operator, denoted |0⟩, so that the multi-qubit state|0⟩⊗n constitutes the input for the computation. This convention shifts theburden of preparing more complicated input states to the second step of thecomputation.In the second step, we perform unitary operations or “quantum gates” onthe prepared qubits. A set of quantum gates is universal if it acts transitivelyon the set of n-qubit quantum states, which means that a universal gate setgenerates the group U(n). More practically, having a universal gate set atour disposal makes it possible to map any input state to any output stateby applying a sequence of gates from the set.In the third and final step, we take projective measurements of some orall of the qubits and record the measurement outcomes. These outcomes areprobabilistic, but we can recover an accurate picture of the output state byrepeating the computation many times. An example of quantum computa-tion in the circuit model is shown in Fig. 3.1.3.2 The Measurement-Based ModelIn the circuit model, state preparation is often an afterthought, and the focusis on the set of quantum gates that can be performed. However, there is an123.2. The Measurement-Based Model|0⟩UUU|0⟩U|0⟩ U|0⟩ UFigure 3.1: Example of a circuit model computation. Each qubit is preparedin a known state, acted on by unitary gates, and read out by projectivemeasurement.alternative model of quantum computation where state preparation takescenter stage, namely measurement-based quantum computation (MBQC)[20]. In MBQC, the input state is a particular type of entangled state calleda resource state. Given a resource state, MBQC is a method for simulatingthe unitary gates of the circuit model using only local measurements. If aresource state can simulate any quantum circuit by local measurements, itis called a universal resource for MBQC.The circuit model encourages us to think of qubits as physical objectson which we do various operations. However, in MBQC, it is often helpfulto think of a “logical qubit” as an abstract packet of information encodedin one or many physical qubits depending on the situation. To emphasizethe distinction between physical and logical qubits, I will reserve the termqubit for logical qubits and refer to physical qubits as spins.3.2.1 Quantum WireMBQC is best understood with the help of an example. The followingexample closely follows [29] but specializes to the case of simulating a singlegate from the circuit model: the identity gate. Although this gate is trivial inthe circuit model, it has great significance in MBQC. Indeed, every operationin MBQC can be thought of as a variation on the identity gate, and theability to simulate the identity gate is an essential prerequisite for simulatingother gates.Consider two spins, the first prepared in an unknown state |ψ⟩ = α |0⟩+β |1⟩ and the second prepared in |+⟩. To create entanglement between the133.2. The Measurement-Based Modelspins, we can apply the control-Z operator CZ. CZ does nothing if the firstspin is in the state |0⟩ and applies Z to the second spin if the first spin is inthe state |1⟩:CZ1,2 |0⟩1 ⊗ |ϕ⟩2 = |0⟩1 ⊗ |ϕ⟩2CZ1,2 |1⟩1 ⊗ |ϕ⟩2 = |1⟩1 ⊗ Z2 |ϕ⟩2 .(3.1)After CZ1,2 is applied, our spins are in the entangled stateα |0+⟩+ β |1−⟩ . (3.2)Next, let us measure the first spin in the X basis |±⟩ with eigenvalues (−1)sfor s ∈ {0, 1}. Putting everything together, we have⟨±|1CZ1,2 |ψ⟩1 ⊗ |+⟩2 = ⟨±|1 (α |0+⟩+ β |1−⟩) = HZs |ψ⟩2 , (3.3)where H = (X + Z)/√2 is the Hadamard operator.What we have done here is teleport the state |ψ⟩ from the first spin to thesecond spin, modulo a unitary operator HZs. This “byproduct operator”is random because it depends on the measurement outcome s. However, ifwe record the measured value of s, then we know the byproduct operator.Furthermore, the byproduct operator is unitary; therefore, we can compen-sate for it deterministically. The critical point is that the state of the logicalqubit |ψ⟩ remains intact.Keeping in mind the 2-spin case, suppose we now entangle |ψ⟩ with alonger spin chain prepared in the 1D cluster state. We have already seenthe stabilizer and MPS forms of this state (Eq. 3.6), but here it will beconvenient to use another definition:|CL⟩ =(n−1∏i=1CZi,i+1)|+⟩⊗n . (3.4)If we start with CZ1,2(|ψ⟩1⊗|CL⟩2,...,n) and measure the first n spins in theX basis, then the final spin will end up in the state HZsn−1 . . . HZs1 |ψ⟩n,which simplifies toH1+(−1)nZs1+s3+...Xs2+s4+... |ψ⟩n . (3.5)To interpret this result, think of the 1D cluster state as the worldline of asingle logical qubit, with each spin representing one discrete time-step. Eq.3.5 says that measuring every spin in the X basis applies the identity gateto our logical qubit, up to a unitary byproduct operator that depends on themeasurement outcomes s1, . . . , sn. This procedure is called quantum wirebecause it shuttles quantum information from one spin to another.143.2. The Measurement-Based Model3.2.2 Single-Qubit GatesBy rotating the measurement basis away from the X basis and into the X-Yplane, a 1D resource state can be used to simulate any unitary operationon a single qubit [20, 29]. However, one complication deserves mentioning:when there are multiple rotated measurements, the value of ϕ required tosimulate a given unitary depends on the past measurement outcomes. Thisdependence imposes time-ordering on the measurement sequence.In contrast, quantum wire requires neither a changing measurement basisnor time-ordered measurements, making it a relatively simple procedure tostudy. Furthermore, the ability to implement quantum wire is a necessarycondition for MBQC. These qualities motivate the study of quantum wire asa practical testing ground to separate computationally useless states fromcandidate states that may be universal resources for MBQC.3.2.3 Universal MBQCA 1D resource state may be used to simulate the evolution of a single logicalqubit. However, we require a 2D resource state to simulate multiple qubitsbecause one spatial dimension is reserved for time-steps.The usual setting for 2D resource states is a square lattice. In this con-text, one dimension of the lattice becomes the virtual qubit register, whilethe other indexes simulated time. Multi-qubit unitaries can be implementedby various measurement patterns that span the worldlines of different qubits[20]. Just as in 1D, we must keep track of measurement outcomes to com-pensate for byproduct operators and adapt subsequent measurement angles.For details, see [20] or [29].Ultimately, these complications amount to classical side-processing. Thecrucial point is that any quantum circuit can be simulated by an appropri-ate pattern of local measurements on a 2D resource state, but not on anarbitrary 2D quantum state. This positions resource states as the principalobjects of interest in the MBQC model.3.2.4 Resource States as Tensor NetworksAs mentioned in the introduction, resource states are rare in Hilbert spacebecause most states are too entangled to be useful [10]. To see this, considera spin chain where each spin is entangled with every other spin. A mea-surement of the first spin in the chain will distribute information about thelogical qubit over the entire chain instead of localizing it at the second spin.This delocalization makes it impossible to manipulate the logical qubit by153.2. The Measurement-Based Modellocal measurements and renders the MBQC protocol useless. In contrast, re-source states like the cluster state have only nearest-neighbor entanglement,which means they have a compact tensor network representation. Further-more, the tensor network representation leads to the elegant interpretationthat MBQC takes place in correlation space [9].To expand on the last statement, let us return to the 1D cluster state inMPS form. The cluster state is translation invariant, so its MPS represen-tation has a single tensor A. We have already seen the components of A inthe computational basis (Eq. 2.20). The components of A in the X basis{|+⟩ , |−⟩} turn out to be [9]A[+] = H, A[−] = HZ, (3.6)which is highly suggestive (c.f. Eq. 3.3).Before any measurements, the tensor diagram for the cluster state is justlike Eq. 2.17, with the understanding that A are the tensors defined in Eq.3.6:. (3.7)Suppose the first qubit is measured in the X basis, and the eigenvalue +1 isobtained. The post-measurement state is given by contracting the physicalleg of the tensor at the first site with |+⟩:. (3.8)As a result of the measurement, the matrix A[+] acts on the vector |L⟩,producing a new boundary vector |L′⟩ = A[+] |L⟩ = H |L⟩. In other words,our projective measurement caused a unitary evolution in correlation space.In light of Section 3.2.1, we can recognize this evolution as quantum wire,but any single-qubit unitary may be implemented by measuring in the X-Yplane, as discussed in Section 3.2.3. Note that the matrices of a generalMPS are not necessarily unitary, so this is one feature that sets the clusterstate apart.The process of 2D MBQC with PEPS is very similar to 1D MBQC withMPS, the crucial difference being that the presence of two spatial dimensionsallows for multiple logical qubits. For example, refer to Eq. 3.9 and supposethat the PEPS in question is a cluster state. The rows of the lattice indexthe logical qubits. Each lattice column represents one step in the discrete-time evolution of these qubits, and an MPS specifies their initial state at the163.2. The Measurement-Based Modelleft boundary. When the spins in the first column are measured, the MPOdefined by the corresponding tensors acts on correlation space. Becausethe cluster state is a resource state, this MPO is unitary. Therefore noinformation is lost, and the computation may proceed onwards.(3.9)17Chapter 4Computation with QuantumPhasesA phase of matter is a family of states that share a common property, eventhough the details of each state differ. This property can be anything froman everyday phenomenon like magnetization to an exotic property like su-perconductivity. Over the past decade, it was discovered that computationalpower may also be a property of a phase [3, 5, 16, 19, 24]. To be precise,there exist certain phases of quantum matter where every state in the phaseis a universal resource for MBQC. Phases with this surprising property arecalled computational phases [21].4.1 Symmetry-Protected Topological PhasesComputational phases fall into a particular category of quantum phasescalled symmetry-protected topological (SPT) phases. SPT phases requirethree ingredients: a continuously parametrized Hamiltonian, an energy gapabove the ground state, and an unbroken symmetry. The defining propertyof an SPT phase is that so long as the symmetry remains unbroken, aquantum phase transition must be heralded by the closing of the energygap [24].For example, let there be two Hamiltonians H(α1) and H(α2), withunique ground states |ϕ(α1)⟩ and |ϕ(α2)⟩, respectively3. Suppose that bothH(α1) and H(α2) have a finite energy gap in the thermodynamic limit,and commute with the same symmetry g. Finally, imagine we can finda continuous parametrization H(α) that interpolates between H(α1) andH(α2) without breaking the symmetry g, that is, [H(α), g] = 0 for all α.Note that the ground states inherit the symmetry of their respective parentHamiltonians, therefore we also have a symmetry-respecting path of groundstates |ϕ(α)⟩.3The theory of SPT phases also applies to ground state manifolds, but for computa-tional phases the ground state is assumed to be non-degenerate [22].184.2. Computation in 1D SPT PhasesGiven this setup, |ϕ(α1)⟩ and |ϕ(α2)⟩ lie in the same SPT phase if andonly if the energy gap never closes along the path parametrized by α [24].In other words, if the gap closes for exactly one value of α = α∗, withα1 < α∗ < α2, then all the states |ϕ(α < α∗)⟩ are in the same SPT phaseand share the same non-trivial property – for example, computational power[22].Note that this statement does not hold if the symmetry g is brokenanywhere along the path parametrized by α. In general, there might beanother parametrization H(β) that interpolates between the same groundstates |ϕ(α1)⟩ and |ϕ(α2)⟩ without any gap closing, i.e. without any phasetransition. However, to do this, H(β) must break the symmetry g for somevalue of β. In this way, the presence of g “protects” the separation of groundstates into distinct phases, hence the name SPT.44.2 Computation in 1D SPT PhasesIn 1D, a complete correspondence has been established between SPT phasesand computational phases: the states in every 1D SPT phase share thesame computational power [22]. 1D SPT phases have been classified bytheir symmetries [3], and this leads directly to a classification of 1D resourcestates by symmetry [22].4.2.1 Tensor SymmetriesConsider a translationally invariant MPS that lies in an SPT phase protectedby a finite abelian symmetry group G. In this situation, the MPS tensorshave the following symmetry [5]:. (4.1)where u(g) is a linear representation of g ∈ G and V (g) is a projectiverepresentation acting on correlation space.A projective representation of a group is a representation where associa-tivity of the group product does not hold:V (g)V (h) = ω(g, h)V (gh). (4.2)4The “topological” part of SPT is something of a misnomer because all SPT phasesare trivial, topologically speaking. The full explanation is interesting but not particularlyrelevant for this thesis [3].194.2. Computation in 1D SPT PhasesThe map ω : G × G → U(1) is called the factor system of the projectiverepresentation, and it includes the linear representation as a particular caseω(g, h) = 1 for all g, h ∈ G.Recall that MPS represent quantum states, which are equivalent up toa phase. Therefore, the factor system of the tensor symmetry group isalso equivalent up to a phase. This equivalence makes ω(g, h) into an objectcalled a 2-cocycle. The equivalence classes of cocycles are called cohomologyclasses, and they are topological invariants, i.e., the cohomology class of acocycle cannot change continuously. It turns out that the 1D SPT phasesare classified by the cohomology classes of ω, so to specify an SPT phase, weneed only specify the symmetry group G and a representative factor systemω [3, 5, 24].4.2.2 Logical TensorsOf particular interest is a type of factor system called a maximally non-commutative factor system, defined by the property{g : ω(g, h) = ω(h, g) for all g, h ∈ G} = {e}. (4.3)In [5], it was proven that if an SPT phase has a maximally non-commutativefactor system, then the MPS tensors for every state in the phase have thefollowing decomposition:A[|i⟩] = Bijunk ⊗ Ci, (4.4)where |i⟩ is the simultaneous eigenbasis of the on-site symmetry u(g), Bijunkare “junk” matrices that vary uncontrollably across the phase, and Ci areunitary and constant throughout the phase.The significance of this result is that there is a protected subspace ofcorrelation space where measurement in the symmetry-respecting basis |i⟩corresponds to the action of the same unitary Ci for every state in the SPTphase. Thus, we can implement quantum wire on the protected subspaceusing any state in the SPT phase, with the byproduct operators given by Ci[5]. Therefore, the protected subspace is called the logical subspace, and thetensors Ci are called logical tensors. Because of the tensor decomposition(Eq. 4.4), the computational power of the logical tensors determines thecomputational power of the entire phase.In the above, we have described computational wire, but recall thatuniversal MBQC requires measurements in the X-Y plane. In the contextof SPT phases, these measurements break the on-site symmetry and cause204.2. Computation in 1D SPT Phasesthe junk subspace to entangle with the logical subspace. Fortunately, a setof techniques have been developed to mitigate decoherence of the logicalsubspace, allowing for universal MBQC in SPT phases [21, 22].As an example, let us again consider the 1D cluster state. It is illumi-nating to look at the definition of this state in three different ways. First,the cluster state has the stabilizer group S = ⟨Zi−1XiZi+1⟩. The stabilizergroup S immediately gives the second viewpoint, namely that the clusterstate is the unique ground state of the HamiltonianH = −∑iZi−1XiZi+1. (4.5)Finally, the cluster state has an MPS representation where the local tensorsare the unique solution of the following symmetry constraints:. (4.6)Note that we can recover the stabilizers Zi−1XiZi+1 by blocking the MPStensors such that the symmetries match on contracted legs:. (4.7)Eq. 4.7 brings our three complementary descriptions of the cluster state fullcircle. From any of the above perspectives, it is straightforward to verifythat the cluster state is invariant under the symmetry groupG = ⟨XIXI . . . , IXIX . . .⟩ ∼= Z2 × Z2. (4.8)The symmetry G protects an SPT phase called the cluster phase (becauseit includes the cluster state). Because G ∼= Z2 × Z2, we say that the clusterphase is protected by a Z2 × Z2 symmetry.For every state in the cluster phase, the MPS tensors have a decompo-sition of the form (Eq. 4.4) into a junk tensor B and a logical tensor C:. (4.9)214.3. Computation in 2D SPT PhasesThe logical tensors C satisfy every symmetry of Eq. 4.6 that locally com-mutes with G. Furthermore, the junk tensors commute locally with G.Thus, every tensor in the cluster phase has the symmetries. (4.10)Eq. 4.10 emphasizes the fact that a computational phase is built aroundthe logical tensors. With this realization, we can analyze the computationalpower of the phase by analyzing the computational power of the logicaltensors.4.3 Computation in 2D SPT Phases2D computational phases are similar to 1D insofar as they have a similartensor structure at the local level, and the logical tensors still form thebackbone of every computational phase. However, because PEPS are notsimply a stack of MPS, a general 2D phase may exhibit a more complicatedencoding of logical qubits into the protected subspace and more complexaction of the logical tensors on the same subspace.4.3.1 Quantum Cellular AutomataIn known 2D computational phases, this extra complexity can be unraveledby treating the action of the logical tensors as a quantum cellular automaton(QCA) [26]. QCA are local, unitary update rules for n-qubit quantum statesthat can describe a wide range of unitary dynamics in a compact way [23, 25].I will phrase the formal definition of QCA in the Heisenberg formalism.Definition 7. Let Hn be the Hilbert space of n qubits and On the space ofHermitian operators acting on Hn. A quantum cellular automaton (QCA)is an update rule T : On → On such that(i) T translation invariant.(ii) T is invertible, i.e. unitary.(iii) T is local, meaning that it maps local operators to local operators.224.3. Computation in 2D SPT PhasesDefinition 8. A Clifford QCA is a QCA T : Pn → Pn that maps Paulioperators to Pauli operators.For the remainder of this thesis, every QCA is assumed to be a CliffordQCA unless stated otherwise. Note that the observables Xi and Zi generatePn. Therefore, any Clifford QCA can be specified by T (Xi) and T (Zi).4.3.2 Logical Tensors in 2DLet us see how QCA fit into the broader picture by continuing with thecluster state example. Our setting will be a square 2D spin-12 lattice withperiodic boundary conditions in the vertical direction and open boundaryconditions in the horizontal direction, i.e., a cylinder. Let the circumferenceof this cylinder be n sites, and the depth be d sites.The 2D cluster state is stabilized by the operatorsKi = Xi∏<i,j>Zi, (4.11)where < i, j > denotes the nearest neighbors of site i. Equivalently, it is theground state of the Hamiltonian H = −∑iKi. H can be seen to satisfy thefollowing diagonal line-like symmetries and all their translates:(4.12)The symmetries in Eq. 4.12 form a group G ∼= Zn2 × Zn2 which protects the2D cluster phase.The PEPS tensors of the 2D cluster state are specified by five symme-tries: one that locally anticommutes with G and four that commute with G,as shown in Eq. 4.13 and 4.14, respectively [21].(4.13)234.3. Computation in 2D SPT Phases(4.14)Because they commute with G, the symmetries from Eq. 4.14 are inheritedby the logical tensors of the 2D cluster phase:(4.15)Following [21], I will refer to tensors that satisfy Eq. 4.15 as cluster-liketensors.Note that our n × d cylinder can be turned into a quasi-1D system byconsidering each n× 1 ring of PEPS tensors as an MPO A:. (4.16)By matching symmetries on contracted legs, we can derive the following244.3. Computation in 2D SPT Phasessymmetries of the logical MPO for the cluster phase:(4.17)That is, the logical MPO induces a transformation T defined by T (Xi) =Xi−1ZiXi+1 and T (Zi) = Xi. T is manifestly unitary and local, and thelogical MPO is translation invariant by definition, therefore T is a QCA.Concatenating T multiple times gives a beautiful cone-shaped pattern ofsymmetries, as shown in Fig. 4.1 [21]. It can also be seen that measuring ablock of n rings in the X basis causes T to simulate the identity gate on thelogical subsystem. This presence of a QCA in the logical subspace allows foruniversal MBQC with any state in the 2D cluster phase [21]. Furthermore,every known computational phase is associated with a QCA in a similar way[26].Figure 4.1: Cone-shaped symmetries formed by the QCA of the cluster-liketensors (Eq. 4.17).25Chapter 5Beyond Quantum CellularAutomata5.1 GHZ TensorsIn the PEPS formalism, the most fundamental objects are not QCA butlocal tensors. In the previous section, we showed how the cluster QCA isconstructed from local tensor symmetries. A similar construction is possiblefor all Clifford QCA, such that every QCA is associated with a local tensorsymmetry. However, it is not the case that every local tensor symmetry givesrise to a QCA, and thus QCA are not sufficient to classify 2D computationalphases.To illustrate this point, consider the effect of applying a Hadamard op-erator to the right and lower legs of the cluster state tensor, which yields atensor with a slightly different symmetry group:(5.1)(5.2)This tensor is called the GHZ tensor because the corresponding PEPS yieldsa 2D GHZ state. Like the 2D cluster state, the 2D GHZ state is invariantunder the line-like symmetries (Eq. 4.12) acting on the physical legs. Asbefore, we discard the symmetry (Eq. 5.1) because it locally anticommuteswith the line-like symmetries, leaving four GHZ-like symmetries (Eq. 5.2).Despite being closely related to the cluster-like tensor, the GHZ-liketensor cannot form a QCA. The easiest way to see this is to note that an265.2. Channel CapacityMPO constructed from the GHZ tensors has the following symmetry:. (5.3)Instead of passing through the MPO to become another local operator T (Z),the operator Z gets reflected back to the same side where it started. Inother words, the update rule defined by this symmetry is non-unitary, andtherefore cannot be a QCA.5.2 Channel CapacityThe example of the GHZ tensor begs the following question: can we expandthe classification of 2D computational phases to include the GHZ tensors,and other logical tensors with a Pauli symmetry? As a first step towardsresolving this question, this thesis addresses a slightly simpler problem: canwe classify the quantum wire capacity of all logical tensors with a Paulisymmetry?Definition 9. The channel capacity or throughput of a quantum wire is thenumber of qubits of information that can be pushed from one end of the wireto the other using MBQC. Equivalently, channel capacity is the number ofbits of entanglement entropy between the wire’s open ends.Studying the channel capacity of the quantum wire formed by the logicaltensors is helpful for two reasons. First, recall from Chapter 4 that thelogical tensors characterize the computational power of the SPT phase thatsurrounds them because they are the only part of the tensor which does notvary across the phase. Second, quantum wire has the advantage of simplicityin that every measurement is in the X basis. Furthermore, if we assume thatX measurements commute with the symmetry of the SPT phase, we knowthat there will be no mixing of the junk and logical subspaces. Thus, we arefree to focus on the action of the logical tensors in correlation space, whichis revealed by the symmetries of their virtual legs.Let us assume that all logical tensors have been measured in the X basis;that is, their physical legs have been contracted with one of the eigenstates|±⟩. Of course, the particular eigenstate at each site is random, but thisrandomness can be accounted for by keeping track of the measurement out-comes, as discussed in Section 3.2. To simplify the tensor diagram notation,275.3. Stabilizer Tensors and Stabilizer MPOsI will adopt the convention that a tensor drawn without a physical leg hasbeen measured in the X basis:. (5.4)The setting for my study of channel capacity is a cylindrical PEPSwith circumference n, depth d, and local tensor A. In this setting, thechannel capacity of the PEPS becomes a function C(A,n, d). For a QCA,C(A,n, d) = n, which is the maximal value. However, depending on thesymmetries of A, the channel capacity may be a more complicated functionof n and d. The remainder of this thesis is devoted to computing the func-tion C(A,n, d) for every possible Pauli symmetry of the logical tensors andclassifying the forms that it may take.5.3 Stabilizer Tensors and Stabilizer MPOsThe first step towards classifying logical tensors with Pauli symmetries isto enumerate all such tensors. Notice that we have four symmetries for anylogical tensor – one for each degree of freedom in the virtual legs. Fur-thermore, the symmetries of interest are tensor products of Pauli operators.Thus, the symmetry group of the tensors we are interested in is none otherthan a 4-qubit stabilizer group. To emphasize this fact, I will define a classof tensors called the stabilizer tensors and refer to the logical tensors as aparticular type of stabilizer tensor.Definition 10. A stabilizer tensor is a PEPS tensor such that the symme-tries acting on its virtual legs form a stabilizer group.With Definition 10 we can clarify that our main objects of study are the4-legged stabilizer tensors. Naturally, these stabilizer tensors correspond tothe 4-qubit stabilizer groups. There are 2295 4-qubit stabilizer groups up tophase, so there are 2295 stabilizer tensors. However, we are not interestedin a single stabilizer tensor so much as a cylindrical network of stabilizertensors – specifically, the channel capacity of that network. A cylindricaltensor network is also an MPO, so defining a class of MPOs constructedfrom stabilizer tensors makes sense.Definition 11. A stabilizer MPO is a translationally invariant MPO whoselocal tensor is a stabilizer tensor.285.3. Stabilizer Tensors and Stabilizer MPOsI will denote a stabilizer MPO by A(A,n, d), where A is the local stabilizertensor, n is the circumference of the cylinder, and d the depth.Definition 12. Let A1 and A2 be stabilizer tensors, then A1 and A2 areleft/right Clifford equivalent (LR equivalent) if there exist U, V ∈ Cn suchthat= . (5.5)I will write A1 ∼LR A2 to denote LR equivalence. LR equivalent stabi-lizer MPOs have the same channel capacity because the conjugation by Uand V is simply a change of basis. However, note that LR equivalence doesnot necessarily imply equivalence of an MPO constructed by repeating A inthe horizontal direction because the transformation V †U inserted betweencolumns is non-trivial.We can also define a local equivalence relation for stabilizer tensors suchthat stabilizer MPOs constructed from equivalent tensors have the samechannel capacity.Definition 13. Let A1 and A2 be stabilizer tensors, then A1 and A2 aresymmetric local Clifford equivalent (SLC equivalent) if there exist U1, V1 ∈ C1such that. (5.6)I will write A1 ∼SLC A2 to denote SLC equivalence. Note that A1 ∼SLCA2 implies A(A1, n, d) ∼LR A(A2, n, d), because they are equal up to con-jugation by U =⊗ni=1 U1. However, SLC equivalence is a more restrictivecondition than LR equivalence because it retains the stabilizer tensor as thefundamental translation-invariant building block of the MPO. Furthermore,unlike LR equivalence, SLC equivalence implies equivalence for all horizontaland vertical tilings because U and V always cancel in the bulk. For the sakeof clarity, I will refer to MPOs as SLC equivalent when their local tensorsare SLC equivalent.5.3.1 Symmetry InheritanceThe symmetry group of a stabilizer MPO A(A,n, d) is inherited from thesymmetry group of A by tiling the symmetries of A such that they match oncontracted tensor legs. Let S(A,n, d) be the symmetries of A(A,n, d) that295.4. Computing Channel Capacity Numericallyact non-trivially on the open edges of the cylinder. S(A,n, d) is a stabilizergroup on 2n qubits; one qubit for each free index of A(A,n, d). Thesequbits have a natural partition into the left and right edges of the cylinder.Therefore, I will write SL and SR to denote the restriction of elements of Sonto the left and right partition, respectively.5.3.2 Canonical Form of a Bipartite StabilizerPartitioning the qubits on which S(A,n, d) acts into left and right subsetsmakes S(A,n, d) a bipartite stabilizer group. The generators of a bipartitestabilizer group have a canonical form which reveals the entanglement struc-ture of the underlying quantum state [6]. Eq. 5.7 shows this canonical formfor the generators of S(A,n, d):ZL(A,n, d) ={ai ⊗ I 1 ≤ i ≤ n− pPLR(A,n, d) ={gLk ⊗ gRkg¯Lk ⊗ g¯Rk1 ≤ k ≤ pZR(A,n, d) ={I ⊗ bj 1 ≤ j ≤ n− p.(5.7)Here ZL is the center of SL and acts trivially on partition R, while ZR is thecenter of SR and acts trivially on partition L. PLR is generated by p locallyanticommuting pairs, meaning that (gLk , g¯Lk ) anticommute with each otherbut commute with all other gLℓ and g¯Lℓ for ℓ ̸= k. The same relationship holdsfor (gRk , g¯Rk ), so that SLR(n, d) is abelian when we look at both partitionssimultaneously. I will write PL and PR for the restriction of PLR to the leftand right partitions, respectively.Later, it will be convenient to encapsulate all the information about thecanonical form of S(A,n, d) with a single mathematical object. To this end,I will denote the canonical form of S(A,n, d) by Φd(A,n). Every Φd withthe same (n, p) is LR equivalent to p Bell pairs encoded by an [n, p] stabilizercode. Therefore, the channel capacity of A(A,n, d) is equal to p, and Φdnaturally separate into equivalence classes labeled by the tuple (n, p).5.4 Computing Channel Capacity NumericallyFor a given Φd, Eq. 5.7 suggests two methods of computing the channelcapacity:C(A,n, d) = p =12rank[PLR(A,n, d)] = n− rank[ZL(A,n, d)]. (5.8)305.4. Computing Channel Capacity NumericallyUsing Eq. 5.8, I developed the following algorithm to compute C(A,n, d).Algorithm 1 Channel Capacity from Lattice Symmetries1. Given a stabilizer tensor A and values for n and d, compute a gener-ating set for the symmetry group of the n × d cylindrical lattice bymatching symmetries on every contracted leg.2. Find the subgroup of symmetries which act non-trivially on the latticeedges; this is S(A,n, d).3. Bring the generators of S(A,n, d) to canonical form by searching foranticommuting pairs. The number of anticommuting pairs is equal toC(A,n, d).The implementation5 of Algorithm 1 uses the symplectic representationof Pn, where finding the lattice symmetries is equivalent to solving a systemof linear equations over the finite field F2. Solving the system of equationsis accomplished by Gaussian elimination modulo two on a matrix whosedimensions scale as nd; this is by far the most resource-intensive part ofAlgorithm 1. As a result, Algorithm 1 has a time complexity of O((nd)3),which makes it impractical to compute C(A,n, d) for arbitrarily large lat-tices.On my laptop6, I used Algorithm 1 to compute C(A,n ≤ 10, d ≤ 10) forevery stabilizer tensor. I found that there are only 13 forms of C(A,n, d), oneof which is the trivial form C(A,n, d) = 0. A heatmap of the 12 non-trivialforms of C(A,n, d) is shown in Fig. 5.1.This result hints at a classification of stabilizer tensors by their quantumwire throughput, but it does not preclude splitting of the classes as thelattice size grows. For this reason, I will refer to the numerically determinedthroughput classes as bounded throughput classes (BTP classes). The restof this thesis is devoted to proving that the BTP classification is completeand there are no other forms of C(A,n, d) for any lattice size.5Implemented in Python. The code makes use of the symplectic Gram-Schmidt proce-dure from [14] (coded by Michael Zurel), and the libraries [11, 13, 15, 27, 28].6Apple Macbook Pro 13-inch, 2019, 1.4 GHz Intel Core i5, 8 GB RAM.315.4. Computing Channel Capacity NumericallyFigure 5.1: Heatmaps of channel capacity fall into 12 non-trivial classes.32Chapter 6Classification of ChannelCapacity6.1 Non-unitary Update RulesConsider a stabilizer MPOA(A,n, d) with stabilizer group S(A,n, d). Bring-ing S to canonical form gives the following symmetries for A:. (6.1)In the spirit of QCA, I will use Eq. 6.1 to define an update rule Td from thesymmetries of A(A,n, 1):Td(ai) = I; Td(gLk ) = gRk ; Td(g¯Lk ) = g¯Rk . (6.2)Td is non-unitary unless every generator of S is part of an anticommutingpair, in which case we recover a QCA by identifying gLk and g¯Lk with encodedPauli operators Xk and Zk, respectively. Unitarity for any value of p can berestored by modifying the update rule such thatTd(ai) = bi, Td(gLk ) = gRk ; Td(g¯Lk ) = g¯Rk . (6.3)However, note that Td is not defined on the full n-qubit Hilbert space.Instead, it maps the subspace SL to the subspace SR. If SL ̸= SR, thensome operators in SL have an image under Td that falls outside the domainof Td. A simple test to determine whether an operator is in the domain ofTd follows directly from the following lemma.Lemma 1. SL(A,n, d) is the centralizer of ZL(A,n, d) in Pn, and SR(A,n, d)is the centralizer of ZR(A,n, d) in Pn.Proof. Without loss of generality I will prove the statement for SL andZL, as the same argument applies to the right partition. Switching to the336.2. Chains of Symmetrysymplectic representation of Pn = Sp2(2n), we have ZL an isotropic sub-space and SL ⊆ Z⊥L . By Eq. 5.7, the dimensions of these subspaces aredim(ZL) = n− p and dim(SL) = n+ p.For any symplectic vector space V and subspace W ⊂ V it is well-known that dim(V ) = dim(W ) + dim(W⊥). Adding dimensions, we havedim(ZL) + dim(SL) = 2n = dim(Sp2(2n)). Therefore SL = Z⊥L . In otherwords, SL centralizes ZL in Pn.Corollary 1. For any x ∈ Pn, x ∈ SL(A,n, d) if and only if x commuteswith ZL(A,n, d).Proof. ZL is the center of SL, therefore x ∈ SL implies that x commuteswith every y ∈ ZL. By Lemma 1, SL is the centralizer of ZL in Pn, thereforethe converse is also true.The domain of Td is SL, thus Corollary 1 says that x ∈ Pn is in the domainof Td if and only if it commutes with ZL.6.2 Chains of SymmetryCorollary 1 is helpful because it tells us which symmetries of a columnA(A,n, 1) may be chained together into symmetries of the lattice A(A,n, d).For example, suppose s ∈ SL(A,n, 1) and T1(s) ∈ SR(A,n, 1). If T1(s)commutes with ZL(A,n, 1), then by Corollary 1, T1(s) ∈ SL(A,n, 1), andthere exists T 21 (s) ∈ SR(A,n, 1). Now we have two symmetries of A(A,n, 1):. (6.4)Using the rule that symmetries must match on contracted tensor legs, thesymmetries from Eq. 6.4 can be chained together into the following symme-try of A(A,n, 2):. (6.5)Any symmetry of A(A,n, d) can be derived by chaining symmetries. Iwill use the chaining process to characterize the group ZR(A,n, d), becauseone way to determine the channel capacity is via the equation C(A,n, d) =n − rank[ZR(A,n, d)]. Elements of ZR(A,n, d) must act as the identity onthe left edge of A(A,n, d) and non-trivially on the right edge. Therefore,346.2. Chains of Symmetrythey have the following form:(6.6)where ai ∈ ZL(A,n, 1), 1 ≤ i ≤ n− p, and γi is the critical depth such thatT γi1 (ai) /∈ SL(A,n, 1). Recall that this implies T γi+11 (ai) is not a symmetry.Reading off the rightmost column of Eq. 6.6, it is clear that ZR(A,n, d) isgenerated by the setTR(n, d) ={T1(ai), . . . , Tmin(d,γi)1 (ai) | 1 ≤ i ≤ n− p}, (6.7)Note that ZR(A,n, d) is invariant for d ≥ maxi(γi), because every chain inEq. 6.6 may be extended to the left by a trivial column symmetry, but nochain may be extended to the right once d ≥ maxi(γi).In the following lemmas, I will use chains of symmetry to prove someresults about channel capacity as a function of depth.Lemma 2. For any fixed value of n, C(A,n, d) ≥ C(A,n, d+ 1).Proof. TR(A,n, d) generates ZR(A,n, d), thereforeC(A,n, d) = n− rank[TR(A,n, d)]. (6.8)Any of the chains in Eq. 6.6 may be extended indefinitely to the left byadding the trivial symmetry ofA(A,n, 1), therefore TR(A,n, d) ⊆ TR(A,n, d+1) and rank[TR(A,n, d)] ≤ rank[TR(A,n, d + 1)]. Substituting Eq. 6.8 intothis inequality gives C(A,n, d) ≥ C(A,n, d+ 1).Lemma 3. For any fixed value of n, if C(A,n, dc) = C(A,n, dc+1) at somecritical depth dc, then C(A,n, d) = C(A,n, dc) for all d ≥ dc.Proof. C(A,n, dc) = C(A,n, dc + 1) requires that T1 map ZR(A,n, dc) toitself, therefore ZR(A,n, dc) is fixed for d ≥ dc. Recall that C(A,n, d) =n− rank[ZR(A,n, d)]. Therefore, C(A,n, d) is also fixed for all d ≥ dc.356.2. Chains of SymmetryLemma 4. For any fixed value of n, the maximum value of dc is C(A,n, 1).Proof. By Lemmas 2 and 3, C(A,n, d) must decrease when d is increased,up to the critical value dc. If it ever fails to decrease, then we have reacheddc and the throughput must be constant thereafter. However, C(A,n, d) is anon-negative quantity. Therefore, it may decrease at most C(A,n, 1) timesbefore reaching zero and becoming constant.Note that Lemma 4 implies maxi(γi) = dc. Taken together, Lemmas 2,3, and 4 suggest a new algorithm to compute C(A,n, d). Algorithm 2 isAlgorithm 2 Channel Capacity from Chains of Symmetry1. Compute Φ1(A,n), which determines ZL(A,n, 1) and the update ruleT1.2. Initialize TR(A,n, 1) = {T1(x)|x ∈ G}, where G is any generating setfor ZL(A,n, 1).3. For every y ∈ TR(A,n, 1), check if y commutes with ZL(A,n, 1). If so,T1(y) exists. Add every valid T1(y) to TR(A,n, 1) to obtain TR(A,n, 2).4. Repeat Step 3 until the desired depth is reached, or until TR(A,n, d) =TR(A,n, d− 1). Return C(A,n, d) = n− rank[TR(A,n, d)].more efficient than the Algorithm 1, but efficiency is not its main purpose.Instead, the point is to show that the following mathematical objects aresufficient to compute C(A,n, d):(i) The canonical generators of S(A,n, 1), i.e. Φ1(A,n).(ii) The commutation relations between generators of ZL(A,n, 1) andSR(A,n, 1), which I will denote Ω1(A,n).Recall from Section 5.3.2 that all Φ1(A,n) with the same (n, p) are LRequivalent. However, LR equivalence of Φ1 does not imply the equivalenceof Ω1 because the Clifford unitary acting on the left may be different fromthe one acting on the right. Thus, a general LR Clifford operation does notnecessarily preserve the commutation relations between ZL,ZR, and PR.Operations that do preserve these subspaces and their commutation re-lations can be inferred from Eq. 5.7, and amount to re-defining the canonicalgenerators:366.2. Chains of Symmetry(i) Swap ai ↔ aj for any ai, aj ∈ ZL, and the same for bi, bj ∈ ZR.(ii) Multiply any ai by any aj , or any bi by any bj .(iii) Multiply any gRk or g¯Rk by any bi.(iv) Swap any gRk ↔ g¯Rk .(v) Multiply any gRk by g¯Rk , and vice versa.(vi) Swap any pair (gRk , g¯Rk ) with any other pair (gRℓ , g¯Rℓ )The above is a fairly long list of equivalence relations, which moti-vates the definition of a standard form for Ω1 to quickly identify whetherΩ1(A1, n) ∼= Ω1(A2, n). To define this standard form, I will represent Ω1 bya bipartite graph GΩ1 with node sets {ai} and {bj , gRk , g¯Rk }. Let the edges ofGΩ indicate anticommutation between operators in different node sets, andlet the biadjacency matrix be MΩ1 , with the following layout:MΩ1 =b1 b2 ··· bn−p gR1 g¯R1 gR2 g¯R2 ··· gRp g¯Rpa1a2...an−p (6.9)The operations onMΩ1 that correspond to the list of subspace-preservingoperations are:(i) Swap any two rows, or any of the first (n− p) columns.(ii) Add any row to any other row, modulo 2.(iii) Add any of the first (n − p) columns to any of the last p columns,modulo 2.(iv) Reorder the 2×(n−p) blocks ofMΩ1 that represent the anticommutingpairs.(v) Within any of the blocks for each anticommuting pair:• Swap columns.• Add one column to the other or vice versa, modulo 2.376.2. Chains of SymmetryAlgorithm 3 Standard form of Ω11. Bring the first (n − p) columns of MΩ1 to reduced row echelon form(RREF), modulo 2.2. Bring the first (n−p) columns ofMΩ1 to reduced column echelon form(RCEF), modulo 2. Along with Step 1, this brings the first (n − p)columns of MΩ1 to diagonal form.3. If any row ofMΩ1 has a leading 1 in the first (n−p) columns, eliminateall other 1’s in that row by adding the column with the leading 1,modulo 2.4. Bring each 2 × (n − p) block representing an anticommuting pair toRCEF, modulo 2.5. Order the anticommuting pair blocks by descending column rank. Incase of rank degeneracy, treat the sequence of 1’s and 0’s in each blockas a binary number and arrange from largest to smallest.Using the above operations, we can define Algorithm 3 to bring MΩ1to a standard form. Note that Step 5 of the algorithm is intended to putthe most “interesting” blocks close together, but any strategy that uniquelysorts the anticommuting pair blocks in RCEF will do. After Algorithm 3 isapplied, MΩ1 has the following form:MΩ1 =λ1λ2. . .λn−p∣∣∣∣∣∣∣∣∣ H1∣∣∣∣∣∣∣∣∣ H2∣∣∣∣∣∣∣∣∣ · · ·∣∣∣∣∣∣∣∣∣ Hp (6.10)where λi ∈ {0, 1} and Hj are 2 × (n − p) block matrices in RCEF, orderedby rank. The RREF and RCEF of any matrix (or block matrix) is unique,therefore the standard form is well-defined and we can use it to compareΩ1(A1, n) with Ω1(A2, n). From now on, I will write Ω1(A1, n) ∼ Ω1(A2, n)if the standard form of their biadjacency matrices are equal.386.3. Local Generators6.3 Local GeneratorsIn Section 6.2, I showed that the objects Φ1(A,n) and Ω1(A,n) are sufficientto determine channel capacity for any n and d. Working with Φ1 and Ω1 issimpler than working with C(A,n, d) because neither Φ1 nor Ω1 depends ond.The next step is to eliminate the dependence of Φ1 and Ω1 on n. I willdo this by exploiting the translation invariance of stabilizer MPOs to find alocal form for the generators of S(A,n, 1). To be precise, I will show thatthe generating set for S(A,n, 1) has a form where every generator save oneis k-local with k ≤ 3. Because there is only one nonlocal generator, I willslightly abuse terminology and refer to the local form of S(A,n, 1). At theend of the section, we will also classify every local form.My method for obtaining a local form of S(A,n, 1) is recursive appli-cation of the canonical bipartite form (Eq. 5.7) to the stabilizer group ofthe local tensor A, using smaller and smaller partitions each time. Let the4 virtual legs of A be partitioned into horizontal and vertical subsystemsH and V , which are subdivided into {u, d, l, r} = {up, down, left, right} asshown in Eq. 6.11. As before, tiling of stabilizer tensors into a stabilizerMPO is done in the vertical direction.(6.11)The first step in the recursive application of Eq. 5.7 is to bring S(A, 1, 1)to canonical form with respect to the {H,V } partition. For convenience, Iwill denote S(A, 1, 1) by SA for the rest of this section. The subsystems Hand V have two legs each, so there may be p = 0, 1, or 2 anticommutingpairs. The canonical form of SA for each case is shown in Eq. 6.12.p = 0h1 ⊗ Ih2 ⊗ II ⊗ v1I ⊗ v2p = 1h⊗ IgH ⊗ gVg¯H ⊗ g¯VI ⊗ vp = 2gH1 ⊗ gV1gH2 ⊗ gV2g¯1H ⊗ g¯1Vg¯2H ⊗ g¯2V .(6.12)Note that symmetries like h1⊗I decouple the action of SA on the horizontallegs from its action on the vertical legs. S(A,n, 1) automatically inherits396.3. Local Generatorsthese symmetries for any n because tiling them into a column becomestrivial. In contrast, symmetries like gV ⊗ gH induce a coupling between thevertical and horizontal legs, in which case we cannot take the vertical tilingof A for granted.In Lemmas 5 through 8, we will work through each value of p from Eq.6.12 and find an expression for the local generating set of S(A,n, 1) on acase-by-case basis.Lemma 5. If there are p = 0 anticommuting pairs in the canonical form ofSA, then S(A,n, 1) has the following local generating set:S(A,n, 1) = ⟨h1,i, h2,i | i = 1, . . . , n⟩ . (6.13)Proof. When p = 0, the action of SA on the horizontal legs is decoupled fromits action on the vertical legs, and S(A,n, 1) directly inherits the operatorsh1,i and h2,i for every site i. The set{h1,i, h2,i | i = 1, . . . , n} (6.14)is independent, commuting, and has rank 2n, therefore it is a generating setfor S(A,n, 1).When p = 1, the situation is more complicated because the action of SAon the horizontal legs is not decoupled from its action on the vertical legs.Consequently, the elements S(A,n, 1) depend on how the elements of SAmatch up on the vertical legs. To determine these vertical tilings, considerthe restriction of SA to subsystem V , denoted S(V )A :S(V )A = {v, gV , g¯V } (6.15)By definition, v and gV commute, thus the subgroup RA =〈v, gV〉 ⊂S(V )A is a 2-qubit stabilizer group and it may be brought to canonical formwith respect to the {u, d} partition. Depending on the number of anticom-muting pairs q, we have the following:q = 0 : RA = ⟨µ⊗ I, I ⊗ δ⟩q = 1 : RA =〈γu ⊗ γd, γ¯u ⊗ γ¯d〉,(6.16)where Greek letters are used to differentiate operators which act on {u, d, l, r}from those that act on {H,V }, and operators that differ only by an over-bar must anticommute. Note that the subsystems {u, d, l, r} contain onlyone tensor leg, thus {µ, δ, γu, γd, γ¯u, γ¯d} are single-qubit Paulis X, Y , or Z.The remaining generator of S(V )A is g¯V , which must commute with v andanticommute with gV .406.3. Local GeneratorsLemma 6. If there are p = 1 anticommuting pairs in the canonical formof SA and q = 0 anticommuting pairs in the canonical form of RA, thenS(A,n, 1) has the following local generating set:S(A,n, 1) =〈gHi , hi | i = 1, . . . , n〉. (6.17)Proof. Without loss of generality let v = µ⊗ I, so thatS(V )A =〈µ⊗ I, I ⊗ δ, I ⊗ δ¯〉 .The cosets with respect to v are as follows.[gV]v= {I ⊗ δ, µ⊗ δ}[g¯V]v= {I ⊗ δ¯, µ⊗ δ¯}[gV g¯V]v= {I ⊗ δδ¯, µ⊗ δδ¯}.(6.18)Note that {δ, δ¯, δδ¯} ∈ {X,Y, Z} are independent, giving one coset for eachPauli operator. Recall from the proof of Lemma 1 that dim(v)+dim(v⊥) =dim(P2) = 4, therefore the centralizer of v has rank 3. This means that Eq.6.18 is the only choice of cosets up to relabeling of gV and g¯V . Furthermore,we have the following independent representatives: I ⊗ δ, I ⊗ δ¯, and I ⊗ δδ¯.However, there are only three single-qubit Pauli operators, thus one of δ, δ¯,or δδ¯ must equal µ. Therefore, without loss of generality let us choose gV =I ⊗ µ, and write every element of S(V )A in terms of µ and its anticommutingpartner µ¯:[v]v = {µ⊗ I, I ⊗ I}[gV]v= {I ⊗ µ, µ⊗ µ}[g¯V]v= {I ⊗ µ¯, µ⊗ µ¯}[gV g¯V]v= {I ⊗ µµ¯, µ⊗ µµ¯}.(6.19)Recall that S(A,n, 1) is constructed from SA by tiling elements of SAsuch that they match on contracted tensor legs. Using Eq. 6.19 it is clearthat the tiling gVi vi+1 is valid, because µ is matched:(6.20)416.3. Local GeneratorsNote that gVi is coupled to gHi and vi is not coupled to anything on thehorizontal partition, therefore gHi ∈ S(A,n, 1) for all i, as shown in Eq.6.20. This gives n local generators of S(A,n, 1). The remaining n localgenerators are given by hi, which are trivially elements of S(A,n, 1) becausethey are decoupled from V .Lemma 7. If there are p = 1 anticommuting pairs in the canonical form ofSA and q = 1 anticommuting pairs in the canonical form of RA, then thelocal generating set of S(A,n, 1) has one of two possible forms, dependingon whether γu = γd or γu ̸= γd.(i) If γu = γd, then S(A,n, 1) =〈hi, gHi gHi+1,∏i g¯Hi | i = 1, . . . , n〉(ii) If γu ̸= γd, then S(A,n, 1) = 〈hi, g¯Hi−1gHi g¯Hi+1 | i = 1, . . . , n〉Proof of (i). Recall from Eq. 6.16 that when q = 1,RA =〈γu ⊗ γd, γ¯u ⊗ γ¯d〉.If γu = γd = γ, we have v = γ ⊗ γ and gV = γ¯u ⊗ γ¯d, where γ, γ¯u, and γ¯dare different Pauli operators. Let γ = X, γ¯u = Z, and γ¯d = Y without lossof generality. This gives v = X ⊗ X and gV = Z ⊗ Y . The only 2-qubitPauli operators that commute with X⊗X but anticommute with Z⊗Y areX ⊗ I and I ⊗X, which are in the same coset with respect to v. Therefore,g¯V = X ⊗ I completes the group S(V )A . The cosets with respect to v are:[v]v = {X ⊗X, I ⊗ I}[gV]v= {Z ⊗ Y, Y ⊗ Z}[g¯V]v= {X ⊗ I, I ⊗X}[gV g¯V]v= {Y ⊗ Y,Z ⊗ Z}.(6.21)It will be convenient to re-label the cosets cyclicly, i.e. gV → g¯V →gV g¯V → gV , because this gives the vertical tilings ∏i g¯Vi and gVi gVi+1. Read-ing off the action of these tilings on the horizontal partition from Eq. 6.12,we have∏i g¯Hi and gHi gHi+1 as elements of S(A,n, 1). The former accountsfor one generator, and the latter for n− 1 independent generators. Finally,hi provide the remaining n generators.Proof of (ii). If γu ̸= γd, then v = γu ⊗ γd. Without loss of generality, letγu = X and γd = Z so that v = X ⊗ Z. Once again we must find three426.3. Local Generatorsindependent cosets that commute with v but anticommute pairwise:[v]v = {X ⊗ Z, I ⊗ I}[gV]v= {Y ⊗ Y, Z ⊗X}[g¯V]v= {X ⊗ I, I ⊗ Z}[gV g¯V]v= {Z ⊗ Y, Y ⊗X}.(6.22)Upon inspection of Eq. 6.22, the vertical tiling g¯Vi−1gVi g¯Vi+1 is a local operator.The action of this operator on the horizontal partition gives g¯Hi−1gHi g¯Hi+1 ∈S(A,n, 1). This is a set of n independent and commuting generators, andhi provide the remaining n generators.Lemma 8. If there are p = 2 anticommuting pairs in the canonical form ofSA, then S(A,n, 1) has the following local generating set:S(A,n, 1) =〈gH1,igH2,i+1, g¯H1,ig¯H2,i+1 | i = 1, . . . , n〉. (6.23)Proof. When p = 2, the restriction of SA to V is S(V )A = {gV1 , gV2 , g¯V1 , g¯V2 }.Since rank(S(V )A ) = 4, we must have S(V )A = P2. Without loss of general-ity, we may pick any generating set for P2 that matches the commutationstructure of S(V )A . Therefore, letgV1 = I ⊗X, gV2 = X ⊗ I, g¯V1 = I ⊗ Z, g¯V2 = Z ⊗ I. (6.24)Clearly the vertical tilings are gV1,igV2,i+1 and g¯V1,ig¯V2,i+1. On the horizontalpartition, these correspond to gH1,igH2,i+1 and g¯H1,ig¯H2,i+1, respectively. The set{gH1,igH2,i+1, g¯H1,ig¯H2,i+1 | i = 1, . . . , n} ⊂ S(n, 1) (6.25)has 2n independent, commuting elements, therefore it is a generating set forS(A,n, 1).Lemma 8 completes the analysis of every case presented in Eq. 6.12.The results are summarized in Lemma 9, and an example of each class oflocal generators is shown in Fig. 6.1.Lemma 9. The generating set for S(A,n, 1) may always be written in oneof four local forms:(i) {h1,i, h2,i | i = 1, . . . , n}(ii){hi, gHi gHi+1,∏i g¯Hi | i = 1, . . . , n}436.3. Local Generators(iii){hi, g¯Hi−1gHi g¯Hi+1 | i = 1, . . . , n}(iv){gH1,igH2,i+1, g¯H1,ig¯H2,i+1 | i = 1, . . . , n}Proof. See Lemmas 5 through 8. The local generating sets from Lemmas 5and 6 are isomorphic, so they both fall under (i) in the above.(i) (ii)(iii) (iv)Figure 6.1: Examples of each class of local generators from Lemma 9.446.3. Local Generators6.3.1 Bipartite Local GeneratorsUp to this point, we have seen two presentations of S(A,n, 1), each withadvantages and disadvantages. The canonical bipartite form directly revealsthe channel capacity of A(A,n, 1) and determines the channel capacity forany depth via Φ1 and Ω1. However, in general, it may depend on n. Thelocal form removes this dependence on n but does not tell us anythingabout channel capacity. In this section, I will connect the local form andthe canonical form of S(A,n, 1).The first step is to partition the local generators into the same left andright subsets used for the canonical form. When viewed on one partitionat a time, the local generators are no longer guaranteed to be abelian; thedegree to which they fail to be abelian dictates Φ1. Without loss of gener-ality, consider the left partition. A computer search reveals that up to SLCequivalence, there are nine local generating sets of SL, as shown in Table6.1. I will refer to these generating sets as the standard local generators.Recall that equivalence classes of Φ1 are labeled by the tuple (n, p), wherep is the number of anticommuting pairs. From Eq. 5.8, we can derive thefollowing relationship between p and the rank of SL:rank(SL) = rank(PL) + rank(ZL)= 2p+ (n− p)=⇒ p = rank(SL)− n.(6.26)Because the rank of SL is independent of any particular generating set, weare free to use the local generators to determine p as a function of n. Therank of SL and the value of p(n) for each standard local generating set isshown in Table 6.1. This table shows a one-to-one correspondence betweenthe non-trivial equivalence classes of Φ1 – that is, classes where p ̸= 0 –and the standard local generating sets. Furthermore, by comparing p(n)with the throughput C(A,n, 1) in Fig. 5.1 we can see that each BTP classcorresponds to exactly one equivalence class of Φ1. This correspondence isdetailed in Table 6.2.Definition 14. Let the vector Φ⃗(A) beΦ⃗(A) = Φ1(A,n) n = 1, 2, . . . ,∞ (6.27)and define Φ⃗(A1) ∼ Φ⃗(A2) if Φ1(A1, n) ∼ Φ1(A2, n) for all n.456.3. Local GeneratorsΦ1ClassStandardLocal Generatorsof SL Rank of SL pa ⟨Zi⟩ n 0a ⟨Xi−1ZiXi+1⟩ n 0a ⟨ZiZi+1,∏iXi⟩ n 0b ⟨Zi,∏iXi⟩ n+ 1 1c ⟨Zi, XiXi+1⟩ 2n− 1 n− 1d ⟨Zi, Xi−1IiXi+1⟩{2n− 2, n even2n− 1, n odd{n− 2n− 1e ⟨Zi, Xi−1XiXi+1⟩{2n− 2, n div. by 32n, otherwise{n− 2nf ⟨Zi, XiXi+1,∏iXi⟩{2n− 1 n even2n n odd{n− 1ng ⟨Zi, Xi⟩ 2n nTable 6.1: Standard local generating sets of SL.Φ1ClassThroughputClassesa 0b 1, 2c 4, 6, 7d 3, 5e 8, 10f 9, 11g 12Table 6.2: Correspondence between throughput classes and equivalenceclasses of Φ1.466.3. Local GeneratorsLemma 10. Φ⃗(A1) ∼ Φ⃗(A2) if and only if p(A1, n) = p(A2, n) for valuesof n such that at least one is even, one is odd, one is divisible by 3, and oneis not divisible by 3.Proof. If Φ⃗(A1) ∼ Φ⃗(A2) then by definition p(A1, n) = p(A2, n) for all n.To prove the converse, notice that for every standard local generatoringset in Table 6.1, the expression for p as a function of n only changes if nswitches from even to odd, or from being divisible by 3 to not divisible by3. Furthermore, these dependencies are mutually exclusive, i.e. if p dependson whether n is even or odd then it does not depend on the divisibility ofn by 3, and vice versa. Therefore, if p(A1, n) = p(A2, n) for values of nthat satisfy the conditions of the lemma, then p(A1, n) = p(A2, n) for all n,which implies Φ1(A1, n) ∼ Φ1(A2, n) for all n.6.3.2 Periodic Boundary ConditionsThe local generators of SL and SR act on a ring of n sites. Because of this,they are subject to the effects of periodic boundary conditions. These effectshave already played a role in the characterization of Φ⃗(A), i.e. in Table 6.1and Lemma 10. The next object we will need to characterize is the set ofcommutators Ω1(A,n), so in this section, I will discuss the effect of PBC onthe commutation relations of local operators.Definition 15 ([25]). Consider two local operators B and C acting on aring of n sites. The intersection between B and C is the overlap betweenthe support of B and the support of C for every translation of C. Theintersection between B and C is regular for a given value of n if its geometrydoes not change as n→∞.For example, let Bi = XiXi+1Xi+2 and Ci = ZiZi+1Zi+2. When n islarge Bi and Cj slide past each other with no boundary effects. However,when n = 4 both ends of C3 simultaneously overlap with B1. This type ofintersection is not possible when n → ∞, so the intersection of B and C isirregular for N = 4.Regularity of intersection has a direct effect on commutation relations, asillustrated by the fact that B1 and C3 commute for N = 4 and anticommutefor n ≥ 5. To formalize this phenomenon, we have the following lemma.Lemma 11. Consider a k-local operator Bi and a set of translation-invariantℓ-local operators Cj acting on a ring of n sites. The intersection between Biand Cj is irregular for n < k + ℓ− 1 and regular otherwise.476.3. Local GeneratorsProof. Let Bi have support on sites i through i+k−1 and Cj have supporton sites j through j + ℓ − 1. The transition between irregular and regularintersection is given by the case where Bi and Ck only intersect at theirendpoints, i.e. at sites k and i. By inspection, this requires n = k + ℓ − 2,therefore the intersection is irregular for n < k + ℓ− 1.Corollary 2. The commutation relations between Bi and Cj change if andonly if n transitions from the irregular to the regular regime, or vice versa.Proof. The commutation relations are determined by the overlap between Biand Cj , and this overlap only changes if there is a transition from irregularto regular intersection, or vice versa.Corollary 3. The commutation relations between the local generators ofSL(A,n, d) and SR(A,n, d) are regular for n ≥ 5, and irregular for n < 5.Proof. Apart from the string-like operators∏i g¯i, every local generator hassupport on at most three adjacent sites. Applying the result of Lemma11, we have regular intersection for n ≥ 3 + 3 − 1 = 5. The string-likeoperators have periodicity one, so their intersection with the rest of theisland stabilizers is regular for n ≥ 3+1−1 = 3. Therefore, the special caseof string-like operators does not violate the general result.Lemma 11 and its corollaries will be essential to the characterization ofΩ1(A,n), because Ω1 is a set of commutators between elements of SL(A,n, 1)and SR(A,n, 1). Elements of these groups have a decomposition into prod-ucts of local generators. Thus, their commutators can be written in terms ofthe pairwise commutators of local generators. Therefore, the commutatorsof any elements of SL(A,n, 1) and SR(A,n, 1) may be subject to effects fromthe irregular intersection of local generators when n is sufficiently small. Theresult of Corollary 3 tells us when n will be large enough that we can safelyignore such effects.A related but subtly different phenomenon is that the string-like gener-ators are indistinguishable from truly local generators for small values of n.For example, the local generator XiXi+1 looks the same as∏iXi on a ringwith only two sites. The same is true of Xi−1XiXi+1 on a ring with threesites. These observations are another reason we can expect the groups SLand SR to behave differently for small values of n, specifically n ≤ 3.Of course, there may be cases where irregular geometry and string-likeoperators do not affect the commutation relations of local operators. How-ever, the threshold that guarantees avoidance of both phenomena is so small486.4. Removing the Bounds on n and dStandardLocal Generatorsof SL Generators of ZL⟨Zi⟩ ⟨Zi⟩⟨Xi−1ZiXi+1⟩ ⟨Xi−1ZiXi+1⟩⟨ZiZi+1,∏iXi⟩ ⟨ZiZi+1,∏iXi⟩⟨Zi,∏iXi⟩ ⟨ZiZi+1⟩⟨Zi, XiXi+1⟩ ⟨∏i Zi⟩⟨Zi, Xi−1IiXi+1⟩{⟨∏i Z2i,∏i Z2i+1⟩ n even⟨∏i Zi⟩ n odd⟨Zi, Xi−1XiXi+1⟩{⟨∏i Z3iZ3i+1,∏i Z3i+1Z3i+2⟩ n div. by 3⟨I⟩, otherwise⟨Zi, XiXi+1,∏iXi⟩{⟨∏i Zi⟩ n even⟨I⟩ n odd⟨Zi, Xi⟩ ⟨I⟩Table 6.3: Generators of ZL for each standard local generating set of SL.that there is little incentive to develop a formalism for describing them inany further detail. Instead, I found it preferable to assume that one or theother phenomena might be relevant whenever n ≤ 4, and develop the restof my results accordingly.6.4 Removing the Bounds on n and dWith the results of Section 6.3, we have all the tools required to complete theclassification of channel capacity. Proof that the classification is completehinges on the characterization of Ω1(A,n) because it is the only object fromAlgorithm 2 which retains its dependence on n.I will begin by showing a variation of Table 6.1. Table 6.3 details thegenerators of ZL for every standard local generating set. It turns out thatZL is key to classifying Ω1(A,n), as explained below.Definition 16. Let the vector Ω⃗(A) beΩ⃗(A) = Ω1(A,n) n = 1, . . . ,∞, (6.28)and define Ω⃗(A1) ∼ Ω⃗(A2) if Ω1(A1, n) ∼ Ω1(A2, n) for all n.496.4. Removing the Bounds on n and dLemma 12. Ω⃗(A1) ∼ Ω⃗(A2) if and only if Ω1(A1, n) ∼ Ω1(A2, n) for n ≤ 6.Proof. By definition, Ω⃗(A1) ∼ Ω⃗(A2) implies Ω1(A1, n) ∼ Ω1(A2, n) for alln. To prove the converse, recall that Ω1(A,n) is the set of commutators ofthe elements of ZL(A,n, 1) with the elements of ZR(A,n, 1) and PR(A,n, 1).Furthermore, ZL dictates the elements of ZR and PR. To see this, note thatPL completes the centralizer of ZL, thus ZL uniquely determines PL. Then,PL uniquely determines PR by taking the right-hand part of each generatorof PL. Finally, PR uniquely determines ZR, because ZR is the center of PR.In Table 6.3, we have an expression for the generators of ZL for everyequivalence class of local tensors. These generating sets show that the ele-ments of ZL(A,n) and ZL(A,m) are equal up to translation, as long as nand m share the same divisibility by 2 or 3. Therefore, the elements of everygroup relevant to Ω1(A,n) remain constant up to translation, as long as nretains the same divisibility by 2 or 3.Having characterized the elements of ZL, ZR and PR up to translation,it remains to deal with their commutation relations. This is not trivialbecause periodic boundary conditions may play a role (see Section 6.3.2).However, every element of ZL, ZR, and PR may be written as a product oflocal generators. Thus, the commutator [x, y] for x ∈ ZL and y ∈ ZR ∪ PRhas a decomposition into pairwise commutators of local generators. ByCorollaries 2 and 3, these pairwise commutators may vary in the irregularregime of intersection (n ≤ 4), but they are invariant in the regular regimeof intersection (n ≥ 5). In other words, for any n ≥ 5, every local generatoranticommutes with the same finite subset of its neighbors.It follows that if n0 ≥ 5 and Ω1(A1, n0) ∼ Ω1(A2, n0), then Ω1(A1, n) ∼Ω1(A2, n) for all n which have the same divisibility by 2 and 3 as n0. There-fore, to guarantee Ω1(A1, n) ∼ Ω1(A2, n) for all n, it suffices to check just afew values of n0 and infer the equivalence of the Ω’s for all other n. Coverageof every n in the regular regime can be obtained by checking at least onevalue of n even, one value of n odd, one divisible by 3, and one not divisibleby 3. The values n = 5, 6 satisfy these requirements.We have made no statement about the irregular regime (n ≤ 4), thus wemust also check every n in the irregular regime. Putting everything together,we have that if Ω1(A1, n) ∼ Ω1(A2, n) for n ≤ 6, then they are equivalentfor all n.The standard form Ω1(A,n) was computed for n ≤ 6 and every equiva-lence class of stabilizer tensor, and it was found that there are 19 differentcases. By Lemma 12, this implies that there are 19 equivalence classes of Ω⃗.506.4. Removing the Bounds on n and dWith this result, we have a classification of both Φ⃗ and Ω⃗. The last piece ofthe puzzle is to show that if two stabilizer tensors share the same Φ⃗ and Ω⃗,then they are guaranteed to share the same channel capacity for any valuesof n and d.Theorem 1. If A1 and A2 are in the same BTP class, then C(a1, n, d) =C(A2, n, d) for all values of n and d.Proof. Upon comparing the Ω⃗ class and the BTP class of each stabilizertensor, it was found that there are 7 different Ω⃗’s that correspond to BTPClass 0 and one unique Ω⃗ for each of the other BTP classes. Thus, wecan assign a unique tuple (Φ⃗, Ω⃗) to the stabilizer tensors of each non-trivialBTP class. By Algorithm 2, Φ⃗ and Ω⃗ are sufficient to compute C(A,n, d)for any n and d, therefore the theorem must be true for every non-trivialBTP class.It remains to show that the theorem holds for the trivial BTP class,i.e. C(A,n, d) = 0. By Lemma 2, C(A,n, 1) cannot increase with depth,and Tables 6.1 and 6.2 show that every Φ⃗ associated with BTP Class 0gives C(A,n, 1) = 0 for all n. Therefore, if A is in BTP Class 0, thenC(A,n, d) = 0 for all n and d.With the result of Theorem 1, we can remove the “bounded” qualifierfrom the BTP classes and state that every 4-legged stabilizer tensor fallsinto one of 13 throughput classes.51Chapter 7ConclusionAs described in Chapter 4, computational phases are built around logicaltensors – tensors that simulate quantum wire when measured in the localsymmetry-respecting basis. Existing work on 2D computational phases con-siders the case where the logical tensors define a QCA acting on correlationspace. In this thesis, I analyzed a larger class of logical tensor candidates:the stabilizer tensors.My results show that the 2D stabilizer tensors can be classified by theirchannel capacity for quantum wire. Specifically, for a cylindrical geome-try with circumference n and depth d, any stabilizer tensor is associatedwith one of 13 types of channel capacity. These include the case of QCAwhere C(n, d) = n, the trivial case where C(n, d) = 0, and 11 intermediatecases where C(n, d) is a more complicated function of n and d. Becausequantum wire is necessary for universal MBQC, this classification is a steptowards classifying those 2D computational phases where the logical tensorsare stabilizer tensors.7.1 Outlook2D computational phases are of great interest in the study of MBQC becausethey form a link between quantum computation, symmetry, and quantummatter. Classifying a more extensive set of 2D computational phases wouldhelp clarify this connection, enhancing our understanding of quantum com-putation and quantum information at a fundamental level. It might also leadto new principles for the design and implementation of quantum hardwareand algorithms.With this in mind, there are at least two promising extensions of thework presented in this thesis. First, the classification of channel capacityhas a numerical part and an analytical part: numerics are used to com-pute C(A,n, d) for small lattices, and analytics to prove that the numericalclassification generalizes to any lattice size. However, it remains to be seenif there is an entirely analytical classification of stabilizer tensors, perhapssimilar to the cohomological classification of SPT phases in 1D.527.1. OutlookOne observation that might lead to an analytic classification is the strik-ing similarity between the patterns of symmetry formed by stabilizer tensors(e.g., Fig. 4.1) and tesselations of the 2D plane, such as the works of M. C.Escher. These tesselations are also known as wallpaper patterns and can beclassified using group cohomology [12, 17]. In brief, the classification restson the difference between the full symmetry group of the wallpaper patternand the symmetry group of a single unit cell.It would appear that networks of stabilizer tensors exist in a similarsetting because the full symmetry group of the tensor network is generatedby a local tensor symmetry and a set of lattice translations. To date, myefforts to distinguish the cluster-like tensors from the GHZ tensors withtools from the classification of wallpaper groups have not been successful.However, it remains an area of significant interest for me, not least becauseit would be a beautiful correspondence if it turns out to be true.The second direction for new research is to extend the classification ofquantum wire to a classification of universal MBQC schemes in 2D compu-tational phases. In this thesis, I considered measurements in the local Xbasis, but universal MBQC requires measurement in the X-Y plane. Recallthat measurements of this kind break the global symmetry of the phase andentangle the logical subspace with the junk subspace. This effect can bemitigated using the methods detailed in [21, 26], but whether those meth-ods work for every phase where the logical tensors are stabilizer tensors isan open question. Therefore, the 13 throughput classes presented in thisthesis may split into subclasses when we consider universal MBQC.Hopefully, the answers to these questions are closely related and help toreveal more about the relationship between symmetry and quantum com-putation.53Bibliography[1] Sergey Bravyi, David Fattal, and Daniel Gottesman. GHZ extractionyield for multipartite stabilizer states. J. Math. Phys., 47(6):062106,Jun 2006.[2] Jacob C. Bridgeman and Christopher T. Chubb. Hand-waving andinterpretive dance: an introductory course on tensor networks. J. Phys.A Math. Theor., 50(22):223001, Jun 2017.[3] Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. Classification ofgapped symmetric phases in one-dimensional spin systems. Phys. Rev.B, 83(3):035107, Jan 2011.[4] Ignacio Cirac, David Perez-Garcia, Norbert Schuch, and Frank Ver-straete. Matrix Product States and Projected Entangled Pair States:Concepts, Symmetries, and Theorems. Nov 2020.[5] Dominic V. Else, Ilai Schwarz, Stephen D. Bartlett, and Andrew C. Do-herty. Symmetry-Protected Phases for Measurement-Based QuantumComputation. Phys. Rev. Lett., 108(24):240505, Jun 2012.[6] David Fattal, Toby S. Cubitt, Yoshihisa Yamamoto, Sergey Bravyi, andIsaac L. Chuang. Entanglement in the stabilizer formalism. pages 1–4,Jun 2004.[7] Daniel Gottesman. The Heisenberg Representation of Quantum Com-puters. 1:1–20, Jul 1998.[8] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. GoingBeyond Bell’s Theorem. In Bell’s Theorem, Quantum Theory and Con-ceptions of the Universe, pages 69–72. Springer Netherlands, Dordrecht,1989.[9] D. Gross and J. Eisert. Novel Schemes for Measurement-Based Quan-tum Computation. Phys. Rev. Lett., 98(22):220503, May 2007.54Bibliography[10] D. Gross, S. T. Flammia, and J. Eisert. Most Quantum States AreToo Entangled To Be Useful As Computational Resources. Phys. Rev.Lett., 102(19):190501, May 2009.[11] Charles R. Harris, K. Jarrod Millman, Ste´fan J van der Walt, RalfGommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Tay-lor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus,Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Hal-dane, Jaime Ferna´ndez del R´ıo, Mark Wiebe, Pearu Peterson, PierreGe´rard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser,Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array pro-gramming with NumPy. Nature, 585:357–362, 2020.[12] Howard Hiller. Crystallography and Cohomology of Groups. Am. Math.Mon., 93(10):765, Dec 1986.[13] J. D. Hunter. Matplotlib: A 2d graphics environment. Computing inScience & Engineering, 9(3):90–95, 2007.[14] Robert Koenig and John A. Smolin. How to efficiently select an arbi-trary Clifford group element. J. Math. Phys., 55(12):122202, Dec 2014.[15] Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba. In Proc.Second Work. LLVM Compil. Infrastruct. HPC - LLVM ’15, pages 1–6,New York, New York, USA, 2015. ACM Press.[16] Akimasa Miyake. Quantum computation on the edge of a symmetry-protected topological order. Phys. Rev. Lett., 105(4):1–5, 2010.[17] Patrick Morandi. The classification of wallpaper patterns: from groupcohomology to escher’s tessellations. Jan 2003.[18] M. Nielsen and I. L. Chuang. Quantum Computation and QuantumInformation: 10th Anniversary Edition. Cambridge University Press,2010.[19] Frank Pollmann, Ari M. Turner, Erez Berg, and Masaki Oshikawa.Entanglement spectrum of a topological phase in one dimension. Phys.Rev. B, 81(6):064439, Feb 2010.[20] Robert Raussendorf and Hans J Briegel. A One-Way Quantum Com-puter. Phys. Rev. Lett., 86(22):5188–5191, May 2001.55Bibliography[21] Robert Raussendorf, Cihan Okay, Dong-Sheng Wang, David T.Stephen, and Hendrik Poulsen Nautrup. Computationally UniversalPhase of Quantum Matter. Phys. Rev. Lett., 122(9):090501, Mar 2019.[22] Robert Raussendorf, Dong-Sheng Wang, Abhishodh Prakash, Tzu-Chieh Wei, and David T. Stephen. Symmetry-protected topologicalphases with uniform computational power in one dimension. Phys.Rev. A, 96(1):012302, Jul 2017.[23] Dirk-M. Schlingemann, Holger Vogts, and Reinhard F. Werner. Onthe structure of Clifford quantum cellular automata. J. Math. Phys.,49(11):112104, Nov 2008.[24] Norbert Schuch, David Pe´rez-Garc´ıa, and Ignacio Cirac. Classifyingquantum phases using matrix product states and projected entangledpair states. Phys. Rev. B, 84(16):165139, Oct 2011.[25] B. Schumacher and R. F. Werner. Reversible quantum cellular au-tomata. 2004.[26] David T. Stephen, Hendrik Poulsen Nautrup, Juani Bermejo-Vega, JensEisert, and Robert Raussendorf. Subsystem symmetries, quantum cel-lular automata, and computational phases of quantum matter. Quan-tum, 3:142, May 2019.[27] David Kingsley Tuckett. Tailoring surface codes: Improvements inquantum error correction with biased noise. PhD thesis, Universityof Sydney, 2020. (qecsim: https://github.com/qecsim/qecsim).[28] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland,Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson,Warren Weckesser, Jonathan Bright, Ste´fan J. van der Walt, MatthewBrett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, AndrewR. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, I˙lhanPolat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, JosefPerktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R.Harris, Anne M. Archibald, Antoˆnio H. Ribeiro, Fabian Pedregosa, Paulvan Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Al-gorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020.[29] Tzu-Chieh Wei. Quantum spin models for measurement-based quantumcomputation. Adv. Phys. X, 3(1):1461026, Jan 2018.56
Thesis/Dissertation
eng
Physics
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Raussendorf, Robert
Classification of quantum wire in tensor network states with a local Pauli symmetry
Text