# Multi-path Summation for Decoding 2D
Topological Codes

Ben Criger<EMAIL_ADDRESS>QuTech, TU Delft  Institute for Globally
Distributed Open Research and Education (IGDORE)  Imran Ashraf  QuTech, TU
Delft

(September 3, 2024)

###### Abstract

Fault tolerance is a prerequisite for scalable quantum computing.
Architectures based on 2D topological codes are effective for near-term
implementations of fault tolerance. To obtain high performance with these
architectures, we require a decoder which can adapt to the wide variety of
error models present in experiments. The typical approach to the problem of
decoding the surface code is to reduce it to minimum-weight perfect matching
in a way that provides a suboptimal threshold error rate, and is specialized
to correct a specific error model. Recently, optimal threshold error rates for
a variety of error models have been obtained by methods which do not use
minimum-weight perfect matching, showing that such thresholds can be achieved
in polynomial time. It is an open question whether these results can also be
achieved by minimum-weight perfect matching. In this work, we use belief
propagation and a novel algorithm for producing edge weights to increase the
utility of minimum-weight perfect matching for decoding surface codes. This
allows us to correct depolarizing errors using the rotated surface code,
obtaining a threshold of $17.76\pm 0.02\%$. This is larger than the threshold
achieved by previous matching-based decoders ($14.88\pm 0.02\%$), though still
below the known upper bound of $\sim 18.9\%$.

##  1 Introduction

Quantum information processing (QIP) provides a means of implementing certain
algorithms with far lower memory and processing requirements than is possible
in classical computing [1, 2]. The analog nature of quantum operations
suggests that devices which perform QIP will have to function correctly in the
presence of small deviations between ideal operations and those that are
actually implemented, a property called _fault tolerance_ [3, 4]. In addition,
many external sources of error exist in current QIP devices, making fault
tolerance a practical necessity as well as a theoretical one.

In order to design fault-tolerant QIP protocols, we first require a set of
quantum states for which the effect of small deviations can be reversed,
called a _quantum error-correcting code_ [5], analogous to _classical_ error-
correcting codes [6]. One important difference between classical and quantum
error correction is that quantum states are inherently continuous, whereas
classical states are discrete. This suggests that noise processes on quantum
computers will also be continuous, and therefore difficult to correct.
However, the action of a projective measurement can effectively discretise the
noise [7, Chapter 2], bringing the study of quantum error correction closer to
classical coding theory. Unfortunately, the action of a projective measurement
also ensures that the qubits used in a quantum code cannot be measured
directly in order to determine where errors have occurred, since such a
measurement would destroy any superposition of code states, discretising the
logical state as well as the noise. However, a large set of quantum error-
correcting codes, called _stabiliser codes_ [3], allow the measurement of
multi-qubit operators which yield results depending only on which error has
occurred, and not on the code state itself. These operators are the
_stabilisers_ of the code, and the result from their measurement is called the
_syndrome_. This syndrome indicates which stabilisers anticommute with the
error.

Typically, the stabilisers are taken to be _Pauli operators_ on $n$ qubits,
tensor products of the operators $\hat{\mathbb{1}}$, $X$, $Y$, and $Z$, where

$\hat{\mathbb{1}}=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},\quad
X=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},\quad Y=\begin{bmatrix}0&-i\\\
i&0\end{bmatrix},\,\,\textrm{and}\,\,Z=\begin{bmatrix}1&0\\\
0&-1\end{bmatrix}.$ (1)

Conveniently, noise discretisation implies that if a code can be used to
correct the random application of these operators on a subset of the qubits,
it can also correct arbitrary operators on the same subset, since the Pauli
operators form a basis for the space of operators.

When measuring the stabilisers, it is possible for the measurement apparatus
to return an incorrect eigenvalue, or for the measurement procedure to produce
errors on the qubits. In order to obtain fault tolerance in such a scenario,
it is necessary to repeat the stabiliser measurements many times. In this
work, we restrict ourselves to a simpler model, in which Pauli errors occur at
random on data qubits, and the measured eigenvalues are correct, and obtained
without consequence.

In order to correct these Pauli errors, it is necessary to derive an error
which reproduces the given syndrome, and is unlikely to alter the intended
logical state if performed on the system. This process, called _decoding_ , is
non-trivial, since a code with $n$ physical qubits will typically contain
$\mathcal{O}(n)$ stabilisers, so the number of possible syndromes scales as
$2^{n}$, prohibiting the use of a simple lookup table. Also, many quantum
codes are _degenerate_ , having multiple errors corresponding to a given
syndrome, further complicating the process of decoding.

The purpose of this work is to improve the accuracy of a frequently-used
method for decoding 2D _homological codes_ [8]. The prototype for these codes
is the 2D _surface code_ , which we review in the following section, along
with the reduction of the decoding problem to minimum-weight perfect matching.
In Section 3, we review prior enhancements to the decoding algorithm of
interest, as well as alternative algorithms. In Sections 4 and 5, we introduce
the methods we propose to enhance the accuracy of surface code decoding and
obtain increased threshold error probabilities. We discuss the effect of
changing boundary conditions, as well as the additional complexity of decoding
using these methods, and conclude in Section 6.

##  2 The Surface Code

A surface code [9, 10, 11] is supported on a square array of qubits, with
stabilisers defined on individual square tiles, see Figure 1. Specifically, we
focus on the _rotated_ surface code, with the boundary conditions from Figure
1. Earlier constructions involve tiling a surface with non-trivial topology,
such as a torus [8], or using an alternate open boundary condition with
_smooth_ and _rough_ boundaries [10]. We choose to study the rotated code,
since it requires the fewest physical qubits per logical qubit.

$\bar{Z}$$\bar{X}$$Z$$Z$$Z$$X$$X$$X$$X$$Z$$Y$$Z$$Z$$Z$$Z$$Z$$Z$$X$$X$$X$$X$$X$$X$
Figure 1: Surface code with distance $d=9$. Data qubits are placed at the
vertices of a $d$-by-$d$ square tiling. Logical operators can be placed along
the sides of the square. Stabilisers of the form $ZZ$/$ZZZZ$ are supported on
grey tiles, and stabilisers of the form $XX$/$XXXX$ are supported on white
tiles. An $X$ or $Z$ error will anticommute with a stabiliser if the
stabiliser is at an endpoint of a path of Pauli operators which is part of the
error. A $Y$ error is detected by both types of stabilisers.

In any of these codes, pairs of stabilisers anticommute with chains of errors
that connect the two tiles supporting the stabilisers, producing a set of
locations where the syndrome is 1 (which we will call _vertices_ for the
remainder of this work). This mathematical structure reduces the decoding
problem to that of finding a likely set of connecting errors which join the
vertices in pairs (we will call these connecting errors _paths_ for the
remainder of this work, and refer to abstract connections between vertices as
_edges_). To maximise the likelihood, we follow the derivation of [12, Section
IV D]. We begin with the assumption that only one type of error ($X$ or $Z$)
can occur, for simplicity. The likelihood of an error $E$ is then a function
of its weight $w(E)$ (the size of its support), the total number of qubits
$n$, and the underlying probability of error $p$:

$p(E)=p^{w(E)}(1-p)^{n-w(E)}=(1-p)^{n}\left(\frac{p}{1-p}\right)^{w(E)}$ (2)

We assume that, if two vertices are connected by a path, the length of that
path is minimal. This implies that the weight of the corresponding edge is
given by the rotated Manhattan distance between the vertices it connects, see
Figure 2.

$X$$X$ Figure 2: A pair of vertices separated by an edge whose minimum length
is 5. A minimum-length path is composed of steps between neighbouring tiles,
and any path which is consistent with the indicated direction will be minimum-
length.

Note that, due to the open boundary conditions, a single vertex can be
connected to the boundary instead of another vertex. This is typically
remedied by introducing _virtual vertices_ which are connected to each other
with weight-0 edges, and to a designated vertex with a weight equal to the
minimum path length between that vertex and the nearest boundary [13].

The total weight of an error is then the sum of the weights of the edges, so
the likelihood can be expressed as a product over the edge set:

$p(E)=(1-p)^{n}\prod_{e\in\mathrm{edges}(E)}\left(\frac{p}{1-p}\right)^{\absolutevalue{e}}$
(3)

To maximise the likelihood, it suffices to maximise any function proportional
to the likelihood, so we can use a simplified cost function:

$\displaystyle p(E)$
$\displaystyle\propto\prod_{e\in\mathrm{edges}(E)}\left(\frac{p}{1-p}\right)^{\absolutevalue{e}}$
(4)
$\displaystyle\sim\sum_{e\in\mathrm{edges}(E)}\absolutevalue{e}\ln\left(\frac{p}{1-p}\right)$
(5) $\displaystyle\propto-\sum_{e\in\mathrm{edges}(E)}\absolutevalue{e}$ (6)

with the minus sign present since the _odds_ of a physical error
$\nicefrac{{p}}{{1-p}}\ll 1$. This implies that, in order to maximise the
likelihood of a prospective error, we should find a set of edges that connects
the vertices in pairs (a _perfect matching_ in graph theory) with minimal
weight. Finding minimal-weight perfect matchings is a well-known combinatorial
problem, solved using the _Blossom_ algorithm [14, 15].

Decoding with this algorithm results in a threshold error rate of $\sim
10.3\%$ [16], compared with a threshold rate of $\sim 10.9\%$ estimated using
a correspondence between the toric code decoding threshold and the phase
transition in a spin model [17, 18]. From this, we surmise that minimum-weight
perfect matching (MWPM) decoding performs well, though not optimally, in the
event that errors of a single type are distributed with identical probability
on each qubit. In addition, there remain many scenarios in which the
independent identically-distributed (IID) error model does not apply. In the
following section, we summarise the current efforts to enhance MWPM decoding
with both IID and more realistic models in mind.

##  3 Prior Work

The derivation of the objective function in Equation 6 assumed that $X$ and
$Z$ errors occur independently, with identical probability on each qubit. This
implies that, if the probability of an $X$ or $Z$ error is $O(p)$, the
probability of a $Y$ error is $O\left(p^{2}\right)$, since $Y\sim XZ$. If the
probabilities of $X$, $Y$, and $Z$ errors differ from this, the performance of
the decoder will be decreased. Consider the frequently used example of
_depolarizing_ noise, in which each type of error is applied with equal
probability. A decoder which minimises the weight of $X$ and $Z$ errors
separately may fail to minimise the relevant weight, resulting in a logical
error, see Figure 3.

$Y$$Y$$Z$$Z$$Z$$X$

$X$$X$

$Z$$Z$$Z$$Z$$Z$

Figure 3: From left to right: a weight-2 $Y$ error acting on a distance-3
surface code, and the independent minimum-weight $X$ and $Z$ corrections. The
appropriate correction, $XX\cdot ZZ$, is not minimum-weight in the independent
error model.

To minimise the appropriate weight function, we need to avoid ‘double-
counting’ the weight of $Y$ errors. To accomplish this, Delfosse [19] and
Fowler [20] reduce the weight of $X$ edges that cross $Z$ edges, since
individual $Y$ errors result in crossed $X$ and $Z$ edges (see Figure 1, upper
left). In order to determine where these crossings occur, the authors first
calculate one of the matchings, $X$ or $Z$, then use the resulting edge set to
determine edge costs for the other matching. In this way, Delfosse
demonstrates that the threshold error rate against $Z$ errors can be raised
for a homological code which has a naturally larger tolerance to $X$ errors.

One obstacle for this approach is that $X$ and $Z$ paths can intersect more
than once, see Figure 4.

$X$$X$$Z$$Z$$Z$$Z$$Y$$X$$X$

$X$$X$$Z$$Z$$Y$$Y$$Y$

Figure 4: For a continuous chain of $Y$ errors, different minimum-weight $X$
and $Z$ paths can be found with different crossing numbers for the same
syndrome.

