figuret

aainstitutetext: Center for Mathematical Sciences and Applications, Harvard
University, Cambridge, MA 02138, USAbbinstitutetext: Department of Physics and
Astronomy, University of British Columbia, Vancouver, Canadaccinstitutetext:
Stewart Blusson Quantum Matter Institute, University of British Columbia,
Vancouver, Canadaddinstitutetext: Institute for Advanced Study, Tsinghua
University, Beijing 100084, China

# The Gauge Theory of Measurement-Based Quantum Computation

Gabriel Wong b,c Robert Raussendorf d and Bartłomiej Czech

###### Abstract

Measurement-Based Quantum Computation (MBQC) is a model of quantum
computation, which uses local measurements instead of unitary gates. Here we
explain that the MBQC procedure has a fundamental basis in an underlying gauge
theory. This perspective provides a theoretical foundation for global aspects
of MBQC. The gauge symmetry reflects the freedom of formulating the same MBQC
computation in different local reference frames. The main identifications
between MBQC and gauge theory concepts are: (i) the computational output of
MBQC is a holonomy of the gauge field, (ii) the adaption of measurement basis
that remedies the inherent randomness of quantum measurements is effected by
gauge transformations. The gauge theory of MBQC also plays a role in
characterizing the entanglement structure of symmetry-protected topologically
(SPT) ordered states, which are resources for MBQC. Our framework situates
MBQC in a broader context of condensed matter and high energy theory.

##  1 Introduction

Measurement-based quantum computation (MBQC) RB01  is a scheme of universal
quantum computation driven solely by measurements; no unitary evolution takes
place in the computational process. The measurements are local, and applied to
an entangled initial state—the resource state. The resource perspective (see
e.g. VdN ; VdN2 , note TooE , however) is suggested by the observation that
once all the local measurements have been performed, the post-measurement
state is a tensor-product state with no entanglement left. The initial
entanglement has been converted into computational output. See Figure 1 for
illustration.

The power of MBQC depends on the resource state used. Several types of
resource states, such as cluster states RB01a  and AKLT states AKLT ; AKLT2
on various two-dimensional lattices, give rise to computational universality
RB01 ; AKLTmbqc_M ; AKLTmbqc_W ; Darmawan ; AKLTmbqc_spin2 . On the other
hand, some highly entangled states, such as Kitaev surface code states, have
extremely limited computational power for MBQC Kit . As a general result, it
is known that universal resource state are extremely rare in Hilbert space,
for the seemingly paradoxical reason that most states are too entangled to be
computationally useful TooE .

The above picture is affected by symmetry. Namely, in certain symmetry
protected phases of matter GW ; Wen1 ; Wen2 ; Schuch , every ground state has
the same computational power Darmawan ; SPT0 ; SPT1 ; SPT2 ; SPT3 ; SPT4 ;
SPT5 ; SPT5b ; SPT6 ; SPT7 . This phenomenon has been termed ‘computational
phases of quantum matter’ SPT0 ; SPT1 . Some of these computational phases
have universal computational power SPT5 ; SPT5b ; SPT6 ; SPT7 . Yet, a
classification of universal resource states has to date remained elusive.

Figure 1: Graphical summary of MBQC with 2D cluster states. The circles
represent the individual qubits of the cluster state, and the grey lines
define the corresponding entanglement structure. The symbol $\odot$ represents
a measurement in the $Z$-basis, and the double-headed arrows are measurements
in the eigenbasis of $\cos\alpha X+\sin\alpha Y$, for various angles $\alpha$.
The $Z$-measurements have the effect of removing the measured qubits from the
cluster, leaving the remainder in a network-like structure. In a circuit model
interpretation, the ‘horizontal’ direction represents circuit time (from left
to right), and the ‘vertical’ direction labels the logical qubits in the
simulated quantum register. The horizontal structures in yellow underlay
represent sequences of one-qubit rotations, and the vertical bridges in yellow
underlay mediate interaction between logical qubits.

Investigations of MBQC have traditionally adopted a local perspective. In this
view, a central lemma is that quantum gates can be simulated by applying local
measurements to an entangled state. Consequently, every circuit model
computation—that is, a series of gates—can be converted into a sequence of
local measurements on an appropriate resource state. From this vantage point,
MBQC functions as a modular protocol for translating circuit model
computations into measurements: gate by gate, measurement by measurement. This
locally focused perspective is rightful and important; indeed, this is how the
universality of MBQC as a computational model is typically proved. It does
not, however, tell the whole story of MBQC.

The present paper lays out a complementary, global perspective. Readers
familiar with MBQC will readily identify one aspect of it, which is tellingly
non-local: the computational output is a specific combination of measurement
outcomes, which were registered over the course of the computation. In this
way, the computational power of MBQC relies on correlations between different
measurement outcomes, which are extracted over many distinct and generically
distant locales in the resource state. This fact is neither here nor there in
a local view of MBQC, but it is an essential aspect of the computational
scheme! Our quest for a global retelling of the MBQC story was initially
motivated by this observation.

One topic in the undergraduate physics curriculum showcases a similar
interplay between the local and the global: gauge theory. In the local
perspective, defining a gauge theory starts with a vector potential
$A_{\mu}(x)$, which is a local but unphysical quantity. It is unphysical
because it is subject to gauge transformations, i.e. local symmetries of the
theory. As the local symmetry acts independently at every location, it strips
$A_{\mu}(x)$ off independent physical meaning because it can always locally
reset it to an arbitrary different value. But this does not make $A_{\mu}(x)$
redundant. As famously explained by Aharonov and Bohm, the global object
$\oint dx^{\mu}A_{\mu}(x)$—a Wilson loop—measures an unambiguously defined,
physical flux. Wilson loops are nonlocal, but they comprise the genuine
degrees of freedom of a gauge theory. These facts show an uncanny resemblance
to MBQC. Our task in this paper is to explain that this resemblance is not
skin-deep or accidental. We argue that MBQC in all its aspects—global and
local—is in fact naturally described by the language of gauge theory.

There is another reason why gauge theory could be suspected to play a role in
MBQC. On one-dimensional cluster states, MBQC can be understood as a sequence
of quantum half-teleportations CLN . However, as explained in Reference
withlenny  (see also mielczarek ), the effect of quantum teleportation is
indistinguishable from the effect of a background gauge field on a charged
particle traveling through space. While the argument in withlenny  assumed
post-selection on projective measurements, we of course know that any
measurement outcome in an appropriate basis affords teleportation if the
recipient applies a corrective gate on her end. If we now return to the
discussion where teleportation and gauge theory are unified, the application
of that corrective gate plays the role of a gauge transformation. This claim,
which generalizes the analysis of withlenny  by eliminating the post-selection
assumption, provides an important connection between MBQC and gauge theory.

To make the translation between MBQC and more familiar gauge theories
transparent, we highlight the main entries of the proposed dictionary:

  1. 1.

In MBQC, one progressively adjusts measurement bases depending on outcomes of
prior measurements. These adjustments are gauge transformations; see Section
4.4.2.

  2. 2.

The computational output of MBQC is a flux analogous to $\oint
dx^{\mu}A_{\mu}(x)$; see Section 4.3.

  3. 3.

Programming MBQC—the choice of quantum algorithm—amounts to choosing a basis,
in which the flux is measured; see Section 5.4.

The gauge theory perspective is directly connected to symmetry-protected
topological (SPT) order, which characterizes one class of states in the
computational phase of quantum matter, including the one-dimensional cluster
state. Although SPT order has long been known to play an important role in
MBQC, we now understand that role on a more formal level: the symmetry, which
protects the topological order, is our gauge symmetry.

A final point worth emphasizing is that the present paper is limited to MBQC
on a one-dimensional cluster state. This setting allows MBQC to simulate
arbitrary $SU(2)$ gates but not larger unitaries, and falls short of
universality. The universal, two-dimensional case will be treated in a future
publication.

##### For whom the paper is written, and why

A target audience for this paper is quantum information theorists and
condensed matter theorists, who are interested in unifying the various guises
of MBQC under a common formalism. MBQC exemplifies many ideas that are of
current relevance in high-energy and condensed matter physics, such as
holographic duality ehm ; daniel ; cohomology  and bulk-boundary
correspondence SPT1 ; Laughlin ; Fuchs , the emergence of temporal order BTO ;
SRTO , and topological order in 3D FTQC1 ; FTQC2 ; FTQC3 ; FTQC4 —in the
setting of quantum information processing. Recently, the subject of symmetry-
protected topological order has contributed to the endeavor of exposing the
fundamental structures of MBQC, and here we identify a further ingredient:
gauge theory. We have kept the discussion of MBQC self-contained, so
physicists outside the quantum information and condensed matter communities
should find it easy to digest.

We use the one-dimensional cluster state as a main stage of presentation. This
considerably simplifies the discussion while permitting to lay out the general
tenet. It shall be noted, however, that universal measurement-based quantum
computation requires cluster states in dimension two or higher.

##### Organization

Section 2 is a pedagogical review of background material, including the one-
dimensional cluster state and the MBQC protocol. Section 3 sets the stage for
the formulation of the MBQC gauge theory by assigning group labels for the
MBQC measurement basis using the MPS symmetries of the cluster state. In
section 3.3, we formulate MBQC on a ring-like cluster state, which manifests
most cleanly the gauge-theoretic character of MBQC. Section 4—the most
important part of the paper—organizes the material in Sections 2 and 3 into
concepts from gauge theory: a covariant derivative, reference sections, gauge
transformations, and fluxes. Section 5 discusses the phenomenological
implications of the MBQC gauge symmetry and shows how the gauge theoretical
formulation sheds light on the relation between MBQC and the circuit model. We
close the paper with a discussion of future directions.

##  2 Review of measurement-based quantum computation

Throughout this paper, we write the Pauli operators as $\sigma_{x}=:X$,
$\sigma_{y}=:Y$, $\sigma_{z}=:Z$, and use a subscript $j$ to indicate when the
Pauli matrix acts on the $j^{\rm th}$ qubit. We let $|\pm\rangle$ be the
eigenstates of $X$ with eigenvalues $\pm 1$. We will often refer to these
eigenstates using a binary variable $s$ according to $\ket{(-)^{s}}$, that is
$s=0$ stands for $|+\rangle$ and $s=1$ stands for $|-\rangle$. We will also
need a notation for eigenstates of $O(\alpha)=(\cos\alpha)X+(\sin\alpha)Y$;
they will be denoted with $\ket{\pm_{\alpha}}$. Measurements of $O(\alpha)$
will also be referenced using a binary variable $s$ according to
$\ket{\pm_{\alpha}}=\ket{(-)^{s}_{\phantom{s}\alpha}}$.

###  2.1 The one-dimensional cluster state

The one-dimensional cluster state is a resource state for MBQC, which affords
enough computational power to simulate $SU(2)$ gates. For reasons which will
become clear in Section 5.4.1, we denote the cluster state as
$\operatorname{|1\rangle}$.

##### Teleportation and the cluster state

The logical processing in MBQC may be understood as a sequence of
teleportations. A resource state can be extracted by reordering commuting
operations in a sequence of teleportation steps.

Figure 2: Circuit diagram for quantum teleportation.

The circuit for quantum teleportation is shown in the left panel of Figure 2.
Alice and Bob share a prearranged resource state in the form of a Bell pair
$\ket{\beta_{00}}:=2^{-1/2}(\ket{11}+\ket{00})$. To teleport an initial qubit
$|{\rm in}\rangle$, Alice makes a measurement in the Bell basis, which
comprises states
$\ket{\beta_{s_{1}s_{2}}}=X_{1}^{s_{2}}Z_{1}^{s_{1}}\ket{\beta_{00}}$ with
$s_{i}=0,1$. (The subscripts in $X_{1}$ and $Z_{1}$ refer to the first qubit
of the Bell pair.) Because Alice does not control the random outcome of this
measurement, the teleported qubit ends up rotated by a known but random
byproduct operator

$\displaystyle V_{s_{2}s_{1}}=X^{s_{2}}Z^{s_{1}}\quad{\rm
where}\leavevmode\nobreak\ s_{i}=0,1.$ (1)

In this way, teleportation defines a randomly fluctuating circuit.

This randomness poses a challenge to our ability to perform the most basic
computation: to simulate the identity gate on the teleported qubit. Luckily,
Bob can undo the effect of the fluctuation because the measurement outcomes
$(s_{2},s_{1})$ are known to Alice, who passes them on to him by classical
channels. Once Bob learns the measurement outcome, he can apply the inverse of
the byproduct (1) and recover $|{\rm in}\rangle$. What is equally important
for the purposes of this paper, the measurement outcomes are related by a
symmetry. The byproduct operators (1) form a projective representation of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, that is they respect the group operation

$(s_{2},s_{1})+(s_{2}^{\prime},s_{1}^{\prime})=(s_{2}+s_{2}^{\prime},s_{1}+s_{1}^{\prime})\qquad\textrm{(mod\leavevmode\nobreak\
2)}$ (2)

up to a multiplicative phase. While the group operation (2) is not essential
in a single instance of quantum teleportation, it makes for a key
simplification when multiple teleportations are conducted in sequence. For
example, after $N$ sequential teleportations, Bob can apply a single
corrective operator to invert

$B=X^{\left(\sum_{j\leavevmode\nobreak\ {\rm
even}}^{2N}s_{j}\right)}Z^{\left(\sum_{j\leavevmode\nobreak\ {\rm
odd}}^{2N-1}s_{j}\right)}$ (3)

and recover the initial state $|{\rm in}\rangle$ up to a phase. We argue that
this simplification, which is essential for MBQC, is best understood in the
language of gauge theory. The $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, which
permutes the random measurement outcomes in each step, plays the role of a
gauge group.

A resource state for a single instance of quantum teleportation is the Bell
pair $|\beta_{00}\rangle$. A resource state for MBQC must, in a similar
fashion, enable multiple teleportations in a sequence. Such a resource is
constructed by putting together many copies of the circuit in Figure 2 as
building blocks. Before the building blocks are assembled, it is useful to
redraw them using the cPhase gate

${\rm
cPhase}(i,j):=\mathbb{I}_{i,j}-\frac{(\mathbb{I}_{i}-Z_{i})(\mathbb{I}_{j}-Z_{j})}{2}$
(4)

as is done in the right panel of Figure 2. In equation (4), $i$ and $j$ label
the two qubits on which cPhase acts. The redrawing reveals that Alice’s
measurement in the $|\beta_{s_{1}s_{2}}\rangle$ basis is equivalent to
measurements in the $X$-basis on the state shown in Figure 3.

Figure 3: MPS tensor from the teleportation circuit.

To enable multiple teleportations to proceed in a sequence, we concatenate
copies of Figure 3, identifying the $\langle{\rm out}|$ leg of one copy with
the $|{\rm in}\rangle$ leg of the next copy. The state obtained this way is a
matrix product state (MPS) and Figure 3 represents its MPS tensor. This MPS
state—the one-dimensional cluster state $\operatorname{|1\rangle}$—is shown in
Figure 4.

##### The cluster state as a matrix product state

It is important to distinguish two Hilbert spaces involved in the MPS tensor.
Alice’s measurement of the indices marked $s_{2}s_{1}$ in Figure 3 effects
quantum teleportation—a linear map from $|{\rm in}\rangle$ to $|{\rm
out}\rangle$. As such, the MPS tensor is an $(s_{2},s_{1})$-dependent linear
map $A_{s_{2}s_{1}}$ with matrix elements $\langle{\rm
out}|A_{s_{2}s_{1}}|{\rm in}\rangle$. In discussions of MPS states, it is
standard terminology to call the Hilbert space spanned by $|{\rm in}\rangle$
and $|{\rm out}\rangle$ the virtual space or correlation space, while the
Hilbert space denoted by the subscript $\cdot_{s_{2}s_{1}}$ is referred to as
the physical space. Virtual space is called virtual because, when the
$\langle{\rm out}|$ leg of one MPS tensor is joined with the $|{\rm
in}\rangle$ leg of the next (when two teleportations are conducted in a
sequence), we lose direct physical access to that degree of freedom. The
physical space is called physical because it is always physically accessible;
it is the space where Alice makes her measurements.

Our discussion should make clear that the MPS tensor $A_{s_{2}s_{1}}$ in the
$X$-basis equals the byproduct $V_{s_{2}s_{1}}$ from equation (1). The cluster
state on a ring of $2N$ qubits is obtained by contracting $N$ copies of this
MPS tensor:

$\\!\\!\\!\\!\\!\\!\operatorname{|1\rangle}=\mathcal{N}\sum_{(s_{2j},s_{2j-1})\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}{\rm
Tr}\big{(}A_{s_{2N},s_{2N-1}}\ldots
A_{s_{4},s_{3}}A_{s_{2},s_{1}}\big{)}|s_{2N},s_{2N-1}\rangle\ldots|s_{4},s_{3}\rangle|s_{2},s_{1}\rangle$
(5)

