Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Computational power of one-dimensional symmetry-protected topological phases Stephen, David Thomas 2017

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2017_september_stephen_david.pdf [ 830.57kB ]
JSON: 24-1.0354465.json
JSON-LD: 24-1.0354465-ld.json
RDF/XML (Pretty): 24-1.0354465-rdf.xml
RDF/JSON: 24-1.0354465-rdf.json
Turtle: 24-1.0354465-turtle.txt
N-Triples: 24-1.0354465-rdf-ntriples.txt
Original Record: 24-1.0354465-source.json
Full Text

Full Text

Computational power ofone-dimensional symmetry-protectedtopological phasesbyDavid Thomas StephenA 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)August 2017c© David Thomas Stephen 2017AbstractWe consider ground states of quantum spin chains with symmetry-protectedtopological (SPT) order as resources for measurement-based quantum com-putation (MBQC). Using tensor network methods, we show that SPT phasesprotected by a finite abelian on-site symmetry group exhibit uniform com-putational power. That is, any state from a given phase leads to the sameLie group of executable gates when used as a resource for MBQC. This Liegroup is determined by the same algebraic information that labels the SPTphase itself, and we give a necessary condition on the phase that guaranteesa full set of single-qubit gates. To obtain our results, we construct severalnew techniques in MBQC and refine the structure of quantum states withabelian SPT order. Our results are analogous to similar results relatingtopological order and topological quantum computation, and we commentson their implications on the general connection between quantum phases ofmatter and quantum computation.iiLay SummaryThe organization of matter into distinct phases is a fundamental propertyof physics with numerous practical applications. Water in its liquid, gas,and solid phases is essential for life, while magnetic materials in their or-dered phase provide the basis for memory in computers. An exciting areaof current research suggests that certain phases of matter may also help inbuilding the coveted quantum computer. A quantum computer uses quan-tum resources like entangled particles to solve certain problems faster thanany conventional computer. Recently, it has been suggested that the use-fulness of these quantum resources for computation depends only on theirphase, akin to deducing properties of chemical elements from their locationin the periodic table. This thesis shows that this is true for a class of exoticphases of matter called the symmetry-protected topological phases, point-ing to the possibility of a deep relation between quantum computation andphases of matter.iiiPrefaceThe contents of this thesis have lead to two publications: Computationalpower of symmetry-protected topological phases published in Physical Re-view Letters, 2017 [1] and Symmetry-protected topological phases with uni-form computational power in one dimension published in Physical ReviewA, 2017 [2], involving the following co-authors: Robert Raussendorf, Dong-Sheng Wang, Abhishodh Prakash, and Tzu-Chieh Wei. The former publica-tion was written by myself, while the latter was written by R. Raussendorf.Parts of the the former publication have been reproduced verbatim in thisthesis in Chapter 3, Section 5.3, and Appendix A.All sections of this thesis are written by myself, with the exception ofSection 3.3, which was written by R. Raussendorf. Chapter 3 involves themost collaboration between the above authors and myself. The constructionof the three computational steps leading to a Lie group of gates is duemainly to R. Raussendorf. The interpretation of these techniques, theirrelation to symmetry-protected topological order, and certain other detailswere discovered by myself, aided by discussions with all above authors. Theresearch found in Chapters 4 and 5 was done primarily by myself, aided bydiscussion with R. Raussendorf and D. -S. Wang.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . viii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Gapped quantum systems and the area law . . . . . . . . . . 42.2 Matrix product states . . . . . . . . . . . . . . . . . . . . . . 52.2.1 Injectivity . . . . . . . . . . . . . . . . . . . . . . . . 72.2.2 Canonical form and symmetries . . . . . . . . . . . . 82.3 Quantum phases of matter . . . . . . . . . . . . . . . . . . . 92.3.1 Definition of gapped phases of matter . . . . . . . . . 102.3.2 Symmetry-protected topological phases in 1D . . . . 112.4 Measurement-based quantum computation . . . . . . . . . . 132.4.1 Computation in virtual space . . . . . . . . . . . . . . 132.5 Computational phases of matter . . . . . . . . . . . . . . . . 153 Computation with maximally non-commutative SPT phases 183.1 Computation in the Haldane phase . . . . . . . . . . . . . . 183.2 Generalization to maximally non-commutative phases . . . . 213.3 Error and cost analysis . . . . . . . . . . . . . . . . . . . . . 223.4 Main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 23vTable of Contents4 Computation in general abelian SPT phases . . . . . . . . . 254.1 A phase with no logical subspace . . . . . . . . . . . . . . . . 254.2 Structure of abelian SPT phases . . . . . . . . . . . . . . . . 264.2.1 Clebsch-Gordon decomposition . . . . . . . . . . . . . 274.2.2 Main structure theorem . . . . . . . . . . . . . . . . . 284.2.3 Refining structure . . . . . . . . . . . . . . . . . . . . 304.3 Computation in abelian SPT phases . . . . . . . . . . . . . . 314.3.1 Encoding and byproduct propagation . . . . . . . . . 314.3.2 Oblivious wire . . . . . . . . . . . . . . . . . . . . . . 324.3.3 Infinitesimal gates and measurements . . . . . . . . . 334.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.5 Main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 365 Determining computational power . . . . . . . . . . . . . . . 375.1 Maximally non-commutative case . . . . . . . . . . . . . . . 375.2 Non-universality in abelian phases . . . . . . . . . . . . . . . 385.3 Proof of Theorem 7 . . . . . . . . . . . . . . . . . . . . . . . 395.3.1 Graphical Description of Computational Power . . . . 395.4 Example: G = Zn × Zn . . . . . . . . . . . . . . . . . . . . . 436 Conclusions and Outlook . . . . . . . . . . . . . . . . . . . . . 45Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48AppendicesA Born rule and mixed state interprtation . . . . . . . . . . . 56A.1 Mixed state interpretation . . . . . . . . . . . . . . . . . . . 57viList of Figures2.1 Tensor networks and matrix product states . . . . . . . . . . 52.2 Symmetries of an MPS . . . . . . . . . . . . . . . . . . . . . . 92.3 Finite depth quantum circuit . . . . . . . . . . . . . . . . . . 112.4 Byproduct propagation by symmetry . . . . . . . . . . . . . . 143.1 Schematic diagram of the computational methods . . . . . . . 195.1 Graphical proof of Theorem 7 . . . . . . . . . . . . . . . . . . 406.1 Summary of the relation between phases of matter and com-putation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46viiAcknowledgementsI will be eternally grateful to my supervisor, Robert Raussendorf, for helpingme to mature as a physicist, conquer my self-doubts, and find my passion.I attribute the success of my degree to his constant support, guidance, tute-lage, and the countless opportunities to connect to other members of myfield that he presented to me.I would also like to thank my fellow students and the staff at UBC fortheir support both on and off campus, particularly the members of the UBCquantum information group and my roommate, rival, and long-time friendJordan Wilson.viiiChapter 1IntroductionThis thesis lies at the intersection between the fields of condensed matterphysics and quantum information science. We study the relationship be-tween two phenomena of highly-entangled many-body quantum systems:quantum phases of matter and quantum computation. Due to the interdis-ciplinary nature of this thesis, our motivation can come from two differentperspectives.Let us start from the condensed matter side. A phase of matter is a col-lection of states of a system that share some property distinct from states ina different phase. In many-body physics, the essential properties of a stateare often determined by the phase of matter in which it resides. Recentyears have witnessed tremendous progress in the discovery and classificationof exotic quantum phases [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], and it is thuspertinent to ask—what can a phase of matter be used for? A traditional ex-ample is the ubiquitous superconductor, while newly discovered phases suchas topological insulators [14] and quantum spin liquids [15] have promisingfuture applications. Quantum phases are useful in quantum informationprocessing as well: certain topological phases allow for error-resilient topo-logical quantum computation via the braiding and fusion of their anyonicexcitations [16, 17].Why is it beneficial for an application to take advantage of a phase ofmatter? For one, they require less accuracy in their preparation, which needsonly prepare any state from a given phase, rather than a particular targetstate. Furthermore, applications which utilize the topological properties ofphases, such as topological quantum computation, are robust against anylocal sources of noise which cannot detect the non-local topological features.Unfortunately, despite the rich zoo of quantum phases, existing applicationstend to use only the simplest examples of quantum phases, such as thesimple Z2 topological order of the toric code [16]. This leads one to seekapplications that delve deeper into the algebraic framework underpinningthe classification of phases, possibly leading to useful or interesting newphenomena. This is the first goal of this thesis.On the other side we have quantum computation, which is a method1Chapter 1. Introductionof computation that exploits quantum resources to achieve computationalspeedups over classical algorithms [18]. A preeminent example of this isShor’s algorithm [19], which solves the factoring problem exponentially fasterthan any known classical algorithm. Despite the apparent supremacy ofquantum computers over their classical counterparts, the source of quantumcomputational power remains unknown. It is not clear which phenomenaof quantum mechanics are responsible for the observed speedup, whetherit be superposition [20], entanglement [21], or more contemporary ideaslike contextuality [22, 23]. Solving this problem would lead to a deeperunderstand of the relationship between quantum mechanics and informationtheory, and better guidelines to design new quantum algorithms.In a particular model of quantum computation called measurement-based quantum computation (MBQC) [24, 25], the quantum resource is ahighly-entangled state of a many-body quantum system—a resource state.Computation is implemented through the use of single-body projective mea-surements alone, such that the power of an MBQC scheme is completely de-termined by the properties of the resource state. Because of this, MBQC pro-vides a setting in which the above problem can be phrased in terms of prop-erties of many-body quantum states, and therefore in the realm of condensedmatter physics. The most relevant question in the context of quantumphases is whether the computational power of MBQC is particular to indi-vidual states, or a property of a phase of matter. This is a long-standing openproblem in the field [26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40].Identifying computational phases of matter, where a physical phase corre-sponds with a region of uniform computational power, is the second goal ofthis thesis.In this thesis, we successfully address the two goals given above. Weconsider the symmetry-protected topological (SPT) phases of matter of spinchains [5, 6, 7], and show that every state in a given phase has equivalentpower as a resource state for MBQC. Furthermore, our results make full useof the algebraic structures that classify SPT phases and reveal that the samestructures also determine MBQC power. Overall, this thesis contributes tothe effort to unite the fields of quantum phases of matter and quantumcomputation, and investigate how research in one may aid or influence theother.In the following chapter, we give the necessary background from bothfields. We first introduce SPT phases and MBQC, and see how they can bothbe compactly described using the language of matrix product states. We willsee that SPT phases are characterized by certain patterns of entanglement,and that it is exactly this entanglement that we use for computation. We2Chapter 1. Introductionthen review the history of the search for computational phases of matter,leading into our own results. In Chapter 3, we introduce three new compu-tational elements that allow us to construct a general scheme of MBQC thattakes advantage of the part of a quantum state that is uniform throughouta phase. With this, we show that MBQC power is uniform in SPT phases,subject to a condition called maximal non-commutativity. In Chapter 4, weremove this condition, proving the necessary theorems about the structureof quantum states with SPT order and adding new computational tech-niques. Then, in Chapter 5, we determine the uniform computational powerof these phases in terms of a Lie group of executable operations, provingthat the maximally non-commutative phases always allow for a full set ofsingle-qubit operations. Finally, in Chapter 6, we discuss possible exten-sions of our results, as well as their impact on the general relation betweenquantum phases of matter and quantum computation.3Chapter 2Background2.1 Gapped quantum systems and the area lawIn this thesis, we will consider quantum spins chains. These are systemsthat consist of spin degrees of freedom arranged in a one dimensional (1D)line. Here, by a spin degree of freedom, we simply mean a finite dimensionalHilbert space; a d-dimensional spin is associated to a Hilbert space Cd, suchthat total Hilbert space of a chain of length N is H = (Cd)⊗N . More specif-ically, we consider the ground states of gapped local Hamiltonians actingon these chains, which are defined by local interactions and a finite gap be-tween the ground state energy and the next excited state that persists as thesystem size is increased. Such gapped quantum systems, besides providing asetting for interesting and exotic physical phenomena, are also good modelsof certain strongly-correlated systems. These the include half-filled Hubbardmodel that describes magnetic properties of crystals [41], and many systemsused for quantum simulations [42] such as optical lattices [43, 44] or certainsuperconducting circuits [45].In general, the Hilbert space dimension of our spin chain is exponentialin its length, a fact that prohibits naive numerical and analytical studies ofsuch systems even for modest system sizes of N ≈ 50. Luckily, one avoidsthis problem by considering gapped quantum states, which have very littleentanglement as quantified by the area law [46]. The area law, which hasbeen rigorously proven for gapped quantum systems in 1D [47], says thatthe entanglement between two regions scales with the size of the boundarybetween them, rather than their volume as would be expected from a genericstate [48]. Because of this, gapped quantum systems occupy only a tinyfraction of the total available Hilbert space, the so-called “physical corner”.This makes such systems amicable to more efficient descriptions that alsoexplore only the physical corner, serving as a basis for powerful numericaltechniques and new mathematical tools. One such example is the tensornetworks formalism, which is the central tool used for the analysis in thisthesis.42.2. Matrix product statesFigure 2.1: Tensor network representations of the objects encountered inthis section. a) An N index tensor like ci1,...,iN is represented by a boxwith N legs. b) The matrix elements Aiαβ of the MPS matrices can berepresented by an 3-leg tensor. i corresponds to the physical index, whilethe other two are virtual indices. c) Joining legs of two tensors correspondsto summing over that index, so this network represents Eq. 2.2. d) Tensornetwork representation of Eq. 2.32.2 Matrix product statesIn this section, we introduce matrix product states (MPS) [49], which are thesimplest example of the more general tensor network states. As proven inRefs. [47, 50, 51], the ground states of gapped 1D systems can be efficientlyrepresented by MPS. Conversely, every MPS is the ground state of a gappedspin chain satisfying an area law, so they are an essential tool for exploringthe physical corner of Hilbert space.A general wavefunction of a spin chain consisting of N spins of dimensiond can be written as:|ψ〉 =d−1∑i1,...,iN=0ci1,...,iN |i1 . . . iN 〉 (2.1)Here we would like to interpret ci1,...,iN as an N -index tensor with dN co-efficients that specifies the wavefunction of our N spins, see Fig. 2.1a). Torepresent this state as an MPS, we decompose this tensor into a numberof smaller tensors1. For a translationally invariant system with periodic1While this decomposition can be always be accomplished via successive schmidt de-composition [21], we consider states that are given to us already in MPS form.52.2. Matrix product statesboundary conditions (ie. a ring), we write|ψ〉 =∑i1,...,iNTr(AiNAiN−1 . . . Ai1) |i1 . . . iN 〉 (2.2)See Fig. 2.1c). Here the MPS matrices Ai are χ × χ matrices where χ iscalled the virtual dimension or bond dimension of the MPS. These matricesact in the virtual space of the tensor network. The origin of the name MPSis now apparent: The overlap of |ψ〉 with any configuration of the localspins |s1s2 . . . sN 〉 is efficiently determined by tracing the product of matricesA[s1]A[s2] . . . A[sN ], where A[s] =(∑i〈s|i〉Ai). This fact, combined withthe fact that we now have only dχ2 coeffcients (Ndχ2 in the absence oftranslation invariance) rather than dN , underpins the success of MPS in 1Dnumerical techniques such as the density matrix renormalization group [52,53].If we choose to have open boundary conditions, our state takes the gen-eral form of|ψ〉 =∑i1,...,iN〈R|AiNAiN−1 . . . Ai1 |L〉|i1 . . . iN 〉. (2.3)Here, the boundary conditions are specified by the vectors |L〉 and |R〉 livingin the virtual space, see Fig. 2.1d). The open boundary form is what we willconsider for the remainder of this thesis.Example: The AKLT stateThe prototypical example of a MPS is the Affleck-Kennedy-Lieb-Tasaki(AKLT) state [54]. This is the ground state of the following spin-1 Hamil-tonian written in terms of the spin-1 operators ~Sj acting on site j:H =∑j12~Sj · ~Sj+1 + 16(~Sj · ~Sj+1)2+13. (2.4)The AKLT state can be written as a MPS with χ = 2. The MPS matrices arethe Pauli matrices, Ai = σi, with respect to the wire basis B = {|x〉, |y〉, |z〉}where |i〉 is the 0 eigenstate of the i-th component of ~S. This example willbe referred to several times throughout this thesis due to its relevance toboth quantum phases and quantum computation.62.2. Matrix product states2.2.1 InjectivityIn this thesis, we will only consider MPS that satisfy a property called injec-tivity. This condition is equivalent to many important physical properties,and it also is an essential tool in proofs due to its connection to quantumchannels.One motivation for this assumption, besides its technical use, is relatedto certain experimental considerations. To every MPS, we can associatea gapped, local parent Hamiltonian for which the MPS is a (possibly de-generate) ground state [49]. Injectivity is equivalent to the condition thatthe MPS with periodic boundaries is the unique ground state of its parentHamiltonian [49]. If we aim to prepare our states by cooling a physicalsystem subject to the parent Hamiltonian, then this uniqueness is essential.To define injectivity, we need to introduce the following quantum chan-nel:E(X) =∑iAi(X)Ai†. (2.5)Such a channel is naturally associated to every MPS, and it encodes manyof the important physical properties. It will also appear as part of ourcomputational scheme in the next chapter. We can always assume thatthe largest eigenvalue of this map is 1 by proper normalization of the MPSmatrices. Since this channel is completely positive, it always has a positivefixed point ρfix [49]. One possible definition of injectivity is in terms of theother eigenvalues of E :Definition 1. [49] A MPS is injective if the channel E has only one eigen-value of modulus 1.This definition shows that, for injective MPS, ρfix is the unique fixedpoint of E . While we have chosen this as our definition of injectivity, thereare a number of equivalent conditions on both E and the MPS matrices Ai:Theorem 1. [55] Given a MPS described by the matrices Ai, the followingconditions are equivalent:1. The MPS is injective.2. The map defined by ΓL(X) =∑i1...iLTr(XAiL . . . Ai1) |i1 . . . iL〉 isinjective for some finite L.3. The set of products matrices {Ai1Ai2 . . . AiL} spans the whole space ofχ× χ matrices for the same L as in condition (2).72.2. Matrix product states4. There exists some q ≤ L such that, for every density operator ρ, Eq(ρ)has full rank.All of these conditions will be relevant to our cause. For example, wemay use them to deduce useful physical properties that are consequencesof injectivity, in addition to uniqueness of ground state. Perhaps the mostimmediate is that an injective MPS has a finite correlation length. A simplecalculation shows that the correlation length of a MPS is given by ξ =−1/ ln |λ1| where λ1 is the second largest eigenvalue of E [56]. This is finiteif and only if E is injective.A consequence of condition (2) is that injectivity is necessary for com-putational readout. The map ΓL can be interpreted as a map from theboundary conditions of an open boundary chain of length L to the resultingquantum state (set X = |L〉〈R| to regain the form of Eq.2.3). If this mapis injective then different boundary conditions give rise to different states.This will be important to us later on when we encode information in thevirtual state |L〉. If different states |L〉 gave the same physical state, thenwe could not reliably deduce the information it encodes.2.2.2 Canonical form and symmetriesGiven a state |ψ〉, there is freedom in the choice of MPS representation.Given a set of MPS matrices Ai, one way to obtain a new set of matrices Biwhich represent the same state is by a gauge transformation, Bi = XAiX−1∀i for some invertible matrix X. It is clear the matrices Bi generate thesame MPS as Ai since the transformation matrices X annihilate pairwise inthe virtual space.Using a gauge transformation it is possible to put any MPS into a canon-ical form which has particularly nice properties:Theorem 2. [49] Given any translationally invariant and injective MPS,it is always possible to use gauge transformations such that• The unique fixed point ρfix of the channel E is the identity matrix I.• The adjoint channel E†(X) = ∑iAi†(X)Ai has a unique fixed point Λwhich can be taken to be a density matrix.In the non-injective case, an MPS decomposes as a superposition ofinjective MPS, each of which satisfy the theorem. The canonical form of anMPS is unique up to a unitary gauge transformation, a fact which is essentialto classifying symmetries in MPS. Indeed, we have the following fundamental82.3. Quantum phases of matterFigure 2.2: a) Illustration of Theorem 3. b) The on-site symmetry is equiv-alent to a virtual symmetry.result regarding on-site symmetries, which are symmetries which act locallyat every site in the same way:Theorem 3. [57] For an injective MPS, a unitary u is an onsite symmetry,u⊗N |ψ〉 = |ψ〉, if and only if there exists a unitary V and a phase eiθ suchthat∑j uijAj = eiθV †AiVFrom now on, we will absorb the phase eiθ into the unitary u such that wecan ignore it without loss of generality. See Fig. 2.2a) for a tensor networkdiagram illustrating this result. This result shows that it is possible todeduce the presence of an on-site symmetry of the whole state using onlythe symmetry properties of a single tensor Ai. Furthermore, it shows thatacting with the symmetry on the physical index is equivalent to a unitarygauge transformation on the virtual indices. Because of this, acting on allspins of an open chain with the symmetry u is equivalent to acting on theboundary states with V , see Fig. 2.2b). These facts are essential to ourunderstanding of quantum phases and quantum computation in 1D.2.3 Quantum phases of matterIn this section, we consider quantum phases of matter. These are families ofquantum states at zero temperature that cannot be connected without pass-ing through a phase transition, marked by the divergence of some physicalobservable. The simplest of phase transitions can be explained by sponta-neous symmetry breaking [58]. This process is defined by the situation inwhich the ground state has less symmetry than the Hamiltonian, and canbe completely understood by examining the original symmetry group and92.3. Quantum phases of matterthe broken symmetry subgroup. Because of this, the theory of symmetrybreaking phases of matter can be completely described using elementarygroup theory.However spontaneous symmetry breaking is inherently associated withground state degeneracy [59], and hence it is excluded by our assumptionof injectivity. Hence, in this section we consider the topological phases ofmatter, which do not involve symmetry breaking. We begin with a definitionthat reveals the nature of such phases, and then give an example of how theymay be classified using MPS technology, leading to mathematical structurebeyond elementary group theory.2.3.1 Definition of gapped phases of matterIn this section, we define gapped phases of matter, which are equivalenceclasses of ground states of gapped quantum systems related by finite depthquantum circuits [60]. A quantum circuit is defined by k layers of localunitaries that act on a state, see Fig. 2.3. Finite depth means that k doesnot grow with the size of the state (here, the length of the spin chain).Precisely, we define quantum phases as follows:Definition 2. [60] Two injective states |ψ0〉 and |ψ1〉 are in the same gappedquantum phase if there exists a finite depth circuit Uc such that Uc|ψ0〉 ∝|ψ1〉.Under this definition, the trivial phase contains all short-range entangledstates—those that can be transformed into local product states—and non-trivial phases are referred to the topological phases of matter. While thisdefinition may seem unfamiliar, it turns out to be essentially equivalent tothe definition that two states are in different phases if and only if they cannotbe smoothly connected without passing through a phase transition [60].This definition can be refined in the presence of symmetry. If a state |ψ〉has a symmetry G, such that U(g)|ψ〉 = |ψ〉 ∀g ∈ G for some representationU of G, then we can add the additional constraint that the finite depthcircuit Uc must also respect this symmetry, [Uc, U(g)] = 0 ∀g ∈ G. Eventhe trivial phase can split into many non-trivial phases in the presence ofsymmetry. These short-range entangled phases are called the symmetry-protected topological (SPT) phases of matter [5, 6, 7]. We note that it ispossible to extend the definition of SPT phases such that the representationU of the symmetry group G can vary throughout the phase [6]. In order tonot exclude this definition, we will also allow U to vary throughout our SPTphases.102.3. Quantum phases of matterFigure 2.3: A finite depth quantum circuit contains several layers of localgates (3 layers pictured), where the number of layers does not grow withsystem size.These definitions reveal the nature of quantum phases: they are definedby the entanglement structure of states. Topological order is characterizedby patterns of long-ranged entanglement that cannot be removed by thelocal operations of a finite depth circuit, whereas SPT order is character-ized by short-ranged, symmetric entanglement which cannot be removed bysymmetric local operations. This is the key insight of this section, as it isprecisely this symmetric entanglement that allows us to achieve quantumcomputation with SPT phases.2.3.2 Symmetry-protected topological phases in 1DIn this section we apply the MPS formalism to explain how SPT phasescan be classified in 1D. We consider MPS |ψ〉 with an onsite symmetryrepresented by a group G, meaning that there exists a unitary representationu of G, which acts on a single spin in the chain, such that u(g)N |ψ〉 = |ψ〉∀g ∈ G. Typical examples of an onsite symmetry are spin-flip symmetry(G = Z2) and spin-rotation symmetry (G = SU(N)). While it is possible toalso consider spatial symmetries like inversion and non-unitary time-reversalsymmetry, here we restrict to unitary on-site symmetries.The basic argument is this: On an open chain, we have degrees of freedomlocalised near the edge, spanned by the boundary vectors |L〉 and |R〉. Asshown in Fig. 2.2b), which now holds for all g ∈ G, the symmetry u(g) actsas V (g) on these edge modes. The non-trivialness of the SPT phase comesfrom the fact that these operators can be non-trivial representations of thesymmetry. What is the structure of the operators V (g) acting in the virtualspace? By using the fact that u(g)u(h) = u(gh), we find thatV (g)†V (h)†AiV (h)V (g) = V (gh)†AiV (gh). (2.6)112.3. Quantum phases of matterIf we apply this relation to L sites in a row, where L is the constant appearingin Theorem 1, we find that the above relation holds with Ai replaced byAi1 . . . AiL . By injectivity, the sets of such products span the space of wholematrices. Hence V (g)V (h)V (gh)† commutes with every matrix, and henceit must be a scalar matrix. Then we can writeV (g)V (h) = ω(g, h)V (gh), (2.7)showing that V (g) is a projective representation of G, with ω(g, h) the factorsystem. In the language of group cohomology ω(g, h) is called a cocycle. Thedetails of this language are not necessary to understand our results, so wedo not include them here. A detailed discussion of group cohomology andits application to SPT phases can be found in Refs. [5, 7].Notice that V (g) appears with its complex conjugate in Fig. 2.2a). Thismeans that we are free to rephase the representation, writing V ′(g) =β(g)V (g) for any phases β(g). If we rephase the representation in this way,the factor system is changed to ω′(g, h) = β(gh)β(g)β(h)ω(g, h). The factorβ(gh)β(g)β(h)is called a coboundary. We say that two cocycles are equivalent if they dif-fer only by a coboundary, as above, and denote equivalence classes by thecohomology class [ω]. The different cohomology classes form a finite groupH2[G,U(1)] called the second cohomology group of G.In Refs. [5, 6], it was proven that two states of a spin chain are in thesame SPT phase if and only if the projective representations of the symmetryacting on the virtual level of the MPS correspond to the same cohomologyclass. In a hand-waving argument, this makes sense because it is impossibleto smoothly interpolate between two such discrete labels, hence they labeldifferent phases. This means that, given a group G, the different possiblephases are labelled by elements of H2[G,U(1)], with the identity elementlabelling the trivial phase. We see that, in the same way group theorydescribes the possible symmetry breaking phases, group cohomology is thelanguage used to classify SPT phases.Example: SPT order of AKLT stateWe can use the above classification to show that the AKLT state has non-trivial SPT order. The symmetry group we consider consists of pi rotationsabout the x, y, and z axes; G = {e,Rx(pi), Ry(pi), Rz(pi)} ∼= Z2 × Z2. Ourbasis B = {|x〉, |y〉, |z〉} consists of rotation eigenstates, such that Ri(pi)leaves |i〉 invariant while giving the other two basis states a −1 phase factor,i = x, y, z. It is straightforward to check that this symmetry action can beachieved in the virtual space by setting V (Ri(pi)) = σi. The Pauli matrices122.4. Measurement-based quantum computationform a non-trivial projective representation of Z2 ×Z2, as evidenced by thefact that they do not commute. Hence, the AKLT state has non-trivialorder protected by Z2 × Z2. The corresponding SPT phase is known as theHaldane phase, which is another key example for the next chapter.2.4 Measurement-based quantum computationAs stated in the introduction, measurement-based quantum computation(MBQC) is model of quantum computation in which the quantum resourceis an entangled state of a many-body quantum system [24, 25]. Initialization,processing, and readout of information are all executed by interpreting theoutcomes of single-site projective measurements performed on the resourcestate. Which algorithm is executed is controlled by the order in which thesites are measured and the basis of measurement at each site. The compu-tational power of an MBQC scheme, defined by the set of logical gates thatcan be executed, is related to the entanglement structure of the resourcestate.Identifying the common properties of universal resource states, thosewhich leads to universal computation, is an ongoing problem in the field.With too little entanglement, measurement can be efficiently simulated witha classical computer [61, 62, 63]. However, it turns out that most quantumstates, in a quantifiable sense, are too entangled to be useful [64, 65]. Some-how, there exists a “sweet spot” of entanglement which balances richnessand structure. This thesis aims to argue that this particular kind of entan-glement is exactly that which is present in resource states with SPT order.To this effort, we use this section to show how MBQC can be understood inthe MPS picture.2.4.1 Computation in virtual spaceThe MPS representation of a spin chain leads to a unique picture of MBQCthat occurs in the virtual space of the tensor network [66, 67]. Consider aresource state with open boundaries in the form of Eq. 2.3. If we measurethe first spin in the chain with measurement outcome |s〉, then the resultingstate of the rest of the chain is:|ψ′〉 =∑i2,...,iN〈R|AiNAiN−1 . . . Ai2 |L′〉|i2 . . . iN 〉. (2.8)where |L′〉 = 1psA[s]|L〉 and ps is the probability of measuring outcome |s〉.We see that the length of the chain has been reduced by 1, and the left132.4. Measurement-based quantum computationFigure 2.4: Byproduct propagation by symmetryboundary condition has evolved in some way that depends on the mea-surement outcome |s〉. We are interested in resource states for which thisoperator is unitary for a proper choice of measurement basis, perhaps onlyon a subspace of the virtual space. In this case, projective measurement ofthe physical system is equivalent to unitary evolution of the virtual system.This is the strength of the virtual space picture of MBQC.An essential aspect of MBQC is byproduct propagation. While we canideally choose any basis for our measurement, we cannot control the out-come of measurement. For a given outcome, we decompose the resultingoperator into the desired gate and an outcome-dependent byproduct oper-ator acting in the virtual space. In general, this byproduct operator mustbe propagated through the computation by altering the bases of future mea-surements. In this way, we can eliminate part of the outcome-dependenceof the computation.The virtual space picture provides a particularly nice picture of byprod-uct propagation in terms of MPS symmetries [35]. Indeed, suppose thatour byproduct operator is an element V (g) of the virtual representation ofG. Then, by Fig. 2.2, if we act with u(g) on the next physical site, we canpropagate the byproduct operator past this site, see Fig. 2.4. This operationis achieved by modifying our intended measurement basis {|i〉} to {u(g)|i〉}.We can modify all future measurement bases in this same way to propagatethe byproduct to the very end of computation, where it affects the basisused for computational readout. It will turn out that, for resource stateswith certain types of SPT order, the byproduct operators are always in thevirtual symmetry representation, so they can always be propagated in thisway.142.5. Computational phases of matterExample: Computation with AKLT stateThe AKLT state provides a simple example of MBQC in virtual space [68].To achieve a rotation by θ about the z-axis, we measure in the basisB(z, θ) = {|θx〉, |θy〉, |z〉} ≡{cosθ2|x〉 − sin θ2|y〉, sin θ2|x〉+ cos θ2|y〉, |z〉}.(2.9)The resulting operator in virtual space for each possible measurement out-come is:|θx〉 : σxe−iθσz/2|θy〉 : σye−iθσz/2|z〉 : σz (2.10)As we saw in the previous section, the virtual representation of the AKLTstate’s Z2 × Z2 symmetry consists of the Pauli matrices. Hence, we cantreat any Pauli matrix acting in the virtual space as a byproduct operator.After propagation, we see that the first two results give the desired rotation,while the third enacts the identity gate. We see that computation with theAKLT state is probabilistic; the executed gate depends on the measurementoutcome even after byproduct propagation. However, if the gate fails, onecan simply attempt the rotation again, so that the only effect of this out-come dependence is an indeterminate length of chain needed to execute acomputation.One can similarly achieve arbitrary rotations about the x (and y) axes,thereby giving a full set of single-qubit SU(2) gates. Since the AKLT stateencodes only one qubit of information, we will say that it is a universalresource state, in a slight abuse of terminology. Is it possible that everystate within the Haldane phase has the same universality AKLT state? Thisquestion is answered affirmatively in the next section.2.5 Computational phases of matterIn an effort to understand the structure of resource states for MBQC, onemay ask the following question: If we begin with a universal resource stateand perturb it in some way, does it remain universal? This question beganby looking at perturbations caused by non-zero temperature [39, 27, 69] andlattice site deletion [26, 67]. In each case, it was shown that the resourceremained useful up to a certain threshold temperature or loss rate, which in152.5. Computational phases of mattersome cases also corresponded to a physical phase transition. This was thefirst evidence that phases of computational power may overlap with physicalphases.The idea of looking at zero-temperature quantum phases as resources be-gan with the effort to find resource states which are ground states of naturalHamiltonians, which naturally led to the question of whether changes in theparameters of these Hamiltonians could affect resource quality [70, 28, 29].To track the history of our approach and the connection to SPT phases, itis best to start with Miyake, who showed that the aforementioned compu-tational power of the AKLT state persists throughout an SO(3) invariantsubset of the Haldane phase [30]. This approach required more controlthan only projective measurements, but this was remedied the next yearby Bartlett et. al. [31]. The new scheme, dubbed “computational renor-malization”, used measurements to drive the resource state back towardsthe AKLT point, allowing computation to proceed. This scheme was unfor-tunately heavily specialized to the specific phase under consideration, andcould not be easily generalised.Later, a general result from Else et. al put the resource quality of Hal-dane phase on clearer footing using the language of MPS [35, 36]. Theyshowed that, for every phase with in the Haldane phase, the MPS matricestake the form:Ai = Bi ⊗ σi (2.11)for some square matrices Bi. Since the AKLT state satisfies Ai = σi, wesee that every state in the Haldane phase can be viewed as an AKLT statewith some additional entanglement on top. The microscopic details of thisentanglement are encoded in the Bi matrices, which vary freely throughoutthe phase, subject only to constraints of injectivity. We call the subspaceof virtual space in which the Pauli part acts the logical subspace, while thematrices Bi act in the junk subspace. The Z2 × Z2 symmetry acts non-trivially only in the logical subspace, V (Ri(pi)) = I⊗ σi.This result immediately explains the ability for states in the Haldanephase to execute the identity gate, ie. to transport quantum state alonga spin chain via measurement [36]. Indeed, measuring in the wire basisresults in Pauli evolution of the logical subspace which can be propagated viasymmetry. If we encode our logical qubit |φ〉 in this subspace, |L〉 = |J〉⊗|φ〉for some state |J〉, then measurement in the wire basis enacts the identitygate, as claimed. Since all microscopic details appear in the junk subspace,this works even without knowledge of which state in the phase is being162.5. Computational phases of matterused 2.The importance of this result came from its generality: it applies to anyphase satisfying a condition they called maximal non-commutativity, whichwe define later. Thus any state coming from a maximally non-commutativeSPT phase can act as a quantum wire. Unfortunately, this uniform com-putational power appeared to be restricted to the identity gate only. Toachieve a non-trivial gate, the basis of measurement must be changed. Butmeasurement outside of the wire basis will in general result in entangle-ment between the junk and logical subspaces [36]. Consider the case themeasurement outcome 1√2(|x〉+ |y〉) is obtained, giving|J〉 ⊗ |φ〉 → 1√2(Bx|J〉 ⊗ σx|φ〉+By|J〉 ⊗ σy|φ〉) . (2.12)Unless Bx = By, the resulting state is entangled between the two subspaces.Since there is no reason for this to hold in general, a random state from thephase cannot be used as a resource for non-trivial gates, at least not withoutsome additional steps to the computation.This was partially solved by Miller and Miyake, who translated the com-putational renormalization scheme of Bartlett et. al. into the MPS lan-guage [37]. They showed that, for the non-trivial SPT phase protected byS4, which is contained in the Haldane phase, the computational renormaliza-tion scheme has the effect of driving By and Bx to the same operator, suchthat the above measurement will not entangle the subspaces. This allowedthem to prove that the entire S4 phase could be used for SU(2) rotations ofthe logical qubit. Once again, this scheme relied on some specific propertiesof the particular phase, and could not obviously be extended to the othermaximally non-commutative phases.These works leave open several questions. Can other SPT phases supportnon-trivial gates throughout the phase? Can the maximal non-commutativityassumption be removed? Is there a way to determine which phases lead touniversal sets of gates? In the following chapters, we answer all three ques-tions affirmatively in the order given. We construct a novel scheme thatallows non-trivial gates throughout the entire Haldane phase, as well as ev-ery other maximally non-commutative phase. We then remove the maximalnon-commutativity property and examine what modifications to our schemeare required to still allow computation. We then determine which gates canbe executed in each SPT phase.2In reality, the steps required to initialize information into the logical subspace andlater read it out cannot be performed without some knowledge of the microscopic details,as observed in Ref. [71]17Chapter 3Computation withmaximally non-commutativeSPT phasesIn this section, we introduce three simple modifications to the usual MBQCscheme that allow the computational power of the AKLT state to extendthroughout the entire Haldane phase. These modifications are describedin Fig. 3. We then extend this scheme to all maximally non-commutativephases.3.1 Computation in the Haldane phaseWe begin this section by introducing the mixed state interpretation of MBQCthat will be used throughout this letter. Here we argue its validity, with aformal proof given in the Appendix. We define a computation by a sequenceof n measurement bases, which are fixed modulo byproduct propagation.That is, we do not allows a “trial-until-success” strategy as is required in thecomputational renormalization scheme mentioned in the previous chapter.In general, an input state |ψ〉 will be taken to a final state |ψ~s〉 whichdepends on the measurement outcomes ~s = (s1, . . . , sn). Then we mea-sure some observable O on |ψ~s〉, whose eigenvalues oi appear with prob-ability p(oi|~s). To garner measurement statistics of O, we must repeatthe computation many times, whereupon the full statistics are given byp(oi) =∑~s p(oi|~s)p~s where p~s is the probability of outcomes ~s. Thesestatistics are encoded in the mixed state σˆ =∑~s p~s|ψ~s〉〈ψ~s|, for instance〈O〉 = ∑~s p~s〈ψ~s|O|ψ~s〉 ≡ Tr (Oσˆ). Hence in this probabilistic scenario thecomputational output must be interpreted to be σˆ.To determine the mixed state σˆ, we simply sum over all possible out-comes of each measurement. It is crucial that this sum-over-outcomes isimplemented after byproduct propagation, making it very different fromsimply tracing over each spin in the chain. The byproducts accumulated at183.1. Computation in the Haldane phaseFigure 3.1: Illustration of the measurements needed to execute a rotationabout the z-axis in the Haldane phase example. Our scheme consists ofthree modifications to the usual MBQC procedure: (1) In analysis of thescheme, measurement outcomes are summed over, such that the computa-tional output is interpreted as a mixed state, (2) finite rotations are splitinto smaller pieces dθ that each differ only slightly from the identity, and (3)consecutive gates are separated by many applications of the identity gate.the end of the computation affect the basis of computational readout, duringwhich we do not sum over outcomes. By analysing the computation in thisway, we can design a sequence of measurement bases such that σˆ approx-imates the desired output. If the computation defined by this sequence ofmeasurements is repeated many times, it will deterministically produce thedesired measurement statistics of any observable O, even though each runof the algorithm may produce a different output state that is meaninglesson its own.Let us return to the AKLT state as an example. By measuring in thebasis B(z, θ) and summing over measurement outcomes, we find that aninitial state |L〉〈L| becomes:σˆ =23e−iθσz/2|L〉〈L|eiθσz/2 + 13|L〉〈L|. (3.1)Since the original gate is probabilistic, this is a mixed state and does notrepresent unitary evolution. However, for small angles dθ, it is unitary upto first order:σˆ = e−i23dθσz/2|L〉〈L|ei 23dθσz/2 +O(dθ2). (3.2)So for small rotation angles dθ, the mixed output state is our initial staterotated by a reduced angle 23dθ about the z-axis. Restriction to gates thatare close to the identity is an unavoidable consequence of the mixed stateinterpretation, and finite rotations must be split into many infinitesimalpieces. The number of measurements needed to execute a unitary gate withrotation angle θ and admissible error  is O(θ2/), as we discuss in detail atthe end of this section.193.1. Computation in the Haldane phaseNow consider the effect of a measurement in the infinitesimally tiltedbasis B(z, dθ) on an arbitrary state in the Haldane phase. Without loss ofgenerality, we assume that our initial state is factorized across the subspacesas I ⊗ |φ〉〈φ|. If we get the outcome |θx〉 and propagate σx on the logicalsubspace, our state becomes:I⊗ |φ〉〈φ| → BxBx† ⊗ |φ〉〈φ| (3.3)+ idθ2(BxBy† ⊗ |φ〉〈φ|σz −ByBx† ⊗ σz|φ〉〈φ|),up to first order in dθ. As before, we see that the two subsystems are nolonger factorized, and the logical state |φ〉〈φ| has become entangled with themicroscopic details of the junk state.To remedy this, we will flow the junk subspace towards a fixed point usinga technique called the oblivious wire. The oblivious wire is implementedsimply measuring a large number m of spins in the wire basis, pictured inFig. 3 as a dotted box. In the mixed state interpretation, a measurement inthe wire basis followed by logical byproduct propagation effects the operation∑iBi(·)Bi† ⊗ I ≡ E˜ ⊗ I. Since our resource state is injective E˜ will havea unique fixed point I, since otherwise E would have more than one fixedpoint. Hence the oblivious wire results in the linear channel E˜m ⊗ I thatprojects the junk subspace onto the fixed point I. The projection occursexponentially fast over the correlation length ξ of the state.Applying this to Eq. 3.3, which must be summed with its counterpartsfor the other measurement outcomes |θy〉 and |z〉, we find that for largeenough m,σˆ = I⊗(ν|φ〉〈φ|+ idθ2(νxy + νyx) [|φ〉〈φ|, σz]), (3.4)where we have defined limm→∞ E˜m(BiBj†) = νijI and ν = νxx + νyy + νzz.Up to first order in dθ, this corresponds to a unitary rotation acting on thelogical subspace:T (z, dθ) = exp{−idθ(νxy + νyx2ν)σz}. (3.5)Hence, making a measurement in the rotated basis B(z, dθ), followed by aseries of measurements in the wire basis, produces the desired rotation of thevirtual state |φ〉 up to a scaling factor νxy+νyxν . As long as this factor is non-zero, it can be measured on the chain prior to computation by attemptinga finite rotation (split into small pieces), and measuring the reduction in203.2. Generalization to maximally non-commutative phasesrotation angle. The parameters νij contain all relevant microscopic detailsof our resource state. Since they can be measured during a calibration step,any state in the phase can be used as a resource without prior knowledge ofits identity.We can repeat the above procedure for rotations about the x-axis togenerate all of SU(2). Hence every state in the Haldane phase, with theexception of a null subset in which some of the constants νij are 0, has thesame computational power as the AKLT state (which satisfies νij = 13 ∀i, j).3.2 Generalization to maximallynon-commutative phasesThe above techniques do not depend on any properties that are particular tothe Haldane phase, so they can be generalised to a large class of other SPTphases. The Haldane phase is an example of a maximally non-commutativeSPT phase, first defined in Ref. [36]. Such phases satisfy all conditionsneeded to apply our methods, namely the existence of a logical subspaceand the ability to propagate byproduct operators within it. Indeed, supposethat G is finite abelian and [ω] is maximally non-commutative, meaning{g ∈ G|ω(g, g′) = ω(g′, g) ∀g′ ∈ G} = {e}. By diagonalizing the rep-resentation u, we obtain the wire basis B = {|0〉, . . . , |d− 1〉} such thatu(g)|i〉 = χi(g)|i〉 ∀g ∈ G where χi(g) are linear characters of G. Maximalnon-commutativity then implies the MPS tensor Ai can be written in thewire basis as [36]:Ai = Bi ⊗ Ci, (3.6)where Ci are D×D unitary and trace-orthogonal matrices and D = √|G| isthe dimension of our logical subspace 3. Ci can be determined uniquely fromG, [ω], and χi as described in Chapter 4. Furthermore, the operators I⊗Ciare always in virtual representation of the symmetry group, so they can bepropagated as byproducts in the usual way. In general, if some group G has afinite abelian subgroup H such that [ω|H ] is maximally non-commutative, wecan make the exact same argument with H taking the place of G everywhere.This means the following results also apply to certain non-abelian groupsand Lie groups. A full proof of these results is given in greater generality inthe next chapter.3D is always defined since any finite abelian group which supports a maximally non-commutative factor system must have the form G ∼= G′ ×G′ for some subgroup G′ [72].213.3. Error and cost analysisNow we add the same three ingredients used to perform computation inthe Haldane phase: the mixed state interpretation, restriction to infinitesi-mal gates, and the oblivious wire. Measurement in the slightly tilted basisB(i, j; dθ, ϕ) = {|0〉, . . . , |i〉+ dθeiϕ|j〉, |j〉 − dθe−iϕ|i〉, . . . , |d− 1〉}, followedby the oblivious wire to drive the junk subspace to a fixed-point state, in-duces an infinitesimal rotation in the logical subspace:T (i, j; dθ, ϕ) = (3.7)exp{dθ|νij |ν(ei(ϕ+δij)Ci†Cj − e−i(ϕ+δij)Cj†Ci)},where νij = |νij |eiδij is as defined earlier and ν = ∑d−1i=0 νii. As before, themicroscopic details of the state enter only as these measurable constants.Computation can only proceed if these constants are non-zero, which issatisfied for all but a null set of states. With knowledge of these constants,B(i, j; dθ, ϕ) can be chosen such that the primitive gates are generated byelements of the set of anti-hermitian operators:O ={αCi†Cj − α∗Cj†Ci}(3.8)with i, j = 0 . . . d−1, i 6= j, |α|  1. Furthermore, we have edθAedθBe−dθAe−dθB ≈e(dθ)2[A,B], so that our infinitesimal generators form a real Lie algebra A[O]which in turn generates a Lie group L[O] of executable gates.To complete the scheme, we would require a method to read out and ini-tialize the virtual state which also works throughout the phase. In Ref. [2],it is shown that, by measuring in finitely tilted bases, rather than the in-finitesimally tilted bases used for gates, one can approximate a projectivemeasurement of any observable in O on the logical subspace. This sufficesfor both initialization and readout.3.3 Error and cost analysisThe gates described above are only approximations of the desired gate. Herewe address the question of what the computational cost is to implementa unitary gate with rotation angle θ while allowing for an error . Thebasic argument is that if a rotation about an angle θ is subdivided into Nrotations about an angle θ/N , then the error per individual small rotation isof order (θ/N)2, and the cumulative error over N such rotations is thus N =O(1/N). Hence, to get by with a total error of , we require a subdivisionof the rotation into N ∼ 1/ steps.223.4. Main theoremIn more detail, there are two sources of error in the present constructionfor unitary gates. First, an elementary unitary operation with small rotationangle dθ incurs an error at second order in dθ, as discussed above. Second,every individual rotation T (dθ) requires the junk system to be brought intothe fixed point state ρfix. This could be achieved by measuring an infinitenumber of spins in the wire basis. In any reasonable implementation, wemeasure only a finite number of spins, producing an error in the state of thejunk system compared to the true fixed point state. Fortunately, this erroris exponentially small in the number n of measured spins,‖ρjunk − ρfix‖ ∼ exp(−n/ξ˜),where ξ˜ is a correlation length ξ˜ = − ln(λ1) associated to the junk subsystem,with λ1 the second-largest eigenvalue of the channel E˜ . This correlationlength is less than or equal to the true correlation length ξ of our resourcestate.The cumulative error due to imperfect preparation of the fixed pointstate of the junk system is fix = O (Nλ1n). Therefore, the choicen = 2ξ˜ logN (3.9)leads to an error fix = O(1/N), which is the same scaling as for N .Splitting the total error  evenly between fix and N , fix = N = /2,we find that we can achieve a total error of  for the choiceN ∼ 1.With Eq. (3.9), the total cost of implementing a unitary gate within an error, in terms of total number C = N(n+ 1) of local measurements, is thusC = O(ξ˜log(1)). (3.10)3.4 Main theoremWith the above discussion, we are ready to state our first main result as thefollowing theorem:Theorem 4. Consider a state in a symmetry-protected topological phasewithout symmetry breaking described by a group G, an on-site representationu, and a cohomology class [ω]. If there exists a finite abelian subgroup H ⊂ G233.4. Main theoremsuch that [ω|H ] is maximally non-commutative, then for any state in thephase, except a null subset, a Lie group of gates determined only by G, u,and [ω] can be efficiently implemented in MBQC with arbitrary high gatefidelity.Before the computation, we must determine the constants νij in a calibrationstep. The null subset refers to those states for which νij = 0 for some i, j.Theorem 4 showcases the main strength of our methods. Given onlythe algebraic quantities G, u, and [ω] which describe the SPT phase of ourresource state, we are able to define a complete MBQC scheme, includingthe set of gates and the measurements needed to execute them. The com-putational power of each state in the phase is uniformly defined as the Liegroup L[O], which is completely determined by the same algebraic quanti-ties. This signifies the existence of a deep connection between SPT orderand MBQC via the language of group cohomology. In a later chapter, weprove that this Lie group always contains a full set of single-qudit relations,regardless of the representation u. This shows that ground states with SPTorder are generically useful as MBQC resources.Now we must ask: which symmetry groups protect phases that satisfyTheorem 4? To answer this in general is a difficult problem of group coho-mology, but we can identify some particularly relevant examples. When Gis a classical Lie group (except Spin(4n)), there is a subgroup of the formZN × ZN ⊂ G such that H2(G,U(1)) ∼= H2(ZN × ZN , U(1)) [73, 74]. SinceZN × ZN protects a maximally non-commutative phase [72, 36], G mustprotect a phase which satisfies our theorem. The same can be said for anysubgroup G′ such that ZN ×ZN ⊂ G′ ⊂ G. This has already been observedin Ref. [38] for the groups D4, A4, S4 ⊂ SO(3), which each contain Z2 ×Z2.Another example is the class of groups for which the subgroup H specifiedin Theorem 4 appears as a (semi)direct factor, that is G = H ′oH for somesubgroup H ′ which could represent eg. time reversal symmetry [75].24Chapter 4Computation in generalabelian SPT phasesThe results of the previous chapter were dependent on the condition of max-imal non-commutativity of the SPT phase, which guarantees that a decom-position of the form Ai = Bi⊗Ci holds throughout the phase. Certainly thisform makes it clear that there is a protected subspace in which informationcan be encoded, but is it required?In Ref. [71] the idea of SPT-entanglement is introduced, although previ-ous works investigated similar ideas [73, 76]. For all abelian SPT phases, theSPT-entanglement is a formal order parameter that detects the symmetricentanglement that is present throughout SPT phases. In this setting, thereis no essential difference when assuming maximal non-commutativity; it sim-ple corresponds to the case where the SPT-entanglement is maximised. Inlight of this, one is led to question whether this condition of maximal non-commutativity is necessary to perform MBQC using SPT-entanglement. Inthis chapter, we show that this is not, and that our computational schemecan be extended to general abelian SPT phases, which we define as phasesthat can be protected by a finite abelian group. Note the wording “canbe protected”, which emphasizes that the finite abelian group may be asubgroup of the full symmetry group.4.1 A phase with no logical subspaceBefore proving general results on the structure of abelian SPT phases, wepresent the simplest example of a non-trivial SPT phase that does not havethe structure Ai = Bi⊗Ci. The symmetry group is Z4×Z2. Since H2[Z4×Z2, U(1)] = Z2, we have only one non-trivial phase. When only the Z2 ×Z2subgroup is enforced this phase becomes trivial, so we cannot use Theorem4. Using the Clebsch-Gordon methods of Ref. [38], we can constrain the formof the MPS matrices for states in this phase. The different matrices can belabelled by the 8 different 1D irreps χi(g) of Z4×Z2, i = 0, . . . , 7. The matrix254.2. Structure of abelian SPT phasesAi is associated to a basis state |i〉 which transforms like u(g)|i〉 = χi(g)|i〉.The resulting matrices have the following forms:A0 =(B011 ⊗ I 00 B022 ⊗ I)A1 =(B111 ⊗ σz 00 B122 ⊗ σz)A2 =(B211 ⊗ σy 00 B222 ⊗ σy)A3 =(B311 ⊗ σx 00 B322 ⊗ σx)A4 =(0 B412 ⊗ σzB421 ⊗ σx 0)A5 =(0 B512 ⊗ IB521 ⊗ σy 0)A6 =(0 B612 ⊗ σxB621 ⊗ σz 0)A7 =(0 B712 ⊗ σyB721 ⊗ I 0)The symmetry representation u(g) is built up of these 1D irreps. Notevery choice is allowed, since it must lead to an injective MPS. For example,if u(g) consists only of irreps χi(g) for i = 0, . . . 3, then there is a tensorproduct structure, but also the virtual space will be block diagonal andhence non-injective, which contradicts the method used to construct thesematrices. No injective state in this phase admits a structure of the formAi = Bi ⊗ Ci. This phase the simplest example of the general structure wederive in the following section.4.2 Structure of abelian SPT phasesLet G be our symmetry group, and [ω] a non-trivial cohomology class la-belling our phase. Since we are dealing with an abelian group, the physicalrepresentation of the symmetry must be diagonal, so thatu(g) =d−1⊕i=0χi(g) ∀g ∈ G264.2. Structure of abelian SPT phaseswhere each χi is a linear character of G (a 1D representation). We willcall the basis in which u(g) is diagonal the wire basis B as before. Thecorresponding representation in the virtual space has the general form:V (g) =⊕αInα ⊗ Vα(g)where Vα(g) are all of the irreducible projective representations with factorsystem ω (ω-irreps), and nα is the number of times irrep α appears. We nowrequire an essential fact about projective representations of abelian groups:all Vα(g) corresponding to the same cohomology class are projectively equiv-alent [77]. That is, we can writeVα(g) = λα(g)UαV˜ (g)U†α,for some preferred irrep V˜ (g) which will be identified later. Let D denotethe common dimension of these irreps. We will ignore the unitaries Uα,which can be eliminated by proper choice of the basis in virtual space. Notethat the case where [ω] is maximally noncommutative is equivalent to therebeing only one ω-irrep, ie. only one block in the virtual space [72].4.2.1 Clebsch-Gordon decompositionTo find the form of ground states in abelian SPT phases, we present a proofthat can be viewed as either a generalisation of the proof in Ref. [36] or arestriction of that found in Ref. [38] to abelian SPT phases.In this setting, the symmetry relation of Fig. 2.2a) reads:(⊕αInα ⊗ χi(g)Vα(g))Ai = Ai(⊕αInα ⊗ Vα(g))(4.1)Now χi(g)Vα(g) is still an ω representation of G, so it is equivalent to anω-irrep which we denote Vpii(g)(g):χi(g)Vα(g) = Cipii(α)Vpii(α)Ci†pii(α)(4.2)where Cipii(α) are the Clebsch-Gordon matrices associated with the fusionof irreps i ⊗ α. This fusion induces induces a permutation pii(α) of irrepsaccording to the Clebsch-Gordon series:1 =1|G|∑g∈Gχi(g)TrVα(g)TrVpii(α)(g)∗. (4.3)274.2. Structure of abelian SPT phasesWith this, we can rewrite Eq. 4.1 as(⊕αInpi−1i(α)⊗ Vα(g))[(⊕αInpi−1i(α)⊗ Ci†α)PiAi]= (4.4)[(⊕αInpi−1i(α)⊗ Ci†α)PiAi](⊕αInα ⊗ Vα(g)). (4.5)Here, we have introduced the matrix Pi which permutes blocks of the virtualspace in accordance with the action of pii on the irreps. Now, by Schur’sLemma, we have:(⊕αInpi−1i(α)⊗ Ci†α)PiAi =⊕αBiα ⊗ ID, (4.6)where Biα is some npi−1i (α)× nα matrix. Finally, we have:Ai = P †i(⊕αBiα ⊗ Ciα). (4.7)When ω is maximally non-commutative, there is only one ω-irrep, henceonly one block in virtual space, and the above form reduces to the morefamiliar Ai = Bi ⊗ Ci. In the general case, we see that the MPS matricesact in the virtual space as a junk and logical operator in each block followedby a permutation of blocks. The logical operators are the Clebsch-Gordoncoefficients. This structure agrees with our Z4 × Z2 example.4.2.2 Main structure theoremWe now prove that the Clebsch-Gordon matrices which will be our logicaloperators are in the projective symmetry irrep V˜ (g), such that we will beable to use the standard method of byproduct propagation. First, we definethe linear character χiα = χiλαλ−1pii(α)and rewrite Eq. 4.2 as:χiα(g)V (g) = CiαV˜ (g)Ci†α (4.8)Theorem 5. The CG-matrices Ciα are in the projective symmetry represen-tation V˜ (g). That is, we have Ciα = V˜ (giα) where giα is uniquely determinedby the relation:χiα(g) = ω(giα, g)ω(g, giα)−1284.2. Structure of abelian SPT phasesTo set up the proof, we first define the normal subgroup K ⊂ G byK = {s ∈ G : ω(s, g)ω(g, s)−1 = 1 ∀g ∈ G}. K is equivalent to the subgroupof group elements that are represented projectively as a scalar matrices inV˜ (g) ([72], Lemma 6.38’(b)). Since we have a phase degree of freedom indefining V˜ (g), we can write K = {s ∈ G : V˜ (s) = I}. Since K is a normalsubgroup, we can form the quotient group G¯ = G/K. Now we need thefollowing lemma:Lemma 1. (a) χiα is a linear character of G¯. (b) V˜ (g) is a faithful, irre-ducible, projective representation of G¯.Proof. Consider a partition of G into cosets of K, G = ∪a∈G¯Kga, wheregagb = s(a, b)gab for s(a, b) ∈ K.(a) If we define χ¯(a) = χiα(ga) ∀a ∈ G¯, we haveχ¯(a)χ¯(b) = χiα(s(a, b))χ¯(ab)Now it is clear by Eq. 4.8 that χiα(s) = 1 ∀s ∈ K since V˜ (s(a, b)) is a scalarmatrix. So χ¯ is indeed a linear character of G¯(b) Similarly, define the projective representation of G¯ as V¯ (a) = V˜ (ga)∀a ∈ G¯. Since V˜ (s) = I ∀s ∈ K, we can again see that V¯ (a) is an ω¯-representation of G¯ where ω¯(a, b) = ω(ga, gb). It is irreducible since V (g) isand the only elements we have removed are scalar matrices, which do notinfluence reducibility. Finally, it is faithful, since if V¯ (a) = V˜ (ga) = 1, thenga ∈ K so a = 1.Essentially, modding out the subgroup K gives us the minimal group inwhich V˜ (g) is a faithful representation. This is important because we cannow repeat the argument used by Else et. al. [36].Proof. of TheoremDefine the homomorphism φω from G¯ to its character group G¯∗ byφω(a)(b) = ω¯(a, b)ω¯(b, a)−1. By construction of G¯, kerφω = {e}, so thisis in fact an isomorphism. That means we can find an element aiα ∈ G¯ suchthat:χ¯(a) = ω¯(aiα, b)ω¯(b, aiα)−1 ∀a ∈ G¯.Since χiα = 1 on K, this extends to G itself. Defining giα = gaiα , we haveχiα(g) = ω(giα, g)ω(g, giα)−1 ∀g ∈ G294.2. Structure of abelian SPT phasesThen it is easy to verify that setting Ciα = V˜ (giα) satisfies Eq. 4.8, whichproves the theorem.For our Z4 × Z2 example, K = Z2 × {e} ∼= Z2, so G¯ = Z2 × Z2. By thetheorem, Ciα form an faithful irreducible projective representation of G¯, andhence they are Pauli matrices, as was observed.4.2.3 Refining structureWe now require three propositions which refine the structure proven by The-orem 5. The first proposition elucidates the structure of the permutationsPi:Proposition 1. Pi = Pj if and only if χi(s) = χj(s) ∀s ∈ K.Proof. The different irreps Vα(g) are labelled by characters ψα of K accord-ing to the relation Vα(s) = ψα(s)I, ∀s ∈ K (see Lemma 6.44 of Ref. [72]).Then the permutation Pi is defined such that χi(s)ψα(s) = ψPi(α)(s) ∀s ∈K. Clearly, this depends only on the values that χi takes on K, proving theproposition.Since the group K∗ of characters of K is isomorphic to K itself, thepermutations Pi are elements of the regular representation of K. Hencethey commute, and we see that nω = |K| gives the number of different irrepsof type ω, the number of distinct permutations Pi, and also the number ofblocks in virtual space.For the Z4 × Z2 example, K = Z2, so there are two blocks in virtualspace, and the only non-trivial permutation Pi swaps these two blocks.Now our second proposition regards the byproduct operators Ciα:Proposition 2. The matrices Ciα can be decomposed as Ciα = DiαCi, whereDiα depends only on Pi and not i itself. Furthermore, Ci and Diα are bothelements of the projective symmetry representation V (g).Proof. Fix an arbitrary j and pick any i such that Pi = Pj . The result isproven if we show that Ciα can be written as CjαCi for some operator Ci, ∀α,whereupon Diα = Cjα. Let Ci = V (gi) for gi such that ω(gi, g)ω(g, gi)−1 =χi(g)χj(g)−1 ∀g ∈ G. Such a gi must exist since χi(s)χj(s)−1 = 1 ∀s ∈ Kby Prop. 1, which implies that χiχj−1 ∈ Im φω. Then it is clear to checkthat χi(g)Vα(g) = CjαCiVPi(α)(g)Ci†Cj†α .304.3. Computation in abelian SPT phasesThis proposition will ensure that the same logical gates are executed in eachblock of the virtual space. This theorem is again evident in our Z4 × Z2example.The dimension D of the byproduct operators is equal to dω, the dimen-sion of ‘V˜ (g). By Theorem 6.39(b) of Ref. [72], this is equal to√G : K =√|G|/|K|.We will require one final proposition which shows how the operators Diαchange under a change of the basis of the virtual space.Proposition 3. Under the change of virtual basis given by Ai → UjAiU †jwith Uj =⊕α I⊗DjP†j (α), the operators Diα become DiP†j (α)Proof. By direct computation, we see that Diα becomes DjP†j (α)DiαDj†Pi◦P†j (α)up to irrelevant phases in each block which are absorbed into Biα. Usingthe Clebsch-Gordon relations self-consistently, it is easy to show that thisoperator is equivalent to DiP†j (α)as claimed.This result will remove any ambiguities present in byproduct propagation.4.3 Computation in abelian SPT phasesNow we use the structure derived in the previous section to show how com-putation can be performed throughout abelian SPT phases. The key obser-vation is the following: if our virtual state is supported on a single blockα of the virtual space, then the matrices in Eq. 4.7 act in essentially thesame way as Eq. 3.6. The difference is that the byproduct operators dependon which block our state is in. However, Prop. 2 will guarantee that thethe same logical gate is performed no matter which block our state is in.Because of these two facts, computation will work in nearly the same wayas in the maximally non-commutative case.4.3.1 Encoding and byproduct propagationThe first issue to deal with is how to encode information such that we cantake care of byproduct propagation. Our mechanism of byproduct propa-gation is as usual symmetry transformations of future measurement bases.Again, we have: ∑ju(g)ijAj = V (g)AiV (g)†,314.3. Computation in abelian SPT phaseswhere V (g) =⊕α λα(g)Inα⊗ V˜ (g). We see that the same byproduct will beundone in each block α, up to irrelevant phases. In general, measurementin the wire basis will result in a different byproduct operator Ciα in eachblock, so this symmetry transformation is not sufficient for propagation.If, however, we restrict to quantum states supported in only one knownblock, we can always propagate the byproduct completely. Since we will beemploying the mixed-state interpretation, we consider only states which area probabilistic mixture over single-blocked states:ρ =⊕αpαρα. (4.9)The interpretation of this state is that we have performed some initializa-tion procedure which puts our virtual state into a single block. In the mixedstate interpretation, we sum over the possible outcomes of this initialization,leading to the above state. However in a given run of the computation wealways know which block supports our state, so we can perform byproductpropagation. The details of this initialization procedure are given in Sec 4.4.For now, we assume that it has been done.We can again define a logical subspace in which we store information. Alogical state σ = |φ〉〈φ| will be encoded as:ρ =⊕α(pαρ˜α ⊗ σ) =(⊕αpαρ˜α)⊗ σ ≡ ρ˜⊗ σ. (4.10)σ is acted on by the CG matrices Ciα, which are defined by the symmetry andphase. ρ˜ lives in the junk system, which now also includes the informationabout which block the state is in.4.3.2 Oblivious wireConsider any state of the form given in Eq. 4.10. In this section we will showhow to send this state to the fixed point I⊗ σ. The protocol is identical tothe oblivious wire used in the maximally non-commutative case: repeatedmeasurements in the wire basis with byproduct propagation.After a single measurement in the wire basis with byproduct propagation,we have:ρ→(∑αBiP†i αρ˜P†i (α)Bi†P†i α)⊗ σ = E˜(ρ˜)⊗ σ.324.3. Computation in abelian SPT phasesAfter m measurements, the junk state ρ˜ is acted on by the channel E˜m. It iseasy to see that E˜ is unital since E is. Furthermore, I is the only fixed pointof E˜ , since any other fixed point would define a fixed point of E , violatinginjectivity. So the oblivious wire projects the junk space onto the maximallymixed state, just as in the maximally non-commutative case.4.3.3 Infinitesimal gates and measurementsWith the oblivious wire, we can get infinitesimal gates in the same way asbefore, with one key difference. In the maximally non-commutative case, wewould perform an infinitesimal gate by measuring in the basisB(i, j; dα, β) = {|0〉, . . . , |i〉+ dαeiβ|j〉, |j〉 − dαe−iβ|i〉, . . . , |d− 1〉},followed by the oblivious wire. The procedure is the same in the presentcase, except now we must restrict the possible pairs i, j to perturb in thebasis. If we perturb basis states i, j where Pi 6= Pj , then we will introducecoherence between blocks of the virtual space and lose the block diagonalstructure. This is not permissible since it removes our ability to propagatebyproduct operators.Let our initial state be ρ = I ⊗ σ. Suppose we measure in the basisB(i, j; dα, β) such that Pi = Pj . If we propagate the byproducts Ciα andsum over outcomes, a simple calculation gives the resulting state as:ρ→⊕α({∑iBiP†i αBi†P†i α}⊗ σ+dα{eiβBiP†i αBj†P†i α⊗[σ,Cj†Ci]+ e−iβBjP†i αBi†P†i α⊗[CiCj†, σ]}).(4.11)Therein, we have used Prop. 2 since Pi = Pj . Finally, we follow this withthe oblivious wire, giving:ρ→ I⊗(νσ + dα[σ, νijeiβCjCi† − νjie−iβCiCj†])where we have defined limm→∞ E˜m(⊕αBiαBj†α ) = νijI and ν =∑i νii. Wesee that, as in the maximally non-commutative case, we get an infinitesimalrotation of the logical subspace. If σ = |φ〉〈φ|, we have:334.4. InitializationT (i, j; dα, β)|φ〉 = exp{dα|νij |ν(ei(β+δij)Ci†Cj − e−i(β+δij)Cj†Ci)}|φ〉Once again, we get a Lie algebra A[O] of infinitesimal rotations and acorresponding Lie group of operators L[O]. We can similarly generalize thescheme for projective measurement of the virtual system given in Ref. [2].4.4 InitializationIn order for the gates to work as described above, we needed to initialize ourstate into a known block of the virtual space. This was to ensure that wecould always propagate the byproduct operators. We will now see that thiscan always be done, although it is somewhat tricky and requires additionalknowledge of the microscopic details of the state (beyond νij).First, we run “completely” oblivious wire, which is the usual obliviouswire only with no byproduct propagation. Measuring m spins results in thechannel Em where E(X) = ∑iAi(X)Ai†. By injectivity and the canonicalform, this channel projects the virtual space onto the state I =⊕α Iα. Wecan interpret this state as a statistical ensemble over the states Iα, eachof which are supported only one block α. So we interpret the completelyoblivious wire as a projection onto a single unknown block of the virtualspace. At the very beginning of computation (ie. the first repetition of analgorithm), we assign this block the label “1”. For the rest of the initializa-tion process, we track the accumulated permutation PΣ =∏i P†i , such thatour virtual state at any time is supported in the block PΣ(1).From Eq. 4.7, we see that the byproduct operators depend on both themeasurement outcome and the block that supported the virtual state beforemeasurement: block α and outcome i result in Ciα. The above proceduregives us a way to identify which block we are in, but only with respect toan arbitrary reference point “1” which does not necessarily correspond tothe block with α = 1 in Eq. 4.7. How do we match up these block labelswith the labels of the byproduct operators? The answer is, we don’t haveto. Suppose the block we called “1” actually corresponds to block β inEq. 4.7. Then, by Prop. 3, we change the basis of our virtual space by theunitary Uj with P†j (β) = 1 (such a unitary always exists), such that theblock we called “1” does indeed transform like the block corresponding toα = 1 in Eq. 4.7. Furthermore, since the permutations Pi all commute, wehave P†j ◦PΣ(β) = PΣ ◦P†j (β) = PΣ(1), hence all byproducts are as dictated344.4. Initializationby Eq. 4.7. So we can match up the labels of byproduct operators with ourarbitrary labelling of blocks by a passive choice of virtual basis.It would seem as though we are done: for each run of the computation,we choose a different virtual basis such that we can propagate byproductoperators as described above. Unfortunately, this is inconsistent with themixed state interpretation. Here, different runs of the computation areinterpreted as different paths, which we eventually sum over. We cannotperform this sum in the desired way if each path uses a different virtualbasis. Because of this, we require a procedure to determine which blockwe are in with respect to “1” that will be performed at the start of everysubsequent repetition of the computation.To do this, we first need an extra calibration step to characterize thedifferent blocks. This step involves simply measuring in the wire basis,collecting every m-th outcome for some m ξ, and binning these outcomesaccording to PΣ before the measurement (so there are |K| bins). Whatwe get out of this procedure is the set of constants {νiiα} as defined in theappendix, where α is defined with respect to 1 as above. To see how thisworks, suppose our virtual space is in the state Iα. Then, by the Bornrule described in the appendix, the probability of obtaining outcome i aftermeasuring in the wire basis is νiiα . If we were able to repeat this measurementmany times, the outcome statistics would be as dictated by the constantsνiiα .The problem is that the first measurement (a) puts us in a different blockand (b) makes our virtual state different from the maximally mixed state.(a) is solved by binning the outcomes according to the block the virtualspace was in before measurement, ie. the accumulated permutation PΣ. (b)is solved by running completely oblivious wire between each measurement.To see why, consider the evolution under the completely oblivious wire ofan initial state ρα which is supported only in block α. Since we are binningmeasurement outcomes according to the accumulated permutation PΣ, wemust only sum over those strings of outcomes which lead to the same PΣ.The resulting channel EPΣ thus gives a state supported only in block PΣ(α).Since Em = ∑PΣ EPΣ , and since Em has the fixed point I = ⊕α Iα, EPΣmust project the initial state ρα onto the state IPΣ(α). This prepares us foranother calibrating measurement.We now have a procedure to determine the constants νiiα for all blocks α(with respect to block 1). For the next run of the computation, the initial-ization is carried out in the same way, only now we use the measurementsstatistics to determine which block we are in. Note that, if νiiα = νiiβ for someα, β, then we cannot distinguish if we are in block α or block β with the354.5. Main theoremabove procedure. This means we do not know which byproducts to propa-gate, and the computation may fail. This condition holds for the case wherethe junk part is trivial.4.5 Main theoremWith the above results, we can state our next main theorem, which is strictlystronger than Theorem 4:Theorem 6. Consider a state in a symmetry-protected topological phasewithout symmetry breaking described by a group G, an on-site representationu, and a cohomology class [ω]. If there exists a finite abelian subgroup H ⊂ Gsuch that [ω|H ] is not the trivial class, then for any state in the phase, excepta null subset, a Lie group of gates determined only by G, u, and [ω] can beefficiently implemented in MBQC with arbitrary high gate fidelity.Before computation, we must perform a calibration step to obtain theconstants νij and νiiα . The null subset of states which cannot be used refersto those with either νij = 0 or νiiα = νiiβ for some α, β.Every phase which satisfies Theorem 4 also satisfies this one, but thisdoes not make the maximally non-commutative case irrelevant. For one, themaximally non-commutative case corresponds to when the logical subspacehas maximum dimension, so it is desirable for this reason. More importantly,we will see in the next chapter that only in the maximally non-commutativecase can we guarantee that L[O] contains a full set of single-qudit gates.36Chapter 5Determining computationalpowerIn the previous two chapters, we saw that SPT phases protected by anabelian (sub)group have uniform computational power, as summarized inTheorems 4 and 6. The final step is to determine the Lie group L[O] thatquantifies this uniform power by using the algebraic structure inherited fromthe SPT phase classification. For the maximally non-commutative case, weare able to prove that this Lie group is always universal, in that it alwaysallows arbitrary operations on a qudit of some dimension. For the generalcase, this is not true, and as a counterexample we construct of a phase whichallows only z-axis rotations of a qubit, which is not universal.5.1 Maximally non-commutative caseRecall that we begin with a symmetry group G and then restrict to a fi-nite abelian subgroup H, whereupon our logical dimension is D =√|H|.Consider first the case where the representation u|H contains all non-trivialcharacters of the subgroup H. This means that O contains D2 − 1 trace-orthogonal, antihermitian operators, so L[O] ∼= SU(D). If the Hilbert spacedimension of our physical sites is smaller than D2 − 1, or certain charac-ters χi do not appear in u|H , L[O] may be some Lie subgroup of SU(D).However, with the condition of maximal non-commutativity, this subgroupis always universal on a qudit system, as stated in the following theorem:Theorem 7. Consider an SPT phase defined by an on-site symmetry groupG and cohomology class [ω]. Suppose there exists a finite abelian subgroupH ⊂ G such that [ω|H ] is maximally non-commutative, and let pn be aprime power dividing√|H|. Then L[O] ⊃ SU(pn). That is, every state inthe phase, except for a null subset, is a resource for universal computationon a pn level system.This result, proven after the next section, determines the minimal compu-tational power of the phase, which is independent of u and hence uniform375.2. Non-universality in abelian phasesamongst the phase. This shows that 1D ground states with SPT order aregenerically useful as MBQC resources.Beyond this minimal case, L[O] can often be expanded to gain addi-tional computational power. For example when H = (Z2)4, our theoremguarantees that SU(2) ⊂ L[O], but this can be expanded to either SU(4)or SU(2)×SU(2) depending on the on-site symmetry representation u. So,while changing u is generally considered to not change the SPT phase of asystem [6], it remains an important label for total computational power inour scheme. If, however, we allow ourselves to redefine the locality of mea-surements by blocking neighbouring sites, L[O] will always equal SU(D)after sufficient blocking.5.2 Non-universality in abelian phasesIn the general abelian case, without the assumption of maximal noncommu-tativity, determining L[O] becomes more difficult. This is because we canonly perturb or measurement basis between certain basis states. Further-more, we cannot always restrict to a subgroup of convenient form, as in theproof contained in the next section. As in the previous section, for eachphase it is possible to choose the representation u such that L[O] = SU(D)where D =√|G|/|K|. However, we can no longer prove that all choices ofu lead to a full set of single-qudit gates. In fact, this is not true in general,as illustrated by the following example.Consider the following state in the non-trivial phase of Z4 × Z2. Thephysical system is a qutrit with MPS matrices given by:A0 =(B011 ⊗ I 00 B022 ⊗ I)A1 =(B111 ⊗ σz 00 B122 ⊗ σz)A6 =(0 B612 ⊗ σxB621 ⊗ σz 0)(5.1)One can confirm numerically that this state is injective for most choices ofmatrices Biαβ. Our scheme only gives a single type of gate, which is rotationabout the Z axis. This does not lead to a universal set of single-qubit gates.385.3. Proof of Theorem 75.3 Proof of Theorem 7By Lemma 36 of Ref. [72] and its proof within, if [ω|H ] is maximally non-commutative then H must have the form H1 × · · · ×Hr where Hi ∼= Zpnii ×Zpnii and pnii is a prime power. Furthermore, [ω|Hi ] is also maximally non-commutative for all subgroups Hi. By restricting to any such subgroupH˜ = ZD ×ZD for D = pn, the operators Ci can be taken to be Heisenberg-Weyl operators of the form ZiXj where XZ = ΩZX and Ω = e2piiD . In thisway, we are able to prove that L[O] is SU(D) for all physical representationsu; see below.5.3.1 Graphical Description of Computational PowerThe primitive gates in our scheme that can be executed in a single step aregenerated by elements from the following set O of antihermitian opertors:O ={αCi†Cj − α∗Cj†Ci}∀i 6= j, ∀|α|  1Throughout the following, α always represents an arbitrary complex num-ber of small magnitude, unless stated otherwise. By concatenating theseprimitive gates, we can execute any unitary gate generated by elements ofthe algebra A[O] defined as the smallest Lie algebra containing O. Thisalgebra, called the dynamical Lie algebra in the context of quantum con-trol, determines the computational power of the resource state; the set ofgates L[O] = eA[O]. We call our resource state universal if L[O] = SU(N),such that A[O] = su(N), the Lie algebra of traceless antihermitian ma-trices with commutator bracket. su(N) can be spanned by the operatorsαXiZj − α∗Zj†Xi† for i, j = 0, . . . , N − 1, and α ∈ C. Denote these op-erators by Oi,j(α). Clearly, by the definition of O, we have A[O] ⊂ su(N)always.The task is then, given O, to determine A[O]. This is facilitated by agraphical interpretation. The elements of A[O] can be indexed by a pair ofmod D integers (i, j), which refer to the set of operators {Oi,j(α)} for allα ∈ C. We can construct a D ×D grid, whose vertices correspond to pairs(i, j). We place a marker on a vertex if the corresponding operators are inA[O](See Fig. 5.1). It is then clear that we have A[O] = su(N) if and onlyif we can mark all vertices on the graph. Note that half of the points onthe graph are redundant, since (i, j) and (D − i,D − j) refer to the sameoperators. So whenever (i, j) is marked, we can mark (D− i,D− j) for free.395.3. Proof of Theorem 7(a) (b)(c) (d)Figure 5.1: Illustration of graphical description of A[O] and proof of Lemma3 for D = 8 and r = 1. (a) Initial points guaranteed by Lemma 2 (redmarks). Arrows indicate basic moves: X move is solid, Z dashed, Y dotted.Starting from a marked point, if any arrow points to another marked point,its opposite can be marked as well. (b) First basic move is done from posi-tion (0,1), abusing periodic boundary conditions indicated by faded marks,creating orange mark. Starting from the orange mark, row/column 1 arefilled using X/Z moves. (c) A Y move is used to obtain new starting pointsin row/column 3 (orange marks), which are then filled using X/Z moves.(d) After every other row/column is filled, the point (2,4) is filled using thespecial rule with the green star indicating the hermitian point (0,4). Theremaining points can now be filled with basic moves.405.3. Proof of Theorem 7Different physical representations u determine the operators in O, whichin turn determines the initial conditions of our grid. We briefly pause for aLemma that restricts the possible initial conditions and is a consequence ofinjectivity:Lemma 2. If D = pn is a prime power, then there exists an integer r whichis not divisible by p such that:{O1,0(α), O0,r(α), OD−1,r(α)} ⊂ O (5.2)The proof will be presented shortly. This lemma allows us to define thebasic moves that can be used to fill up the graph starting from this initialpoint. Consider the following commutator of two elements in A[O]:[Oi,j(α), O1,0(1)] = Oi+1,j(α(Ω−j − 1))−Oi−1,j(α(Ωj − 1)) (5.3)So, starting from the point (i, j), we get out a linear combination ofoperators represented by points (i − 1, j) and (i + 1, j). If either of thesepoints are already filled, we can simply subtract out that part we alreadyhave, allowing us to fill the other point since α is a free parameter. We cando the same thing with the operator O0,r(1) and also OD−1,r(1). So ourthree basic moves are, starting from a marked point (i, j):X) Inspect points (i + 1, j) and (i − 1, j). If one is marked already andj 6= 0, mark the other.Z) Inspect points (i, j + r) and (i, j − r). If one is marked already andi 6= 0, mark the other.Y) Inspect points (i−1, j+r) and (i+1, j−r). If one is marked alreadyand ir + j 6= 0, mark the other.See Fig. 5.1(a) for an illustration. Recall that, since we are workingwith integers mod D, our graph has periodic boundaries. Basic moves areforbidden for certain values of (i, j) because these correspond to taking thecommutator of commuting operators, which will give 0. The points where aY move are forbidden form a line with slope −r starting from the origin,There is one final rule that applies only when D is even: If at any time apoint corresponding to a hermitian operator [i.e. (D2 , 0), (0,D2 ), (D2 ,D2 )] canbe inspected by a basic X, Y, or Z move, it can be considered marked. Thisrule can be explained by an example. Consider the commutator:[O1,D2(α), O1,0(β)]= O0,D2(2αβ∗)−O2,D2(2αβ) (5.4)415.3. Proof of Theorem 7Since ZD2 is hermitian, we can choose α = β and annihilate the firstterm automatically, leaving the second term with the free coefficient α. Thisallows us to mark O2,D2(α), which in turn allows us to mark O0,D2(α). Thisprocess generalises whenever one of the operators is hermitian, giving thebasis for the final rule. With these rules in hand, we have our final lemma:Lemma 3. With the initial conditions of Lemma 2, each point on the graphcan be marked using basic moves. That is, the set of operators in Eq. 5.2generates su(pn).Proof. We prove first for the case r = 1, and comment on general r at theend. Based on Lemma 2, our initially marked points include (1, 0), (0, 1), (D−1, 1) where D = pn. We also get (D−1, 0), (0, D−1), (1, D−1) by the afore-mentioned redundancy of the points (See Fig. 5.1(a)) We start with an Xmove from (0, 1). Since (D−1, 1) is filled, we can fill (1, 1). Using a sequenceof X/Z moves, we get (i, 1)/(1, i) for all i (See Fig. 5.1(b)). Now we performa Y move from (2, 1)/(1, 2) to get (3, 0)/(0, 3). Again using a sequence ofX/Z moves, we get (i, 3)/(3, i) for all i (See Fig. 5.1(c)). Continuing in thisfashion, we can fill every other row and every other column. We must nowseparate the proof into two cases:Case 1: p odd (p 6= 2). In this case, the periodic boundary conditionsmean that filling every other row/column will in fact fill every row/column.So the above procedure is enough to fill the grid.Case 2: p = 2. Here, filling every other row/column will miss half of therows/columns, so we must use the final rule involving hermitian operatorsto continue. We use an X move at (1, D2 ). Since (0,D2 ) corresponds to ahermitian operator, we mark (2, D2 ) for free (See Fig. 5.1(d)). It is now clearthat we can mark all remaining point using basic moves.A final check is that we did not perform any forbidden moves in the aboveprocedure; this can be easily verified. The case r 6= 1 is almost identical.Our initially marked points include (1, 0), (0, r), (D−1, r). A key observationis that, since r is coprime with D, all integers 0, . . . , D − 1 can be obtainedas multiples of r. Then we can repeat the above procedure of filling rowsand columns one by one. The only difference is the order in which they arefilled.By our two lemmas, we have A[O] = su(pn) in every case. Since pn wasan arbitrary divisor of |H|, we have completed the proof of the theorem. Wefinish with the proof of Lemma 2.Proof. of Lemma 2. It is convenient to assume that C0 = I. This canalways be done by enacting a transformation Ci → C˜i = C0†Ci. Such a425.4. Example: G = Zn × Zntransformation does not change O; it is just a relabelling of the elements.Define the set C˜ ={C˜i, i = 0 . . . d− 1}.In order to impose further structure on C˜, we use injectivity which statesthat the set of products {Ai1Ai2 . . . AiL} spans the space of all complexmatrices for large enough L (condition 3, Theorem 1). By tracing out thejunk subspace corresponding to the matrices Bi, we see that this propertyholds on the logical subspace alone. That is, every D × D matrix can beexpressed as a linear combination of products Ci1Ci2 . . . Cin . The fact thatthis also holds for the matrices C˜i can be seen by using the statement ofinjectivity given by condition 4 of Theorem 1, which clearly holds for C˜i ifit does for Ci.Now, since the matrices C˜i span all matrices with their products, andtheir products are always Heisenberg-Weyl operators, they must generatethe entire set of Heisenberg-Weyl operators, up to complex phases. Thismeans we must have a pair of operators C˜a and C˜b such that C˜aC˜b =ΩrC˜bC˜a where p does not divide r. If not, define the numbers rij by C˜iC˜j =Ωrij C˜jC˜i. Then a commutator of arbitrary elements can be written:∏i(C˜i)ai∏j(C˜j)bj = Ω∑ij aibjrij∏j(C˜i)bj∏i(C˜i)ai (5.5)If p|rij for all i, j, then p|∑ij aibjrij , which cannot always be true ifwe have a generating set. Finally, for any unitary operators that commutelike C˜aC˜b = ΩrC˜bC˜a there exists a unitary U such that UCaU † = X andUCbU † = Zr (see Ref. [78] for the case r = 1, which generalizes easily).In the basis defined by U , we have I,X,Zr ∈ C˜, which gives the claimedoperators in O.5.4 Example: G = Zn × ZnIn this section, we remark on some interesting applications of our results inthe context of a symmetry group G is of the form Zn × Zn for some integern. Note that, as discussed in Sec. 3.4, this also covers the case when G is aclassical Lie group as well as certain finite groups like dihedral groups. Thesecond cohomology group is H2[Zn × Zn, U(1)] = Zn, so there are n − 1non-trivial phases. To label these phases, suppose the group is generated bytwo elements a and b, and suppose V (a)V (b) = ΩrV (b)V (a) where V (g) isthe representation of G in the virtual space. Then r labels the SPT phase,and the phase is maximally non-commutative if gcd(r, n) = 1 [73, 74, 76].435.4. Example: G = Zn × ZnUsing the results of Ref. [77], it is possible to calculate that the dimen-sion of irreps in the phase labelled by r, that is the dimension of the logicalsubspace, is Dr = n/gcd(r, n). By our results, we then get computation ona Dr-level system for all phases, consistent with the results of Refs. [79].However, only for those satisfying gcd(r, n) = 1 are we guaranteed univer-sality (perhaps on a subspace of the whole logical subspace). Even still, thefact that all non-trivial SPT phases protected by classical Lie groups can beused for computation has great practical interest.This result also means that we can compute on a qudit of arbitrarily largedimension with a chain of physical spins of bounded dimension. Indeed,consider the case where n = 2m and r is odd. By the above arguments, thisgives a universal set of gates on a system of dimension 2m, equivalent to thatof m qubits, no matter what the physical dimension is. This goes against theusual idea that 1D systems can only process a single qudit of information.However one should be careful not to take this argument too far. Supposeour physical system is a qutrit, meaning that we have only three primitivegates to work with. By the proof in the previous section, this is still enoughto generate all gates in SU(2m), but the number of steps needed to generatean arbitrary gate will grow exponentially with m, at least when using ourmethod. So, while we are able to process m qubits with a chain of qutrits,the scaling may not be efficient, and indeed results such as that given inRef. [49] suggest it is not.44Chapter 6Conclusions and OutlookIn this thesis, we studied the relationship between measurement-based quan-tum computation and symmetry-protected topological order, one which sitson the border of condensed matter physics and quantum information sci-ence. More specifically, we began with the following question: Does thereexist a broad family of SPT phases which support non-trivial gates through-out each phase? To answer this, we introduced three computational tech-niques: the mixed state interpretation, the oblivious wire, and the use ofinfinitesimal gates. With these pieces, we proved that all of the maximallynon-commutative SPT phases have uniform computational power. By prov-ing new results on the structure of MPS with SPT order and introducingsome additional computational techniques, we were able to extend this re-sult to all SPT phases that can be protected by a finite abelian group. Wethen used the algebraic structure inherited from the SPT phase classifica-tion to determine the computational power of each phase. We proved thatthe maximally non-commutative phases were always universal for a quditsystem, but we gave a non-universal counterexample in the general case.The immediate questions that follow are whether our results can extendto arbitrary SPT phases in 1D, and then to higher-dimensional phases. Theanswer to the former is likely to be negative. Firstly, most of the importantresults in this thesis rely crucially on the abelian condition in one way oranother. Indeed, for general SPT phase we cannot even define a consistentdimension of the logical subspace since, given a phase labelled by [ω], theremay be ω-irreps of different dimensions. The notion of SPT entanglement isalso not well-defined within non-abelian phases [71]. For higher-dimensionalsystems there are several examples of states with SPT order that can beused as universal resources [80, 81, 82]. In some cases, these states havecertain advantages over other states without SPT order [81, 82]. On theother hand, there has been comparatively little success in extending theseresults throughout the corresponding SPT phases [40], and the methodsdeveloped here may aid this venture.In general, higher-dimensional systems support more complex forms ofSPT order such as weak SPT [7, 13] and phases protected by higher-form45Chapter 6. Conclusions and OutlookIntrinsictopological orderSymmetry-protectedtopological orderTopologicalquantum computationMeasurement-basedquantum computationGroup cohomologyCategory theoryFigure 6.1: In the same way that the language of category theory allows usto classify gates that can be executed by braiding the anyonic excitations oftopologically ordered systems in 2D [86, 17, 87], group cohomology deter-mines the gates implementable in measurement-based quantum computationusing 1D resource states with symmetry-protected topological order.symmetries [83, 84, 85], and it is not yet clear which type would most natu-rally support computation. Another issue is how information is propagatedthrough the virtual space of higher dimensional tensor networks. All higher-dimensional resource states known to the author have the property thatindividual “wires” that carry one qubit each can be cut out of the lattice,perhaps after some preparatory measurements. This property is not likelyto persist throughout phases, and furthermore it inherently eliminates someaspect of the SPT order by reducing to a pseudo-1D system. The authors ofRef. [81] get around this by only cutting out wires in certain regions of theresource state, leaving other regions in tact to take advantage of the SPTorder, but there may be a more natural solution.We will end by discussing the implications of our results on the con-nection between quantum phases of matter and quantum computation, assummarized in Fig.6.1. A similar result to ours already exists in the con-text of topological quantum computation (TQC). Topological order in 2Dis classified by the braiding and fusion statistics of bulk anyonic excitations,which can be compactly described by modular tensor categories [17, 88]. Be-cause TQC relies on manipulating these excitations, it can be characterizedby the same algebraic framework [86, 17, 87]. This is exactly analogous tothe current result. SPT phases can be classified by their edge modes whichtransform non-trivially under the symmetry, as described by group coho-mology. The Hilbert space associated to the logical subspace in which weencode and process information corresponds precisely to this edge mode in1D. Because of this, group cohomology also determines the computationalpower of 1D SPT phases.46Chapter 6. Conclusions and OutlookThus the results in this thesis can be seen as evidence of a more gen-eral theme. A typical method to classify quantum phases is by examiningthe non-trivial excitations above the ground states in the phase [7, 88, 8].If computation proceeds by manipulating these same excitations, then thecomputation will inherit the algebraic structure that describes the phase,and also its robustness to certain perturbations. There is already evidenceof this conjecture in higher-dimensional SPT phases [81, 82, 89, 83]. Itwould also be interesting to see whether the mathematical frameworks thatunify topological order and SPT order, such as G-crossed braided tensorcategories [8], could also describe computation with systems that have bothtypes of order.47Bibliography[1] David T. Stephen, Dong-Sheng Wang, Abhishodh Prakash, Tzu-ChiehWei, and Robert Raussendorf. Computational power of symmetry-protected topological phases. Phys. Rev. Lett., 119:010504, Jul 2017.[2] 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:012302, Jul 2017.[3] Michael A. Levin and Xiao-Gang Wen. String-net condensation: Aphysical mechanism for topological phases. Phys. Rev. B, 71:045110,Jan 2005.[4] Lukasz Fidkowski and Alexei Kitaev. Topological phases of fermions inone dimension. Phys. Rev. B, 83:075103, Feb 2011.[5] Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. Complete classifi-cation of one-dimensional gapped quantum phases in interacting spinsystems. Phys. Rev. B, 84:235128, Dec 2011.[6] Norbert Schuch, David Pe´rez-Garc´ıa, and Ignacio Cirac. Classifyingquantum phases using matrix product states and projected entangledpair states. Phys. Rev. B, 84:165139, Oct 2011.[7] Xie Chen, Zheng-Cheng Gu, Zheng-Xin Liu, and Xiao-Gang Wen. Sym-metry protected topological orders and the group cohomology of theirsymmetry group. Phys. Rev. B, 87:155114, Apr 2013.[8] Maissam Barkeshli, Maissam Bonderson, Meng Cheng, and ZhenghanWang. Symmetry, defects, and gauging of topological phases. 2014.[9] Zheng-Cheng Gu and Xiao-Gang Wen. Symmetry-protected topologi-cal orders for interacting fermions: Fermionic topological nonlinear σmodels and a special group supercohomology theory. Phys. Rev. B,90:115141, Sep 2014.48Bibliography[10] Anton Kapustin, Ryan Thorngren, Alex Turzillo, and Zitao Wang.Fermionic symmetry protected topological phases and cobordisms.Journal of High Energy Physics, 2015(12):52, 2015.[11] Hao Song, Sheng-Jie Huang, Liang Fu, and Michael Hermele. Topologi-cal phases protected by point group symmetry. Phys. Rev. X, 7:011020,Feb 2017.[12] Tian Lan, Liang Kong, and Xiao-Gang Wen. Classification of 2+1dtopological orders and spt orders for bosonic and fermionic systemswith on-site symmetries. 2016.[13] Meng Cheng, Michael Zaletel, Maissam Barkeshli, Ashvin Vishwanath,and Parsa Bonderson. Translational symmetry and microscopic con-straints on symmetry-enriched topological phases: A view from thesurface. Phys. Rev. X, 6:041068, Dec 2016.[14] Xiao-Liang Qi and Shou-Cheng Zhang. Topological insulators and su-perconductors. Rev. Mod. Phys., 83:1057–1110, Oct 2011.[15] Leon Balents. Spin liquids in frustrated magnets. Nature,464(7286):199–208, 2010.[16] A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annalsof Physics, 303(1):2 – 30, 2003.[17] Chetan Nayak, Steven H. Simon, Ady Stern, Michael Freedman, andSankar Das Sarma. Non-abelian anyons and topological quantum com-putation. Rev. Mod. Phys., 80:1083–1159, Sep 2008.[18] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation andQuantum Information: 10th Anniversary Edition. Cambridge Univer-sity Press, New York, NY, USA, 10th edition, 2011.[19] Peter W. Shor. Polynomial-time algorithms for prime factorizationand discrete logarithms on a quantum computer. SIAM Journal onComputing, 26(5):1484–1509, 1997.[20] D. Deutsch. Quantum theory, the church-turing principle and the uni-versal quantum computer. Proceedings of the Royal Society of LondonA: Mathematical, Physical and Engineering Sciences, 400(1818):97–117, 1985.49Bibliography[21] Guifre´ Vidal. Efficient classical simulation of slightly entangled quan-tum computations. Phys. Rev. Lett., 91:147902, Oct 2003.[22] Mark Howard, Joel Wallman, Victor Veitch, and Joseph Emerson. Con-textuality supplies the /‘magic/’ for quantum computation. Nature,510(7505):351–355, Jun 2014. Article.[23] Robert Raussendorf. Contextuality in measurement-based quantumcomputation. Phys. Rev. A, 88:022322, Aug 2013.[24] Robert Raussendorf and Hans J. Briegel. A one-way quantum com-puter. Phys. Rev. Lett., 86:5188–5191, May 2001.[25] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel.Measurement-based quantum computation on cluster states. Phys. Rev.A, 68:022312, Aug 2003.[26] Daniel E Browne, Matthew B Elliott, Steven T Flammia, Seth TMerkel, Akimasa Miyake, and Anthony J Short. Phase transition ofcomputational power in the resource states for one-way quantum com-putation. New Journal of Physics, 10(2):023010, 2008.[27] Sean D. Barrett, Stephen D. Bartlett, Andrew C. Doherty, David Jen-nings, and Terry Rudolph. Transitions in the computational power ofthermal states for measurement-based quantum computation. Phys.Rev. A, 80:062328, Dec 2009.[28] Andrew C. Doherty and Stephen D. Bartlett. Identifying phases ofquantum many-body systems that are universal for quantum computa-tion. Phys. Rev. Lett., 103:020506, Jul 2009.[29] Stein Olav Skrøvseth and Stephen D. Bartlett. Phase transitions andlocalizable entanglement in cluster-state spin chains with ising couplingsand local fields. Phys. Rev. A, 80:022316, Aug 2009.[30] Akimasa Miyake. Quantum computation on the edge of a symmetry-protected topological order. Phys. Rev. Lett., 105:040501, Jul 2010.[31] Stephen D. Bartlett, Gavin K. Brennen, Akimasa Miyake, andJoseph M. Renes. Quantum computational renormalization in the hal-dane phase. Phys. Rev. Lett., 105:110502, Sep 2010.[32] Keisuke Fujii and Tomoyuki Morimae. Topologically protectedmeasurement-based quantum computation on the thermal state of a50Bibliographynearest-neighbor two-body hamiltonian with spin-3/2 particles. Phys.Rev. A, 85:010304, Jan 2012.[33] Keisuke Fujii, Yoshifumi Nakata, Masayuki Ohzeki, and Mio Murao.Measurement-based quantum computation on symmetry breaking ther-mal states. Phys. Rev. Lett., 110:120502, Mar 2013.[34] Andrew S Darmawan, Gavin K Brennen, and Stephen D Bartlett.Measurement-based quantum computation in a two-dimensional phaseof matter. New. J. Phys., 14(1):013023, 2012.[35] Dominic V Else, Stephen D Bartlett, and Andrew C Doherty. Symme-try protection of measurement-based quantum computation in groundstates. New Journal of Physics, 14(11):113016, 2012.[36] Dominic V. Else, Ilai Schwarz, Stephen D. Bartlett, and Andrew C.Doherty. Symmetry-protected phases for measurement-based quantumcomputation. Phys. Rev. Lett., 108:240505, Jun 2012.[37] Jacob Miller and Akimasa Miyake. Resource quality of a symmetry-protected topologically ordered phase for quantum computation. Phys.Rev. Lett., 114:120506, Mar 2015.[38] Abhishodh Prakash and Tzu-Chieh Wei. Ground states of one-dimensional symmetry-protected topological phases and their utilityas resource states for quantum computation. Phys. Rev. A, 92:022310,Aug 2015.[39] Tzu-Chieh Wei, Ying Li, and Leong Chuan Kwek. Transitions in thequantum computational power. Phys. Rev. A, 89:052315, May 2014.[40] Tzu-Chieh Wei and Ching-Yu Huang. Universal measurement-basedquantum computation in two-dimensional spt phases. 2017.[41] E. Fradkin. Field Theories of Condensed Matter Physics. Field Theoriesof Condensed Matter Physics. Cambridge University Press, 2013.[42] Iulia Buluta and Franco Nori. Quantum simulators. Science,326(5949):108–111, 2009.[43] D. Jaksch, C. Bruder, J. I. Cirac, C. W. Gardiner, and P. Zoller. Coldbosonic atoms in optical lattices. Phys. Rev. Lett., 81:3108–3111, Oct1998.51Bibliography[44] Immanuel Bloch, Jean Dalibard, and Wilhelm Zwerger. Many-bodyphysics with ultracold gases. Rev. Mod. Phys., 80:885–964, Jul 2008.[45] Andrew A. Houck, Hakan E. Tureci, and Jens Koch. On-chip quantumsimulation with superconducting circuits. Nat Phys, 8(4):292–299, Apr2012.[46] J. Eisert, M. Cramer, and M. B. Plenio. Colloquium. Rev. Mod. Phys.,82:277–306, Feb 2010.[47] M B Hastings. An area law for one-dimensional quantum systems. Jour-nal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024,2007.[48] Don N. Page. Average entropy of a subsystem. Phys. Rev. Lett.,71:1291–1294, Aug 1993.[49] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac. MatrixProduct State Representations. Quant. Inf. Comp., 7:401, 2007.[50] F. Verstraete and J. I. Cirac. Matrix product states represent groundstates faithfully. Phys. Rev. B, 73:094423, Mar 2006.[51] Norbert Schuch, Michael M. Wolf, Frank Verstraete, and J. IgnacioCirac. Entropy scaling and simulability by matrix product states. Phys.Rev. Lett., 100:030504, Jan 2008.[52] Steven R. White. Density matrix formulation for quantum renormal-ization groups. Phys. Rev. Lett., 69:2863–2866, Nov 1992.[53] U. Schollwo¨ck. The density-matrix renormalization group. Rev. Mod.Phys., 77:259–315, Apr 2005.[54] Ian Affleck, Tom Kennedy, Elliott H. Lieb, and Hal Tasaki. Rigorousresults on valence-bond ground states in antiferromagnets. Phys. Rev.Lett., 59:799–802, Aug 1987.[55] Mikel Sanz, David Pe´rez-Garc´ıa, Michael M. Wolf, and Juan I. Cirac.A quantum version of wielandt’s inequality. IEEE Trans. Inf. Theor.,56(9):4668–4673, September 2010.[56] Bei Zeng, Xie Chen, Duan-Lu Zhou, and Xiao-Gang Wen. Quantuminformation meets quantum matter – from quantum entanglement totopological phase in many-body systems. 2016.52Bibliography[57] D. Pe´rez-Garc´ıa, M. M. Wolf, M. Sanz, F. Verstraete, and J. I. Cirac.String order and symmetries in quantum spin lattices. Phys. Rev. Lett.,100:167202, Apr 2008.[58] Lev Davidovich Landau and Evgenii M Lifshitz. Statistical Physics: V.5: Course of Theoretical Physics. Pergamon press, 1969.[59] Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. Complete classifi-cation of one-dimensional gapped quantum phases in interacting spinsystems. Phys. Rev. B, 84:235128, Dec 2011.[60] Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. Local unitary trans-formation, long-range quantum entanglement, wave function renormal-ization, and topological order. Phys. Rev. B, 82:155138, Oct 2010.[61] M Van den Nest, W Du¨r, A Miyake, and H J Briegel. Fundamentals ofuniversality in one-way quantum computation. New J. Phys., 9(6):204,2007.[62] M. Van den Nest, W. Du¨r, G. Vidal, and H. J. Briegel. Classical simu-lation versus universality in measurement-based quantum computation.Phys. Rev. A, 75:012337, Jan 2007.[63] Y.-Y. Shi, L.-M. Duan, and G. Vidal. Classical simulation of quan-tum many-body systems with a tree tensor network. Phys. Rev. A,74:022320, Aug 2006.[64] D. Gross, S. T. Flammia, and J. Eisert. Most quantum states are tooentangled to be useful as computational resources. Phys. Rev. Lett.,102:190501, May 2009.[65] Michael J. Bremner, Caterina Mora, and Andreas Winter. Are ran-dom pure states useful for quantum computation? Phys. Rev. Lett.,102:190502, May 2009.[66] D. Gross and J. Eisert. Novel schemes for measurement-based quantumcomputation. Phys. Rev. Lett., 98:220503, May 2007.[67] D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia. Measurement-based quantum computation beyond the one-way model. Phys. Rev. A,76:052315, Nov 2007.[68] Gavin K. Brennen and Akimasa Miyake. Measurement-based quantumcomputer in the gapped ground state of a two-body hamiltonian. Phys.Rev. Lett., 101:010502, Jul 2008.53Bibliography[69] Ying Li, Daniel E. Browne, Leong Chuan Kwek, Robert Raussendorf,and Tzu-Chieh Wei. Thermal states as universal resources for quantumcomputation with always-on interactions. Phys. Rev. Lett., 107:060501,Aug 2011.[70] Leong Chuan Kwek, Zhaohui Wei, and Bei Zeng. Measurement-basedquantum computing with valence-bond-solids. International Journal ofModern Physics B, 26(02):1230002, 2012.[71] Iman Marvian. Symmetry-protected topological entanglement.[72] I A G Berkovich and EM Zhmud. Characters of finite groups, volume 1.American Mathematical Soc., 1998.[73] Kasper Duivenvoorden and Thomas Quella. From symmetry-protectedtopological order to landau order. Phys. Rev. B, 88:125115, Sep 2013.[74] Kasper Duivenvoorden and Thomas Quella. Topological phases of spinchains. Phys. Rev. B, 87:125145, Mar 2013.[75] Zhaoxi Xiong. Minimalist approach to the classification of symmetryprotected topological phases. 2016.[76] Dominic V. Else, Stephen D. Bartlett, and Andrew C. Doherty. Hiddensymmetry-breaking picture of symmetry-protected topological order.Phys. Rev. B, 88:085114, Aug 2013.[77] NB Backhouse and CJ Bradley. Projective representations of abeliangroups. Proceedings of the American Mathematical Society, 36(1):260–266, 1972.[78] D. L. Zhou, B. Zeng, Z. Xu, and C. P. Sun. Quantum computationbased on d -level cluster state. Phys. Rev. A, 68:062303, Dec 2003.[79] Dong-Sheng Wang, David T. Stephen, and Robert Raussendorf. Quditquantum computation on matrix product states with global symmetry.Phys. Rev. A, 95:032312, Mar 2017.[80] Hendrik Poulsen Nautrup and Tzu-Chieh Wei. Symmetry-protectedtopologically ordered states for universal quantum computation. Phys.Rev. A, 92:052309, Nov 2015.[81] Jacob Miller and Akimasa Miyake. Hierarchy of universal entangle-ment in 2d measurement-based quantum computation. Npj Quant. Inf.,2:16036, 2016.54[82] Jacob Miller and Akimasa Miyake. Latent computational complexity ofsymmetry-protected topological order with fractional symmetry. 2016.[83] Beni Yoshida. Topological phases with generalized global symmetries.Phys. Rev. B, 93:155131, Apr 2016.[84] Sam Roberts, Beni Yoshida, Aleksander Kubica, and Stephen D.Bartlett. Symmetry protected topological order at nonzero tempera-ture. 2013.[85] Anton Kapustin and Ryan Thorngren. Higher symmetry and gappedphases of gauge theories. 2013.[86] Michael Freedman, Alexei Kitaev, Michael Larsen, and ZhenghanWang. Topological quantum computation. Bull. Amer. Math. Soc.,40:31–38, 2003.[87] Eric Rowell, Richard Stong, and Zhenghan Wang. On classification ofmodular tensor categories. Communications in Mathematical Physics,292(2):343–389, 2009.[88] Xiao-Gang Wen. A theory of 2+1d bosonic topological orders. NationalScience Review, 3(1):68–106, 2016.[89] Beni Yoshida. Gapped boundaries, group cohomology and fault-tolerant logical gates. 2015.55Appendix ABorn rule and mixed stateinterprtationHere we derive the Born rule for matrix product states in Abelian SPTphases. This will allow us to formally argue the validity of the mixed stateinterpretation of MBQC. Suppose our left boundary condition is in the stateρ such that our ground state is the mixed state ψ:ψ =∑i0,...,iNj0,...,jN〈R|AiN . . . Ai1Ai0ρAj0†Aj1† . . . AjN †|R〉|i0 . . . iN 〉〈j0 . . . jN |(A.1)This state is normalized when it is in canonical form. Now suppose wemeasure some observable O on spin i0. The probability of outcome oα isthen:p(oi) =∑i1,...,iN〈R|AiN . . . Ai1A[oα]ρA[oα]†Ai1† . . . AiN †|R〉=∑i1,...iNTr[(Aik+1† . . . AiN †|R〉〈R|AiN . . . Aik+1)(Aik . . . Ai1A[oα]ρA[oα]†Ai1† . . . Aik†)](A.2)Again by the canonical form, the channel E†(X) = ∑iAi†(X)Ai is tracepreserving and has a unique fixed point Λ which is a density operator. Λcommutes with V(g), so it can be decomposed as Λ =⊕α pαΛα ⊗ Ω whereeach Λα is a density operator in block α and Ω = I/D is the maximallymixed state. Then the first term in the trace evaluates to Tr (|R〉〈R|) Λ = Λ.Similarly, the second term is Tr(ΛA[oα]ρA[oα]†) I [49]. Then we have:p(oi) = Tr(ΛA[oα]ρA[oα]†)Tr Λ = Tr(ΛA[oα]ρA[oα]†)(A.3)56A.1. Mixed state interpretationIf the outcome oα labels a state |i〉 in the wire basis, we have:p(i) = Tr[ΛP†i(⊕αBiα ⊗ Ciα)ρ(⊕αBi†α ⊗ Ci†α)Pi](A.4)= Tr[(⊕αpP†i (α)ΛP†i (α)⊗ Ω)(⊕αBiα ⊗ I)ρ(⊕αBi†α ⊗ I)](A.5)If ρ = Iα, then we have:p(i|α) = Tr(pP†i (α)ΛP†i (α)BiαBi†α)≡ νiiα (A.6)Note that the constants νiiα can be summed over α to recover νii asdefined earlier. For any measurement basis given by an observable O, thesum of probabilities of all possible outcomes can be shown to be Tr(Λρ).This is equal to the trace of ψ in the large N limit, so our probabilities sumto one if our state is normalized.A.1 Mixed state interpretationNow we use the above calculation to argue the validity of our mixed stateinterpretation and the corresponding “sum over outcomes” approach. Con-sider an MBQC scheme in which the logical evolution depends on measure-ment outcomes, even when supplemented by byproduct propagation. Thatis, we assume that measuring the next spin in the chain with outcome |s〉enacts the evolution|L〉 → 1√ps(∑i〈s|i〉Ai)|L〉 = 1√psΣsΓs|L〉, (A.7)where Σs is the unitary byproduct operator, and Γs is the desired evolution,which at this point may not yet be unitary. ps is the probability of obtainingoutcome s, which appears via the Born rule.Now a general computation involves the measurement of m spins inany basis with outcomes ~s = (s1, . . . , sm), propagating byproduct operatorsafter each step. The initial state |L〉 evolves to a final state 1√p~sΣ~s|L′~s〉where |L′~s〉 = Γsm . . .Γs1 |L〉, Σ~s =∏mi=1 Σsi is the accumulated byproductoperator, and p~s is the probability of the outcome string ~s. At this point,our resource state |ψ〉 has evolved to57A.1. Mixed state interpretation|ψ~s〉 = 1√p~s∑〈R|Ain . . . Aim+1Σ~s|L′~s〉|im+1 . . . in〉. (A.8)Computation ends with readout of some observable O on the final state|L′~s〉. Our only tool available to do this is a measurement of the next spinin the chain, m + 1, whose measurement outcome must be used to infersomething about O. Let {|oi〉|i = 0, . . . , d−1} be the relevant measurementbasis for read out of O, which has been appropriately modified to propa-gate the accumulated byproduct operator Σ~s past the readout site. LettingA[oα] =∑i 〈oα|i〉Ai we can use Eq. A.3 to determine the probability ofobtaining the outcome |oα〉 given the previous outcomes ~s:p(oi|~s) = Tr(ΛΣ~sA[oα]|L′~s〉〈L′~s|p~sA[oα]†Σ†~s). (A.9)Since Λ acts trivially in the logical subspace, Σ~s can be eliminated fromthis equation using the unitarity and the cyclicity of the trace. We are leftwith:p(oi|~s) = Tr(ΛA[oα]|L′~s〉〈L′~s|p~sA[oα]†). (A.10)Now, the total probability of obtaining outcome oα is given by p(oα) =∑~s p(oα|~s)p~s. By exploiting linearity within the above expression, we have:p(oi) = Tr(ΛA[oα]σˆA[oα]†). (A.11)where we have introduced the mixed state σˆ given by:σˆ =∑~s|L′~s〉〈L′~s|=∑smΓsm(. . .(∑s1Γs1 |L〉〈L|Γ†s1). . .)Γ†sm . (A.12)So we see that the readout statistics of O are encoded in the mixed state σˆwhich can be determined by summing over the outcomes of each measure-ment during computation. This sum occurs after byproduct propagation,and the accumulated byproduct operator has no effect other than changingthe final readout basis.58


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items