It is not clear during decoding which error corresponding to a given edge
should be selected in order to maximise the crossing number, thus minimising
the total weight. Furthermore, there can be more than one minimum-weight
perfect matching corresponding to a vertex set, further hampering any effort
to obtain an accurate correction to the depolarizing channel using MWPM
decoding. Accounting for degeneracy caused by edge and matching multiplicity,
it appears, will provide insight in this direction.

There have been multiple efforts to address these types of degeneracy. The
first is due to Barrett, Stace and Doherty [21, 22, 23], and uses the IID
error model. They derive a modified objective function, accounting for the
fact that there are multiple error configurations with the same weight
corresponding to a given matching, see Figure 5.

$X$$X$$X$$X$$X$$X$$X$$X$$X$$X$ Figure 5: Syndrome set with a single minimum-
weight matching (weight 5) and 16 matchings with a single unit of excess
weight. If the odds of an error $\nicefrac{{p}}{{1-p}}>\nicefrac{{1}}{{16}}$,
then the higher-weight matching is more likely, see Equation 7.

If this number of minimum-weight configurations corresponding to the error $E$
is labeled $\Omega(E)$, then the derivation beginning with Equation 3 instead
begins with the likelihood function

$\Omega(E)(1-p)^{n}\left(\frac{p}{1-p}\right)^{w(E)}.$ (7)

In order to use an MWPM-based decoder, it is necessary to express the
likelihood function as a product over the set of edges. This requires us to
express $\Omega(E)$ as a product over the set of edges. This is possible,
since the number of paths joining a pair of vertices depends only on the
positions of those vertices, and not on any property of the graph not related
to the edge under consideration. See, for example, Figure 5, in which the
total number of weight-6 errors (16) is a product of the number of paths
joining the paired vertices (2, 2, and 4). The probability of a minimum-weight
error equivalent to $E$ can then be factored as before:

$p(E)\propto\prod_{e\in\mathrm{edges}(E)}\Omega(e)\left(\frac{p}{1-p}\right)^{\absolutevalue{e}}$
(8)

Taking the logarithm results in the final form of the objective function:

$p(E)\propto-\sum_{e\in\mathrm{edges}(E)}\absolutevalue{e}-\frac{\ln\Omega(e)}{\ln\nicefrac{{1-p}}{{p}}}.$
(9)

In order to calculate $\Omega(e)$ for an edge between two real vertices,
Barrett/Stace/Doherty note that there are
$\binom{\Delta_{y}+\Delta_{x}}{\Delta_{x}}$ paths between points on a rotated
square tiling of the torus separated by $(\Delta_{x},\Delta_{y})$ (see also
[24]).

Using this modification to the edge weights, MWPM decoding results in a
threshold near $10.3\%$ when correcting IID $X$/$Z$ noise. This is similar to
the increase in the threshold that can be obtained from solving an associated
statistical physics model using matchings obtained from Metropolis sampling
[25], which suggests a connection between the two methods. In addition,
efforts have been made to improve the threshold of MWPM decoders by
constraining the input graph to support errors from a specific coset, and by
modifying the obtained solutions through Markov Chain Monte Carlo [26].
However, the thresholds from modified MWPM decoding are still suboptimal,
suggesting that further improvements are required.

In a recent departure from MWPM-based decoding, Bravyi, et al. [27] have
introduced polynomial-time maximum-likelihood decoders for surface codes which
are based on efficient sub-theories of quantum mechanics. For IID $X$/$Z$
noise, they begin by matching each vertex to an arbitrary boundary, producing
a correction which eliminates the syndrome, but results in a logical error
with high likelihood (also known as a _pure error_ [28]). They then provide a
reduction from the problem of determining the probability that the pure error
is an accurate correction to the calculation of the output of a _matchgate
circuit_ [29, 30]. For arbitrary stochastic Pauli noise, likelihood estimation
reduces instead to the problem of contracting a tensor network state [31],
which can also be solved in polynomial time, reminiscent of earlier decoders
for topological codes which use the Renormalisation Group [32, 33]. Using
these techniques, Bravyi et al. are able to obtain optimal thresholds against
IID $X$/$Z$ and depolarizing noise, opening a gap between MWPM and maximum-
likelihood decoding.

This gap can be narrowed by introducing a generalised edge weight calculation,
similar to the method of Barrett/Stace/Doherty, adapted to the case in which
there are different probabilities of error on each qubit. We do this in the
following section.

##  4 Odds Calculation

In order to more accurately approximate the odds of a path existing between
two vertices, we first generalise the calculation of Barrett/Stace/Doherty to
cases where a vertex is being matched to the boundary, or to where some paths
cannot be realised, see Figure 6.

$X$$X$$X$$X$

$X$$X$

Figure 6: Two cases in which the number of paths is not
$\binom{\Delta_{y}+\Delta_{x}}{\Delta_{x}}$, due to open boundary conditions.
Left: one otherwise-possible path between two syndromes cannot be realised
since two of the qubits on the path are outside the lattice. Right (also see
Figure 5): Paths from a syndrome to the boundary can exit the lattice at
multiple points, further preventing a simple calculation of $\Omega_{e}$.

To count the number of paths on _directed acyclic graphs_ such as these, we
can use the following function:  function num_paths($g$, $v_{i}$, $F$)
$\triangleright$ $g$ directed acyclic graph, $v_{i}$ initial vertex, $F$ final
vertex set;  for all $v\in$ vertices(g) do $\texttt{count}[v]\leftarrow 0$ end
for $\texttt{count}[v_{i}]\leftarrow 1$ while true do if
$\texttt{all}(\texttt{count}[f]\neq 0\,\,\texttt{for}\,\,f\in F)$ then return
$\texttt{sum}(\texttt{count}[f]\,\,\texttt{for}\,\,f\in F)$ end if for all
$v\in$ vertices(g) do if $\texttt{all}(\texttt{count}[i]\neq
0\,\,\texttt{for}\,\,i\in\texttt{incoming}(v))$ then
$\texttt{count}[v]\leftarrow\texttt{sum}(\texttt{count}[i]\,\,\texttt{for}\,\,i\in\texttt{incoming}(v))$
end if end for end while end function If this function is applied to a closed
bounding box (see Figure 2), the result will be
$\binom{\Delta_{y}+\Delta_{x}}{\Delta_{x}}$, which simplifies the calculation
for periodic boundary conditions, for which all bounding boxes are closed. For
a generic directed acyclic graph, this function requires one operation for
every edge of the input graph, and can be parallelized using _message passing_
[34, Chapter 16], reducing the runtime to be proportional to the path length
using one constant-size processor per vertex of the input graph. To be
implemented serially, the input graph $g$ should first be _topologically
sorted_ [35, Section 22.4], also requiring a number of operations at most
linear in the graph’s size. The key to the derivation of the path-counting
algorithm is that the number of paths reaching a vertex $w$ is the sum of the
number of paths reaching the vertices with edges incoming to $w$. Using this
function to calculate $\Omega_{e}$, we can replicate the result of
Barrett/Stace/Doherty using the rotated surface code, see Figure 7.

0.080.090.100.110.120.130.10.20.30.40.5physical error probabilitylogical error
probabilityIID $X$/$Z$ Error Model, without multi-path
summation$d=7$$d=11$$d=15$$d=19$$d=23$

0.080.090.100.110.120.130.10.20.30.40.5physical error probabilitylogical error
probabilityIID $X$/$Z$ Error Model, with multi-path
summation$d=7$$d=11$$d=15$$d=19$$d=23$

Figure 7: Threshold of the rotated surface code correcting IID $X$/$Z$ errors.
Above: Edge weights for MWPM are derived using the Manhattan distance,
resulting threshold is $9.97\pm 0.01\%$, lower than the value of $10.3\%$
obtained using alternate boundary conditions in [36]. Below: Edge weights for
MWPM are derived using path-counting, resulting in a threshold of $10.34\pm
0.01\%$, compensating for the disadvantage imposed by the rotated boundary
conditions. Error bars represent a $99\%$ confidence interval. Solid lines are
maximum-likelihood fits to data near the threshold.

To generalise to the case where $Y$ errors can occur with arbitrary
probability, we first consider the role of detected $Z$ errors in determining
where $X$ errors have occurred (see [19] for an in-depth discussion). We
assume that the physical error model has a fixed probability of $X$, $Y$, or
$Z$ on each qubit, which is qubit-independent. To see the role that detected
$Z$ errors play, we imagine that we could determine with certainty the
positions of errors that anticommute with the $Z$-detecting stabilisers. These
errors must be either $Z$ or $Y$, and the qubits which have not been affected
by one of these errors must have been affected by an $X$ error, if at all. To
use this information in determining the positions of $X$ errors, we use the
_conditional_ probabilities of an $X$ error occurring, depending on the result
of the $Z$ decoding:

$p\left(X\textrm{ or }Y\middle|Y\textrm{ or
}Z\right)=\dfrac{p_{Y}}{p_{Y}+p_{Z}},\qquad p\left(X\textrm{ or
}Y\middle|\hat{\mathbb{1}}\textrm{ or
}X\right)=\dfrac{p_{X}}{p_{X}+p_{\hat{\mathbb{1}}}}$ (10)

Thus, we see that attempting to account for $X$/$Z$ correlations in the error
model will require us to consider error models in which there are different
probabilities of error on each qubit, even when the underlying error model is
qubit-independent.

The method we use to approximate conditional probabilities of error in the
absence of perfect detection is explained in the following section. For now,
we generalise the derivation of the likelihood of an error beginning in
Equation 3, with a few approximations and definitions:

  * •

We only consider minimum-length paths, which are restricted to the set of
qubits within bounding boxes of the type seen in Figures 2 and 6.

  * •

We consider two possibilities, either the vertices being considered are joined
by a single path, or none of the qubits in the bounding box are in error.

The probability $p(E)$ (now referring to the probability of any error
equivalent to $E$ under a change of minimum-length path) can then be expressed
in terms of the odds of error on a given qubit,
$o_{q}\equiv\frac{p_{q}}{1-p_{q}}$:

$\displaystyle p(E)$
$\displaystyle=\prod_{q}(1-p_{q})\times\prod_{e\in\mathrm{edges}(E)}\sum_{p\in\mathrm{paths}(e)}\prod_{q\in
p}o_{q}$ (11)
$\displaystyle\sim\sum_{e\in\mathrm{edges}(E)}\log\left(\sum_{p\in\mathrm{paths}(e)}\prod_{q\in
p}o_{q}\right)$ (12)

We can divide the set $\mathrm{paths}(e)$ into disjoint subsets that pass
through each of the vertices adjacent to the final vertex, assuming that there
is only one (otherwise, we can divide the set $\mathrm{paths}(e)$ into
disjoint subsets associated with individual final vertices, then proceed). The
path from each of these _predecessor_ vertices to the final vertex only
traverses a single qubit $q_{p}$, so:

$\sum_{p\in\mathrm{paths}(e)}\prod_{q\in
p}o_{q}=\sum_{q_{p}}o_{q_{p}}\sum_{p^{\prime}\in\mathrm{paths}(q_{p})}\prod_{q\in
p^{\prime}}o_{q},$ (13)

where $\mathrm{paths}(q_{p})$ is the set of paths leading from the initial
vertex to the predecessor vertex $q_{p}$. This reduction is similar to the sum
reduction used in path-counting, though now the sum is weighted by
$o_{q_{p}}$. The path-counting function can be easily modified to evaluate
this quantity:  function path_sum($g$, $v_{i}$, $F$, o_q) $\triangleright$ o_q
$o_{q}$ associated with edges $(v,v^{\prime})$ of $g$;  for all $v\in$
vertices(g) do $\texttt{odds}[v]\leftarrow 0$ end for
$\texttt{odds}[v_{i}]\leftarrow 1$ while true do if
$\texttt{all}(\texttt{odds}[f]\neq 0\,\,\texttt{for}\,\,f\in F)$ then return
$\texttt{sum}(\texttt{odds}[f]\,\,\texttt{for}\,\,f\in F)$ end if for all
$v\in$ vertices(g) do if $\texttt{all}(\texttt{odds}[i]\neq
0\,\,\texttt{for}\,\,i\in\texttt{incoming}(v))$ then
$\texttt{odds}[v]\leftarrow\texttt{sum}(\texttt{o\\_q}[(i,v)]\ast\texttt{odds}[i]\,\,\texttt{for}\,\,i\in\texttt{incoming}(v))$
end if end for end while end function This produces an approximate cost
function, since we have neglected the possibility that there is an error
inside the bounding box that does not cause a syndrome (a randomly applied
stabiliser), and we have failed to account for the large number of less likely
matchings that are equivalent to the likeliest matchings up to a stabiliser.
Nevertheless, we will see that surface code decoding can be improved, once we
have an accurate set of estimates for the marginal probability of each type of
error on each qubit. In the following section, we review belief propagation, a
method which can provide these estimates.