Each $|s_{2j},s_{2j-1}\rangle$ is a two-qubit state taken from
$\\{|\\!++\rangle,|\\!+-\rangle,|\\!-+\rangle,|\\!--\rangle\\}$, labeled with
an element $(s_{2j},s_{sj-1})\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. We use
the generic notation $A_{(s_{2j},s_{2j-1})}$ for the MPS tensor rather than
$V_{(s_{2j},s_{2j-1})}$ since we will later be interested in evaluating the
same tensor in a different basis. Here and in similar formulas below the
factor $\mathcal{N}$ ensures a proper normalization of the state.

Throughout this paper, the notation ‘$|1\rangle$’ shall stand for the 1D
cluster state, not for a computational basis state. The reason for this
notation will become clear later. In short, the cluster state is identified as
an eigenstate of a flux observable with eigenvalue 1.

For a chain-like cluster state, the traces in the amplitudes are replaced by
analogous expressions, which depend on a choice of boundary conditions at
endpoints:

${\rm Tr}\big{(}A_{s_{2N},s_{2N-1}}\ldots
A_{s_{4},s_{3}}A_{s_{2},s_{1}}\big{)}\,\,\longrightarrow\,\,\langle{\rm
out}|A_{s_{2N},s_{2N-1}}\ldots A_{s_{4},s_{3}}A_{s_{2},s_{1}}|{\rm in}\rangle$
(6)

##### A glimpse of a global structure.

Equation (5) offers a first sighting of the kind of global structure, which we
seek to identify. This comes in the form of a global selection rule, which
determines which combinations of physical spins do / do not overlap with the
ring-like cluster state.

The amplitudes in (5) involve products of projective representation matrices
of $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. We can use the group multiplication
$A_{(s_{2j+2},s_{2j+1})}A_{(s_{2j},s_{2j-1})}\propto
A_{(s_{2j+2},s_{2j+1})+(s_{2j},s_{2j-1})}$ to simplify them:

$\\!\operatorname{|1\rangle}=\mathcal{N}\sum_{(s_{2j},s_{2j-1})\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}\textrm{(phase)}\times({\rm
Tr}A_{(s_{2N},s_{2N-1})+\ldots(s_{4},s_{3})+(s_{2},s_{1})}\,|s_{2N},s_{2N-1}\rangle\ldots|s_{4},s_{3}\rangle|s_{2},s_{1}\rangle$
(7)

Since every $A_{(\cdot)}$ except $A_{++}$ is traceless, the wavefunction
vanishes unless

$(s_{2N},s_{2N-1})\ldots(s_{4},s_{3})+(s_{2},s_{1})=(0,0)\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$
(8)

Component-wise, we thus have

$a\equiv s_{1}+s_{3}+\ldots+s_{2N-1}=0\qquad{\rm and}\qquad b\equiv
s_{2}+s_{4}+\ldots+s_{2N}=0\quad\textrm{(mod 2)}$ (9)

We will recast the selection rule (8-9) as a holonomy $(a,b)$ of a
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ gauge field. In this view, the cluster
state on a ring represents a gauge theory state with trivial
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ flux. Equivalently, the Wilson line
around the cluster evaluates to $++$, which is the identity element of the
group. This is a first reason why we denote the cluster state as
$\operatorname{|1\rangle}$, though a more complete explanation will be given
in Section 5.4.1.

Readers familiar with MBQC will recognize the meaning of this discussion. When
we measure $\operatorname{|1\rangle}$ in the $|\pm\rangle$ basis, we
effectively simulate the identity gate. This simulation happens to have a
fully deterministic outcome—reflecting the fact that
$\operatorname{|1\rangle}$ is a state of definite $++$ (identity) flux.

##### The cluster state is short ranged entangled

Figure 3 shows that the MPS tensor can be constructed by acting with two-qubit
entangling gates (4) on a product state. Naturally, the same can be said about
the full MPS state. The left panel of Figure 4 shows (a segment of) the
cluster state, constructed by repeated applications of the cPhase gate on a
product state. As an equation, we have:

$\operatorname{|1\rangle}:=\prod_{i=1}^{2N-1\leavevmode\nobreak\ {\rm
or}\leavevmode\nobreak\
2N}\\!\\!\\!\\!\\!\\!\\!\text{cPhase}(i,i+1)\left(\bigotimes_{j=1}^{2N}|+\rangle_{j}\right)$
(10)

The $(2N)^{\rm th}$ gate $\text{cPhase}(2N,2N+1)\equiv\text{cPhase}(2N,1)$ is
only applied on a ring, where we define $2N+1\equiv 1$. Note that all cPhases
commute because they are simultaneously diagonal in the $Z$-eigenbasis.

As seen in Figure 4, the preparation of the cluster from the product state
$\otimes_{j}|+\rangle_{j}$ can be achieved in two time steps: the application
of the cPhases$(i,i+1)$ with $i$ odd, and with $i$ even. Because the cluster
state can be prepared by a circuit of finite depth (two), it is short range-
entangled. This demonstrates that using the cluster state for quantum
computation does not introduce hidden costs associated with the preparation of
the initial state.

Figure 4: The cluster state, as given by equation (10) (left) and in its MPS
form (middle). The highlighted part of the left panel is one matrix of the MPS
description (right); it covers one ‘block.’

##### The cluster state as a stabilizer state.

Equation (10) reveals that $\operatorname{|1\rangle}$ is a stabilizer state
GomaSM ; Goma2SM . Because every $X_{j}$ stabilizes
$\otimes_{j}|+\rangle_{j}$, conjugating $X_{j}$ by the cPhases in (10) gives a
stabilizing operator for $\operatorname{|1\rangle}$. Using the identity ${\rm
cPhase}(i,j)X_{i}\,{\rm cPhase}(i,j)=X_{i}Z_{j}$, we find the following
stabilizers:

$K_{j}\operatorname{|1\rangle}=\operatorname{|1\rangle}\qquad{\rm
with}\leavevmode\nobreak\ \leavevmode\nobreak\ K_{j}:=Z_{j+1}X_{j}Z_{j-1}$
(11)

On a ring, these equations completely determine $\operatorname{|1\rangle}$. On
a chain indexed by $1\leq j\leq 2N$, equation (11) makes no sense for $j=1$ or
$2N$. In that context, in addition to (11), the chain-like cluster state is
also stabilized by two special operators $Z_{2}X_{1}$ and $X_{2N}Z_{2N-1}$.
The $K_{j}$ with $2\leq j\leq 2N-1$, along with the two special stabilizers at
endpoints, completely determine the cluster state on a chain. For future use,
we remind the reader that each $K_{j}$ squares to the identity.

The stabilizer conditions (11) translate the entanglement structure of the
cluster state into a set of algebraic constraints, which can be solved
explicitly by summing over orbits of the stabilizers:

$\displaystyle\operatorname{|1\rangle}\propto\prod_{i}\left(\frac{1+K_{i}}{2}\right)\left(\bigotimes_{j=1}^{2N}|+\rangle_{j}\right)$
(12)

The structure of these constraints as well as their solution mirrors the
structure of gauge constraints, which is why we will be able to embed the
cluster state into a gauge theory. The stabilizer conditions play an important
role in mitigating the randomness of measurement outcomes in MBQC. Much of our
paper is devoted to understanding this feature of MBQC in terms of a gauge
symmetry. For a preview of this interpretation, observe that for any operator
$O$, conjugation by a stabilizer does not affect expectation values taken in
$\operatorname{|1\rangle}$:

$\operatorname{\langle
1|}K_{j}OK_{j}\operatorname{|1\rangle}=\operatorname{\langle
1|}O\operatorname{|1\rangle}$ (13)

This means that, so long as we work with the cluster state
$\operatorname{|1\rangle}$, it is redundant and unnecessary to distinguish $O$
from $K_{j}OK_{j}$. For a technician operating on $\operatorname{|1\rangle}$,
the difference between $O$ and $K_{j}OK_{j}$ is a redundancy of description—a
redundancy, which markedly resembles a gauge symmetry.

Because the stabilizers $K_{j}$ commute with one another, the full stabilizer
group of the cluster state is isomorphic to $\mathbb{Z}_{2}^{2N}$. In fixing a
‘stabilizer gauge,’ one independent binary choice—to apply or not to apply
$K_{j}$ (as in (12))—is available at every qubit $j$. The independence of
these choices agrees with the understanding of gauge symmetry as a local
symmetry, one $\mathbb{Z}_{2}$ per qubit. In fact, the $K_{j}$s which act on
even and odd sites can be meaningfully distinguished from one another. We will
see that this implies the cluster state supports a
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ gauge symmetry, and that the gauge
character of this symmetry is an essential component of MBQC.

###  2.2 MBQC

Here we review MBQC on a chain, following the treatment of Eis2  in the MPS
formalism. In Section 2.2.1 we introduce the idea of a logical quantum
register propagating in the MPS virtual (or correlation) space, first for the
special instance where all measurements are performed in the local $X$-basis.
In Section 2.2.2 we introduce more general local measurement bases, leading to
more MBQC-simulated quantum gates. In Section 2.2.3 we describe how to extract
the computational output from the measurement record.

####  2.2.1 Basic idea

To begin, we write down the cluster state on a chain as defined by equations
(5) and (6):

$\operatorname{|1\rangle}=\mathcal{N}\sum_{s_{j}\in\mathbb{Z}_{2}}\Big{(}\langle{\rm
out}|A_{s_{2N},s_{2N-1}}\ldots A_{s_{4},s_{3}}A_{s_{2},s_{1}}|{\rm
in}\rangle\Big{)}|s_{2N},s_{2N-1}\rangle\ldots|s_{4},s_{3}\rangle|s_{2},s_{1}\rangle.$

At present, we consider the above expansion in the local $X$-basis only. This
restriction will subsequently be lifted. One way to interpret this formula is
as a sum over trajectories, which an input state $|{\rm in}\rangle$ follows
under successive applications of operators $A_{s_{2j},s_{2j-1}}$. In a
laboratory, an experimenter can (partly) control these trajectories by
projecting the cluster state onto chosen states of successive qubits. To wit,
measuring the first two qubits in the $\langle s_{2},s_{1}|$ basis applies the
gate $A_{s_{2},s_{1}}=V_{s_{2},s_{1}}$:

$\langle
s_{2},s_{1}\\!\operatorname{|1\rangle}=\mathcal{N}^{\prime}\sum_{s_{j}\in\mathbb{Z}_{2}}\Big{(}\langle{\rm
out}|A_{s_{2N},s_{2N-1}}\ldots A_{s_{4},s_{3}}V_{s_{2},s_{1}}|{\rm
in}\rangle\Big{)}|s_{2N},s_{2N-1}\rangle\ldots|s_{4},s_{3}\rangle$ (14)

Note that the matrix $V_{s_{2},s_{1}}$, which is left inside the amplitude
after the $\langle s_{2},s_{1}|$ projection, is not an MPS tensor anymore
because its physical indices are no longer summed over. This is why we denote
it as $V_{s_{2},s_{1}}$ and not $A_{s_{2},s_{1}}$; see the comment above
equation (5). A sequence of projections determines a longer trajectory:

$\ldots\,\longleftarrow\,V_{s_{6},s_{5}}V_{s_{4},s_{3}}V_{s_{2},s_{1}}|{\rm
in}\rangle\,\longleftarrow\,V_{s_{4},s_{3}}V_{s_{2},s_{1}}|{\rm
in}\rangle\,\longleftarrow\,V_{s_{2},s_{1}}|{\rm
in}\rangle\,\longleftarrow\,|{\rm in}\rangle$ (15)

MBQC uses such trajectories to realize quantum computation. Indeed, (15) can
be viewed as a simulation of a computation in the circuit model, in which the
applied gates are of the form (1). The lab technician, who projects
$\operatorname{|1\rangle}$ onto chosen single qubit states, is a quantum
computer programmer. In the final step of this quantum computation, the last
state on the trajectory

$V_{s_{2N},s_{2N-1}}\ldots V_{s_{4},s_{3}}V_{s_{2},s_{1}}|{\rm
in}\rangle={\rm(phase)}\times V_{(s_{2N},s_{2N-1})+\ldots+(s_{2},s_{1})}|{\rm
in}\rangle$ (16)

is measured in some basis $\langle{\rm out}|$ to produce one classical bit of
computational output.

The above description leaves out two important aspects of MBQC. The first one
concerns the set of quantum gates, which MBQC can simulate. Thus far, we have
only drawn gates from (1), but for realizing general $SU(2)$ transformations a
larger gate set is necessary. This will require a generalization of the
quantum teleportation protocol, in which the measurement basis is modified.
The second wanting point, which is conceptually more important, is about
control over measurement outcomes. The preceding discussion pretended that the
technician could project $\operatorname{|1\rangle}$ onto chosen qubit states
at will, but of course every quantum measurement is probabilistic. When the
technician does not obtain her planned outcome, the virtual qubit in (15)
takes an unplanned turn. For a complete definition of MBQC, we must give a
protocol to address both of those outstanding points. We do so presently.

####  2.2.2 Measurement basis and temporal order

In order to simulate an arbitrary $SU(2)$ gate, MBQC generalizes the
teleportation protocol by measuring the cluster state in a rotated basis on
the $XY$ plane. To prevent the randomness of measurement outcomes from
contaminating the quantum computation, future measurement angles must be
adapted based on past outcomes. These two features can be achieved by
measurements in a temporally ordered basis, given by

$O\big{(}(-)^{q_{i}}\alpha_{i}\big{)}:=\cos(\alpha_{i})X+\sin\big{(}(-)^{q_{i}}\alpha_{i}\big{)}Y,$
(17)

where

$q_{i}=\,s_{i-1}+s_{i-3}+\ldots+\big{(}s_{2}\leavevmode\nobreak\ {\rm
or}\leavevmode\nobreak\ s_{1}\big{)}.$ (18)

Here $s_{i}$ denotes the measurement outcome for measuring along
$(-)^{q_{i}}\alpha_{i}$. The parameters $q_{i}$ tell the experimenter
measuring the $i^{\rm th}$ qubit to adapt the sign of $\alpha_{i}$ based on
results of previous measurements. Eq. (18) is one of the two classical side
processing relations of MBQC. It governs the adaptation of measurement bases
to account for the randomness of earlier measurement outcomes.

To understand the adapted basis (18) in the simplest setting, consider
measurements on a single block of two sites. (We will refer to consecutive
pairs of spins as ‘blocks’ throughout the paper; cf. Figure 4.) Let us denote
the projection of the MPS tensor onto $O(\alpha_{i})$-eigenstates with
$A_{s_{2}s_{1}}\\!(\alpha_{2},\alpha_{1})$. Equation (18) instructs us to flip
the sign of $\alpha_{2}$ based on the result of measuring the first spin along
$\alpha_{1}$ because $q_{2}=s_{1}$. Doing so results in the following
operators acting on the virtual space:

$\begin{array}[]{rcl}A_{++}(\alpha_{2},\alpha_{1})&=&V_{++}\,U\\\
A_{-+}(\alpha_{2},\alpha_{1})&=&V_{-+}\,U\\\
A_{+-}(-\alpha_{2},\alpha_{1})&=&V_{+-}\,U\\\
A_{--}(-\alpha_{2},\alpha_{1})&=&V_{--}\,U\end{array}$ (19)

where

$U=\exp\left(-i\frac{\alpha_{2}}{2}X\right)\exp\left(-i\frac{\alpha_{1}}{2}Z\right)=A_{++}(\alpha_{2},\alpha_{1})$
(20)

and $V_{s_{2}s_{1}}$ was defined in (1). These equations generalize
teleportation, in the sense that the ‘teleported’ input state arrives rotated
by a unitary transformation $U$, up to a random byproduct operator
$V_{s_{2}s_{1}}$. Ordinary teleportation corresponds to $U=1$ and is recovered
when $\alpha_{i}=0$.

Now consider a cluster chain with $N$ blocks, that is $2N$ spins. We find in
eq. (19) that for all four combinations of measurement outcomes, the unitary
$U$ is the same, and the evolution of the virtual system differs only by the
random byproduct operator. The byproduct operators $V$ are all of Pauli type.

These random byproduct operators, one produced by each measurement, need to be
removed from the computation. This is achieved by propagating them forward in
time, through the not yet implemented part of the computation, and past the
logical readout measurements. What happens after logical readout doesn’t
affect the computational output.

Inspecting equation (20), we find:

$A_{++}(\alpha_{2},\alpha_{1})X=XA_{++}(\alpha_{2},-\alpha_{1})\qquad{\rm
and}\qquad A_{++}(\alpha_{2},\alpha_{1})Z=ZA_{++}(-\alpha_{2},\alpha_{1}).$
(21)

The forward-propagation of the byproduct operators flips angles of rotations
on virtual space, and those flips have to be compensated by flips of the
measurement angle, cf. Eq. (17). The binary observables $q_{i}$ account for
this. With eqs. (1) and (20) we verify that the sign flip of the measurement
angle on an even site depends on the parity of all measurement outcomes on
earlier odd sites, and the sign flip of the measurement angle on an even site
on the parity of the measurement outcomes of the earlier odd sites. This is
the content of the classical processing relation (18).

Denoting the MPS tensor in the adapted basis by

$A_{s_{i+1},s_{i};q_{i+1},q_{i}}:=A_{s_{i+1},s_{1}}((-1)^{q_{i+1}}\alpha_{2N},(-1)^{q_{i}}\alpha_{2N-1}),$
(22)

the result of the byproduct propagation can be summarized by

$A_{s_{2N},s_{2N-1};q_{2N},q_{2N-1}}\ldots
A_{s_{2},s_{1};q_{2},q_{1}}=B\,U_{\rm total},$ (23)

where

$\displaystyle B$ $\displaystyle=V_{s_{2N},V_{2N-1}}\ldots
V_{s_{4},s_{3}}V_{s_{2},s_{1}}={\rm(phase)}\times
V_{(s_{2N},s_{2N-1}+\ldots+(s_{2},s_{1})},$ (24) $\displaystyle U_{\rm total}$
$\displaystyle=A_{++}(\alpha_{2N},\alpha_{2N-1})\ldots
A_{++}(\alpha_{4},\alpha_{3})A_{++}(\alpha_{2},\alpha_{1}).$ (25)

We now recognize that equation (17) is designed to render (25)—so that the
adapted measurements always simulate the same unitary transformation $U_{\rm
total}$.

Equation (23) is the most important result of the MBQC protocol. It shows that
when the cluster state is measured in the adapted basis, the ‘teleported’
qubit arrives rotated by $U_{\rm total}$, up to a known byproduct operator $B$
for which the recipient must correct. In Section 4.2 we explain that $B$
functions as a $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ Wilson line.

##### Simulating a general unitary

Finally, observe that a general $SU(2)$ gate can be generated by measuring
four qubits:

$A_{++}(0,\alpha_{3})A_{++}(\alpha_{2},\alpha_{1})=\exp\left(-i\frac{\alpha_{3}}{2}Z\right)\exp\left(-i\frac{\alpha_{2}}{2}X\right)\exp\left(-i\frac{\alpha_{1}}{2}Z\right)$
(26)

This expression parametrizes the $SU(2)$ manifold with Euler angles
$\alpha_{1,2,3}$. We conclude that measurements of $\operatorname{|1\rangle}$
in the $O(\alpha)$ eigenbasis can simulate every $SU(2)$ gate on virtual space
so long as the effect of byproduct operators—an imprint of the randomness of
measurement outcomes—can be properly remedied.

####  2.2.3 Computational output for MBQC on a chain

After qubits 1 through $2N$ of a chain-like cluster state have been measured
in the adapted basis, the experimenter gets a probability distribution, which
depends on the boundary condition $\langle{\rm out}|$ at the other end.
Instead of a preordained boundary condition, we will follow the logic of
equation (47) and treat the choice of $\langle{\rm out}|$ as one final
projective measurement, applied to the $(2N+1)^{\rm st}$ qubit in the state:

${\rm(phase)}\times B\,U|{\rm in}\rangle$ (27)

The $B$ and $U$ are given in (24-25) and we drop the subscript ‘total’ from
$U$.

In the circuit model of quantum computing, the application of a gate $U$ to an
initial state $|{\rm in}\rangle$ is followed by a measurement of $U|{\rm
in}\rangle$ in some orthogonal basis, for example $\langle\pm|$. The
computational output is sampled from the resulting probability distribution
$p_{\pm}=|\langle\pm|U|{\rm in}\rangle|^{2}$.

In MBQC, we mirror that last step by measuring state (27) in an orthogonal
basis $\langle{\rm out}_{\pm}|$, with $\langle\pm|$ being a canonical choice.
The hitherto unfixed choice of boundary condition $\langle{\rm out}|$ at the
end of the chain represents the choice of basis for the final measurement,
whose outcome serves as the computational output.

In equation (27), the randomness of prior measurement outcomes remains visible
in the byproduct operator $B$. For a computational output that is free of
randomness, we again adjust the measurement basis and project state (27) onto
$\langle{\rm out}_{\pm}|B$ instead of $\langle{\rm out}_{\pm}|$. This works
because $B^{2}=\pm 1$ implies:

$\langle{\rm out}_{\pm}|B\,{\rm(phase)}\times B\,U|{\rm
in}\rangle=\textrm{(phase)}\times\langle{\rm out}_{\pm}|U|{\rm in}\rangle$
(28)

When the final measurement is done in the $X$-eigenbasis $\langle{\rm
out}_{\pm}|=\langle\pm|$, the adjustment $\langle{\rm
out}_{\pm}|\to\langle{\rm out}_{\pm}|B$ is particularly simple. Let us write
the byproduct $B$ in terms of the ‘holonomy’ variables $(a,b)$ from (9):

$B=X^{b}Z^{\tilde{a}}\qquad{\rm with}\leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{a}=\sum^{2N-1}_{j\leavevmode\nobreak\ {\rm odd}}s_{j}\quad{\rm
and}\quad b=\sum^{2N}_{j\leavevmode\nobreak\ {\rm even}}s_{j}$ (29)

We ignore the possible phase because it will drop out of the reported
probability distribution $p_{\pm}=|\langle{\rm out}_{\pm}|U|{\rm
in}\rangle|^{2}$. Letting $\langle{\rm out}_{\pm}|:=\bra{s_{2N+1}}$, we see
that the byproduct transforms the final projection basis as:

$\displaystyle\bra{s_{2N+1}}B=\bra{s_{2N+1}+\tilde{a}}:=\bra{a}$ (30)

Accordingly, we define the computational output as:

$a:=s_{2N+1}+\tilde{a}=s_{1}+s_{3}+\ldots+s_{2N-1}+s_{2N+1}$ (31)

Eq. (31) is the second classical processing relation of MBQC. Together with
eq. (18), which governs the adaptation of measurement bases, it is responsible
for compensating the randomness inherent in the quantum measurements driving
MBQC.

The probability $p(a)$ of observing the output $a=0,1$ is exactly equal to the
probability $p(a)=|\braket{a}{U}{\rm{in}}|^{2}$ for the corresponding quantum
circuit realizing the unitary $U$ and finding $a$ upon readout.

Equation (31) puts all $2N+1$ measurements on equal footing. Here, again, a
global structure that underlies MBQC becomes evident. We have advertised in
the Introduction, and we argue in Section 4.2, that the MBQC computational
output is (one component of) a Wilson line of a
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ gauge field.

##  3 Preparations for the MBQC gauge theory

To set the stage the presentation of the MBQC gauge theory in Section 4, we
introduce two additional ingredients in this section: a group valued label for
the measurement outcomes with respect to the adapted basis (17), and an
algorithm for performing MBQC on a ring.

###  3.1 $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ action and MPS tensor symmetries

We begin by reviewing the relevant representations of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ on the physical Hilbert space and the
transformation laws of the MPS tensor under these symmetries SPT2 ; Schuch .
There are two projective representations of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, which we refer to as $l(g)$ and $r(g)$.
Using the multiplicative mod 2 notation
$g=(\pm,\pm)\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, their action on each block
of physical qubits are:

$\displaystyle l(++)$ $\displaystyle=1\otimes 1,\quad l(+-)=X_{2}\otimes
Z_{1},\quad l(-+)=Z_{2}\otimes 1,\quad l(--)=Z_{2}X_{2}\otimes Z_{1}$ (32)
$\displaystyle r(++)$ $\displaystyle=1\otimes 1,\quad r(+-)=1\otimes
Z_{1},\quad r(-+)=Z_{2}\otimes X_{1},\quad r(--)=Z_{2}\otimes X_{1}Z_{1}$ (33)

We refer to these as the left and right action of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. The product

$u(g):=l(g)r(g)$ (34)

generates a linear representation $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ which
acts by $X$ on even and odd sites:

$u(++)=1\otimes 1,\quad u(+-)=X_{2}\otimes 1,\quad u(-+)=1\otimes X_{1},\quad
u(--)=X_{2}\otimes X_{1}$ (35)

The MPS tensor satisfies a set of equivariant transformation laws under
(32-35). These are illustrated graphically in Figure 5. They relates the
action of $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ on the physical and virtual
degrees of freedom, giving the experimentalist indirect access to correlation
space via manipulations on physical qubits.

Figure 5:  The left panels show the equivariant transformation law of the
cluster MPS tensor under the left $l(g)$ and right $r(g)$ action of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. Composing these gives the transformation
under $u(g)=l(g)r(g)$. More generally, analogous group actions and
transformation laws apply to the fixed point MPS of any SPT phase protected by
an onsite $G$ symmetry Pgarcia ; Schuch .

###  3.2 Group labels for measurement outcomes

We can use the left action $l(\mathbb{Z}_{2}\times\mathbb{Z}_{2})$ to assign a
group label to the measurement outcomes in each block. For simplicity let us
begin with a chain containing only a single block. $l(g)$ acts on the
$O(\alpha_{i})$ eigenstates according to the commutation relations:

$\displaystyle X_{i}\,O(\alpha_{i})$ $\displaystyle=O(-\alpha_{i})\,X_{i}$
$\displaystyle Z_{i}\,O(\alpha_{i})$ $\displaystyle=-O(\alpha_{i})\,Z_{i}$
(36)

In effect, $Z_{i}$ flips the measurement outcomes $s_{i}$. $X_{i}$, on the
other hand, flips the sign of $\alpha_{i}$ but leaves $s_{i}$ invariant.
Because equation (32) features $X_{2}$ only in the combination $X_{2}\otimes
Z_{1}$, we see that $\alpha_{2}$ gets flipped only when $s_{1}=1$. Equation
(17) encodes this fact in the classical processing relation $q_{2}=s_{1}$.

Under the action of this symmetry, the locally adapted basis

$|+_{\alpha_{2}}\rangle\otimes|+_{\alpha_{1}}\rangle\quad{\rm
and}\quad|+_{(-\alpha_{2})}\rangle\otimes|-_{\alpha_{1}}\rangle\quad{\rm
and}\quad|-_{\alpha_{2}}\rangle\otimes|+_{\alpha_{1}}\rangle\quad{\rm
and}\quad|-_{(-\alpha_{2})}\rangle\otimes|-_{\alpha_{1}}\rangle$ (37)

forms an orbit under $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. Therefore, we can
label the basis vectors by group elements using
$\ket{+_{\alpha_{2}}}\otimes\ket{+_{\alpha_{1}}}$ as a reference:

$\displaystyle\ket{g}=l(g)\ket{+_{\alpha_{2}}}\otimes\ket{+_{\alpha_{1}}},\quad{\rm
where}\leavevmode\nobreak\ \leavevmode\nobreak\
g\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ (38)

Thus, the measurement outcomes can be identified with elements of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. We use the same group label to denote
the MPS tensor components $\eqref{defu}$ with respect to the adapted basis
(38):

$\displaystyle A_{g}:=A_{g}((-)^{s_{1}}\alpha_{2},\alpha_{1}),$ (39)

where we will occasionally drop the argument of $A_{g}$ when there is no risk
of confusion.

When we measure the MPS tensor in the state $\ket{g}$, the equivariant
transformation law under $l(g)$ (Figure 5) implies:

$\displaystyle A_{g}=V_{g}\,U=V_{g}\,A_{++}(\alpha_{2},\alpha_{1})$ (40)

This equation, presented graphically in Figure 6, succinctly summarizes (19)
and explains its origin via the MPS symmetries. In Section 4, we interpret
this equation as a discrete analogue of the covariant derivative in continuum
gauge theory.

Figure 6: The MPS symmetry transformation under $l(g)$ can be applied to
decompose each measured MPS tensor into an intended unitary $U$ and a
byproduct $V_{g}$.

####  3.2.1 Incorporating temporal order

##### Adaptation by symmetry

The left action $l(g)$ which defines the states $\ket{g}$ in equation (38)
accounts for the adaptation of measurement basis within a block, but does not
account for the adaptation between different blocks. To incorporate these
global adaptations, we have to change the reference state in (38) to depend on
the previous outcomes. This modification can be achieved using the group
action $u(g)$ SPT2 . To explain this, let us first reformulate the basis
adaptation between different blocks in terms of symmetry operations. This is
illustrated in Figure 7.

Figure 7: Adaptation of measurement basis can by implemented by applying
$u(g)$.

This first equality shows that the effect of obtaining and an unwanted outcome
$g$ at the first block is to produce a byproduct operator in the virtual
Hilbert space, which cannot be accessed directly. However, equipped with the
symmetry operation $u(g)$, our MBQC programmer can cancel out any unwanted
byproduct operator $V_{g}$ in the interior of the chain by applying $u(g)$ to
all yet-to-be-measured qubits. This sends the byproduct $V_{g_{i}}$ to the end
of the chain, where it joins other $V_{g}$’s in forming the byproduct $B$ in
equation (24). The effect of $u(g)$ on unmeasured qubits is captured by
equations (3.2). As $u(g)$ contains only $X$ operators, future measurement
outcomes are undisturbed but even/odd measurement angles are flipped.
Iterating this procedure for all interior $V_{g_{i}}$’s reproduces equation
(23).

##### Group labels for the globally adapted basis

By iterating the adaptation procedure in Figure 7, we find that the adaptation
between different blocks is implemented by the cumulative action of $u(g)$ on
the $j^{\rm th}$ block:

$\displaystyle u(g_{\prec j})$
$\displaystyle=X^{s_{2j-3}+\ldots+s_{3}+s_{1}}\otimes
X^{s_{2j-2}+\ldots+s_{4}+s_{2}}$ $\displaystyle g_{\prec j}$
$\displaystyle:=g_{j-1}\ldots g_{2}\,g_{1}$ (41)

Thus we can incorporate the global adaptation into the definition of $\ket{g}$
in by changing the reference basis to:

$u(g_{\prec
j})\ket{+_{\alpha_{2j}}}\otimes\ket{+_{\alpha_{2j-1}}}=\ket{+_{\big{(}(-)^{q_{2j}-s_{2j-1}}\alpha_{2j}\big{)}}}\otimes\ket{+_{\big{(}(-)^{q_{2j-1}}\alpha_{2j-1}\big{)}}}$
(42)

Relative to this reference state, the measurement basis at the $j$th
block111Explicitly, we can write (44) as
$\displaystyle\ket{g_{j}}=l(g_{j})\ket{+_{\big{(}(-)^{q_{2j}-s_{2j-1}}\alpha_{2j}\big{)}}}\otimes\ket{+_{\big{(}(-)^{q_{2j-1}}\alpha_{2j-1}\big{)}}},\quad{\rm
where}\leavevmode\nobreak\ \leavevmode\nobreak\
g\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ (43) Note how the adaptive parameter
in front of $\alpha_{2j}$ excludes $s_{2j-1}$, so that the action of
$X_{2j}Z_{2j-1}$ in $l(g)$ reproduces equation (17).  is:

$\displaystyle\ket{g_{j}}=l(g_{j})u(g_{\prec
j})\ket{+_{\alpha_{2j}}}\otimes\ket{+_{\alpha_{2j-1}}}$ (44)

Using this notation, the cluster state in the globally adapted basis is simply
given by:

$\operatorname{|1\rangle}=\mathcal{N}\sum_{g\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}\Big{(}\langle{\rm
out}|A_{g_{N}}\ldots A_{g_{2}}A_{g_{1}}|{\rm in}\rangle\Big{)}|g_{N},\ldots
g_{2},g_{1}\rangle$ (45)

Here $A_{g}$ denotes the MPS tensor measured in the globally adapted basis
(44). To unpack this notation a bit, note that using the transformation laws
in Figure 5, we can write:

$\displaystyle A_{g_{j}}=V_{g_{\prec
i}}\left(V_{g_{j}}U_{f_{j}}\right)V_{g_{\prec i}}^{\dagger}$ (46)

##### Adaptation using stabilizers

Consider a single step of the ‘adaptation by symmetry’ procedure shown in
Figure 7. To cancel out the byproduct $V_{g_{i}}$ at the end of the chain, we
should apply $V^{\dagger}_{g_{i}}$ to the uncontracted virtual leg of the last
MPS tensor. It is now useful to view this leg as a final, $(2N+1)^{\rm st}$
qubit of a cluster chain of length $2N+1$. After doing so, the total
transformation that corrects the measurement outcome $g_{i}$ is:

$\displaystyle\mathcal{K}_{i}(g_{i})=\overbrace{\phantom{-}V^{\dagger}_{g_{i}}\phantom{-}}^{(2N+1)^{\rm
st}\leavevmode\nobreak\ {\rm
qubit}}\left(\prod_{j=i+1}^{N}u_{j}(g_{i})\right)l_{i}(g_{i})$ (47)

Notice that this is a product of stabilizers. In particular, for the
nontrivial generators $g_{i}=+-$ and $g_{i}=-+$ we have:

$\displaystyle\mathcal{K}_{i}(+-)$ $\displaystyle=Z_{2N+1}\big{(}X_{2N}\cdots
X_{2i+2}X_{2i}\big{)}Z_{2i-1}$ $\displaystyle\mathcal{K}_{i}(-+)$
$\displaystyle=X_{2N+1}\big{(}X_{2N-1}\cdots X_{2i+1}\big{)}Z_{2i}$ (48)

$\mathcal{K}_{i}(+-)$ is a telescoping product of $K_{j}=Z_{j+1}X_{j}Z_{j-1}$
while $\mathcal{K}_{i}(-+)$ combines $K_{j}$’s with the special stabilizer
$X_{2N+1}Z_{2N}$, which acts at the end of the chain.

##### Equivalent measurement records

A stabilizer transformation manifestly leaves $\operatorname{|1\rangle}$
invariant, but conjugates the operators $O(\alpha_{i})$ as in equation (13).
This in turn implies a nontrivial transformation of the classical processing
data $(q_{i},s_{i})$:

$\displaystyle K_{j}:s_{j-1}$ $\displaystyle\to s_{j-1}+1$ $\displaystyle
s_{j+1}$ $\displaystyle\to s_{j+1}+1$ (49) $\displaystyle q_{j}$
$\displaystyle\to q_{j}+1$

Finally, we observe that each stabilizer $K_{j}$ can be expressed entirely in
terms of projective representations of $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$.
Recalling that the $j^{\rm th}$ block in the MPS description contains the
$(2j-1)^{\rm st}$ and the $(2j)^{\rm th}$ qubit, we see that the stabilizers
can be expressed as:

$\displaystyle K_{2j}$ $\displaystyle=r_{j+1}(+-)l_{j}(+-)$ $\displaystyle
K_{2j-1}$ $\displaystyle=r_{j}(-+)l_{j-1}(-+)$ (50)

###  3.3 MBQC on a ring

In a conventional treatment, MBQC stops at equation (31), having extracted
from a simulation of a general single-qubit gate $U$ one classical bit of
computational output. Yet common lore (technically known as the superdense
coding protocol) implies that a single qubit ought to be equivalent to two
bits of classical data. Working with a chain-like cluster state, we could try
to recover another classical bit of data by varying the initial boundary
condition $|{\rm in}\rangle\to|{\rm in}_{\pm}\rangle$, just like we did with
the final boundary condition $\langle{\rm out}_{\pm}|$. Doing so would probe
the other $\mathbb{Z}_{2}$ component of the advertised
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ Wilson line.

In fact, setting this up on a chain-like cluster state is an awkward exercise.
The same benefit is achieved far more simply by placing the cluster state on a
ring. The extra simplicity afforded by the ring topology mirrors facts from
gauge theory. A closed integral of a gauge field such as $\oint
dx^{\mu}A_{\mu}(x)$, called a Wilson loop, is automatically gauge invariant.
Its line analogue, $\int_{i}^{f}dx^{\mu}A_{\mu}(x)$, called a Wilson line, is
tainted by a gauge dependence at endpoints. For a gauge-invariant object on a
line segment, a Wilson line must be combined with a charge at each end. In our
discussion, the role of these charges is played by the variable boundary
conditions $\langle{\rm out}_{\pm}|$ and $|{\rm in}_{\pm}\rangle$. Indeed,
what achieves gauge-independence in equation (28) is the transformation
$\langle{\rm out}_{\pm}|\to\langle{\rm out}_{\pm}|B$, i.e. $\langle{\rm
out}_{\pm}|$ must be charged under the gauge symmetry.

##### The MBQC protocol on a ring

With respect to the adaptive eigenbasis of $O\big{(}(-)^{q_{j}}\alpha_{j})$,
the wavefunction for the cluster state is given by

$\displaystyle\ket{1}=\mathcal{N}\sum_{g_{j}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}{\rm
Tr}(B_{g_{N}\cdots g_{1}}U)\,\ket{g_{N}}\cdots|g_{2}\rangle|g_{1}\rangle,$
(51)

where $\ket{g}$ are adapted basis elements as defined in (38), and we have
applied equation (23). We now observe that any $SU(2)$ matrix $U$ can be
expanded in the operator basis $V_{g}$ as

$\displaystyle U=\sum_{g}c_{g}V_{g}$ (52)

The coefficients in this expansion are:

$c_{g}={\rm Tr}(V_{g}^{\dagger}U)/{\rm
Tr}(V_{g}^{\dagger}V_{g})=\tfrac{1}{2}{\rm Tr}(V_{g}^{\dagger}U)$ (53)

Since $B$ takes values in $V_{g}=\pm V_{g}^{\dagger}$, the amplitudes ${\rm
Tr}(B\,U)$ determine the coefficients $c_{g}$ up a phase.

The MBQC protocol on a ring returns as computational output the probability
distribution $p_{g}=|c_{g}|^{2}$. As anticipated, the reported data consist of
two classical bits of information. They fully characterize the simulated
unitary $U\in SU(2)$ as an expansion in the operator basis $V_{g}$. In the
end, the output is sensitive only to the overall byproduct operator (24),
which accumulates around the ring.

In the next section, we interpret the byproduct $B$ as a Wilson loop of a
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ gauge field or, equivalently, as a
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ flux. In terms of individual measurement
outcomes $s_{j}$, the computational output is the
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$-valued random variable:

$o=\prod_{j}g_{j}$ (54)

Once more, we emphasize that (54) puts all measurement outcomes on equal
footing.

For future reference, notice that the adaptation of measurement angles on the
ring can again be understood in terms of stabilizer transformations, just as
it could on the chain. In particular, equations (3.2.1), which generate the
globally adapted basis, leave the computational output invariant. One
simplification on the ring is that the corrective procedure involves only
$K_{j}=Z_{j+1}X_{j}Z_{j-1}$; there are no more special stabilizers such as
$X_{2N+1}Z_{2N}$.

##  4 The gauge theory of MBQC

In this section, we establish the gauge theory of MBQC. In Section 4.1, we
describe the MBQC gauge principle, first informally and then formally as a
theorem. This invokes centrally a notion of ‘reference.’ The mathematics of
gauge theory knows of such an object—the section. This correspondence forms
the starting point for reviewing the mathematical underpinning of gauge theory
in Section 4.2. There we establish how the notion of gauge potential applies
to MBQC. With this insight, we re-examine the classical side processing
relations of MBQC in Section 4.4.

###  4.1 Gauge principle

In the circuit interpretation of MBQC, individual quantum gates can only be
implemented up to a byproduct operator in the Pauli group. The byproduct
operator is a priori random but known through the outcome of the measurement
that implemented the gate. That is, if $U_{i}$ is the intended gate, then in
any given run of the MBQC, any of the four gates in the equivalence class

$[U_{i}]=\\{U_{i},X\,U_{i},Y\,U_{i},Z\,U_{i}\\}.$ (55)

may be implemented, depending on the measurement outcome $s_{i}$ on block $i$.
Thus, the procedure of gate simulation is one and the same for the entire
class $[U_{i}]$. The in-advance unpredictable measurement result is picked by
a whim of nature, and it determines the representative.

Likewise, the person operating an MBQC may choose a representative of
$[U_{i}]$ as the operation intended. Different choices of target within the
class $[U_{i}]$ are equivalent, because the implementation procedure can aim
for the class only. Picking the intended operation is therefore a choice of
reference. In the following we denote it as $U_{f_{i}}\in[U_{i}]$, keeping in
mind that there is one choice $f_{i}$ per block $i$; i.e. the total gauge
choice is $\textbf{f}=(f_{1},..,f_{N})$.

The gauge theory formulation of MBQC developed here is based on the following
observation:

MBQC gauge principle. For any given MBQC, the reference f can be changed
without changing the quantum computation. The changes in the reference f are
the MBQC gauge transformations.

The principle says that an external observer of a measurement-based quantum
computation who has access to the measurement record, the measurement bases,
and the computational output, and who furthermore knows what the computational
task is, can not infer which gauge-equivalent reference f is used by the
operator of the MBQC.

####  4.1.1 Formulating the MBQC gauge principle as a theorem

Since the framework of MBQC already exists, the MBQC gauge principle cannot
just be postulated. Rather it arises as a theorem. We establish it here for
measurement-based quantum computations on 1D cluster states, as the simplest
instance. Beyond 1D cluster states, we establish it for the entire
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ SPT phase surrounding the 1D cluster
state in Section 5.6. We conjecture the MBQC gauge principle to hold for
cluster states in arbitrary dimension, and for subsystem SPT phases
surrounding them.

In the review of MBQC in Section 2, and indeed in the exploration of MBQC to
date, the concept of the reference f has not been identified. Implicitly, the
choice $\textbf{f}=0$ has always been assumed. This is not the only admissible
choice of reference, and structural information about MBQC is revealed by
realizing that this is so.

We now formulate the gauge principle at the level of the MPS tensors
representing the cluster state in the MBQC measurement basis. We do this in
two stages. First, we consider individual MPS matrices in isolation, which
conveys the general idea. In a second step, we consider all the MPS matrices
(one per block) in combination, as they are linked through the adaptation of
measurement bases in MBQC. This leads us to the explicit form of the gauge
transformation in Lemma 2 below.

##### Single block level.

Let us focus on a single MPS tensor and denote the physical measurement
outcomes (two bits’ worth) at the $i^{\rm th}$ block as $s_{i}$. Denoting the
reference for block $i$ by $f_{i}$, we consider measurements in the locally
adapted basis $\ket{s_{i}}=l(g_{i})\ket{f_{i}}$ as in eq. (37). Projected onto
this basis, the MPS tensor decomposes as

$A_{s_{i}}=V_{g_{i}}U_{f_{i}},$

with $U_{f_{i}}:=A_{f_{i}}$ the ‘intended gate,’ and $V_{g_{i}}$ the outcome-
dependent Pauli byproduct. We observe that the different components of the MPS
tensor $A$ of the cluster state differ only by Pauli operators. As shown in
Figure 6, this is a special property of the cluster tensor implied by its
transformation law under the symmetry $l(\mathbb{Z}_{2}\times\mathbb{Z}_{2})$.

At this point, we realize that the splitting into an outcome-dependent Pauli
part $V_{g}$ and an outcome-independent unitary $U_{f}$ is not unique. In
particular, we are not required to take
$f_{i}=(+_{\alpha_{2i}}+_{\alpha_{2i-1}})$ as the reference outcome; any
outcome $f$ will do. Under a change of reference

$\displaystyle\quad\ket{\tilde{f}_{i}}:=l(h_{i})\ket{f_{i}},\qquad\tilde{g}_{i}=g_{i}h^{-1},$
(56)

we may write

$\displaystyle\ket{s_{i}}=l(g_{i})\ket{f_{i}}=l(\tilde{g_{i}})\ket{\tilde{f_{i}}},\;\;\forall
i=1,..,N,$ (57)

so the group label for $\ket{s_{i}}$ changes to $\tilde{g}_{i}$. Each
component $A_{s}$ of the MPS tensor $A$ may now be written as

$\displaystyle
A_{s_{i}}=V_{g_{i}}U_{f_{i}}=V_{\tilde{g}_{i}}U_{\tilde{f}_{i}}.$ (58)

For any Pauli operator $V_{h}\in{\cal{P}}_{1}$, the mapping $U_{f}\mapsto
U_{\tilde{f}_{i}}=V_{h}U_{f_{i}}$, $V_{g_{i}}\mapsto
V_{\tilde{g}_{i}}=V_{g_{i}}V_{h}^{\dagger}$ keeps $A_{s_{i}}$ invariant; and
furthermore $V_{h}U_{f_{i}}\in SU(2)$ for all $U_{f_{i}}\in SU(2)$, and
$V_{s_{i}}V_{h}^{\dagger}\in{\cal{P}}_{1}$ for all
$V_{s_{i}}\in{\cal{P}}_{1}$. The splitting of $A_{s_{i}}$ into an outcome-
dependent Pauli part $V_{s_{i}}$ and an outcome-independent general unitary
part $U_{f_{i}}$ is therefore ambiguous. This ambiguity is the origin of the
MBQC gauge principle.

##### Gauge dependence at the multi-block level.

The reason we need to look at multiple MPS matrices combined is the adaptivity
of local measurement basis in MBQC, according to previously obtained
measurement outcomes. This is captured by equation (43), where the outcome
dependence of the measurement basis at block $i$ is implemented by
$u({g_{\prec i}})$. Since $u({g_{\prec i}})$ depends on the group labels
$g_{j},j\leq i$, the basis states $\ket{g_{i}}$ transform nontrivially under a
change of reference on any site $j\leq i$. Likewise the MPS tensor $A_{g_{i}}$
measured in the adapted basis depends on reference choices on sites $j\leq i$.
To make explicit the dependence of MBQC on change of references, let us
introduce reference labels on the globally adapted basis states and the
corresponding MPS tensors :

$\displaystyle\ket{g_{i}}$
$\displaystyle:=\ket{g_{i},f_{i}}=l(g_{i})u({g_{\prec i}})\ket{f_{i}}$
$\displaystyle A_{g_{i}}$ $\displaystyle:=A_{g_{i},f_{i}}=V_{g_{\prec
i}}\left(V_{g_{i}}U_{f_{i}}\right)V_{g_{\prec i}}^{\dagger}$ (59)

Similarly, classical side processing data depend on the reference via their
explicit dependence on group labels:

$\displaystyle(q_{2i},q_{2i-1})$ $\displaystyle=g_{\prec i}\qquad\textrm{(as
element of $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$)}$ (60) $\displaystyle o$
$\displaystyle=\prod_{i}g_{i}$ (61)

If we define

$\displaystyle A_{\mathbf{g},\mathbf{f}}=\prod_{i}A_{g_{i},f_{i}},\quad
V_{o}=\prod_{i}V_{g_{i}},\quad U_{\mathbf{f}}=\prod_{i}U_{f_{i}},$ (62)

the total MPS wavefunction for the cluster chain is given by

$\displaystyle A_{\mathbf{g},\mathbf{f}}=V_{o}U_{\mathbf{f}}$ (63)

where we have used byproduct propagation to obtain the RHS as in equation
(23).

Equations (4.1.1-63) summarize all the relevant formulas of MBQC. Inspection
of these relations motivates a further constraint to impose on the change of
reference. From the circuit model perspective, $U_{\textbf{f}}$ is the unitary
that MBQC realizes and to which the classical output of MBQC refers; i.e. the
MBQC output reveals properties of $U_{\textbf{f}}$. The change of reference
should not change that interpretation. Thus, while the locally implemented
pieces $U_{f_{i}}$ may change under the gauge transformation, their cumulative
product $U_{\textbf{f}}$ should not.

We thus arrive at the following definition for the notion of MBQC gauge
transformations.

######  Definition 1.

An MBQC gauge transformation is a change of reference
$\ket{\textbf{f}}\mapsto\ket{\tilde{\textbf{f}}}$ and accompanying change of
the group labels for the byproducts $\textbf{g}=(g_{1},..,g_{N})$ such that
(i) all MPS matrices $A_{g_{i},f_{i}}$ are preserved, up to possible global
phases, and (ii) the total MBQC-implemented unitary is preserved,

$U_{\textbf{f}}\mapsto U_{\tilde{\textbf{f}}}=U_{\textbf{f}}.$ (64)

In a different terminology, the gauge transformations defined above are called
proper gauge transformations whereas changes of reference that satisfy
condition (i) but do not satisfy (ii) are called ‘large’ gauge
transformations.

Eq. (63), in combination with Definition 1, leads to the following
observation:

######  Lemma 1.

The cumulative MPS matrix $A_{\textbf{g},\textbf{f}}$, the target unitary
$U_{\textbf{f}}$ and the cumulative byproduct $V_{o}$ are, up to possible
global phases, invariant under the MBQC gauge transformations.

Proof of Lemma 1. $A_{\textbf{g},\textbf{f}}$ and $U_{\textbf{f}}$ are
invariant by Definition 1. Therefore, by Eq. (63), the cumulative byproduct
$V_{o}$ is also invariant. $\Box$

We now provide an explicit construction of the gauge transformations according
to Definition 1. We have the following result:

######  Lemma 2.

For all $i=1,..,N-1$ and all $h\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, the
transformations $h^{(i)}$ defined by

$\begin{array}[]{rclcrcl}U_{f_{i}}&\mapsto&U_{\tilde{f}_{i}}=V_{h}U_{f_{i}},&&V_{g_{i}}&\mapsto&V_{\tilde{g}_{i}}=V_{g_{i}}V_{h}^{\dagger},\\\
U_{f_{i+1}}&\mapsto&U_{\tilde{f}_{i+1}}=U_{f_{i+1}}V_{h}^{\dagger},&&V_{g_{i+1}}&\mapsto&V_{\tilde{g}_{i+1}}=V_{g_{i+1}}V_{h}.\end{array}$
(65)

are MBQC gauge transformations.

The gauge transformations Eq. (65), together with the equivariant
transformations $l(\cdot)$ and $r(\cdot)$ of the cluster state MPS tensor
displayed in Figure 5, imply the following transformation on the reference
$\ket{\textbf{f}}$:

$h^{(i)}:\;\;\ket{f_{i}}\mapsto l(h)\ket{f_{i}},\;\ket{f_{i+1}}\mapsto
r(h)\ket{f_{i+1}},$ (66)

with all other components of f unchanged. The corresponding change in group
labels is:

$\displaystyle\tilde{g}_{i}=g_{i}h^{-1},\qquad\tilde{g}_{i+1}=hg_{i+1}.$ (67)

Proof of Lemma 2. We have to check that the transformations according to eq.
(65) satisfy Properties (i) and (ii) of Definition 1.

Property (i). The gauge transformation (65), for any fixed $i$, affects non-
trivially only blocks $i$ and $i+1$. Checking the corresponding MPS matrices,
we find:

$\begin{array}[]{rcl}A_{g_{i},f_{i}}&=&V_{g_{\prec
i}}\left(V_{g_{i}}U_{f_{i}}\right)V_{g_{\prec i}}^{\dagger}\\\
&\mapsto&V_{\tilde{g}_{\prec
i}}\left(V_{\tilde{g}_{i}}U_{\tilde{f}_{i}}\right)V_{\tilde{g}_{\prec
i}}^{\dagger}\\\ &\propto&V_{g_{\prec
i}}\left(V_{g_{i}}V_{h}^{\dagger}V_{h}U_{f_{i}}\right)V_{g_{\prec
i}}^{\dagger}\\\ &=&V_{g_{\prec i}}\left(V_{g_{i}}U_{f_{i}}\right)V_{g_{\prec
i}}^{\dagger}\\\ &=&A_{g_{i},f_{i}},\end{array}$

and

$\begin{array}[]{rcl}A_{g_{i+1},f_{i+1}}&=&V_{g_{\prec
i+1}}\left(V_{g_{i+1}}U_{f_{i+1}}\right)V_{g_{\prec{i+1}}}^{\dagger}\\\
&\mapsto&V_{\tilde{g}_{\prec
i+1}}\left(V_{\tilde{g}_{i+1}}U_{\tilde{f}_{i+1}}\right)V_{\tilde{g}_{\prec{i+1}}}^{\dagger}\\\
&\propto&V_{g_{\prec
i+1}}V_{h}^{\dagger}\left(V_{g_{i+1}}V_{h}U_{f_{i+1}}V_{h}^{\dagger}\right)V_{h}V_{g_{\prec{i+1}}}^{\dagger}\\\
&\propto&V_{g_{\prec
i+1}}\left(V_{g_{i+1}}U_{f_{i+1}}\right)V_{g_{\prec{i+1}}}^{\dagger}\\\
&=&A_{g_{i+1},f_{i+1}}.\end{array}$

Thus, up to possible global phases, the MPS matrices are invariant. Property
(i) is satisfied.

Property (ii). Using (65), we have:

$\begin{array}[]{rcl}U_{\textbf{f}}&=&U_{f_{N}}..U_{f_{i+2}}U_{f_{i+1}}U_{f_{i}}U_{f_{i-1}}..U_{f_{1}}\\\
&\mapsto&U_{f_{N}}..U_{f_{i+2}}\left(U_{f_{i+1}}V_{h}^{\dagger}\right)\left(V_{h}U_{f_{i}}\right)U_{f_{i-1}}..U_{f_{1}}\\\
&=&U_{f_{N}}..U_{f_{i+2}}U_{f_{i+1}}U_{f_{i}}U_{f_{i-1}}..U_{f_{1}}\\\
&=&U_{\textbf{f}}.\end{array}$

Thus, Property (ii) holds as well. $\Box$

We can now state the MBQC gauge principle as a theorem:

######  Theorem 1 (MBQC gauge principle).

For any given MBQC on 1D cluster states, the measurement bases
$\\{\ket{g_{i},f_{i}}\\}$ chosen as a function of prior measurement record
${g_{\prec i}}$, the output $o$ given the measurement record g, and the
probability distribution of the computational output $o$,
$p(o)=|\text{Tr}(U_{\textbf{f}}V_{o})|^{2}$, are invariant under gauge
transformations (65-67).

This has the following consequence: An external observer, who tracks an MBQC
computation and has access to all measurement settings, the measurement record
and the computational output, cannot infer which reference f is used in the
internal classical side processing.

Proof of Theorem 1. (i) The local measurement bases: Under the gauge
transformation $h^{(i)}$, the local measurement basis
$\\{|g_{i+1},f_{i+1}\rangle,g_{i+1}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}\\}$
at block $i+1$ transforms as:

$\displaystyle l(g_{i+1})u({g_{\prec i+1}})\ket{f_{i+1}}$ $\displaystyle\to
l(\tilde{g}_{i+1})u({\tilde{g}_{\prec i+1}})\ket{\tilde{f}_{i+1}}$
$\displaystyle=l(hg_{i+1})u({g_{\prec i+1}})u(h)r(h)\ket{f_{i+1}}$
$\displaystyle=l(g_{i+1}h)u({g_{\prec i+1}})l(h)\ket{f_{i+1}}$
$\displaystyle\propto l(g_{i+1}h)l(h)u({g_{\prec i+1}})\ket{f_{i+1}}$
$\displaystyle=l(g_{i+1})u({g_{\prec i+1}})\ket{f_{i+1}}$ (68)

In the first line, we have used the gauge transformations (66-67). In the
third line we have used $u(h)=l(h)r(h)$, cf. eq. (34), and in the fourth we
commuted $u({g_{\prec i+1}})$, and $l(h)$ at the cost of an irrelevant sign.
We thus find that the measurement basis for block $i+1$ is indeed invariant
under the gauge transformations $h^{(i)}$.

On the $i^{\rm th}$ block, we have:

$\displaystyle l(g_{i})u(g_{\prec i})\ket{f_{i}}$ $\displaystyle\to
l(\tilde{g}_{i})u({\tilde{g}_{\prec i}})\ket{\tilde{f}_{i}}$
$\displaystyle=l(g_{i}h)u(g_{\prec i})l(h)\ket{f_{i}}$ $\displaystyle\propto
l(g_{i}h)l(h)u(g_{\prec i})\ket{f_{i}}$ $\displaystyle\propto
l(g_{i})u(g_{\prec i})\ket{f_{i}}$ (69)

On all other blocks, the gauge transformation $h^{(i)}$ acts trivially. Thus,
all local measurement bases are gauge-invariant.

(ii) Single-shot computational output $o$: A gauge transformation $h^{(i)}$
transforms the computational output as follows:

$\begin{array}[]{rcl}o&=&g_{1}..g_{N}\\\
&\mapsto&g_{1}..g_{i-1}(g_{i}h^{-1})(hg_{i+1})g_{i+2}..g_{N}\\\
&=&g_{1}..g_{N}\\\ &=&o.\end{array}$

Thus, the output $o$ is invariant under $h^{(i)}$, for any
$h\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, for any $i$.

(iii) Output statistics: Since $o$ is gauge invariant per item (ii), so is
$V_{o}$, up to a possible phase. $U_{\textbf{f}}$ is invariant by assumption;
cf. eq. (64). Therefore $p(o)=|\text{Tr}(U_{\textbf{f}}V_{o})|^{2}$ is gauge-
invariant. $\Box$

###  4.2 Mathematical underpinning of gauge theory

We now formalize the objects encountered in Section 4.1. Our first goal is to
review the concept of ‘section,’ and, for the application to MBQC, identify it
with the reference f.

####  4.2.1 Fiber bundles, sections, and gauge transformations

Gauge theory is a theory of fiber bundles. Accordingly, our next step is to
present a (discrete) fiber bundle, which describes the geometry of an MBQC
computation. We begin with a lightning review of fiber bundles.

A fiber bundle is a family of identical spaces (fibers) $F_{b}$, which are
labeled by elements of another topological space $\mathcal{B}\ni b$, called
the base space. The union of all fibers is called ‘total space’ and denoted
$\mathcal{E}$:

$\mathcal{E}=\bigcup_{b\in\mathcal{B}}F_{b}$ (70)

Locally, any fiber bundle looks like the direct product $F\times\mathcal{B}$.
Globally, however, the direct product structure breaks down because the
different fibers can be arranged over $\mathcal{B}$ in a nontrivial way.
Common examples of nontrivial bundles include the Möbius strip, in which the
interval $[0,1]=:F_{b}$ gets reflected as $b$ goes around the circle
$S^{1}=:\mathcal{B}$, or the tangent spaces $T_{b}=:F_{b}$ over a manifold
$\mathcal{M}=:\mathcal{B}$ if the manifold is curved.

It is useful to distinguish two types of bundles. First, a principal fiber
bundle $\mathcal{G}$, also called a gauge bundle, has as fibers copies of a
symmetry group $G$. Given a gauge bundle and a choice of representation $R$,
we can define an associated vector bundle $\mathcal{V}_{R}$ whose fibers are
the vector spaces on which the representation $R$ acts. In the conventional
setting of continuum gauge theory, $\mathcal{V}_{R}$ corresponds to a choice
of matter field transforming in the representation $R$. The gauge field then
couples to this matter field via covariant derivatives in the chosen
representation.

##### The MBQC gauge bundle

The structure of the MBQC gauge bundle is manifest in the MPS description of
the resource state. The base space $\mathcal{B}$ is the one-dimensional
lattice where the physical qubits live. In the cluster state, due to the
symmetries of the MPS tensor, we will identify a single point
$j\in\mathcal{B}$ with a block of two physical qubits.

The fiber above each block is the group $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$,
which permutes the four possible measurement outcomes. Equivalently, each
fiber of the MBQC gauge bundle consists of the measurement outcomes
themselves. We anticipated this in equation (38) when we labeled measurement
outcomes with group elements.

As emphasized above that equation, a labeling of a fiber with group elements
is not unique since we can always act with the group on itself and get a new
labeling. To coordinatize a fiber with group elements, we must therefore
choose a so-called section222In a general fiber bundle there may not exist a
global section, but this subtlety does not arise in this paper.: an outcome in
every fiber, which is labeled with the identity element of the group. We did
that in equation (38) by choosing the outcome
$(s_{2j},s_{2j-1})=(0,0)$—equivalently, the basis vector
$|+_{\alpha_{2j}}\rangle\otimes|+_{\alpha_{2j-1}}\rangle$—as a reference. Note
that, from the MBQC programmer’s point of view, the identification of the
state $|+_{\alpha_{2j}}\rangle\otimes|+_{\alpha_{2j-1}}\rangle$ with the group
element $++\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ is an arbitrary choice.
Other measurement outcomes can be identified with the identity element equally
well. To maintain the visual correspondence between measured states
$|\pm_{(\cdots)}\rangle$ and group elements, the programmer can always modify
the reference measurement angles, for example:

$|-_{(-\alpha_{2})}\rangle\otimes|-_{\alpha_{1}}\rangle=|+_{(\pi-\alpha_{2})}\rangle\otimes|+_{(\pi+\alpha_{1})}\rangle$
(71)

More formally, a section is one choice of element in each fiber:

$f\\!:\leavevmode\nobreak\ \mathcal{B}\to\mathcal{E}\qquad\textrm{such
that}\leavevmode\nobreak\ \leavevmode\nobreak\ j\to f_{j}\in F_{j}$ (72)

In MBQC, we identify the set of reference outcomes $\mathbb{f}$ with a section
$f$ of the gauge bundle.

A gauge transformation $h$ is a map that relates two sections $f_{j}$ and
$\tilde{f}_{j}$:

$h\\!:\leavevmode\nobreak\ \mathcal{B}\to G\qquad\textrm{such
that}\leavevmode\nobreak\ \leavevmode\nobreak\ j\to h_{j}\quad{\rm
with}\quad\tilde{f}_{j}=h_{j}f_{j}$ (73)

This is depicted in the right of Figure 8.

Note the subtle difference between a section and a gauge transformation. The
former maps $\mathcal{B}$ to the fibers while the latter maps $\mathcal{B}$
directly to the group. This is because $h_{j}=\tilde{f}_{j}{f}^{-1}_{j}$ is a
relative construct, from which the ambiguity in labeling fibers cancels out.

##### The associated bundle

The associated bundle $\mathcal{V}_{R}$ for MBQC has the same base space as
the gauge bundle, but the fibers are replaced by the virtual Hilbert space,
which transforms under the projective representation of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. More specifically, we define $F_{j}$ on
the $j^{\rm th}$ block to be the Hilbert space on the left virtual edge of the
MPS tensor. A gauge transformation $h_{j}$ acts on the associated bundle via
the projective representation $V_{h_{j}}$, which rotates each fiber of
$\mathcal{V}_{R}$. The virtual qubit in the circuit simulation thus plays the
role of the ‘matter field’ in the analogy with ordinary field theory.

Figure 8: The MBQC gauge bundle is defined by the action of the
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ transformations $l_{i}(g)$ on the
measurement outcomes. The orbits form the fiber $\\{f_{i}\\}$ over a block,
which is just a copy of $Z_{2}\times Z_{2}$. The purple and blue dots describe
two sections of this bundle, corresponding to two sets of measurement
outcomes. The sections are related by a gauge transformation, denoted by
$h_{i}$. Figure 9: The fibers $F_{i}=\mathcal{H}^{i}_{c}$ of the vector bundle
$\mathcal{V}$ are copies of the virtual Hilbert space where the virtual qubit
lives.

####  4.2.2 Parallel transport

A key concept in the study of fiber bundles is parallel transport. It sets a
convention for what it means for a trajectory in the total space $\mathcal{E}$
to travel entirely in a ‘horizontal direction,’ with no component of motion in
the fiber. (In this nomenclature, motion over one point $j$ in the base
space—that is entirely within $F_{j}$—is ‘vertical.’) Without a definition of
parallel transport there is no canonical way of comparing fibers over
different base points. Parallel transport relates different fibers to one
another in a definite, albeit non-canonical, way. It is specified by a linear
map between adjacent fibers $F_{j-1}$ and $F_{j}$. In MBQC, parallel transport
is generated by the MPS tensor
$A_{s_{j}}=A_{s_{j}}\big{(}(-)^{q_{2j}}\alpha_{2j},(-)^{q_{2j-1}}\alpha_{2j-1}\big{)}$
in the adapted basis:

$\displaystyle A_{s_{j}}:F_{j-1}\to F_{j},$ (74)

We thus identify parallel transport on the bundle $\mathcal{V}_{R}$ with the
quantum teleportation of the virtual qubit. In MBQC, parallel transport is
induced by measurements. Prior to a measurement, the definition of parallel
transport is fluctuating; we called this circumstance a fluctuating circuit in
Section 2.1. Measurements in the MBQC basis force parallel transport to take
on a definite, classical form.

##### Gauge connection

The generator of local parallel transport $A_{s}$ is a gauge invariant linear
map describing a horizontal motion between neighboring fibers. It is
independent of the group label assigned to the measurement outcome $s$. On the
other hand, the gauge connection describes a gauge dependent motion along
$F_{i}$ that depends on a choice of section. To determine the MBQC gauge
connection, recall that a choice of section provides a group label for the
measurement outcome $s$ according to

$\displaystyle s=gf=\tilde{g}\tilde{f}$ (75)

We think of $s$ as an element of the fiber $F_{j}$ in the gauge bundle, which
has coordinates $g$ and $\tilde{g}$ relative to two reference sections $f$ and
$\tilde{f}$. Using the relation (40), we can write the parallel transport as

$\displaystyle A_{s}=V_{g}U_{f}=V_{\tilde{g}}U_{\tilde{f}},$ (76)

where we used the notation $U_{f}=A_{f}$ to emphasize that $A_{f}$ is the
(desired) local circuit simulation.

Equation (76) shows that a gauge choice decomposes the parallel transport
operator into two parts. The first is a ‘naïve motion’ $U_{f}$, which can
contain both horizontal and vertical motion. In the total space $\mathcal{E}$,
this naïve motion simply follows the section $f$. The second part, $V_{g}$, is
the gauge connection. It is a correction term, whose action is entirely
vertical—that is, it maps the fiber to itself. Its job is ensure that the
combination $V_{g}U_{f}$ generates parallel transport. Note that, when viewed
in isolation, both $V_{g}$ and $U_{f}$ are ambiguous up to multiplication by
$V_{h}$ for arbitrary $h$ in the gauge group; only their product has invariant
meaning. This is the gauge symmetry of MBQC: the freedom to reset the section
$f$ and the corresponding ambiguity in the byproduct $V_{g}$.

##### Parallel transport in the globally adapted basis

The MPS tensor $A_{s}$ in equation (76) describes the evolution a virtual
qubit $\ket{\psi}$ in the locally adapted basis defined in (37). Measurements
in that basis produce the virtual evolution

$\displaystyle\ket{\psi}\to\cdots V_{g_{i}}U_{f_{i}}\cdots
V_{g_{1}}U_{f_{1}}\ket{\psi}$ (77)

However, MBQC involves measurement in a globally adapted basis, in which the
MPS tensor $A_{s_{i}}$ is conjugated by the byproduct operator $V_{g\prec i}$
as in (46). Naïvely, the virtual evolution is more complicated, but if
propagate the byproducts as described in Section 2, we again get a simple form
of the virtual evolution:

$\displaystyle\ket{\psi}\to\big{(}\cdots
V_{g_{2}}V_{g_{1}}\big{)}\big{(}\cdots U_{f_{2}}U_{f_{1}}\big{)}\ket{\psi}$
(78)

Thus, after the $i^{\rm th}$ measurement, we can interpret
$\big{(}\prod_{j\leq i}V_{j}\big{)}\big{(}\prod_{j\leq i}U_{f_{j}}\big{)}$ as
total parallel transport, expressed as a combination of the ‘naïve’ motion
$\big{(}\prod_{j\leq i}U_{f_{j}}\big{)}$ and a correction $\big{(}\prod_{j\leq
i}V_{j}\big{)}$.

##### Gauge connection on the principal bundle

We can also define a gauge connection directly on the gauge bundle
$\mathcal{G}$. Given a history of measurement outcomes

$\displaystyle s_{j}=g_{j}f_{j}\qquad j=1,\cdots N$ (79)

and a gauge choice $f$, we define the connection on the gauge bundle to be
$\textbf{g}=(g_{1},\cdots,g_{N})$. Thus, the measurement record, labelled by a
set of elements of $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, is the MBQC gauge
field! This is because the connection on the vector bundle is $V_{g_{j}}$ and
the two bundles are related to one another by the representation map.
Furthermore, we can define the gauge potential at block $j$ as the pair of
binary numbers $\vec{a}_{j}=(a_{j:1},a_{j:2})$ satisfying:

$\displaystyle g_{j}=\big{(}(-1)^{a_{j:1}},(-1)^{a_{j:2}}\big{)}$ (80)

Thus, the gauge potential is just a $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$
variable like $g_{j}$, written in additive notation.

###  4.3 Holonomies and fluxes

Observables in gauge theory are fluxes through closed loops. In mathematical
terms, a (classical) flux corresponds to a property of a fiber bundle called
holonomy. It is computed by the product of parallel transport generators
around a given loop:

${\rm flux}\leftrightarrow{\rm holonomy}=\prod_{\rm loop}\textrm{(parallel
transport)}$ (81)

This formula is illustrated in Figure 10. As reviewed in the previous
subsection, parallel transport is a map from one fiber to another: $F_{j}\to
F_{j+1}$. A composition of parallel transport around a closed loop therefore
gives a transformation of the initial fiber to itself:

${\rm holonomy}:F_{1}\to F_{1}$ (82)

Geometrically, this transformation tells us whether (and how) a fiber bundle
is ‘twisted.’ In the present context, where fibers are labeled by group
elements, we expect four distinct holonomies that send $|g\rangle\in F_{1}$ to
$|hg\rangle\in F_{1}$, where $h\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$.
Physically, the ‘twisting’ of the fiber bundle is interpreted as a classical
value of flux.

Figure 10: A holonomy $H_{\gamma}$ on the principal fiber bundle is defined by
lifting a curve $\gamma(t)$ from the base space to the total space. Given a
section, this curve is a choice of group element $g_{i}$ at each fiber
describing local parallel transport, which combines into a holonomy
$o=\prod_{i}g_{i}$.

##### Physical flux

Substituting the definition of parallel transport in (74) and equation (78),
we get:

${\rm
flux}=\prod_{j=1}^{N}A_{g_{j},f_{j}}=\left(\prod_{j=1}^{N}V_{g_{j}}\right)\left(\prod_{j=1}^{N}U_{f_{j}}\right)=V_{o}U_{\rm
total}$ (83)

This is the flux after a complete set of MBQC measurements, which force the
fluctuating parallel transport operators to take on define values
$A_{g_{j},f_{j}}$.

Equation (83) does not correspond to any one element $h$ of
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, so how to interpret this equation? We
view it as a quantum mechanical superposition of fluxes. To do so, expand

$U_{\rm total}=\sum_{g\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}c_{g}V_{g}$ (84)

in the $V_{g}$, which form a complete basis in the space of $SU(2)$ matrices.
Then equation (83) becomes:

${\rm
flux}=\sum_{g\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}c_{g}\,b(o,g)V_{o\cdot g},$
(85)

where the projective phases $b(o,g)$ are defined by
$V_{o}V_{g}=b(o,g)V_{o\cdot g}$ (These are never observed in MBQC). The right
hand side is a linear combination of the four classically allowed holonomies
$o\cdot g\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$.

Since classical fluxes correspond to differently twisted bundles, states of a
quantum gauge theory naturally describe superpositions of distinct bundles.

Figure 11: This figure illustrates the superposition of vector bundles
$\mathcal{V}_{g}$ with holonomy $V_{g}$. In contrast with the gauge bundle
where the fibers are copies of the gauge group, the fibers of
$\mathcal{V}_{g}$ are virtual Hilbert spaces $\mathbb{C}^{2}$ where the
virtual qubit lives. On the right, each term in the sum describes the parallel
transport of an element $p_{0}\in\mathbb{C}^{2}$ around a closed loop, which
transforms $p_{0}$ by a holonomy matrix $V_{g}$. MBQC superposes such
holonomies to obtain a general $SU(2)$ transformation $U$, which gives the
simulated unitary.

A special case of (85) occurs in an MBQC simulation of $U_{\rm total}=1$ or a
Pauli matrix. In this circumstance the superposition (85) involves a single
term with $o\cdot g=++\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, so the outcome
$o$ of MBQC is deterministic. We can understand such deterministic MBQC as
measuring the trivial flux of the initial resource state $|1\rangle$. Non-
deterministic MBQC, in contrast, projects the resource state onto
superpositions of fluxes, which are defined in equation (85). We examine those
states, and explain MBQC as a flux measurement in a non-diagonal basis, in
Section 5.4.

##### MBQC flux

Consider one MBQC run, during which the resource state gets projected onto a
superposition of fluxes defined in equation (85). The MBQC technician records
the computational outcome

$o=g_{N}\ldots g_{2}g_{1}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ (86)

where $V_{o}=B$ from equation (23). From the technician’s perspective, it is
tedious and pedantic to say that she has projected the resource state onto a
superposition of flux states; identifying flux with $o$ directly is equally
informative but far simpler.

In the remainder of the paper, we refer to
$o\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ as ‘MBQC flux.’ Notice that MBQC
fluxes could be made consistent with equation (81) if we identified ‘MBQC
parallel transport’ with the individual measurement outcomes
$g_{j}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$:

$\textrm{`MBQC parallel transport'}=g_{j}\leavevmode\nobreak\ \textrm{measured
on the $j^{\rm th}$ block}$ (87)

As we presently explain, this definition depends on subjective intentions of
the MBQC technician. This is why it is useful to distinguish MBQC flux and
‘MBQC parallel transport’ from their physical counterparts: only the latter
are free of teleological considerations.

##### MBQC flux versus physical flux

Consider a run of deterministic MBQC, in which every qubit is measured in the
$X$-basis. Two quantum programmers, Alice and Bob, observe the run and jot
down all measurement outcomes. Whereas Alice intends to use this MBQC run as a
simulation of $U_{\rm total}^{\rm Alice}=1=V_{++}$, Bob intends to simulate
$U_{\rm total}^{\rm Bob}=X=V_{+-}$. We observed previously that the outcome
$o$ of deterministic MBQC satisfies $o\cdot g=++$, where the simulated unitary
is $U_{\rm total}=V_{g}$. Therefore, Alice reports MBQC flux $o^{\rm
Alice}=++$ whereas Bob reports MBQC flux $o^{\rm Bob}=+-$. Their MBQC fluxes
differ even though they are describing the same physical experiment.

Physical fluxes defined by equation (83) do not suffer from this teleological
ambivalence. On the other hand, it is the MBQC fluxes that constitute the
computational output $o$. With a fixed choice of the simulated $U_{\rm
total}$, going from the physical fluxes to MBQC fluxes is a simple change of
basis described by equation (85). We can already see—and we will explain in
more detail in Section 5.4—that MBQC proceeds by projecting states of definite
physical flux (such as the cluster state) onto states of definite MBQC flux.

##### Analogy

It is useful to compare the definitions of flux (both physical and MBQC) with
more familiar gauge theories such as electromagnetism. In $U(1)$ gauge theory,
the Aharonov-Bohm effect relates the flux of a magnetic field through a loop
to the additional phase incurred by a charged particle that circles that loop:

${\rm flux}\,\,\,\propto\,\,\,\exp\oint D_{\mu}dx^{\mu}=\exp\oint
A_{\mu}dx^{\mu}\in U(1)$ (88)

Written in this form, the flux is also known as a Wilson loop. The object
$D_{\mu}=\partial_{\mu}+A_{\mu}$ is the covariant derivative, which generates
parallel transport in the underlying $U(1)$ fiber bundle. In more technical
language, $D_{\mu}$ is the Ehrenfest connection—the generator of parallel
transport acting in the total space $\mathcal{E}$. It is the action of
$D_{\mu}$, which is pictured in red in Figure 10.

The object $A_{\mu}$ is what physicists call the gauge potential. As
emphasized before, it is defined relative to a section $f$, which is a map
from the base to the fibers. The equality of the two integrals in (88) follows
from the assumed single-valuedness of $f$. The two integrands differ by pure
coordinate transport $\partial_{\mu}=D_{\mu}-A_{\mu}$ in the base, which lifts
in total space to following the section $f$. When the section is single-
valued, a closed loop in the base lifts to a closed loop in total space and
explicitly including $\partial_{\mu}$ in (88) becomes immaterial.

The situation is different when we contemplate a choice of ‘section,’ which is
not single-valued. In that circumstance, a closed loop in the base lifts to a
non-trivial transformation on the fiber

$U_{\rm section}\\!:f_{\rm initial}\to f_{\rm final}$ (89)

and equation (88) becomes modified:

${\rm flux}\,\,\,\propto\,\,\,\exp\oint D_{\mu}dx^{\mu}=\exp\oint
A_{\mu}dx^{\mu}\times U_{\rm section}\in U(1)$ (90)

This relation is directly analogous to equation (83), which relates the
physical and MBQC flux. Parallel transport defined in (74) plays the role of
the covariant derivative $D_{\mu}$ in continuum gauge theory. The role of the
gauge potential333When the gauge group is continuous—like $U(1)$—the gauge
potential is valued in the Lie algebra and its exponentials are group
elements. When the gauge group is discrete, we work directly with group
elements. Therefore, it is more accurate to say that measurement outcomes
$g_{j}$ are analogous to path-ordered exponentials of $A_{\mu}dx^{\mu}$, i.e.
Wilson lines of the continuum theory. is played by the measurement outcomes
$g_{j}$ (in the gauge bundle $\mathcal{G}$) or by their representations
matrices $V_{g_{j}}$ (in the associated bundle). The physical flux on the left
hand side of (83) and the MBQC flux $o$ are off by the simulated $U_{\rm
total}$. By comparing (90) with (83), we see that $U_{\rm total}$ is analogous
to $U_{\rm section}$ in electromagnetism. The analogy is imperfect because
$U_{\rm total}$ in MBQC is not associated with one section of the
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ bundle.

###  4.4 Elements of computation

####  4.4.1 Output

We have the following result:

######  Theorem 2.

For MBQC on 1D cluster states, in all gauges reachable from $\textbf{f}=0$ by
a gauge transformation, the MBQC output $o$ equals the holonomy $g$ of the
MBQC gauge potential g.

Proof of Theorem 2. The classical side processing relation (61) provides
$o=g$, by Theorem 1 valid for all gauges f equivalent to 0 up to gauge
transformation. Then, $g$ has been shown to be the holonomy of the gauge
potential g in Section 4.2.2. $\Box$

The classical side processing relations are, from the phenomenological
perspective, an essential ingredient of MBQCs. Even the simplest MBQC—the
three-qubit GHZ-MBQC of Anders and Browne AB , repurposing Mermin’s star Merm
—has them. Their presence is a direct consequence of the fundamental
randomness in quantum measurement. In MBQC, such randomness must be prevented
from affecting the logical processing, and the classical side processing
relations ensure that. Theorem 2 places the classical side processing relation
Eq. (61) in the general theoretical framework of gauge theory.

####  4.4.2 Measurement basis from gauge fixing

In Section 4.1, we explained that changing the reference f—a choice of one
intended gate $U_{i}$ from the set $[U_{i}]$ at every $i$—does not affect an
MBQC computation. For this reason, we identified the reference f with the
concept of a section or—in common physics parlance—with the choice of gauge.
The reference f is physically undetectable.

As is common in gauge theory, we can exploit the flexibility in choosing f for
our convenience by imposing suitable gauge-fixing conditions. A particularly
convenient gauge-fixing condition reads:

$V_{g_{i}}=1\qquad\textrm{for all}\leavevmode\nobreak\ \leavevmode\nobreak\
i<N$ (91)

Note that the condition is imposed on all blocks except the final one. We
cannot impose $V_{g}=1$ on all blocks because, by equation (81), this would
incorrectly reset the physical flux of the resource state.444In the continuum,
this corresponds to the fact that the gauge potential can always be locally
set to zero, but a nonvanishing flux represents an obstruction to achieving
such a gauge globally. Gauge condition (91) has no independent meaning before
a run of MBQC is executed. The choice of reference that is consistent with
(91) depends on the registered measurement outcomes. More explicitly, up to
(but excluding) the final block, the condition demands that the section value
$f_{i}$ on the $i^{\rm th}$ block be simply equal to the outcome of the
$i^{\rm th}$ measurement. Equating the reference with the measurement outcome
locally obviates the need for a byproduct, thereby setting $V_{g_{i}}=1$.

On the final block, the reference can be chosen so that:

$\prod_{i}U_{f_{i}}=U_{\rm total}$ (92)

We have seen in equation (23) that a complete run of MBQC induces a
transformation in virtual space, which equals $BU_{\rm total}$, where $B$ is
the byproduct operator. A gauge fixing choice, which best accords with the
MBQC interpretation, will pick a section which—if measured—ends up simulating
$U_{\rm total}$ with no need for further corrections.

##### The adaptive gauge selects the measurement basis

An obvious feature of the adaptive gauge is that the measurement basis
executed in an MBQC run must always include the section value $f_{i}$, for all
$i$. After all, on each block $i<N$, the section $f_{i}$ equals the measured
basis state. On the final block, the measurement basis certainly contains the
state, which induces $U_{\rm total}$ as the transformation on virtual space.
That state completes the choice of the adaptive gauge according to equation
(92).

In summary, the fiber element $f_{i}$ that is selected by the adaptive gauge-
fixing condition stands for a state, which must necessarily be part of the
measurement basis on block $i$. The full measurement basis over block $i$ is
the $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ multiplet, which is generated from
$|f_{i}\rangle$ by the projective representation $l(g)$. We saw this
measurement basis multiplet explicitly in equation (43). The section
$|f_{i}\rangle$, from which the multiplet is generated, is the reference state
(42).

We emphasize that identifying a section $f_{i}$ with the measurement record on
$i<N$—and with the adaptive measurement basis everywhere—is a gauge choice,
not an identity. Other gauge choices are viable, and indeed necessary, for
defining MBQC. When planning an MBQC calculation, a quantum programmer must
select a set of reference angles $\alpha_{i}$, which will be subject to later
adaptation. At this initial planning stage (sometimes called pre-compiling),
the programmer does not yet know the outcomes of future measurements and so
cannot gauge-fix according to (91). Pre-compiling crucially requires gauges
other than (91).

##### MBQC measurement gauge and temporal order

The relation between the MBQC measurement basis and the reference in the
adaptive gauge—the fact that the former always contains the latter—gives an
explanation for the temporal order in MBQC. Condition $V_{g}=1$ (or any other
gauge condition) can only be imposed by acting with $r(g)\otimes l(g)$ because
those are the generators of gauge transformations (66). The action of $l(g)$
fixes $V_{g}=1$, but the associated action of $r(g)$ always affects the
section on the subsequent site. Since equation (91) identifies the section
with the measurement basis, this is synonymous with the adaptation of the MBQC
measurement basis.

Of course, condition (91) can only be applied in a temporally ordered fashion.
This is evident from the mechanics of MBQC, but the gauge theory language
reveals a deeper explanation. The condition $V_{g_{i}}=1$ sets Wilson lines
$V_{g_{\prec j}}\equiv 1$ for all $1\leq j\leq N$. (This includes the gauge-
fixing condition (92) because $V_{g_{\prec N}}=B$.) Those Wilson lines are
path-ordered products of individual $V_{g_{j}}$s. Setting $V_{g_{\prec
j}}\equiv 1$ can only be done in a time-ordered fashion: first $V_{g_{\prec
1}}\equiv V_{g_{1}}$, then $V_{g_{\prec 2}}\equiv V_{g_{2}}V_{g_{1}}$, etc.

##  5 Phenomenological ramifications of the gauge principle

###  5.1 Equivalent measurement records

As reviewed in Section 2, there are classes of distinct measurement records
that yield the same computational output. This is reflected in the classical
side processing relations. Here we show how the MBQC gauge transformations,
together with the MPS tensor symmetry $l(\mathbb{Z}_{2}\times\mathbb{Z}_{2})$,
imply this property. Specifically, we show that the change in the measurement
record $\textbf{g}=(g_{1},g_{2},..,g_{N})$ given by

$\textbf{g}\to(g_{1},..g_{i-1},h^{-1}g_{i},hg_{i+1},g_{i+2},..,g_{N})$ (93)

leaves the circuit simulation invariant for all
$h\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. These transformations, with $h$
acting on all adjacent block pairs except $(N,1)$, generate a class of
equivalent outcomes.

To show this, we subject the product $A_{\textbf{g},\textbf{f}}$ to the MBQC
gauge transformation (57) and (65). Only the product
$A_{g_{i+1},f_{i+1}}A_{g_{i},f_{i}}$ is potentially non-trivially affected,
and so we focus on that part:

$\begin{array}[]{rcl}A_{g_{i+1},f_{i+1}}A_{g_{i},f_{i}}&=&\left(V_{g_{\prec
i+1}}\left(V_{g_{i+1}}U_{f_{i+1}}\right)V_{g_{\prec
i+1}}^{\dagger}\right)\left(V_{g_{\prec
i}}\left(V_{g_{i}}U_{f_{i}}\right)V_{g_{\prec i}}^{\dagger}\right)\\\
&\mapsto&\left(V_{\tilde{g}_{\prec
i+1}}\left(V_{\tilde{g}_{i+1}}U_{\tilde{f}_{i+1}}\right)V_{\tilde{g}_{\prec
i+1}}^{\dagger}\right)\left(V_{\tilde{g}_{\prec
i}}\left(V_{\tilde{g}_{i}}U_{\tilde{f}_{i}}\right)V_{\tilde{g}_{\prec
i}}^{\dagger}\right)\\\ &\propto&\left(V_{\tilde{g}_{\prec
i+1}}\left(V_{g_{i+1}}V_{h}U_{f_{i+1}}V_{h}^{\dagger}\right)V_{\tilde{g}_{\prec
i+1}}^{\dagger}\right)\left(V_{\tilde{g}_{\prec
i}}\left(V_{g_{i}}U_{f_{i}}\right)V_{\tilde{g}_{\prec i}}^{\dagger}\right)\\\
&\propto&\left(V_{\tilde{g}_{\prec
i+1}}\left(V_{h}\left(V_{g_{i+1}}U_{f_{i+1}}\right)\right)V_{\tilde{g}_{\prec
i+1}}^{\dagger}\right)\left(V_{\tilde{g}_{\prec
i}}\left(V_{h}^{\dagger}\left(V_{g_{i}}U_{f_{i}}\right)\right)V_{\tilde{g}_{\prec
i}}^{\dagger}\right)\\\ &=&\left(V_{\tilde{g}_{\prec
i+1}}V_{hg_{i+1}}U_{f_{i+1}}V_{\tilde{g}_{\prec
i+1}}^{\dagger}\right)\left(V_{\tilde{g}_{\prec
i}}V_{h^{-1}g_{i}}U_{f_{i}}V_{\tilde{g}_{\prec i}}^{\dagger}\right)\\\
&=&A_{hg_{i+1},f_{i+1}}A_{h^{-1}g_{i},f_{i}}\end{array}$

In the second line we applied the gauge transformation $h^{(i)}$ according to
eq. (65), in the third line we unravelled it, in the fourth line we reordered
operators that commute up to phase. In the fifth line and the sixth line, we
used the left symmetry $l(h)$ and noted that adaptation in the $i+1$ block
given by the conjugation of $V_{\tilde{g}_{\prec i}}$ is consistent with the
change in measurement outcome $g_{i}\to h^{-1}g_{i}$ on the previous block.

Thus we have shown that measurement records related by

$\displaystyle g_{i+1}$ $\displaystyle\to hg_{i+1},\quad g_{i}\to h^{-1}g_{i}$
$\displaystyle f_{i+1}$ $\displaystyle\to f_{i+1}\qquad f_{i}\to f_{i}$ (94)

are equivalent with respect to the quantum computation. We emphasize that
unlike the gauge transformations, in (5.1) the group labels change while the
references are fixed. Consequently, the gauge invariant outcomes
$s_{i}=g_{i}f_{i}$ transform as

$\displaystyle s_{i}\to h^{-1}s_{i},\qquad s_{i+1}\to hs_{i+1},$ (95)

whereas all other measurement outcomes remain unchanged.

###  5.2 MBQC holonomy and the virtual circuit simulation

For simplicity, here and in the next subsection we consider the special case
of deterministic MBQC, i.e., where one of the four possible output values $o$
occurs with unit probability. This means that

$U_{\textbf{f}}\in[I].$

Note that this does not require that all local measurement bases are the
trivial $X$-basis. The Pauli unitary $U_{\textbf{f}}$ may be accumulated in
small (non-Clifford) chunks.

The cluster state resolved in the measurement basis is:

$|1\rangle=\mathcal{N}\sum_{\textbf{g}}\text{Tr}(A_{\textbf{g},\textbf{f}})\,|\textbf{g},\textbf{f}\rangle.$

With eq. (63) and the case assumption $U_{\textbf{f}}\in[I]$, it holds that
$A_{\textbf{g},\textbf{f}}\in[I]$, for all (potential) measurement records g.
Therefore, for all measurement records g that can actually occur with non-zero
probability, it follows that $A_{\textbf{g},\textbf{f}}=I$. Using (63) again,
we find that

$\displaystyle U_{\textbf{f}}=V_{o}^{-1}\propto V_{o},$ (96)

for all measurement records that occur with non-zero probability. Thus, the
holonomy $U_{\textbf{f}}$ of the virtual quantum register is cancelled by the
holonomy $o=g$ of the gauge potential g. This goes to the essence of the MPS
circuit model interpretation Eis2  of MBQC: the circuit model quantum
register, living on the virtual (or correlation) space, is never directly
probed. It interacts with the physical spins, and those are being measured.
The measurement record gives rise to the holonomy $g$, which equals the MBQC
output. Thus, the virtual quantum register is measured indirectly, relying on
the above cancellation of holonomies.

Non-deterministic simulations require a more detailed analysis, which involves
quantum superpositions of fluxes. That case will be covered in Section 5.4.

###  5.3 Computational output and homotopy

Here we introduce the notion of MBQC order parameter, and discuss how the non-
Abellianness of the first homotopy group of the order parameter space relates
to MBQC temporal order.

We observed in (55) that in the MBQC implementation of every gate $U_{i}$ we
can only aim for the equivalence class $[U_{i}]$. This suggests that it is
meaningful to consider $[U_{\prec t}]$ as an order parameter, evolving in time
$t$. The possible order parameters form the manifold ${\cal{M}}$.

With an eye on homotopy, we want the time parameter to be continuous. This is
achieved as follows: for an integer time $i$, $i\leq t\leq i+1$, the
measurement angles $\alpha_{i,1}$ and $\alpha_{i,2}$ are ramped up
continuously from $\alpha_{i,1}=\alpha_{i,2}=0$ to their intended values as
$t$ increases from $i$ to $i+1$. In this way, we are mapping the interval
$[0,N]\ni t$ to a trajectory in the parameter space ${\cal{M}}$. In our MBQC
on a cluster ring, this parameter space is

${\cal{M}}=SU(2)/{\cal{Q}}.$ (97)

Herein ${\cal{Q}}=\\{\pm I,\pm iX,\pm iY,\pm iZ\\}$ is the quaternion group,
which is the lift of the group $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ into
$SU(2)$.

For deterministic MBQCs, $[U_{\prec t}]$ is the same at $t=0$ and $t=2$. We
may therefore identify the two points, and obtain a mapping from the circle
into ${\cal{M}}$. These maps, with base point at $t=0$, are classified by the
first homotopy group $\pi_{1}({\cal{M}})$. They are also classified by the
total (Pauli) unitary accumulated in $U_{\prec N}\in SU(2)$ at time $t=N$, and
it is the same classification.

For our order parameter space of eq. (97), the first homotopy group is:

$\pi_{1}(SU(2)/{\cal{Q}})={\cal{Q}}.$ (98)

The total Pauli operator accumulated during the evolution from continuous time
$t=0$ to $t=N$ is not visible in ${\cal{M}}$ at any given instant of time,
because its modded out in ${\cal{M}}$. But it is captured in the trajectory in
${\cal{M}}$ as a whole, specifically as the homotopy class of the trajectory.

We learn: In case of deterministic MBQC, the total unitary accumulated is an
element of the homotopy group $\pi_{1}({\cal{M}})$. This group element
contains the computational output $o$, and in addition a global phase $\pm 1$.

The phase $\pm 1$ shows up in the classification but is not directly of
physical interest. So one may wonder whether it is a nuisance or a feature.
There is indeed a role that the phases play—they are a signature of the non-
Abelianness of the homotopy group ${\cal{Q}}$. Is the non-Abelianness of
${\cal{Q}}$ of significance for MBQC?

The elements of ${\cal{Q}}$ are the byproduct operators, which are also the
generators of the simulated unitary evolution. We recall that the forward-
propagation of byproduct operators is responsible for temporal order in MBQC.
And this is precisely where the commutation relations of the byproduct
operators come into play. There is non-trivial temporal order if and only if
the byproduct operators do not commute.

##### Analogy.

A system from classical physics with the same order parameter space
${\cal{M}}=SO(3)/(\mathbb{Z}_{2}\times\mathbb{Z}_{2})=SU(2)/{\cal{Q}}$ are the
biaxial nematics Merm2 . There, too, the non-Abelianness of
$\pi_{1}({\cal{M}})$ matters. Namely, it gives rise to non-trivial interaction
among linear defects in 3D crystals of such materials. See Fig. 12 for a
comparison of the two realizations of the order parameter space.

Figure 12: The order parameter spaces for biaxial nematics and MBQC on a
cluster ring are the same,
${\cal{M}}=SO(3)/(\mathbb{Z}_{2}\times\mathbb{Z}_{2})=SU(2)/{\cal{Q}}$. (a)
Order parameter of biaxial nematics. The symmetry is realized by reflections
about the horizontal and the vertical axis. (b) Order parameter of MBQC on a
cluster ring. The symmetry is implemented by left-multiplication with elements
of ${\cal{Q}}$.

###  5.4 A quantum MBQC gauge theory

A classical gauge theory is described by a principal fiber bundle on which
every path $\gamma$ in the base space picks out a definite holonomy. In
contrast, a quantum gauge theory acommodates (and requires) superposition of
states with different holonomies. For example, such superpositions are a basic
feature of quantum electrodynamics, in which Wilson loops are fluctuating
observables.

Likewise, in MBQC, holonomies are superposed in order to simulate a general
unitary $U\in SU(2)$ in a probabilistic fashion. More precisely, given an
expansion

$\displaystyle U=\sum_{o}c_{o}V_{o},\qquad
o\in\mathbb{Z}_{2}\otimes\mathbb{Z}_{2}$ (99)

the cluster state can be expanded in terms of a set of $U$-dependent,
entangled states $\ket{U^{\dagger}V_{o}}$ with holonomy $o$:

$\displaystyle\ket{1}=\sum_{o}c_{o}\ket{U^{\dagger}V_{o}}$ (100)

Equations (99) and (100) generalize the relation (96) between $o$ and the $U$
to allow for quantum superpositions. The probabilities $|c_{o}|^{2}$ provide a
sort of state-operator correspondence, in which logical states
$\ket{U^{\dagger}V_{o}}$ in the physical Hilbert space are mapped to operators
$U$ in the virtual space.555Actually MBQC only determines the modulus of
$c_{o}$ and not the relative phases. This feature is explained below in terms
of the decomposition of the Hilbert space into superselection sectors. In this
section, we explain the precise nature of this correspondence. In particular,
we will show how the logical states $\ket{U^{\dagger}V_{o}}$ arise from a
decomposition of the physical Hilbert space into flux sectors, and how MBQC
uses this decomposition to implement quantum computations.

####  5.4.1 Superselection (flux) sectors

##### Superselection sectors in the $X$-basis

In Section 2 we showed that the holonomy $o$ is invariant under changes of the
measurement record generated by stabilizers. These transformations permute the
computationally equivalent measurement outcomes described in Section 5.1. They
determine a basis, which forms an orbit under the action of the stabilizers

$\displaystyle\mathcal{L}=\\{K_{i},i=2,\cdots N-1\\}.$ (101)

We exclude the stabilizers $K_{1}$ and $K_{N}$ because they are not needed to
span the measurement outcomes, and are also inconsistent with the temporal
order on the circle.666 The temporal order in MBQC selects out a ‘base point’
on the circle, which separates the past from the future. Indeed, measurement
outcomes at the $j=N$ block should not affect measurement angles at the j=1.
The stabilizers $K_{1},K_{N}$ violate this constraint.

We define a flux sector to be the span of such an orbit. Each flux sector is
labelled by the holonomy $o$, so that the total Hilbert space
$\mathcal{H}_{S^{1}}$ on a circle decomposes into a direct sum

$\displaystyle\mathcal{H}_{S^{1}}=\oplus_{o}\mathcal{H}_{o}$ (102)

As an example, for measurements along $X$, the basis for $\mathcal{H}_{o}$
comprises $X$-eigenstates:

$\displaystyle|g_{2N}\rangle\otimes\ldots\otimes|g_{1}\rangle,\qquad
o=\prod_{i}g_{i}$ (103)

We first encountered these sectors in Section 2.1, in the paragraph ‘A glimpse
of a global structure.’

##### Twisted states

We continue to concentrate on $X$-measurements, postponing the general case
till the next paragraph. In each sector labeled by
$o\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, there is a distinguished
representative, which can be expressed as an entangled matrix product state:

$|V_{o}\rangle:=\mathcal{N}\sum_{g_{j}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}{\rm
Tr}\big{(}V_{o}A_{g_{N}}\ldots
A_{g_{2}}A_{g_{1}}\big{)}|g_{N}\rangle\ldots|g_{2}\rangle|g_{1}\rangle.$ (104)

Notice that the cluster state, as defined in (5), is (104) with $V_{o}=1$.
This is the precise reason for denoting the cluster state as
$\operatorname{|1\rangle}$.

Equation (104) encompasses three other matrix product states—$|X\rangle$,
$|Z\rangle$, and $|XZ\rangle$—which are canonical representatives of the three
other superselection sectors. Their wavefunctions overlap only with those
states $|g_{N}\rangle\ldots|g_{2}\rangle|g_{1}\rangle$ whose labels satisfy

$g_{N}\ldots g_{2}\,g_{1}=o.$ (105)

Notice that any of these states can be used as a resource for MBQC. In
particular, measurements of $|V_{o}\rangle$ along $X$ give the deterministic
computational output $o$.

Including a nontrivial $V_{o}$ in the wavefunction (104) is an insertion of
physical $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ flux. We will call states
$|V_{o}\rangle$ ‘twisted states’ because a flux insertion corresponds to
imposing a ‘twisted boundary condition’ on a matter particle living in virtual
space. In a continuum gauge theory, such twisted boundary conditions are
implemented by coupling a matter field $\Phi(x)$ to the gauge field via
$\Phi(x)\to e^{i\int^{x}A_{\mu}dx^{\mu}}\Phi(x)$ and demanding:

$\displaystyle\Phi(x+2\pi)$ $\displaystyle=e^{i\oint A}\Phi(x)$ (106)

##### Flux sectors for a general measurement basis

We can apply the same logic to decompose $\mathcal{H}_{S^{1}}$ into sectors
$\mathcal{H}_{o}(U)$ defined with respect to a general, $U$-dependent
measurement basis:

$\displaystyle\bigotimes_{j=1}^{2N}|(-)^{s_{j}}_{\big{(}(-)^{q_{j}}\alpha_{j}\big{)}}\rangle=\bigotimes_{i=1}^{N}|g_{i}\rangle$
(107)

A projection of the cluster state onto a product state in (107) represents one
measurement history of an MBQC computation, which is designed to simulate a
unitary $U$. These histories, too, fall into four orbits under $\mathcal{L}$.
Each orbit is labeled by the holonomy $o=\prod_{i}g_{i}$, where the group
labels $g_{i}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ are relative to a section
in the adapted basis.

Following (104), we define twisted matrix product states, which have definite
holonomy as measured by a run of MBQC:

$|U^{\dagger}V_{o}\rangle:=\mathcal{N}\sum_{g_{j}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}{\rm
Tr}\big{(}U^{\dagger}V_{o}A_{g_{N}}\ldots
A_{g_{2}}A_{g_{1}})|g_{N}\rangle\ldots|g_{2}\rangle|g_{1}\rangle$ (108)

Note that this notation is consistent with the definition in (104) because the
combination

$\displaystyle\sum_{g_{j}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}\big{(}A_{g_{N}}\ldots
A_{g_{2}}A_{g_{1}}\big{)}|g_{N}\rangle\ldots|g_{2}\rangle|g_{1}\rangle$ (109)

is basis-independent. So equation (108) can be read with $\ket{g}$ defined
relative to any measurement basis. In particular, for measurements in the
$X$-basis, the twisted states (108) reduce to equation (104) with $V_{o}$
replaced by $U^{\dagger}V_{o}$.

The twisted states (108) can be characterized by the fact that running an MBQC
simulation of $U$ on them would return a deterministic outcome. Indeed, using
(23), we can express the wavefunction of these twisted states in the adapted
basis as:

$\displaystyle{\rm Tr}\big{(}U^{\dagger}V_{o}A_{g_{N}}\ldots
A_{g_{2}}A_{g_{1}}\big{)}={\rm Tr}\big{(}V_{o}B_{{g_{N}}\ldots
g_{2}g_{1}}\big{)}\propto\delta_{o,g_{N}\ldots g_{2}g_{1}}$ (110)

Thus, state $|U^{\dagger}V_{o}\rangle$ has definite MBQC holonomy
$o=g_{N}\ldots g_{2}g_{1}$.

####  5.4.2 A logical Hilbert space of fluxes

The resource states for MBQC live in the $2^{2N}$-dimensional Hilbert space
$\mathcal{H}_{S^{1}}$ of physical qubits. On the other hand, the twisted
states span a four-dimensional Hilbert space

$\displaystyle\mathcal{H}_{\text{flux}}=\text{span}\\{\ket{V_{o}}\\}$ (111)

whose kets represent flux sectors of the gauge theory. MBQC uses
$\mathcal{H}_{\text{flux}}$ as a logical Hilbert space to perform quantum
computations. In particular, MBQC makes use of the freedom to rotate the basis
of twisted states (104) into (108). We can make the unitary rotation explicit
by reading both (104) and (108) in the $X$-basis, and then expanding:

$U^{\dagger}:=\sum_{k\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}\tilde{c}_{k}V_{k}$
(112)

The linearity of the matrix product states then immediately implies:

$|U^{\dagger}V_{o}\rangle=\mathcal{N}\\!\\!\\!\\!\sum_{k\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}\tilde{c}_{k}\sum_{g_{j}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}}{\rm
Tr}\big{(}V_{k}V_{o}A_{g_{N}}\ldots
A_{g_{2}}A_{g_{1}}\big{)}|g_{N}\rangle\ldots|g_{2}\rangle|g_{1}\rangle=\mathcal{N}\sum_{k}\tilde{c}_{k}\,b(k,o)\,|V_{ko}\rangle,$
(113)

where $b(k,o)$ is the projective phase defined by $V_{k}V_{o}=b(k,o)V_{ko}$.

We thus have two flux bases for $\mathcal{H}_{\text{flux}}$. On the one hand,
we have a canonical set $|V_{o}\rangle$ to which the cluster state
$\operatorname{|1\rangle}$ belongs; these are resource states that an MBQC
technician will hold in her lab. On the other hand, we have
$\ket{U^{\dagger}V_{o}}$, defined so that a $U$-simulating MBQC protocol
conducted on the initial state $\ket{U^{\dagger}V_{o}}$ would return a
definite holonomy (deterministic computational output.) While the latter are
not resource states, they are nevertheless essential in MBQC.

To see this, let us revisit the MBQC protocol on a ring from the perspective
of $\mathcal{H}_{\text{flux}}$. We can expand the cluster state $\ket{1}$ in
terms of $\ket{U^{\dagger}V_{o}}$ by applying the inverse of (113), or
equivalently, by expanding $U=\sum_{o}c_{o}V_{o}$ in equation (51). This
gives:

$\displaystyle\mathcal{N}^{-1}\ket{1}$ $\displaystyle=\sum_{g}{\rm
Tr}(UB_{g_{N}\ldots g_{2}g_{1}})|g_{N}\rangle\ldots|g_{2}\rangle|g_{1}\rangle$
$\displaystyle=\sum_{o}c_{o}\big{(}\sum_{g}{\rm Tr}(V_{o}B_{g_{N}\ldots
g_{2}g_{1}})|g_{N}\rangle\ldots|g_{2}\rangle|g_{1}\rangle\big{)}$
$\displaystyle=\sum_{o}c_{o}\ket{U^{\dagger}V_{o}}$ (114)

Recall from Section 3.3 that the raw output of an MBQC calculation on a ring
is a probability distribution $p_{o}=|c_{o}|^{2}$, which characterizes the
simulated unitary $U$. Thus, even though MBQC is physically implemented by
single qubit measurements, from a global perspective it is measuring the MBQC
flux corresponding to $\ket{U^{\dagger}V_{o}}$.

####  5.4.3 MBQC versus the circuit model

Equation (5.4.2) presents the cluster state as an element of the four-
dimensional flux Hilbert space $\mathcal{H}_{\text{flux}}$. This perspective
provides an important insight into the relation between MBQC and the circuit
model. To illustrate this relation, consider the following hypothetical
realization of the circuit model. Suppose we can create arbitrary
superpositions of the twisted states $\ket{V_{o}}$. We could then effectively
apply a unitary rotation on $\mathcal{H}_{\text{flux}}$ such that

$\displaystyle\ket{1}\to\ket{U}=\sum_{o}c_{o}\ket{V_{o}}$ (115)

In the $X$-basis, the resulting resource state is:

$\displaystyle\ket{U}=\mathcal{N}\sum_{g_{1},\cdots
g_{n}}\operatorname{tr}(UA_{g_{N}}\cdots
A_{g_{1}})\ket{g_{N}}\cdots\ket{g_{1}}$ (116)

The form of this MPS wavefunction implies that single qubit measurements of
$\ket{U}$ along $X$ will simulate the unitary $U$. The computational output is

$p_{o}=|\langle V_{o}|U\rangle|^{2}=|c_{o}|^{2}.$ (117)

From the point of view of the flux Hilbert space $\mathcal{H}_{\text{flux}}$,
this protocol is a realization of the circuit model.

Let us contrast this with MBQC. Here, too, we start with
$\operatorname{|1\rangle}$ as the initial state. However, instead of applying
unitary gates to $\operatorname{|1\rangle}$, we measure it in the basis
$|U^{\dagger}V_{o}\rangle$. Equation (113) implies these measurements produce
the same probability distributions as above:

$p_{o}=|\langle U^{\dagger}V_{o}|1\rangle|^{2}=|c_{o}|^{2}=|\langle
V_{o}|U\rangle|^{2}$ (118)

In this way, MBQC can be viewed as a ‘passive’ counterpart to an ‘active’
circuit model. Whereas the circuit model implements its programming via the
active transformations $\operatorname{|1\rangle}\to|U\rangle$, MBQC implements
its programming via a $U$-dependent rotation of the measurement basis. In
particular, from the viewpoint of the logical Hilbert space
$\mathcal{H}_{\text{flux}}$, MBQC measurements project $\ket{1}$ onto the
rotated states $|U^{\dagger}V_{o}\rangle$. Meanwhile, from the persective of
the physical Hilbert space $\mathcal{H}_{S_{1}}$, MBQC projects $\ket{1}$ onto
a superselection sector $\mathcal{H}_{o}(U)$ represented by
$|U^{\dagger}V_{o}\rangle$. This superselection sector is defined by the
$U$-dependent decomposition

$\displaystyle\mathcal{H}_{S^{1}}=\oplus_{o}\mathcal{H}_{o}(U),$ (119)

which is determined by the change of basis (113) from $\ket{V_{o}}$ to
$\ket{U^{\dagger}V_{o}}$. This rotation is responsible for introducing
temporal order into the measurement basis.

###  5.5 Extension to fixed point of SPT phases with onsite symmetries

In the preceding sections, we have formulated all elements of the MBQC gauge
theory in terms of the symmetry actions $l(g)$, $r(g)$, and $u(g)$, as well as
the equivariant transformation laws of the cluster MPS tensor; see Figure 5.
These symmetry properties are not unique to the cluster state. Indeed, they
are shared by resource states that belong to the fixed point of any SPT phase
protected by an onsite symmetry $G$. Such a resource state has a ‘fixed point’
MPS representation Schuch , in which $G$ acts via the ordinary representation
$u(g)$. As in the cluster state, this symmetry fractionalizes into left and
right projective representations $l(g)$ and $r(g)$ in the sense that
$u(g)=l(g)r(g)$. Moreover, the fixed point MPS tensor satisfies the same
equivariant transformation laws shown in Figure 5. Therefore, we expect that
our formulation of the MBQC gauge theory applies to each of these fixed
points.

###  5.6 Extension of the gauge principle to SPT cluster phase

The 1D cluster state is surrounded by an SPT phase with global symmetry
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ SPT1 ; SPT2 ; SPT3 . It is known that
MBQC computational power extends from the 1D cluster state into all of that
phase SPT4 . What about the MBQC gauge principle—does it extend as well? In
this regard, we have the following result:

######  Theorem 3.

For any given MBQC on a ground state in the
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ SPT phase surrounding the 1D cluster
state, the measurement bases $|g_{i},f_{i}\rangle$ chosen as a function of
prior measurement record $g_{\prec i}$, the output $o$ given the measurement
record g, and the probability distribution of the computational output $o$,
$p(o)=|\text{Tr}(U_{\textbf{f}}V_{o})|^{2}$, are all invariant under the gauge
transformations (65-67).

The proof of Theorem 3 is the same as of Theorem 1.

Remark: The reason that the proofs of Theorems 1 and 3 are the same is that
both theorems are chiefly about the classical side processing in MBQC (items
(i) and (ii)), and this classical side processing extends from the cluster
state into the surrounding SPT phase without change SPT4 . The invariance of
$p(o)$ in item (iii) also follows as before, but the equality
$p(o)=|\text{Tr}(U_{\textbf{f}}V_{o})|^{2}$ needs to be established for the
SPT phase first; this was done in SPT4 .

There is a lesson to learn from the ease with which the MBQC gauge principle
extends from the cluster point into the surrounding phase. The gauge theory of
MBQC is, in a certain sense, complementary to ‘computational phases of quantum
matter,’ i.e., to viewing MBQC through the lens of symmetry-protected
topological order. Computational phases of matter are about quantum states.
The MBQC gauge theory is, in turn, about observables.

##  6 Conclusion

The main thesis of this work is that the workings of MBQC can be recast in
terms of concepts from gauge theory. The principal identifications are as
follows:

  1. 1.

There are many ways to describe the same MBQC computation to a lab technician.
They are related by gauge transformations; see Section 4.1.

  2. 2.

Under a suitable gauge-fixing condition (equations 91-92), different gauges
also correspond to distinct but computationally equivalent measurement
records. Imposing this gauge-fixing condition determines the temporal order in
the adaptation of measurement angles; see Section 4.4.2.

  3. 3.

Computational output is a holonomy of the gauge field or, equivalently, a
flux; see equation (86).

We hope that this correspondence helps to bridge a gap between the quantum
computing community and high energy and condensed matter theorists, for whom
gauge theory is an essential tool. From the condensed matter perspective, a
connection between MBQC and gauge theory could have been anticipated: a large
class of MBQC resource states have SPT order SPT0 ; SPT1 ; SPT2 ; SPT3 ; SPT4
; SPT5 ; SPT5b ; SPT6 ; SPT7 , and SPT order has been characterized in gauge
theoretic terms . In this sense, our work completes the missing link in the
triangle: MBQC-SPT-gauge theory.

Several features of the gauge theoretic description of MBQC may seem
unfamiliar or even exotic when compared with a standard textbook on gauge
theory. The foremost of them is that MBQC encodes the simulated unitary $U$
using linear superpositions of distinct physical fluxes; see equation (108).
Such flux superpositions give our gauge theory the flexibility to describe all
MBQC computations (in one dimension) in one unified language. Different
simulated $U$s lead to distinct notions of MBQC flux, but each of them is
unitarily related to physical flux; see equation (86).

One innovation, which made our analysis possible, was to consider as resources
cluster states with the topology of a circle. On a technical level, this is
what allowed us to define fluxes—that is, holonomies of a fiber bundle. But
the novelty of considering circular resource states also brings about a modest
practical benefit. In contrast to MBQC on a cluster with endpoints, MBQC on a
ring-like resource extracts two classical bits
$o\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ of computational output. This agrees
with the common lore (superdense coding) that one qubit is worth two classical
bits.

Circular resource states are also intriguing from a more conceptual point of
view, which concerns the relationship between gauge theory and teleportation.
We have motivated our analysis by explaining that MBQC in one dimension is a
sequence of gate teleportations. Our identifications between MBQC and gauge
theory concepts therefore have direct meaning in quantum teleportation:

  1. 1.

Physical parallel transport (74) is the gate, which is induced by a projective
measurement in quantum gate teleportation.

  2. 2.

The intended gate in gate teleportation depends on the intention of the sender
and recipient, so it is not gauge invariant. Different intended gates
correspond to different gauges—different reference states $|f\rangle$ for the
projective measurements.

  3. 3.

The classical information sent by Alice to Bob concerns how the measured state
$|g\rangle$ differs from $|f\rangle=l(g)^{-1}|g\rangle$. That is, the
classical message exchanged in quantum teleportation is an analogue of the
gauge potential.

These identifications extend and complement similar observations about quantum
teleportation, which were made in withlenny ; see also mielczarek . Ref.
withlenny  argued that quantum teleportation with post-selection has the same
physical effect as parallel transport of a charged particle in a background
gauge field. This is a special case of our identifications, restricted to the
circumstance where no corrective operation is necessary. The present work
generalizes withlenny  by removing the post-selection assumption, and by
explaining that the corrective operator applied by Bob (the recipient) plays
the role of the gauge connection. It also explains how the ‘entanglement
holonomies’ defined in withlenny  can be constructed and measured in a lab. To
close an ‘entanglement holonomy,’ the authors of withlenny  needed a sequence
of teleportations, with the initial state of the first teleportation
identified with the final state of the last one. MBQC can realize this setup
without closing a loop in time and without post-selection—by using a resource
state with a ring-like topology.

##### Future directions.

This paper covers MBQC on one-dimensional resource states—settings, which
afford simulation of single-qubit gates. For universal quantum computation,
one also needs an entangling gate. To simulate it, MBQC requires a two-
dimensional resource state. Upgrading our discussion to this more elaborate
context is the obvious next step of our program.

Another specialization adopted in this paper is that we mostly focused on MBQC
on circular resource states. They are best suited for the gauge-theoretic
treatment because they naturally support holonomies / fluxes, i.e. Wilson
loops. But in its conventional form, MBQC assumes a resource state with the
topology of a line segment. Naïvely, designing a gauge-invariant computational
output on a line segment is challenging because the natural objects—Wilson
lines—are not gauge-invariant. The solution involves Stückelberg fields / edge
modes of the gauge theory Buividovich:2008gq ; Donnelly:2014gva ;
Donnelly:2016auv , whose transformations cancel out the gauge dependence of a
Wilson line at its endpoints. We postpone a detailed description of
conventional MBQC in terms of gauge theory with Stuckelberg fields till a
future publication.

A different conceptual perspective, which we mentioned only briefly in the
current work, would take the symmetry protected topological (SPT) order of the
resource state as an analytic starting point. SPT-ordered phases of matter are
in one-to-one correspondence Shiozaki:2016cim  with equivariant topological
field theories (TFT) Moore:2006dw . This correspondence suggests elevating the
connection between MBQC and gauge theory to one with topological field theory.
That, in turn, should bring to focus aspects of MBQC that are more germane to
the spirit of a topological field theory, for example scale invariance or an
axiomatic definition.

## Acknowledgments

GW acknowledges support by Fudan University, the Thousand Talents Program, and
Harvard CMSA. RR is supported by NSERC, in part trough the Canada First
Research Excellence Fund, Quantum Materials and Future Technologies Program,
and by US ARO (W911NF2010013). We thank the organizers of workshop ‘Quantum
Information and String Theory 2019’ held at Yukawa Institute for Theoretical
Physics, Kyoto University, where this work was initiated. We also acknowledge
the workshop ‘Symmetry, Phases of Matter and Quantum Computing – ASQC’ (2019)
held at Perimeter Institute and BC acknowledges the workshop ‘Reconstructing
the Gravitational Hologram with Quantum Information’ (2022) held at the
Galileo Galilei Institute in Florence, where this work was partly carried out.

## References

  * (1) P. V. Buividovich and M. I. Polikarpov, Phys. Lett. B 670, 141-145 (2008) doi:10.1016/j.physletb.2008.10.032 [arXiv:0806.3376 [hep-th]].
  * (2) W. Donnelly, Class. Quant. Grav. 31, no.21, 214003 (2014) doi:10.1088/0264-9381/31/21/214003 [arXiv:1406.7304 [hep-th]].
  * (3) G. W. Moore and G. Segal, [arXiv:hep-th/0609042 [hep-th]].
  * (4) R. Raussendorf and H.-J. Briegel, Phys. Rev. Lett. 86, 5188 (2001).
  * (5) M. Van den Nest, W. Dür, G. Vidal, H. J. Briegel, Phys. Rev. A 75, 012337 (2007).
  * (6) M. Van den Nest, A Miyake, W Dür, HJ Briegel, Phys. Rev. Lett. 97, 150504 (2006).
  * (7) D. Gross, S. T. Flammia, and J. Eisert, Phys. Rev. Lett. 102, 190501 (2009).
  * (8) H.J. Briegel and R. Raussendorf, Phys. Rev. Lett. 86, 910 (2001).
  * (9) I. Affleck, T. Kennedy, E.H. Lieb, and H. Tasaki, Phys. Rev. Lett. 59, 799 (1987).
  * (10) I. Affleck, T. Kennedy, E.H. Lieb, and H. Tasaki, Commun. Math. Phys. 115, 477 (1988).
  * (11) A. Miyake, Ann. Phys. 326, 1656 (2011).
  * (12) T.-C. Wei, I. Affleck, and R. Raussendorf, Phys. Rev. Lett. 106, 070501 (2011).