##  5 Belief Propagation

Belief propagation (BP) is a message-passing algorithm for calculating
marginal probabilities, which has been applied to decoding quantum codes
correcting Pauli noise [37]. To use BP for decoding, we first define the
_Tanner graph_ corresponding to a surface code, which contains a _qubit
vertex_ for every qubit in the code, and a _check vertex_ for every stabiliser
check. An edge exists between each check vertex and each qubit vertex in its
support, see Figure 8.

Figure 8: Tanner graph for the $d=5$ surface code. Qubit vertices are shown in
black, stabiliser vertices are shown in white. Edges exist between stabiliser
vertices and the qubit vertices in the support of the corresponding
stabiliser.

The algorithm begins with a probability distribution $p(E_{q})$ (also called a
_belief_), assigned to each qubit $q$, of the form
$\left[1-(p_{Z}+p_{X}+p_{Y}),\,p_{Z},\,p_{X},\,p_{Y}\right]$, equal to the
_prior distribution_ of error probabilities on each qubit (called ‘the
physical distribution’ earlier). These beliefs are passed as messages to each
of the neighbouring check vertices. Each check vertex $c$ calculates messages
to be passed back to each of its neighbouring qubit vertices, one for each
possible error $E_{q}$ on the qubit:

$m_{c\rightarrow
q}(E_{q})\propto\sum_{E_{q^{\prime}},\,q^{\prime}\in\mathrm{supp}(c)\backslash
q}\left(\delta_{\mathrm{synd}_{c},S_{c}\cdot
E_{c}}\prod_{q^{\prime}\in\mathrm{supp}(c)\backslash
q}m_{q^{\prime}\rightarrow c}(E_{q^{\prime}})\right).$ (14)

Here, proportionality indicates that the messages are to be normalized after
they are calculated. Each qubit vertex then calculates a set of messages to be
passed back:

$m_{q\rightarrow c}(E_{q})\propto
p(E_{q})\prod_{c^{\prime}\in\mathrm{supp}(q)\backslash
c}m_{c^{\prime}\rightarrow q}(E_{q}),$ (15)

where proportionality again indicates that the messages are to be normalized.

Once the algorithm has converged, we calculate the updated beliefs (the
conditional probabilities):

$b_{q}(E_{q})=p(E_{q})\prod_{c\in\mathrm{supp}(q)}m_{c\rightarrow q}(E_{q}).$
(16)

These beliefs can, in some instances, be used to provide an approximate
maximum-likelihood error, but belief propagation is only guaranteed to provide
an accurate estimate of likelihood on _trees_ (acyclic graphs). In decoding,
where Tanner graphs have many short cycles, the product of the likeliest
errors on each qubit may not conform with the syndrome. For an example of
this, consider the scenario in Figure 9 (also [37]). In this scenario, an $X$
error has occurred on the upper-left corner, causing a single vertex to appear
in the neighbouring square. With equal likelihood, this vertex could have been
caused by an $X$ error on the neighbouring qubit. In this case, belief
propagation outputs a marginal probability $p_{X}+p_{Y}$ slightly below
$\nicefrac{{1}}{{2}}$ on each of these qubits. We refer to this scenario as a
_split belief_. Taking the likeliest error on each qubit results in an error
which does not conform with the syndrome, preventing the use of BP as a
decoder. However, using a split belief in the approximate cost calculation in
Section 4 still provides a final odds near 2, resulting in a small negative
edge weight, and a good chance that the vertex in question will be matched to
the boundary, as it should be.

$X$$X$$X$$X$

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$number of iterationsBeliefs, Upper-Left
Qubit$p_{\hat{\mathbb{1}}}+p_{Z}$$p_{X}+p_{Y}$

Figure 9: Left: Two possible errors which result in a split belief. Right:
Convergence of beliefs when the true error is a weight-one $X$ error on the
upper-left qubit, the underlying error model has probabilities
$\left[0.97,\,0.01,\,0.01,\,0.01\right]$. A nearly-identical set of beliefs is
supported on the neighbouring qubit.

Using $d$ rounds of belief propagation and the cost calculation in Section 4,
we obtain a threshold of $17.76\pm 0.02\%$ when correcting depolarizing noise,
see Figure 10.

0.130.140.150.160.170.180.100.150.200.250.300.350.400.45physical error
probabilitylogical error probabilityDepolarizing Error Model, without
BP/multi-path summation$d=7$$d=11$$d=15$$d=19$$d=23$

0.150.160.170.180.190.200.100.150.200.250.300.350.400.45physical error
probabilitylogical error probabilityDepolarizing Error Model, with BP/multi-
path summation$d=7$$d=11$$d=15$$d=19$$d=23$

Figure 10: Threshold for the rotated surface code correcting depolarizing
errors. Above: Using uniform edge weights, the threshold is $14.88\pm 0.02\%$,
less than the value of $15.5\pm 0.5\%$ obtained using smooth/rough boundary
conditions in [13]. Below: When using multi-path odds summation as discussed
in Section 4, the threshold improves to $17.76\pm 0.02\%$. Error bars are
$99\%$ confidence intervals. Solid lines are maximum-likelihood fits to data
points near the threshold.

This is a significant improvement over normal MWPM decoding, though not
optimal. In the following section, we discuss the complexity of the additional
steps in the decoder, as well as potential enhancements and other
applications.

##  6 Discussion/Conclusion

To our knowledge, little discussion exists in the literature regarding the
effect of boundary conditions on the performance of surface code decoders. In
addition, it is important to note the complexity of the additional steps used
in the decoder studied in this work. In this section, we address these topics,
and conclude by pointing out opportunities for future research.

###  6.1 Boundary Conditions

Intuition drawn from the statistical physics of spin models which are related
to surface codes motivates the belief that the decoding threshold of a surface
code is independent of ‘finite-size’ considerations such as boundary
conditions and aspect ratio (if non-square lattices are used). Indeed, we see
this belief to be approximately correct in the current work, though there are
small deviations from decoding thresholds calculated elsewhere. To ensure that
these deviations are related to boundary conditions, we re-evaluate the
decoders we consider using smooth/rough boundary conditions in Figures 11 and
12, obtaining thresholds for comparison to Figures 7 and 10.

0.0800.0850.0900.0950.1000.1050.1100.1150.1200.10.20.30.40.5physical error
probabilitylogical error probabilityIID $X$/$Z$ Error Model, without multi-
path summation$d=7$$d=11$$d=15$$d=19$$d=23$

0.0800.0850.0900.0950.1000.1050.1100.1150.1200.10.20.30.40.5physical error
probabilitylogical error probabilityIID $X$/$Z$ Error Model, with multi-path
summation$d=7$$d=11$$d=15$$d=19$$d=23$

Figure 11: Replication of previous results using smooth/rough boundary
conditions. The threshold error rate of $10.30\pm 0.01\%$ is in accordance
with earlier results. This threshold increases to $10.59\pm 0.01\%$ using
path-counting, comparable to the $\sim 10.6\%$ observed by
Barrett/Stace/Doherty (with periodic boundary conditions) [21, 23]. Error bars
are $99\%$ confidence intervals. Solid lines are maximum-likelihood fits near
the threshold.

0.1350.1400.1450.1500.1550.1600.1650.1700.1750.100.150.200.250.300.350.400.45physical
error probabilitylogical error probabilityDepolarizing Error Model, without
BP/multi-path summation$d=7$$d=11$$d=15$$d=19$$d=23$

0.170.180.190.200.210.20.30.40.50.6physical error probabilitylogical error
probabilityDepolarizing Error Model, with BP/multi-path
summation$d=7$$d=11$$d=15$$d=19$$d=23$

Figure 12: Application of belief propagation/multi-path summation to the
decoding of surface codes with smooth/rough boundaries which are subjected to
depolarising noise. A similar increase in threshold error rates is observed
using these boundary conditions, with a threshold of $15.42\pm 0.01\%$
obtained using a standard MWPM decoder, compatible with the observation of
$15.5\pm 0.5\%$ by [13]. This increases to $17.84\pm 0.01\%$ when belief
propagation and multi-path summation are incorporated. Error bars are $99\%$
confidence intervals. Solid lines are maximum-likelihood fits near the
threshold.

The fact that these thresholds exceed those for the rotated boundary
conditions is confusing if the decoding threshold corresponds exactly with a
thermodynamic property. However, this correspondence is only exact when using
an _optimal_ decoder [38]. The suboptimality of the matching-based decoders
studied here thus allows for boundary conditions to influence decoder
performance. Nonetheless, it is surprising that the change in threshold caused
by the change in boundary condition should be discernible, and that it should
be similar to the change in threshold caused by the change in decoding
algorithm.

While we cannot explain this discrepancy completely, it can be explained
partially by comparing the sets of minimum-length paths which traverse the two
lattices, shown in Figure 13. When using smooth/rough boundary conditions,
each vertex on the graph to be traversed only has one neighbouring edge which
can be part of a minimum-length directed path from top to bottom, the edge
immediately below. A minimum-length logical operator must, therefore, traverse
the lattice directly from top to bottom. Therefore, there are exactly $d$
minimum-length paths across the lattice. When using rotated boundary
conditions, however, there are two edges neighbouring each vertex which can be
part of a minimum-length path. The total number of minimum-length paths is
therefore much larger, being bounded from below by
${d\choose\left\lfloor\nicefrac{{d}}{{2}}\right\rfloor}$, since the graph
being traversed contains a
$\left(\left\lfloor\nicefrac{{d}}{{2}}\right\rfloor\right)$-by-$\left(\left\lceil\nicefrac{{d}}{{2}}\right\rceil\right)$
bounding box as a subgraph. The number of minimum-length paths on the rotated
lattice can also be calculated exactly in linear time by path-counting, as
explained in Section 4.

Figure 13: Graphs for which paths between the two coloured vertices correspond
to logical Paulis on distance-5 surface codes. Left: Smooth/rough boundary
conditions, right: rotated boundary conditions, with grey edges costing
nothing to traverse. With smooth/rough boundary conditions, horizontal edges
cannot be used in a minimum-length path, resulting in a number of minimum-
length paths equal to $d$. With rotated boundary conditions, every edge can be
part of a minimum-length path, resulting in a number of minimum-length paths
which can be calculated by path-counting as explained in Section 4 (in this
instance, there are $52$ such paths), and lower-bounded by
${d\choose\left\lfloor\nicefrac{{d}}{{2}}\right\rfloor}$ (see text).

In order for a minimum-weight decoder to produce a logical error when a small
number of (for example, $X$) errors occur on the lattice at random, it must be
possible to produce a minimum-length path by traversing at least
$\left(\left\lceil\nicefrac{{d}}{{2}}\right\rceil\right)$ edges corresponding
to qubits on which errors have occurred. When the number of available minimum-
length paths is much larger, intuition would say that should occur with higher
probability. This qualitative difference sheds some light on the origin of the
difference in threshold, though we cannot explain it fully.

We note, in addition, that this difference in threshold has also been observed
in predictions of logical error rates [39] and when using highly-correlated
error models [40]. It is interesting to note that, for the two error models
considered here, the difference in threshold between code families with
different boundary conditions is smaller when the decoder is closer to
optimality, though this is by no means conclusive. Another confounding factor,
which prevents us from attributing these deviations solely to boundary
conditions, is the behaviour of the Blossom V MWPM implementation on graphs
with non-unique minimum-weight perfect matchings, also noted by [22], which
may also play a role.

###  6.2 Complexity

The decoder studied in this work does not require any modification to the
Blossom algorithm, but adds pre-calculation steps which determine the edge
weights. The additional overhead from belief propagation is $O(d^{3})$, since
it acts for $d$ rounds and performs $O(d^{2})$ operations in each round. The
operations in each round of belief propagation can be carried out
independently of one another, allowing parallelization to $O(d)$ time using
$O(d^{2})$ processors. The path-summation function is more complex. If all
path-sums are calculated, $O(d^{4})$ operations are required, since there are
$O(d^{4})$ ancilla pairs, each one requiring a constant number of operations
for calculation, assuming that they are performed in the appropriate order. A
naïve parallel implementation of this algorithm would require one processor
per pair of stabilisers ($O(d^{4})$ processors) and $O(d)$ time, since the
longest minimum-length paths are of $O(d)$ length. It is likely possible to
reduce the number of processors, since each processor in the naïve
parallelization only performs a calculation during one of the $O(d)$ timesteps
of the algorithm. It is also likely possible to reduce the overall complexity
of decoding by combining the proposed edge weight evaluation techniques with
methods for pruning the syndrome graph [41], which is input to Blossom.

###  6.3 Future Work

To address the sub-optimality of the decoder, it is necessary to determine
which of the approximations made in its definition are limiting accuracy. The
first of these approximations is the set of marginal probabilities from belief
propagation. The split belief in Figure 9 produces an odds near 2, where it
should be much higher in principle (in the absence of other nearby syndromes,
or a strong prior). Efforts to decrease this inaccuracy by altering the Tanner
graph or prior used in BP have failed. Immediate future work will likely focus
on finding a modification to or substitute for the BP algorithm which remedies
this inaccuracy.

In any event, it will be interesting to apply multi-path odds summation to the
$(2+1)$-dimensional problem of decoding the surface code when incorporating
multiple rounds of measurement to combat errors in the syndrome measurement
circuit, as well as to the problem of decoding 2D colour codes, which can be
reduced to multiple correlated instances of surface code decoding [42].

## Acknowledgements/Remarks

The authors would like to thank Tom O’Brien and Brian Tarasinski for the
motivation to study this problem, as well as Barbara Terhal, Kasper
Duivenvoorden, Christophe Vuillot, Nikolas Breuckmann and Ben Brown for useful
discussions. Open-source software libraries used in this work include the
Python libraries numpy [43], networkx [44], scipy [45], matplotlib [46],
seaborn [47], and emcee [48], as well as Blossom V [15] in C++. Additional
software produced for this work is available on Github [49].

## References

  * Shor [1997] Peter W. Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  _SIAM Journal on Computing_ , 26(5):1484–1509, 1997.  doi: 10.1137/S0097539795293172.  URL http://dx.doi.org/10.1137/S0097539795293172.
  * Georgescu et al. [2014] I. M. Georgescu, S. Ashhab, and Franco Nori.  Quantum simulation.  _Rev. Mod. Phys._ , 86:153–185, Mar 2014.  doi: 10.1103/RevModPhys.86.153.  URL https://doi.org/10.1103/revmodphys.86.153.
  * Gottesman [1997] Daniel Gottesman.  _Stabilizer Codes and Quantum Error Correction_.  Caltech Ph.D. Thesis, 1997.  doi: 10.7907/rzr7-dt72.  URL https://doi.org/10.7907/rzr7-dt72.
  * Steane [1997] A. M. Steane.  Active stabilization, quantum computation, and quantum state synthesis.  _Phys. Rev. Lett._ , 78:2252–2255, Mar 1997.  doi: 10.1103/PhysRevLett.78.2252.  URL https://doi.org/10.1103/physrevlett.78.2252.
  * Knill and Laflamme [1997] Emanuel Knill and Raymond Laflamme.  Theory of quantum error-correcting codes.  _Phys. Rev. A_ , 55:900–911, Feb 1997.  doi: 10.1103/PhysRevA.55.900.  URL https://doi.org/10.1103/physreva.55.900.
  * MacWilliams and Sloane [1978] F.J. MacWilliams and N.J.A. Sloane.  _The Theory of Error-Correcting Codes_.  North-Holland Publishing Company, 2nd edition, 1978.  ISBN 9780080570877.  URL https://elsevier.com/books/the-theory-of-error-correcting-codes/macwilliams/978-0-444-85193-2.
  * Lidar and Brun [2013] Daniel A. Lidar and Todd A. Brun.  _Quantum Error Correction_.  Cambridge University Press, 2013.  doi: 10.1017/CBO9781139034807.  URL https://doi.org/10.1017/CBO9781139034807.
  * Kitaev [2003] A.Yu. Kitaev.  Fault-tolerant quantum computation by anyons.  _Annals of Physics_ , 303(1):2 – 30, 2003.  ISSN 0003-4916.  doi: 10.1016/s0003-4916(02)00018-0.  URL https://doi.org/10.1016/s0003-4916(02)00018-0.
  * Freedman and Meyer [2001] Michael H. Freedman and David A. Meyer.  Projective plane and planar quantum codes.  _Foundations of Computational Mathematics_ , 1(3):325–332, jul 2001.  doi: 10.1007/s102080010013.  URL https://doi.org/10.1007%2Fs102080010013.
  * Bravyi and Kitaev [1998] Sergey B. Bravyi and A. Yu. Kitaev.  Quantum codes on a lattice with boundary.  _arXiv preprint quant-ph/9811052_ , 1998.  URL https://arxiv.org/abs/quant-ph/9811052.
  * Bombin and Martin-Delgado [2007] H. Bombin and M. A. Martin-Delgado.  Optimal resources for topological two-dimensional stabilizer codes: Comparative study.  _Physical Review A_ , 76(1), jul 2007.  doi: 10.1103/physreva.76.012305.  URL https://doi.org/10.1103%2Fphysreva.76.012305.
  * Dennis et al. [2002] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  Topological quantum memory.  _Journal of Mathematical Physics_ , 43(9):4452–4505, 2002.  doi: 10.1063/1.1499754.  URL http://dx.doi.org/10.1063/1.1499754.
  * Wang et al. [2010] D.S. Wang, A.G. Fowler, A.M. Stephens, and L.C.L. Hollenberg.  Threshold error rates for the toric and planar codes.  _Quantum Information & Computation_, 10(5):456–469, 2010.  doi: 10.26421/QIC10.5.  URL https://doi.org/10.26421/QIC10.5.
  * Edmonds [1965] Jack Edmonds.  Paths, trees, and flowers.  _Canadian Journal of Mathematics_ , 17:449–467, 1965.  doi: 10.4153/CJM-1965-045-4.  URL http://dx.doi.org/10.4153/CJM-1965-045-4.
  * Kolmogorov [2009] Vladimir Kolmogorov.  Blossom V: a new implementation of a minimum cost perfect matching algorithm.  _Mathematical Programming Computation_ , 1:43–67, 2009\.  doi: 10.1007/s12532-009-0002-8.  URL http://dx.doi.org/10.1007/s12532-009-0002-8.
  * Wang et al. [2003] Chenyang Wang, Jim Harrington, and John Preskill.  Confinement-higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory.  _Annals of Physics_ , 303(1):31–58, jan 2003\.  doi: 10.1016/s0003-4916(02)00019-2.  URL https://doi.org/10.1016%2Fs0003-4916%2802%2900019-2.
  * Merz and Chalker [2002] F. Merz and J. T. Chalker.  Two-dimensional random-bond ising model, free fermions, and the network model.  _Physical Review B_ , 65(5), jan 2002.  doi: 10.1103/physrevb.65.054425.  URL https://doi.org/10.1103%2Fphysrevb.65.054425.
  * Honecker et al. [2001] A. Honecker, M. Picco, and P. Pujol.  Universality class of the nishimori point in the 2d$\pm$JRandom-bond ising model.  _Physical Review Letters_ , 87(4), jul 2001.  doi: 10.1103/physrevlett.87.047201.  URL https://doi.org/10.1103%2Fphysrevlett.87.047201.
  * Delfosse and Tillich [2014] Nicolas Delfosse and Jean-Pierre Tillich.  A decoding algorithm for CSS codes using the $X$/$Z$ correlations.  In _2014 IEEE International Symposium on Information Theory_. IEEE, jun 2014.  doi: 10.1109/isit.2014.6874997.  URL https://doi.org/10.1109%2Fisit.2014.6874997.
  * Fowler [2013a] Austin G. Fowler.  Optimal complexity correction of correlated errors in the surface code.  _arXiv preprint arXiv:1310.0863_ , 2013a.  URL https://arxiv.org/abs/1310.0863.
  * Stace et al. [2009] Thomas M. Stace, Sean D. Barrett, and Andrew C. Doherty.  Thresholds for topological codes in the presence of loss.  _Physical Review Letters_ , 102(20), may 2009.  doi: 10.1103/physrevlett.102.200501.  URL https://doi.org/10.1103%2Fphysrevlett.102.200501.
  * Barrett and Stace [2010] Sean D. Barrett and Thomas M. Stace.  Fault tolerant quantum computation with very high threshold for loss errors.  _Physical Review Letters_ , 105(20), nov 2010.  doi: 10.1103/physrevlett.105.200502.  URL https://doi.org/10.1103%2Fphysrevlett.105.200502.
  * Stace and Barrett [2010] Thomas M. Stace and Sean D. Barrett.  Error correction and degeneracy in surface codes suffering loss.  _Physical Review A_ , 81(2), feb 2010.  doi: 10.1103/physreva.81.022317.  URL https://doi.org/10.1103%2Fphysreva.81.022317.
  * [24] Project Euler: Problem 15.  https://projecteuler.net/problem=15.  Accessed: 2017-08-07.
  * Freund and Grassberger [1989] H Freund and P Grassberger.  The ground state of the $+$ or $-$ $J$ spin glass from a heuristic matching algorithm.  _Journal of Physics A: Mathematical and General_ , 22(18):4045–4059, sep 1989.  doi: 10.1088/0305-4470/22/18/036.  URL https://doi.org/10.1088%2F0305-4470%2F22%2F18%2F036.
  * Hutter et al. [2014] Adrian Hutter, James R. Wootton, and Daniel Loss.  Efficient markov chain monte carlo algorithm for the surface code.  _Physical Review A_ , 89(2):022326, feb 2014.  doi: 10.1103/physreva.89.022326.  URL https://doi.org/10.1103%2Fphysreva.89.022326.
  * Bravyi et al. [2014] Sergey Bravyi, Martin Suchara, and Alexander Vargo.  Efficient algorithms for maximum likelihood decoding in the surface code.  _Physical Review A_ , 90(3), sep 2014.  doi: 10.1103/physreva.90.032326.  URL https://doi.org/10.1103%2Fphysreva.90.032326.
  * Duclos-Cianci and Poulin [2010a] Guillaume Duclos-Cianci and David Poulin.  A renormalization group decoding algorithm for topological quantum codes.  In _2010 IEEE Information Theory Workshop_. IEEE, aug 2010a.  doi: 10.1109/cig.2010.5592866.  URL https://doi.org/10.1109%2Fcig.2010.5592866.
  * Valiant [2002] Leslie G. Valiant.  Quantum circuits that can be simulated classically in polynomial time.  _SIAM Journal on Computing_ , 31(4):1229–1254, jan 2002.  doi: 10.1137/s0097539700377025.  URL https://doi.org/10.1137%2Fs0097539700377025.
  * Bravyi [2005] Sergey Bravyi.  Lagrangian representation for fermionic linear optics.  _Quantum Information & Computation_, 5(3):216–238, 2005.  doi: 10.26421/QIC5.3.  URL https://doi.org/10.26421/QIC5.3.
  * Vidal [2003] Guifré Vidal.  Efficient classical simulation of slightly entangled quantum computations.  _Physical Review Letters_ , 91(14), oct 2003.  doi: 10.1103/physrevlett.91.147902.  URL https://doi.org/10.1103%2Fphysrevlett.91.147902.
  * Duclos-Cianci and Poulin [2010b] Guillaume Duclos-Cianci and David Poulin.  A renormalization group decoding algorithm for topological quantum codes.  _Information Theory Workshop (ITW), IEEE_ , pages 1 – 5, 2010b.  doi: 10.1109/CIG.2010.5592866.  URL http://dx.doi.org/10.1109/CIG.2010.5592866.
  * Hutter et al. [2015] Adrian Hutter, Daniel Loss, and James R Wootton.  Improved HDRG decoders for qudit and non-abelian quantum error correction.  _New Journal of Physics_ , 17(3):035017, mar 2015\.  doi: 10.1088/1367-2630/17/3/035017.  URL https://doi.org/10.1088%2F1367-2630%2F17%2F3%2F035017.
  * MacKay [2003] D.J.C. MacKay.  _Information Theory, Inference and Learning Algorithms_.  Cambridge University Press, 2003.  ISBN 9780521642989.  URL https://books.google.nl/books?id=AKuMj4PN_EMC.
  * Cormen et al. [2009] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein.  _Introduction to Algorithms_.  Computer science. MIT Press, 2009.  ISBN 9780262533058.  URL https://books.google.nl/books?id=aefUBQAAQBAJ.
  * Stephens [2014] Ashley M. Stephens.  Fault-tolerant thresholds for quantum error correction with the surface code.  _Physical Review A_ , 89(2), feb 2014.  doi: 10.1103/physreva.89.022321.  URL https://doi.org/10.1103%2Fphysreva.89.022321.
  * Poulin and Chung [2008] David Poulin and Yeojin Chung.  On the iterative decoding of sparse quantum codes.  _Quantum Information & Computation_, 8(10):987–1000, 2008.  doi: 10.26421/QIC8.10.  URL https://doi.org/10.26421/QIC8.10.
  * Flammia [2017] S. Flammia.  personal communication, 2017.
  * Fowler [2013b] Austin G. Fowler.  Accurate simulations of planar topological codes cannot use cyclic boundaries.  _Physical Review A_ , 87(6), jun 2013b.  doi: 10.1103/physreva.87.062320.  URL https://doi.org/10.1103%2Fphysreva.87.062320.
  * Tuckett et al. [2018] David K. Tuckett, Stephen D. Bartlett, and Steven T. Flammia.  Ultrahigh error threshold for surface codes with biased noise.  _Physical Review Letters_ , 120(5), jan 2018.  doi: 10.1103/physrevlett.120.050505.  URL https://doi.org/10.1103%2Fphysrevlett.120.050505.
  * Fowler et al. [2012] Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg.  Towards practical classical processing for the surface code.  _Physical Review Letters_ , 108(18), may 2012.  doi: 10.1103/physrevlett.108.180501.  URL https://doi.org/10.1103%2Fphysrevlett.108.180501.
  * Delfosse [2014] Nicolas Delfosse.  Decoding color codes by projection onto surface codes.  _Physical Review A_ , 89(1), jan 2014.  doi: 10.1103/physreva.89.012317.  URL https://doi.org/10.1103%2Fphysreva.89.012317.
  * van der Walt et al. [2011] Stéfan van der Walt, S Chris Colbert, and Gaël Varoquaux.  The NumPy array: A structure for efficient numerical computation.  _Computing in Science & Engineering_, 13(2):22–30, mar 2011.  doi: 10.1109/mcse.2011.37.  URL https://doi.org/10.1109%2Fmcse.2011.37.
  * Hagberg et al. [2008] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart.  Exploring network structure, dynamics, and function using networkx.  In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, _Proceedings of the 7th Python in Science Conference_ , pages 11 – 15, Pasadena, CA USA, 2008.  URL https://networkx.github.io/.
  * Jones et al. [2001–] Eric Jones, Travis Oliphant, Pearu Peterson, et al.  SciPy: Open source scientific tools for Python, 2001–.  URL https://scipy.org/.  [Online; accessed 2017-09-01].
  * Hunter [2007] John D. Hunter.  Matplotlib: A 2D graphics environment.  _Computing in Science & Engineering_, 9(3):90–95, 2007.  doi: 10.1109/mcse.2007.55.  URL https://doi.org/10.1109%2Fmcse.2007.55.
  * [47] Seaborn: statistical data visualization.  https://seaborn.pydata.org/.  Accessed: 2017-09-01.
  * Foreman-Mackey et al. [2013] Daniel Foreman-Mackey, David W. Hogg, Dustin Lang, and Jonathan Goodman.  emcee: The MCMC hammer.  _Publications of the Astronomical Society of the Pacific_ , 125(925):306–312, mar 2013.  doi: 10.1086/670067.  URL https://doi.org/10.1086%2F670067.
  * [49] sc_decoding.  https://github.com/bcriger/sc_decoding.


#  _What_ and _How Well_ You Performed? A Multitask Learning Approach to
Action Quality Assessment

Paritosh Parmar Brendan Tran Morris
University of Nevada, Las Vegas
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Can performance on the task of action quality assessment (AQA) be improved by
exploiting a description of the action and its quality? Current AQA and skills
assessment approaches propose to learn features that serve only one task -
estimating the final score. In this paper, we propose to learn spatio-temporal
features that explain three related tasks - fine-grained action recognition,
commentary generation, and estimating the AQA score. A new multitask-AQA
dataset, the largest to date, comprising of 1412 diving samples was collected
to evaluate our approach (https://github.com/ParitoshParmar/MTL-AQA). We show
that our MTL approach outperforms STL approach using two different kinds of
architectures: C3D-AVG and MSCADC. The C3D-AVG-MTL approach achieves the new
state-of-the-art performance with a rank correlation of 90.44%. Detailed
experiments were performed to show that MTL offers better generalization than
STL, and representations from action recognition models are not sufficient for
the AQA task and instead should be learned.

##  1 Introduction

What score should an athlete receive on her dive/gymvault/skating/etc? Which
med student has the highest surgical skill level? How well can he paint or
draw? How is a patient progressing in their physical rehabilitation program?
Answering these questions involves the quantification of the quality of the
action – determining how well the action was carried out, also known as action
quality assessment (AQA).

(a)  Figure 1: Multitask AQA concept. Recognizing an action instance in detail
and verbally describing its good and bad points can be helpful in the process
of quantifying the quality of that action instance. We propose to learn a
model that delineates an action besides measuring its quality. To see the
videos play, please download the manuscript and view in an Adobe Reader.

[autoplay,loop,poster=17,height=0.15]3videos/d4/image_00010030

Existing AQA [18, 16, 26, 13, 25] and skills assessment [4, 10, 31, 32, 33]
approaches use a single label, known as a final score or skill-level, to train
the system using some kind of regression or ranking loss function. However,
the performance of these systems is limited and it seems that a single score
is not sufficient to characterize a complicated action. In AQA, the final
score is dependent on what was done (this determines the difficulty level) and
how was that done (this determines the quality of execution). We pose the
following question: can learning to describe and commentate on the action
instances help improve the performance on the AQA task?

We hypothesize that by forcing the network to learn to do so will help better
characterize the action, and hence aid in AQA. So, rather than using just a
single encompassing quality label to train the network, we introduce a
multitask learning (MTL) approach (Fig. 1a) to assess the quality of an
action. Specifically, we propose to utilize 3D CNN’s to learn spatio-temporal
representations of salient motion and appearance; optimize those using loss
functions which account for i) the action quality score, ii) factorized
(detailed) action classification, and iii) generate a verbal commentary of
performance; and are trained end-to-end. Note that the architectures are
multitask and not multi-modal since the input does not use captions or action
classification to produce the AQA score. Besides straight forward utility for
AQA and action classification, automatic commentary or sports narrative
generation has been viewed valuable and greatly applicable in a recent work by
Yu _et al_. [29].

For AQA tasks, domain experts can provide detailed analysis of performance. In
the professional sports setting, ground truth annotations for detailed action
classification and commentary by former athletes are readily available in
broadcast footage facilitating extraction of labels and descriptive captions.
As such, to evaluate our approach, we introduce the first multitask AQA
dataset with 1412 samples of diving which is also the largest AQA dataset to
date.

Experimental evaluation show that performance of both the architectures
improved as more tasks were added and the C3D-AVG-MTL variant outperforms all
existing AQA approaches in literature. MTL was shown to outperform STL across
various training set sizes. Further experiments explore the AQA-orientedness
of the feature representations learned by our networks and find they
outperform action-recognition representations on unseen actions indicating
that better generalized concepts of quality were learned.

Contributions: primary novelty of this works lies in the problem formulation –
to learn spatio-temporal representations by optimizing networks end-to-end
jointly for fine-grained action description and AQA scoring. Task selection is
intuitive. No previous work has done this; not just for AQA, but even action
recognition and captioning tasks. We release a novel MTL-AQA dataset which is
the largest AQA dataset so far, much more diverse, challenging, and richly
annotated with factorized fine-grained action class and AQA-oriented captions;
can help researchers in the field to examine new ideas for AQA and auxiliary
tasks. We show that our MTL approach works across different architectures. Our
approach is applicable to a wide range of problems. Proposed models are
simple, yet intuitive, and effective in carrying out central idea. Our
C3D-AVG-MTL surpasses all the existing approaches.

Dataset | Events | Height | Genders | # Samples | Events |  | View Variation/
---
Background
Labels
MIT Dive [18] | Individual | 10m Platform | Male | 159 | 1 | No/Same | AQA score
UNLV Dive [16] | Individual | 10m Platform | Male | 370 | 1 | No/Same | AQA score
Ours MTL-AQA |  | Individual,
---
Synchronous
| 3m Springboard,
---
10m Platform
| Male,
---
Female
1412 | 16 | Yes/Different |  | AQA score,
---
Action class,
Commentary
Table 1: Details of our newly introduced dataset, and its comparison with the
existing AQA datasets.

##  2 Related Work

#### AQA:

Pirsiavash _et al_. [18] proposed the use of DFT/DCT of body pose as features
for a support vector regressor (SVR) to map to a final action quality score.
They introduced an action quality dataset containing two actions: Diving and
Figure Skating. However, since their method relied solely on pose features, it
neglected important visual quality cues, like splash in the case of Diving.
Since accurate pose is especially difficult in sports scenarios where athletes
undergo extremely convoluted poses, Venkataraman _et al_. [25] better encoded
using the approximate entropy of the poses to improve the results.

More recently, spatio-temporal features from 3D convolutional neural networks
(C3D) [24] proved to be very successful on a related task of action
recognition since they captured appearance and salient motion. Seeing this as
a desirable property that would help to take into account visual cues, Parmar
and Morris [16] proposed using C3D features for AQA. They proposed three
frameworks, C3D-SVR, C3D-LSTM, and C3D-LSTM-SVR, which differed in their
feature aggregation and regression scheme. All the frameworks worked better
than previous models proving the efficacy of C3D features for AQA. Xiang _et
al_. [26] proposed breaking video clips into action specific segments and
fusing segment-averaged features instead of over full videos. By adding finer
segment labels to data samples performance was improved. Li _et al_. [13]
divide a sample into 9 clips and use 9 different C3D networks dedicated to
different stags of Diving. Features are concatenated and further processed
through conv and fc layers to produce a final AQA score using a ranking loss
along with the more typical L2 loss. Xu _et al_. [27] tackle AQA for longer
action sequences using self-attentive and multiscale convolutional skip LSTM.

#### Skills assessment:

Zia _et al_. [33] extract spatio-temporal interest points (STIP’s) in the
frequency domain to classify a sample into novice, intermediate or expert
skills level. Instead of using handcrafted STIP’s Doughty _et al_. [4] learn
and use convolutional features with ranking loss as their objective function
to evaluate surgical, drawing, chopstick use and dough rolling skills. In
their subsequent work [5], they use temporal attention. Li _et al_. [14], make
use of spatial attention in the assessment of hand manipulation skills.
Bertasius _et al_. [1] focus on measuring basketball skills but rely only on
assessment of a single basketball coach making their dataset subjective to a
particular evaluator.

All of the existing AQA and skills assessment frameworks are single task
models and only give the final AQA score. Our proposed framework is a
multitask model to recognize the action, measures its quality and also
generates captions (or commentary).

#### Multi-modal approaches and captioning:

Images and videos (especially sports) are often accompanied by a caption or
commentary which can themselves serve as labels yet to be exploited for AQA or
skill assessment. Quattoni _et al_. [19] use large quantities of unlabeled
images, with associated captions, to learn image representations. They found
that this sort of pre-training with extra information could speed up the
learning on a target task. Rather than using captions as groundtruth labels,
Sonal _et al_. [6] treated captions as a “view” and use them along with images
to learn a classifier using co-training. They again used commentary as a
“view” for action recognition with success. To train an activity classifier in
an automated fashion, without the requirement of any manual labeling, Sonal
and Mooney [7] make use of broadcast closed captions and used the system for
video retrieval. There are a few works which focus on captioning in sports
settings. Yu _et al_. [29] address the task of generating fine-grained video
descriptions for basketball and evaluate performance using their novel metric.
Commentary generation in cricket has been addressed in [20, 21], while
Sukhwani addressed the problem of describing tennis videos in [23]. While
these works focus on captioning or improving captioning, we integrate a
captioning task with an AQA task to provide stronger supervision as commentary
is a verbal description of AQA.

##  3 Multitask AQA Dataset

Position | Armstand |  | Rotation type
---
# SS | # TW
| Free
---
Tuck
Pike
| No
---
Yes
| Inward
---
Reverse
Backward
Forward
0 to 4.5 | 0 to 3.5
Table 2: Classification of dives. Each combination of the presented sub-fields
produces a different kind of maneuver.

In order to facilitate research in the area of AQA, we release a new dataset.
This is the first of a kind multitask AQA dataset. With 1412 samples, it is
the largest AQA dataset to date. This particular dataset focuses only on
Diving as it has seen the most usage recently. Data was compiled from 16
different events unlike the single main event (2012 Olympics Men’s 10m
Platform Diving competition) used for previous datasets [18, 16] to provide
significantly more variation. Diving samples in the new dataset were collected
from various International competitions and include the 10m Platform as well
as 3m Springboard, include both male and female athletes, individual or pairs
of synchronized divers, and different views. A comparison of our new dataset
with existing Diving AQA datasets is provided in Table 1.

Since data was collected from televised international events, before the
athletes perform their routines, information regarding their routine is
displayed. This information includes the difficulty of the dive and a
description of the dive. The AQA score is extracted from the judges’ scores
after the dive completion. The dataset uses the same dive classification
strategy as Nibali _et al_. [15], where instead of using dive number
(equivalent to an action class in action recognition) directly, we factorize a
dive into its components such as the position of the dive, the number of
somersaults (SS), and number of twists (TW). Full details for the dive
classification is in Table 2.

Further, during and after a diving routine, television analysts provide
commentary. These analysts are often retired athletes and have deep
understanding of the sport. This verbal account of the athlete’s performance
is recorded for the third type of action label. The commentary was considered
an important indicator for performance since it was the only way to “watch” an
event before telecast was available. Commentators say what the athlete
performed, what was correct with the athlete’s performance, and where and how
athletes made mistakes. This provides deeper insight into the athlete’s
performance and can help an average person better understand the sport. We
used Google’s Speech-To-Text API to convert commentary audio to text.

##  4 Multitask Approach to AQA

MTL is a machine learning paradigm in which a single model caters to more than
a single task. An example is to recognize road signs, roads, and vehicles
together while an STL approach would require separate models for each object
type. MTL tasks are generally chosen such that they are related to one another
and their networks have a common body that branches into task-specific heads.
The total network loss is the sum of individual task losses. When optimized
end-to-end, the network is able to learn richer representation in the common
body section since it must be able to serve/explain all tasks. With the use of
related auxiliary tasks, which are complementary to the main task, the richer
representation tends to help improve performance on the main task.

In general, not just for diving, action quality is a function of _what_ action
was carried out and how well that action was executed. This makes the choice
of auxiliary tasks natural: detailed action recognition is the answer to the
‘what’ part and commentary, being a verbal description containing good and bad
points about action execution, is an answer to the ‘how well’ part. AQA can be
thought of as finding a function that maps input video to the AQA scores.
Caruana in [2] views supervision signals from auxiliary tasks as an inductive
bias (assumptions). Inductive bias can be thought of as constraints that
restrict the hypothesis/search space when finding the AQA function. Through
inductive biases, MTL provides improved generalization as compared STL [2].

In this work, the main task is to assess the action quality (AQA score) and
the auxiliary tasks are to recognize the action (dive type classification) and
to generate descriptive captions/commentary. Action recognition in turn
consists of five fine-grained dive sub-recognition tasks: recognizing position
and rotation type, detecting armstand, and counting somersaults and twists.

First, let us formalize the settings and objective functions. AQA is a
regression problem where, generally, the Euclidean distance between the
predicted quality score and the ground truth is used as the objective function
to be minimized [16, 26, 13]. Initial experimentation found that using L1
distance in addition to L2 yielded better results on the AQA task

$\mathcal{L}_{AQA}=-\frac{1}{N}\sum_{i=1}^{N}(x_{i}-y_{i})^{2}+|x_{i}-y_{i}|$
(1)

where $x_{i}$ is the predicted score and $y_{i}$ is the ground truth score for
each of the $N$ samples. For action recognition, we use cross-entropy loss
between the predicted labels and ground truth label

$\mathcal{L}_{Cls}=-\frac{1}{N}\sum_{i=1}^{N}\sum_{sa}\sum_{j=1}^{k_{sa}}y^{sa}_{i,j}log(x^{sa}_{i,j})$
(2)

where $k_{sa}$ is the number of categories in sub-action class $sa$ (as in
Table 2). Negative log likelihood is used as the loss function for the
captioning task

$\mathcal{L}_{Cap}=-\frac{1}{N}\sum_{i=1}^{N}\sum_{sl}ln({x^{cap}}_{y^{cap}})$
(3)

with $sl$ is the sentence length. The overall objective function to be
minimized is the summation of all the losses

$\mathcal{L}_{MTL}=\alpha\mathcal{L}_{AQA}+\beta\mathcal{L}_{AR}+\gamma\mathcal{L}_{Cap}.$
(4)

where $\alpha,\beta,\gamma$ are loss the weights. Now, we will introduce two
different architectures for MTL-AQA.

#### MTL-AQA architectures

Unlike action recognition that may be accomplished by looking at as little
evidence as just a single frame [11], for AQA the complete action sequence
needs to be considered because the athlete can make or lose points at any
point during the whole sequence.

While spatio-temporal representations learnt using 3D CNN’s capture appearance
and salient motion patterns [24], which makes them one of the best candidates
for action recognition [24, 8] and also for AQA [16, 26, 13], 3D CNN’s require
large memories which limits their application to small clips. We tackle this
bottleneck in two ways:

  1. 1.

divide the video (96 frames) into small clips (16 frames), and then aggregate
clip-level representations to obtain video-level description (Sec. 4.1)

  2. 2.

downsample the video into a small clip (Sec. 4.2)

Networks designed for multitask learning generally two segments: common
network backbone and task-specific heads. Common network backbone learns
shared representations, which are then further processed through task-specific
heads to obtain more task-oriented features and outputs.

###  4.1 Averaging as aggregation (C3D-AVG)

Figure 2: C3D-AVG-MTL network.

The first network we present is C3D-AVG (Fig. 2).
Network backbone: Backbone consists of C3D network [24] up to the fifth
pooling layer.
Aggregation scheme: An athlete gathering (or losing) points throughout the
action can be seen as an addition operation. Combining this perspective with a
good rule of thumb that when good representations are learned, linear
operations on them become meaningful, we propose to enforce a linear
combination of representations to be meaningful, in order to learn good
representations. Specifically, we propose to use averaging as the linear
combination. The network is optimized end-to-end for all three tasks.

C3D-AVG network up to Average layer can be considered as an encoder, which
encodes input video-clips into representations that when averaged (in feature
space) would correspond to the total AQA points gathered by the athlete.
Subsequent layers can be thought of decoders for individual tasks.
Task-specific heads: For action-recognition and AQA tasks, clip-level pool-5
features are averaged element-wise to yield a video-level representation.
Since captioning is a sequence-to-sequence task, the individual clip-level
features are input to the captioning branch before averaging (individual clip-
level features worked better in practice than averaged clip-level features for
captioning).

###  4.2 Multiscale Context Aggregation with Dilated Convolutions (MSCADC)

Multiscale context aggregation with dilated convolutions (MSCADC) [28] has
been shown to improve the classification of dives in the work of Nibali _et
al_. [15]. Given its strong performance on an auxiliary task MSCADC was
selected for MTL. Our MTL variant network has a backbone and multiple heads as
illustrated in Table 3.
Network backbone:  The MSCADC network is based on C3D network [24] and
incorporates improvements like using Batch Normalization [9] to provide better
regularization which is needed in AQA where data is quite limited.
Additionally, pooling is removed from the last two convolutional groups of C3D
and instead a dilation rate of 2 is used. This backbone structure is shared
among all the MTL tasks.
Task-specific heads:  We use separate heads, one for each task. Heads consist
of a context net followed by a few additional layers. The context net is where
the feature maps are aggregated at multiple scales.

Dilated convolutions and multi-scale aggregation have shown improvements in
the tasks involving dense predictions [28]. We believe that removing pooling
layers and using dilated convolutions better maintains the structure of the
diving athlete without losing resolution. This helps in better assessment of
the athlete’s pose which is critical for AQA. For example, pose can identify
when legs are aligned or split which is useful not only for diving but also
other sports such as gymnastic vault, figure skating, skiing, snowboarding,
etc.

Unlike the C3D-AVG network, we downsample the complete action into a short
sequence of only 16 frames (something like key action snapshots) as done by
Nibali _et al_. [15]. This reduces our 96-frames videos into key action
snapshots which helps in processing the complete action sequence in a single
pass. Processing an action sequence using this network can be thought of as
distilling information from the input frames and putting it into feature maps,
with different feature maps containing different kinds of pose information. A
natural benefit of downsampling the sequence is that there is a significant
reduction in the the number of network parameters and memory which can be used
instead to increase spatial resolution.

| (Common network body) |
---|---|---
[HTML]FFFFFF |  [HTML]ECF4FFC3(32); BN |
[HTML]FFFFFF |  [HTML]ECF4FFMP(1,2,2) |
[HTML]FFFFFF |  [HTML]ECF4FFC3(64); BN |
[HTML]FFFFFF |  [HTML]ECF4FFMP(2,2,2) |
[HTML]FFFFFF |  [HTML]ECF4FF{C3(128); BN} x2 |
[HTML]FFFFFF |  [HTML]ECF4FFMP(2,2,2) |
[HTML]FFFFFF |  [HTML]ECF4FF{C3(256); BN} x2 |
[HTML]FFFFFF |  [HTML]ECF4FF{C3(d=2,256); BN} x2 |
[HTML]FFFFFF |  [HTML]ECF4FFDropout(0.5) |
| (Task-specific heads) |
[HTML]FBE8E7 | (AQA Score
---
Head)
[HTML]EDFFED | (Action
---
recognition Head)
[HTML]D4F5FF | (Captioning
---
Head)
[HTML]FBE8E7C1(12) |  [HTML]EDFFEDC1(12) |  [HTML]D4F5FFC1(12)
[HTML]FBE8E7{Cntxt net} |  [HTML]EDFFED{Cntxt net} |  [HTML]D4F5FF{Cntxt net}
[HTML]FBE8E7MP(2,2,2) |  [HTML]EDFFEDMP(2,2,2) |  [HTML]D4F5FFMP(2,2,2)
[HTML]FBE8E7C3(12); BN |  [HTML]EDFFEDC3(12); BN |  [HTML]D4F5FFC3(12); BN
[HTML]FBE8E7C3(1) |  [HTML]EDFFED |  [HTML]D4F5FFEnc. GRU
[HTML]FBE8E7AP(2,11,11) | [HTML]EDFFED  (Action recognition sub-heads) |  [HTML]D4F5FFDec. GRU
Table 3: MSCADC-MTL architecture. C3(d,ch): 3D convolutions, ch-no. of
channels, d-dilation rate. C1: 1 $\times$ 1 $\times$ 1 convolutions. BN: batch
normalization. MP(kr): max pooling operation, kr-kernel size. Cntxt net:
context net for multi-scale context aggregation. AP: average pooling across (2
$\times$ 11 $\times$ 11) volume.

##  5 Experiments

#### Implementation:

PyTorch [17] is used to implement all the networks; common network backbones
were pretrained on the UCF101 [22] action recognition dataset. The captioning
module utilized a GRU [3] cell and a dropout rate of 0.2 in the encoder and
decoder. Maximum caption length is set to 100 words. Full vocabulary size is
5779. The parameters $\alpha$, $\beta$, and $\gamma$ in Eq. 4 are set to 1, 1,
and 0.01. All networks used the Adam optimizer [12] and were trained for 100
epochs with initial learning rate of 1e-4. Data augmentation is performed
through center cropping with temporal augmentation and random horizontal
flipping. The center crop was found to reliably capture both the athlete and
other prominent visual cues such as splash. Batch-size was set to three
samples. Additional architecture-specific implementation details are as
follows:
C3D-AVG: The model is trained end-to-end with a $112\times 112$ center crop
from the $171\times 128$ pixel input video. Each dive sample was temporally
normalized to a length of 96 frames.
MSCADC: Since this architecture does not contain fully-connected layers and
all videos are downsampled to 16 frames, there are fewer model parameters
allowing the use of higher resolution video input. Frames are resized to
$640\times 360$ pixels and $180\times 180$ center cropping is used.
Evaluation metrics: AQA is assessed using Spearman’s rank correlation, dive
classification uses accuracy, and commentary uses captioning metrics of Bleu,
Meteor, Rouge, and CIDEr.

###  5.1 Single-task vs. Multi-task approach

Tasks |  | C3D-AVG
---
| MSCADC
---
AQA | 89.60 | 84.72
\+ Cls | 89.62 | 85.76
\+ Caps | 88.78 | 85.47
\+ Cls + Caps | 90.44 | 86.12
Table 4: STL vs. MTL across different architectures. Cls - classifiction, Caps
- captioning. First row shows STL results, while the remaining rows show MTL
results.

We carry out an experiment to compare the performance of STL against that of
MTL. We have a total of 3 tasks: AQA, detailed action recognition, and
commentary generation. This experiment first considered the STL approach to
AQA task and then measured the effect of including auxiliary tasks. The
evaluation is summarized in Table 4. We observe that MTL approaches perform
better than STL approach for both the networks, which shows that our MTL
approach is not limited to a network but is generalizable across networks.
Other thing to note here is that MTL performance improves as we incorporate
more tasks. Comparing both the architectures, we find that our C3D-AVG
outperforms our MSCADC for both STL and MTL, while MSCADC has the advantage of
being fast and lower memory requirement than C3D-AVG. For qualitative results,
refer to Table 7 and supplementary material.

Method | Sp. Corr.
---|---
Pose+DCT [18] | 26.82
C3D-SVR [16] | 77.16
C3D-LSTM [16] | 84.89
Ours MSCADC-STL | 84.72
Ours C3D-AVG-STL | 89.60
Ours MSCADC-MTL | 86.12
Ours C3D-AVG-MTL | 90.44
Segment-specific methods (train/test on UNLV Dive [16])
S3D (best performing in [26]) | 86.00
Li _et al_. [13] | 80.09
Ours MSCADC-STL | 79.79
Ours C3D-AVG-STL | 83.83
Ours MSCADC-MTL | 80.60
Ours C3D-AVG-MTL | 88.08
Table 5: Performance comparison with the existing AQA approaches.

|  Nibali _et al_. [15] | Ours-MTL
---|---|---
| MSCADC | C3D-AVG
Position | 74.79 | 78.47 | 96.32
Amstand | 98.30 | 97.45 | 99.72
Rotation type | 78.75 | 84.70 | 97.45
# Somersaults | 77.34 | 76.20 | 96.88
# Twists | 79.89 | 82.72 | 93.20

Model | B1 | B2 | B3 | B4 | M | R | C
---|---|---|---|---|---|---|---
C3D-AVG | 0.26 | 0.10 | 0.04 | 0.02 | 0.11 | 0.14 | 0.06
MSCADC | 0.25 | 0.09 | 0.03 | 0.01 | 0.11 | 0.13 | 0.05

Table 6: Performance on auxiliary tasks.

[loop,autoplay,poster=17,height=0.1]3clip2/22/029 |  GT labels: 89.08; [Tuck, No, Backwards, 3.5, 0]
---|---
C3D-AVG labels: 80.41; [Tuck, No, Backwards, 3.5, 0]
MSCADC labels: 85.09; [Pike, No, Backwards, 2.5, 0]
GT Caps: Games but that shoulder issue it’s not even paddling with that arm I
hope he hasn’t done something serious here and I think he has he looks even he
is struggling he is in trouble and this is most concerning his hope he hasn’t
suffered a little dislocation there he’s managed to get himself up onto the
pool edge that looks like a dislocation to me what a way to end that’s not the
case but he’s in trouble
C3D-AVG Caps: that’s good she will certainly keep that with a dive that we can
certainly do it in that field very impressive it is very good but it was a
good dive here playing a little bit low water which is a strong start one look
at that closes vertical position it’s gonna get seven and a half’s I think
super slow-motion just throwing up a little bit too much splash but she’ll get
over 60s mid sixties probably and that will be good enough to keep her middle
of the pack which is where she needs to be to
|  MSCADC Caps: well that’s a really good dive from her Cheung just last night
for that the dive and over she goes die are faltering and a good takeoff if
she gets her feet are so she drills she’s feet up and then she goes into the
water with her chin on the end of the diving board on the end of the diving
board squeezing into the Tuck shape as tight as you can see here we are here’s
the one and a half twist into the pike and that makes it down there have a lot
[loop,autoplay,poster=17,height=0.1]3clip2/38/029 |  GT labels: 63.07; [Free, Yes, Backwards, 2, 2.5]
C3D-AVG labels: 65.79; [Free, Yes, Backwards, 2, 1.5]
MSCADC labels: 63.23; [Free, Yes, Backwards, 2, 1.5]
GT Caps: it’s beautiful our balance he is cranked the start a little bit too
much he giving too much beans and could not stop that rotation it’s a tricky
dive to do it many times it’s just a real pain because you’ve got so many
twists to do to get in with a rotation it’s very easy to over rotate that’s
exactly what Mitchum’s done he is lagging behind now this could prove to be
critical dropped another 12
C3D-AVG Caps: well it’s okay and the entry into the water not quite 100%
vertical but he’s just a little bit overcooked on the end obviously there’s a
few of the divers have you use themselves so if you’re getting your hands out
there we are rocking and rolling a little bit of a splash with technically a
little bit of splash that’s not the splash means that the judges will penalize
him or only got to 17 from the two and a half somersaults before he goes into
the water now that was a
|  MSCADC Caps: well that’s a really good dive yeah it’s a good dive from
enough so she needed to be faltering she knows to go in her hair it’s a
difficult dive to finish in the business end of the field and away in the pike
position this is the reverse two and a half there she didn’t get around but
instead of she goes wrong with her hands on I think she has done very well I’m
not surprised as Paul Espinoza she gets around the 310 mark maybe yeah she
will do well do
[loop,autoplay,poster=17,height=0.1]3clip2/68/029 |  GT labels: 84.15; [Tuck, No, Backwards, 3.5, 0]
C3D-AVG labels: 81.94; [Tuck, No, Backwards, 3.5, 0]
MSCADC labels: 87.04; [Tuck, No, Backwards, 3.5, 0]
GT Caps: states very good seventy nine point two for the dive last night
brings a smile to the US coaching staff great height off the platform so he’s
already threw his first somersault before he passes it on the way down give
yourself time to get the entry angle just right which he did started off as a
swimmer and said that to switch to diving because he looked more fun having a
bit more fun
C3D-AVG Caps: excellent excellent dive if you might he’s got a lot of divers
here with their hands together for him a lot of them here and take a little
bit of an angle on the entry that does good through that would not quite a way
over a vertical look at that perfect angle so much better judges will like
that that angle so not too many
|  MSCADC Caps: well that’s a really good dive yeah it’s a good dive from
marginally short she goes in but it’s not going to get more than a couple of
those three point seven as you can see here we are here’s to show diving
consistently and here but she didn’t falter but she had enough mediocre dives
on the dive you need to be doing the back of the head there you know you need
to flick it and then just about that toes on the head on this dive is there
when you know the competition’s are coming from
[loop,autoplay,poster=17,height=0.1]3clip2/71/029 |  GT labels: 47.77; [Pike, No, Forwards, 2.5, 1]
C3D-AVG labels: 53.04; [Pike, No, Forwards, 2.5, 1]
MSCADC labels: 67.98; [Pike, No, Backwards, 2.5, 0]
GT Caps: final but she has benefited from the experience and again another
diver going a long long way down the pool and away from the platform yeah just
it’s the technique if you haven’t got the right timing on the jump and
momentum of the run down the board just drags you forward high score so far is
46 there we
C3D-AVG Caps: nice nice entry because the execution was fine and then just
suggesting she went surfing over the end of the diving board anyway she’s a
safe distance from the diving board so that’s a good dive in the prelims you
can see the splash moving away from the diving board six and a half’s sevens
at best moving further away from the podium dive after dive star with a 58 and
it with a 64 this
|  MSCADC Caps: well that’s a busy dive finish from the end but she certainly
was better than the three point three she didn’t really attack she was her
fourth round dive she knows too far away from the diving board squeezing into
the Tuck shape just bending at a little bit too early they’re short of
vertical an injury little bit too much splash but she’ll be lucky by the toes
on the water the divers would have been that towel on the end of the divers do
that the divers would have touched the scoreboard but I think she’s gonna

Table 7: Qualitative results. Labels are ordered as follows: AQA score;
[Position, Armstand?, Rotation type, #SS, #TW].

Next, we compare our models with the existing methods in Table 5. We obtain
the results for all of the existing methods on our dataset. C3D-SVR was the
best performing method in [16] but it does not seem to benefit from the
increased number of training samples. In [16], C3D-LSTM was reported to be
performing worse than C3D-SVR due to insufficient amount of training data and
does outperform C3D-SVR with the expanded training data. Our MSCADC-STL works
better than most of the existing methods, whereas our C3D-AVG-STL is better
performing than all the existing methods. Furthermore, C3D-AVG-MTL with 90.44%
correlation achieves new state-of-the-art results.

Method proposed by Xiang _et al_. [26] requires manual annotation to mark end
points of all the segments which is not available in the new Diving-MTL data.
Xiang _et al_. [26] used the UNLV-Dive dataset [16] so for a fair comparison
with [26] we train and test our models on UNLV-Dive [16]. The results are
enumerated in Table 5. Our C3D-AVG-STL does not perform as well S3D [26].
However, our C3D-AVG-MTL outperforms the S3D model. An important thing to note
here is that UNLV-Dive dataset is quite a bit smaller than our newly
introduced MTL-AQA dataset which should limit MTL performance. However, as
pointed out in Section 4, MTL provides better generalization than STL, which
allows C3D-AVG-MTL to learn effectively from fewer training samples.

Performance on the auxiliary tasks is presented in Table 6. To the best of our
knowledge there is only one work (by Nibali _et al_. [15]) on detailed dive
classification. Our C3D-AVG-MTL performed best on the classification task as
well. We also give captioning metrics for the two networks though there is no
baseline for comparison in literature.

# samples | 1059 | 450 | 280 | 140
---|---|---|---|---
STL | 89.60 | 77.27 | 69.63 | 64.17
MTL | 90.44 | 83.52 | 72.09 | 68.16
Table 8: STL vs. MTL generalization. Training using increasingly reduced no.
of training samples.

#### Generalization provided by MTL:

To ascertain that MTL is providing more generalization, we train our C3D-AVG-
STL and C3D-AVG-MTL models using fewer number of datapoints. Train set size
and the corresponding STL/MTL performances are detailed in Table 8. We see
that MTL consistently outperforms STL, and also the gap seems to widen with
fewer training samples.

###  5.2 AQA-orientedness of the learned
representations

| c1 | c2 | c3 | c4 | c5
---|---|---|---|---|---
Baseline-1 | 71.01 | 71.39 | 73.13 | 76.34 | 73.69
Baseline-2 | 72.43 | 70.15 | 70.35 | 57.20 | 37.63
C3D-AVG-MTL | 74.26 | 77.95 | 82.78 | 86.18 | 85.75
Table 9: Performance of fitting linear regressors on the activations of all the convolutional layers. | c1 | c2 | c3 | c4 | c5
---|---|---|---|---|---
Train/Test events overlapping
Baseline-1 | 41.10 | 32.06 | 36.53 | 46.86 | 44.78
Baseline-2 | 37.76 | 42.02 | 37.98 | 44.28 | 38.56
C3D-AVG-MTL | 38.32 | 42.68 | 45.53 | 49.18 | 38.47
| Train/Test events non-overlapping
---
(requires more generalization)
Baseline-1 | -02.68 | 00.75 | -03.91 | -02.22 | 03.17
Baseline-2 | -07.52 | -02.44 | 05.07 | 24.09 | 25.80
C3D-AVG-MTL | -07.75 | -02.77 | 23.51 | 29.56 | -03.25
Table 10: Performance of fitting linear regressors on the activations of all
the convolutional layers for a novel action class, Gymnastic vault. Top rows:
Within-dataset evaluation, bottom rows: Out-of-dataset evaluation.

We trained our networks end-to-end to learn AQA-specific feature
representation rather than relying on pretrained action-recognition oriented
features (as done in [16]). However, we question if there is a utility in
learning AQA-specific feature representation or are action-recognition
oriented features equally good? To answer this, we follow an evaluation scheme
similar to Zhang _et al_. [30], where we train linear regressors on top of all
the convolutional layers, and compare the performance obtained for AQA and
action-recognition models. In particular, we consider two action-recognition
baselines: C3D model trained on UCF-101 dataset [22] (Baseline-1), and our
model trained on our MTL-AQA dataset, but for factorized action recognition
task (Baseline-2).

In the primary evaluation, we compare the representations for measuring the
quality of diving action. Comparison is detailed in Table 9. In comparison to
both the baselines, we find that our C3D-AVG-MTL learns better representations
at all the intermediate layers.

Further we compare the representations for measuring the quality of an unseen
action class – Gymnastic vault [16]. This helps in estimating the
generalizability of the representations. We hypothesize that if our AQA
network has learned better representations that actually capture the concept
of _quality_ in an action, then it should be able to measure the quality of an
unseen action better than action-recognition specific networks. We carry out 2
different evaluations: 1) Within-dataset evaluation and 2) Out-of-dataset
evaluation. In Within-dataset evaluation we randomly divide the samples into
train set and test set, whereas in Out-of-dataset evaluation, train and test
samples are drawn from different athletic competitions. Out-of-dataset
evaluation is more challenging and requires feature representations to be more
generalizable and not suffer from dataset-bias. Like the previous experiment,
to compare learned representations, we train linear regressors on top of all
the convolutional layers. Train and test sets consist of 125 and 56 samples
respectively. Results from both evaluations are presented in Table 10.

In the Within-dataset evaluation, the representations learned by all the
models seem to be working well, although C3D-AVG-MTL performs best. The
difference in performance becomes clearer in the Out-of-dataset evaluation. As
expected, Out-of-dataset evaluation is more challenging and performances of
all the models drop. However, the performances of Baseline-2 and our model
drop more gracefully.

##  6 Discussion

We introduced a multitask learning approach to AQA and showed that MTL
performs better than STL because of better generalization which is especially
important in AQA and skill assessment since datasets are small. We showed that
the representations learned by our MTL models are better able to capture the
inherent concept of quality of actions. Our approach is scalable since the
supervision required for the auxiliary tasks is readily available from the
existing video footage with minimal extra effort compared to just AQA
labeling. In addition, state-of-the-art performance was achieved without any
finetuning of hyperparameters. Our best performing and recommended model,
C3D-AVG-MTL, achieved 90.44% correlation with judged scores which still leaves
a small gap to achieve human-experts-level performance (96% [18]).

#### Extension to other actions and skills assessment:

Although this paper is geared specifically toward multitask diving AQA, the
approach is general in nature. No design decisions were biased towards or
specific to the diving tasks. Experiments even showed that the models trained
on diving do work reasonably well for another action, gymnastic vault. This
encouraging result hints at the direct application of our MTL approach on
other actions and everyday skills assessment. Commentary and action class
details are available almost all the of time in the sport footages. For non-
sport skills assessment, such as surgery, needle passing, drawing, or
painting, experts could be used to generate comments and definition of sub-
actions for classification. Note that existing datasets can simply be
augmented to include additional labels, instead of building new datasets from
scratch. Also, our MTL approach is complementary to the existing AQA and
skills assessment approaches.

#### Acknowledgements:

We would like to thank Andy Squadra, Mark Wilbourne, Josh Rana for helping us
with the dataset collection.

## References

  * [1] Gedas Bertasius, Hyun Soo Park, X Yu Stella, and Jianbo Shi.  Am i a baller? basketball performance assessment from first-person videos.  In Computer Vision (ICCV), 2017 IEEE International Conference on, pages 2196–2204. IEEE, 2017.
  * [2] Rich Caruana.  Multitask learning.  Machine learning, 28(1):41–75, 1997.
  * [3] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  arXiv preprint arXiv:1406.1078, 2014.
  * [4] Hazel Doughty, Dima Damen, and Walterio Mayol-Cuevas.  Who’s better? who’s best? pairwise deep ranking for skill determination.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [5] Hazel Doughty, Walterio Mayol-Cuevas, and Dima Damen.  The pros and cons: Rank-aware temporal attention for skill determination in long videos.  arXiv preprint arXiv:1812.05538, 2018.
  * [6] Sonal Gupta, Joohyun Kim, Kristen Grauman, and Raymond Mooney.  Watch, listen & learn: Co-training on captioned images and videos.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 457–472. Springer, 2008.
  * [7] Sonal Gupta and Raymond Mooney.  Using closed captions to train activity recognizers that improve video retrieval.  In Proceedings of the CVPR-09 Workshop on Visual and Contextual Learning from Annotated Images and Videos (VCL), Miami, FL, June 2009.
  * [8] Kensho Hara, Hirokatsu Kataoka, and Yutaka Satoh.  Can spatiotemporal 3d cnns retrace the history of 2d cnns and imagenet?  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6546–6555, 2018.
  * [9] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International Conference on Machine Learning, pages 448–456, 2015.
  * [10] Hassan Ismail Fawaz, Germain Forestier, Jonathan Weber, Lhassane Idoumghar, and Pierre-Alain Muller.  Evaluating surgical skills from kinematic data using convolutional neural networks.  In International Conference On Medical Image Computing and Computer Assisted Intervention (MICCAI), 2018.
  * [11] Andrej Karpathy, George Toderici, Sanketh Shetty, Thomas Leung, Rahul Sukthankar, and Li Fei-Fei.  Large-scale video classification with convolutional neural networks.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 1725–1732, 2014.
  * [12] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [13] Yongjun Li, Xiujuan Chai, and Xilin Chen.  End-to-end learning for action quality assessment.  In Pacific Rim Conference on Multimedia, pages 125–134. Springer, 2018.
  * [14] Zhenqiang Li, Yifei Huang, Minjie Cai, and Yoichi Sato.  Manipulation-skill assessment from videos with spatial attention network.  arXiv preprint arXiv:1901.02579, 2019.
  * [15] Aiden Nibali, Zhen He, Stuart Morgan, and Daniel Greenwood.  Extraction and classification of diving clips from continuous video footage.  In Computer Vision and Pattern Recognition Workshops (CVPRW), 2017 IEEE Conference on, pages 94–104. IEEE, 2017.
  * [16] Paritosh Parmar and Brendan Tran Morris.  Learning to score olympic events.  In Computer Vision and Pattern Recognition Workshops (CVPRW), 2017 IEEE Conference on, pages 76–84. IEEE, 2017.
  * [17] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  2017\.
  * [18] Hamed Pirsiavash, Carl Vondrick, and Antonio Torralba.  Assessing the quality of actions.  In European Conference on Computer Vision, pages 556–571. Springer, 2014.
  * [19] Ariadna Quattoni, Michael Collins, and Trevor Darrell.  Learning visual representations using images with captions.  In Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE Conference on, pages 1–8. IEEE, 2007.
  * [20] Ashish Sharma, Jatin Arora, Pritam Khan, Sidhartha Satapathy, Sumit Agarwal, Satadal Sengupta, Sankarshan Mridha, and Niloy Ganguly.  Commbox: Utilizing sensors for real-time cricket shot identification and commentary generation.  In Communication Systems and Networks (COMSNETS), 2017 9th International Conference on, pages 427–428. IEEE, 2017.
  * [21] Rahul Anand Sharma, K Pramod Sankar, and CV Jawahar.  Fine-grain annotation of cricket videos.  In Pattern Recognition (ACPR), 2015 3rd IAPR Asian Conference on, pages 421–425. IEEE, 2015.
  * [22] Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah.  Ucf101: A dataset of 101 human actions classes from videos in the wild.  arXiv preprint arXiv:1212.0402, 2012.
  * [23] Mohak Kumar Sukhwani.  Understanding and Describing Tennis Videos.  PhD thesis, International Institute of Information Technology Hyderabad, 2016.
  * [24] Du Tran, Lubomir Bourdev, Rob Fergus, Lorenzo Torresani, and Manohar Paluri.  Learning spatiotemporal features with 3d convolutional networks.  In Proceedings of the IEEE international conference on computer vision, pages 4489–4497, 2015.
  * [25] Vinay Venkataraman, Ioannis Vlachos, and Pavan K Turaga.  Dynamical regularity for action analysis.
  * [26] Xiang Xiang, Ye Tian, Austin Reiter, Gregory D Hager, and Trac D Tran.  S3d: Stacking segmental p3d for action quality assessment.  In 2018 25th IEEE International Conference on Image Processing (ICIP), pages 928–932. IEEE, 2018.
  * [27] Chengming Xu, Yanwei Fu, Bing Zhang, Zitian Chen, Yu-Gang Jiang, and Xiangyang Xue.  Learning to score the figure skating sports videos.  arXiv preprint arXiv:1802.02774, 2018.
  * [28] Fisher Yu and Vladlen Koltun.  Multi-scale context aggregation by dilated convolutions.  arXiv preprint arXiv:1511.07122, 2015.
  * [29] Huanyu Yu, Shuo Cheng, Bingbing Ni, Minsi Wang, Jian Zhang, and Xiaokang Yang.  Fine-grained video captioning for sports narrative.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [30] Richard Zhang, Phillip Isola, and Alexei A Efros.  Colorful image colorization.  In European Conference on Computer Vision, pages 649–666. Springer, 2016.
  * [31] Aneeq Zia and Irfan Essa.  Automated surgical skill assessment in rmis training.  International journal of computer assisted radiology and surgery, 13(5):731–739, 2018.
  * [32] Aneeq Zia, Yachna Sharma, Vinay Bettadapura, Eric L Sarin, and Irfan Essa.  Video and accelerometer-based motion analysis for automated surgical skills assessment.  International journal of computer assisted radiology and surgery, 13(3):443–455, 2018.
  * [33] Aneeq Zia, Yachna Sharma, Vinay Bettadapura, Eric L Sarin, Thomas Ploetz, Mark A Clements, and Irfan Essa.  Automated video-based assessment of surgical skills for training and evaluation in medical schools.  International journal of computer assisted radiology and surgery, 11(9):1623–1636, 2016.