# Approximate symmetries of Hamiltonians

Christopher T. Chubb1 and Steven T. Flammia1,2
1Centre for Engineered Quantum Systems, University of Sydney, Sydney, NSW,
Australia.
2Center for Theoretical Physics, Massachusetts Institute of Technology,
Cambridge, MA, USA.

###### Abstract

We explore the relationship between approximate symmetries of a gapped
Hamiltonian and the structure of its ground space. We start by considering
approximate symmetry operators, defined as unitary operators whose commutators
with the Hamiltonian have norms that are sufficiently small. We show that when
approximate symmetry operators can be restricted to the ground space while
approximately preserving certain mutual commutation relations. We generalize
the Stone-von Neumann theorem to matrices that _approximately_ satisfy the
canonical (Heisenberg-Weyl-type) commutation relations, and use this to show
that approximate symmetry operators can certify the degeneracy of the ground
space even though they only approximately form a group. Importantly, the
notions of “approximate” and “small” are all independent of the dimension of
the ambient Hilbert space, and depend only on the degeneracy in the ground
space. Our analysis additionally holds for any gapped band of sufficiently
small width in the excited spectrum of the Hamiltonian, and we discuss
applications of these ideas to topological quantum phases of matter and
topological quantum error correcting codes. Finally, in our analysis we also
provide an exponential improvement upon bounds concerning the existence of
shared approximate eigenvectors of approximately commuting operators under an
added normality constraint, which may be of independent interest.

###### Contents

  1. 1 Introduction
    1. 1.1 Results
  2. 2 Restriction to the ground space
  3. 3 Degeneracy lower bounds
    1. 3.1 Stone-von Neumann Theorem
    2. 3.2 One twisted pair
    3. 3.3 Two twisted pairs
  4. 4 Minimum twisted commutation value
    1. 4.1 Frobenius spectral bound
    2. 4.2 Higher norms and tightness
  5. 5 Applications and open questions
    1. 5.1 Local Hamiltonians
    2. 5.2 Topologically ordered systems
    3. 5.3 Quantum codes
  6. A Approximate shared eigenvectors for approximately commuting matrices
  7. B An algorithm for the certifiable degeneracy of a twisted pair

##  1 Introduction

Given a quantum system described by a Hamiltonian $H$, a symmetry is simply an
operator that commutes with $H$. The symmetry can be block diagonalized with
respect to the energy eigenspaces, and so the degeneracy within these blocks
is constrained by the symmetry. In a system that possesses exact symmetries, a
sufficiently weak perturbation will preserve the number of states of any band
gapped away from the rest of the spectrum, but the symmetries will generally
become only approximate.

In this work we consider a natural converse to this: suppose we know that a
system has some approximate symmetries and a gapped band, such as the ground
space band. Can we “unperturb” the symmetries into exact symmetries within the
given band? Can we also use the approximate group structure of the approximate
symmetries to count the degeneracy within the band? We answer these questions
in the affirmative, giving quantitive bounds on when such a procedure can be
performed, and thus when such approximate symmetries can be used as
certificates of ground space degeneracy.

A related area of mathematical research with a long and rich history is the
relationship between the properties of approximately and exactly commuting
matrices. An exemplary problem which dates back as far as the 1950s [2, 3, 4,
5, 6] is whether a pair of approximately commuting matrices lie near an
exactly commuting pair, i.e. whether there exists a dimension independent
$\delta>0$ for each $\epsilon>0$ such that for all $H,S$ with
$\left\|H\right\|\\!,\left\|S\right\|\leq 1$,

$\left\|\left[H,S\right]\right\|\leq\delta\qquad\implies\qquad\exists\tilde{H},\tilde{S}:\bigl{[}\tilde{H},\tilde{S}\bigr{]}=0,\text{
where
}\bigl{\|}H-\tilde{H}\bigr{\|},\bigl{\|}S-\tilde{S}\bigr{\|}\leq\epsilon,$

where here and throughout the norm $\|\cdot\|$ is the operator norm.
Interpreting $H$ as the Hamiltonian and $S$ as a symmetry, this problem can be
interpreted as whether approximate symmetries are necessarily near exact
symmetries of a perturbed system. It has been shown that just such a theorem
holds if all matrices are Hermitian [7, 8, 9, 10]. A physical consequence of
this is that a pair approximately commuting observables can be approximately
simultaneously measured [10].

For unitary matrices the above is however known to be generally false [11].
This is due to a K-theoretic obstruction [12, 13, 14], though it is true if
this obstruction vanishes [7, 8, 15], or under the assumption of a spectral
gap [16]. Imposing a form of self-duality analogous to time-reversal symmetry
the relevant K-theoretic obstruction reduces to the spin Chern number of a
fermionic system [17], highlighting a link between the fields of topologically
ordered quantum systems [18] and approximately commuting matrices.

Here we will consider Hamiltonians $H$ with multiple non-commuting approximate
symmetries, and establish a connection to the ground space degeneracy. Ground
space degeneracy is a property of a quantum system that plays a special role
in several important applications, such as quantum coding theory and the study
of phases of matter. Quantum codes, especially those encoded into ground
spaces of local Hamiltonians, are the leading candidates for thermally stable
quantum memories [19, 20]; in these models approximate symmetries constitute
approximate logical operators and the ground space degeneracy corresponds to
the code size. In the context of condensed matter systems, the link between
symmetries and degeneracies plays an important role both in classical
symmetry-breaking phases [21], and also in exotic quantum phases, such as
those exhibited by topologically ordered models [18]. Unfortunately,
determining the ground space degeneracy of (finite) systems is generally
#P-complete, even for gapped bands [22]. However, if we restrict to more
structured examples such as 1D-local spin systems, then ground spaces can in
fact be efficiently approximated [23, 24]. Our results show that when
structure is present in the form of certain mutual commutation relations, one
can obtain certifiable bounds on the degeneracy of a ground space by only
knowing bounds on these relations. We go into more detail about these two
applications in Section 5.

The form of non-commutation we will consider will involve _twisted_
commutation relations.

######  Definition 1 (Twisted commutator).

For $\alpha\in[0,1)$, the _twisted commutator_ is defined as

$\left[X,Y\right]_{\alpha}:=XY-e^{2i\pi\alpha}YX.$

We will refer to $\alpha$ as the _twisting parameter_ , and for some unitarily
invariant norm
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\cdot\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
we will refer to
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[\cdot,\cdot\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
as the _twisted commutation value_. When considering a pair of operators in
tandem such that each has a small twisted commutation value we will refer to
it as a _twisted pair_.

We note that the $\alpha=0$ and $\alpha=1/2$ cases correspond to the
commutator and anti-commutator respectively.

Commuting operators exist in all dimensions, finite or infinite. Twisted
commuting operators on finite-dimensional spaces, however, only exist in
certain dimensions depending on the twisting parameter, e.g. no $\alpha\neq 0$
twisted commutator can non-trivially vanish in a one-dimensional space. For
general operators, twisted commuting operators were studied in some detail in
Ref. [25]. If we restrict to unitary operators however, the Stone-von Neumann
Theorem111As usually stated, the Stone-von Neumann theorem is much more
general than 1. We will only be concerned with twisted commutation in finite-
dimensional spaces, and unconcerned with uniqueness, so this form will suffice
for our purposes. [26, 27] classifies the dimensions in which twisted
commutation can occur.

######  Theorem 1 (Finite-dimensional Stone-von Neumann theorem).

Given $\alpha=p/q$ with $p,q$ coprime, then unitary operators $X$ and $Y$
which exactly twisted commute as

$\left[X,Y\right]_{\alpha}=0$

only exist in dimensions which are multiples of $q$.

In this paper we will generalize this connection into the regime of
_approximately_ twisted-commuting operators. Properties of both approximate
commuting, and approximately twisted-commuting operators are reviewed in Ref.
[28]. The rigidity of algebraic structures to small perturbations in the
commutation relations that define them has been studied in several other
settings, such as the soft torus [29, 30] and approximate representations of
groups [31, 32, 33].

Suppose we have a physical system with a self-adjoint Hamiltonian $H$, acting
on a possibly infinite-dimensional Hilbert space. Let $\Pi$ be the orthogonal
projector onto the finite-dimensional ground space, and $\bar{\Pi}:=I-\Pi$.
For simplicity, take the ground state energy of $H$ to be zero, such that $\Pi
H=0$. As well as this, we will assume that the excited states are gapped away
from the ground space, such that they all have an energy at least $\Delta$,
i.e. $H\geq\Delta\bar{\Pi}$. For such a system there exist two notions of
symmetry we will discuss.

######  Definition 2 (Symmetry).

We define a _ground symmetry_ as an operator $U$ that commutes with the ground
space projector

$\left[U,\Pi\right]=0,$

and acts unitarily on the ground space $\Pi U^{\dagger}U\Pi=\Pi
UU^{\dagger}\Pi=\Pi$. Moreover, we refer to a unitary as an _$\epsilon$
-approximate symmetry_ if it approximately commutes with the Hamiltonian with
respect to a given unitarily invariant norm

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[U,H\right]\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\epsilon.$

Here we use
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\cdot\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
to denote any unitarily invariant norm.

The error thresholds we are going to consider will depend on the spectral gap
$\Delta$ of the system in question. One way to improve the scaling with the
gap would be to consider symmetries defined not by commutation with the
Hamiltonian, but by commutation with functions of the Hamiltonian. For example
we could consider commutation with an (unnormalized) Gibbs state

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[U,e^{-\beta
H}\right]\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\epsilon.$

Such a symmetry can be seen to be an $\epsilon$-approximate symmetry of
$H^{\prime}=I-e^{-\beta H}$, which shares a ground space with $H$ and has a
gap of $1-e^{-\beta\Delta}$. If we have some control over the temperature,
such as in Monte Carlo simulations, then this gives a tradeoff we can use to
improve the gap scaling. If for example we set $\beta=\ln(2)/\Delta$, then we
get a fixed gap of $1/2$. A similar analysis could be performed with any
function of $H$ which leaves the relevant band gapped.

###  1.1 Results

The main goal of this paper will be to establish a connection between twisted
commuting symmetries and the ground space dimension, even when the relevant
commutation relations are only approximate. A key feature of our bounds is
that they can be expressed entirely in terms of the Hamiltonian, and do not
require objects such as the ground space projector, which can often be
prohibitively difficult to calculate, represent, or perform calculations with.
Without access to the ground space projector, whether or not a unitary is a
ground symmetry cannot be directly verified.

In Section 2 we will explore the relationship between approximate and ground
symmetries, showing that an approximate symmetry is always near a ground
symmetry. Extending this to the case of multiple symmetries, we will see that
approximate symmetries can be restricted to the ground space with low
distortion, implying the existence of unitaries on the ground space with
certain twisted commutation relations. In showing these results, we will make
repeated use of the following function and note some simple bounds on it,

$\displaystyle f:[0,1]\to[0,1]\,,\qquad
f(x):=1-\sqrt{1-x}\,,\qquad\tfrac{x}{2}\leq f(x)\leq x\,.$

Then our first main result is the following.

######  Theorem 2 (Restriction to the ground space).

For two $\epsilon$-approximate symmetries $U$ and $V$ which approximately
twisted commute

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[U,V\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\delta,$

then if $\xi:=\epsilon/\Delta<1$ there exists unitaries $u$ and $v$ acting on
the ground space which also approximately twisted commute as

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[u,v\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq\delta+2\xi^{2}+4f(\xi^{2})\,.$

Rather importantly, we note that the above theorem holds independent of the
ground space dimension. This will allow us to use approximate symmetries alone
as witnesses of ground space degeneracy, circumventing the need for direct
access to the ground space, which is often inaccessible in non-exactly
solvable models.

Note that for simplicity we will henceforth take the band in consideration to
be an exactly degenerate ground space. We will see however that our proof will
rely not on the bound $H\geq\Delta\bar{\Pi}$, but on its relaxation
$H^{2}\geq\Delta^{2}\bar{\Pi}$, meaning that the band could be anywhere in the
spectrum, so long as it is gapped on both sides by at least $\Delta$.
Furthermore we can take
$w:={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|H\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\geq
0$ when our band has a potentially non-zero width. By considering the new
Hamiltonian $H^{\prime}:=H-H\Pi$, we get that our restricted result holds for
more general bands once the necessary changes have been made.

######  Corollary 3 (Restriction to a general band).

If there are two $\epsilon$-approximate symmetries $U$ and $V$ which
approximately twisted commute

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[U,V\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\delta,$

then if $\xi^{\prime}:=(\epsilon+w)/\Delta<1$ there exists unitaries $u$ and
$v$ acting on band of gap $\Delta$ and width $w$ which also approximately
twisted commute

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[u,v\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq\delta+2\xi^{\prime 2}+4f(\xi^{\prime 2})\,.$

Now that we have restricted our symmetries down to the ground space, by
studying the relationship between dimensionality and approximate twisted
commutation, we can hope to use these twisted symmetries as witnesses of
ground space degeneracy. As above, we will henceforth adhere to the convention
of upper case letters denoting operators which act on the system as a whole,
and lower case operators which only act on the ground space.

In Section 3 we start by giving a proof of 1, and consider generalizing this
argument to the case of _approximately_ twisted commuting operators. We
consider a twisted pair of unitaries, and construct states which can be used
to lower bound the number of eigenvalues these operators possess. By doing so
we will show that if these operators have a sufficiently small twisted
commutation value in the operator norm, then a lower bound on their degeneracy
can be inferred.

######  Theorem 4.

If $u$ and $v$ are unitaries such that for some $d\in\mathbb{N}$

$\left\|\left[u,v\right]_{1/d}\right\|<\frac{2}{d-1}\Bigl{[}1-\cos\pi/d\Bigr{]},$

then the dimension of each operator is at least $d$.

While we do not have a closed form bound on the twisted commutation value
required to certify other dimensions ($d\neq 1/\alpha$), in Appendix B we
discuss an algorithm to determine which degeneracies are certified by twisted
pairs of given parameters. Using this we will plot the dimension that can be
certified as a function of both the twisting parameter and the corresponding
twisted commutation value.

In Appendix A we strengthen existing results on shared approximate
eigenvectors for approximately commuting operators when a normality condition
is introduced, exponentially improving the dimension dependence of the bounds
relative to known results [34]. Using this, in Section 3.3 we consider
extending this procedure to the case of two pairs of twisted commuting
unitaries. Here we will once again construct a set of ground states, showing
that for sufficient parameters that they are linearly independent. Using this
we can obtain a similar dimensionality lower bound.

######  Theorem 5.

If $u_{1}$, $u_{2}$, $v_{1}$ and $v_{2}$ are unitaries such that they satisfy
the commutation relations

$\left\|\left[u_{1},u_{2}\right]\right\|\leq\gamma\qquad\left\|\left[u_{1},v_{2}\right]\right\|\leq\delta\qquad\left\|\left[u_{2},v_{1}\right]\right\|\leq\delta$

and twisted commutation relations

$\left\|\left[u_{1},v_{1}\right]_{1/d_{1}}\right\|\leq\delta\qquad\left\|\left[u_{2},v_{2}\right]_{1/d_{2}}\right\|\leq\delta$

with $d_{1}\leq d_{2}$ and

$\sqrt{\gamma}d_{1}d_{2}+(d_{1}+d_{2})\delta<\frac{\sin^{2}(\pi/2d_{1})}{(d_{1}d_{2}-1)^{2}},$

then the dimension of each operator is at least $d_{1}d_{2}$.

In Section 4 we provide a more comprehensive analysis for the case of a single
twisted pair. Leveraging results from spectral perturbation theory, we find an
explicit closed form for the minimum twisted commutation value for a class of
norms known as the $(p,k)$-Schatten-Ky Fan norms. These are defined as the
$p$-norm of the largest $k$ singular values, or more formally as

$\displaystyle\left\|X\right\|_{(p,k)}:=\sup_{A}\left\\{(\operatorname{Tr}\left|AX\right|^{p})^{1/p}\,\middle|\,\left\|A\right\|\leq
1,\,\mathrm{rank}(A)\leq k\right\\}\,.$

For a $g$-dimensional operator, the special case $k=g$ reduces to the Schatten
$p$-norm, and the case $p=1$ reduces to the Ky Fan $k$-norm. In particular,
the $p=\infty$ and $(p,k)=(2,g)$ special cases reduce to the operator and
Frobenius norms respectively.

######  Theorem 6 (Minimum twisted commutation value).

Suppose that $u$ and $v$ are $g$-dimensional unitaries, then for any $p\geq 2$
the twisted commutator is lower bounded

$\Bigl{\|}\left[u,v\right]_{\alpha}\Bigr{\|}_{(p,k)}\geq
2k^{1/p}\sin\left(\pi\left|\frac{\left\lfloor
g\alpha\right\rceil-g\alpha}{g}\right|\right),$

where $\left\|\cdot\right\|_{(p,k)}$ is the $(p,k)$-Schatten-Ky Fan norm.
Moreover this bound is tight, in that sense that there exist families of
$g$-dimensional unitaries which saturate the above bounds and only depend on
$\left\lfloor g\alpha\right\rceil$, the nearest integer to $g\alpha$.

For a given twisted pair, all dimensions for which the twisted commutation
value falls below this minimum can therefore be ruled out as valid dimensions.
As this bound is not monotonic as a function of $g$, it not only provides a
lower bound, but a full classification of which dimensions are disallowed.

After giving proofs of the main results outlined above in Sections 2, 3, and
4, we turn to broader discussion and applications of these ideas. Section 5 is
devoted to discussion of future directions for this work that add the
additional constraint that the Hamiltonian is _local_ , and we discuss the
relationship to the notions of topological order and topological quantum
codes. In particular we show how recent numerical methods for studying quantum
many-body systems [35] could leverage the bounds presented here to provide
certificates of the topological degeneracy of certain quantum systems.

##  2 Restriction to the ground space

In this section we will make precise the notion that approximate symmetries
can be utilized as proxies of ground symmetries. We first establish a
relationship between approximate symmetries and the ground symmetries that
they imply. Then we consider operators with approximate twisted commutation
relations, and we show that these can also be restricted faithfully to the
ground space with low distortion.

Constructing a ground symmetry from an approximate symmetry will come in two
steps. First we will pinch the symmetry $U$ with respect to $\Pi$, giving an
operator $P$ for which $\left[P,\Pi\right]=0$. While this will render $P$ no
longer unitary, we will see that its action upon the ground space will still
be _approximately_ unitary. Using this we will construct a nearby operator
$\tilde{U}$ that retains commutation with the ground space projector, and acts
unitarily on the ground space, thus constituting a ground symmetry.

We will start by showing that the off-diagonal blocks of an approximate
symmetry are small, and then follow by showing that its action on the ground
space is approximately unitary.

######  Lemma 2.1 (Small off-diagonal blocks).

If $U$ is an $\epsilon$-approximate symmetry, then off-diagonal blocks of $U$
with respect to $\Pi$ have bounded norms, in particular
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\epsilon/\Delta$.
For Hamiltonians of the form $H=\Delta\bar{\Pi}$, this inequality is tight.

###### Proof.

We start by noting that $\left|A\right|^{2}\geq\left|B\right|^{2}$ implies
$\left|AX\right|^{2}\geq\left|BX\right|^{2}$ for any $X$, where
$\left|M\right|:=\sqrt{M^{\dagger}M}$. Taking $X$ to be finite-rank, we have
from Weyl’s inequalities [1] that the singular values of $AX$ majorize those
of $BX$. Unitarily invariant norms222Following Ref. [36, 37] we adopt the
normalization
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|A\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}=\left\|A\right\|$
for all rank-1 operators $A$. act as symmetric gauge functions on finite-rank
operators[38, 37, 36], which implies from Refs. [36, Prop.IV.1.1, Thm.IV.2.2]
that
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|AX\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\geq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|BX\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$—a
similar argument for the adjoint also gives
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|XA\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\geq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|XB\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$.
Because $H$ has a gapped band with projector $\Pi$, we have that
$H^{2}\geq\Delta^{2}\bar{\Pi}$. Using this, we can bound the off-diagonal
blocks in terms of the commutator

$\displaystyle\Delta{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|(\bar{\Pi}\Delta+\Pi)\left(\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right)\left(\Delta\bar{\Pi}+\Pi\right)\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{~{}}}}{{\leq}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|(\bar{\Pi}H+\Pi)\left(\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right)\left(H\bar{\Pi}+\Pi\right)\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}HU\Pi+\Pi
UH\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\,,$

where the inequality follows from the aforementioned monotonicity property.
Now using the unitary invariance of the norm (since $\bar{\Pi}-\Pi$ is
unitary), we find that

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}HU\Pi+\Pi
UH\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}HU\Pi-\Pi
UH\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}\left[H,U\right]\Pi+\Pi\left[H,U\right]\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{~{}}}}{{\leq}}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[H,U\right]\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\epsilon,$

where the second equality makes use of $H\Pi=0$ and the first inequality is
the pinching inequality.

With regard to tightness, if we take $H=\Delta\bar{\Pi}$ then we can see
$\left[H,U\right]$ has no on-diagonal blocks, and therefore
$\Delta\left(\bar{\Pi}U\Pi-\Pi U\bar{\Pi}\right)=\left[H,U\right]$. Taking
norms of both sides of this equation give
$\Delta{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[H,U\right]\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$,
meaning that
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\epsilon/\Delta$
is tight.

∎

######  Lemma 2.2 (Approximate unitarity on the ground space).

For an $\epsilon$-approximate symmetry $U$ with $\xi:=\epsilon/\Delta\leq 1$,
the action on the ground space is approximately unitary

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi-\left|\Pi
U\Pi\right|\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq
f(\xi^{2}),$

where $f(x):=1-\sqrt{1-x}$. In the operator norm, this expression is tight.

###### Proof.

First we can bound $\left|\Pi U\Pi\right|^{2}$ near $\Pi$ by using the
unitarity of $U$ itself as

$\displaystyle\Pi-\left|\Pi U\Pi\right|^{2}$ $\displaystyle=\Pi-\Pi
U^{\dagger}\Pi U\Pi$ $\displaystyle=\Pi U^{\dagger}U\Pi-\Pi U^{\dagger}\Pi
U\Pi$ $\displaystyle=\Pi U^{\dagger}\bar{\Pi}U\Pi$
$\displaystyle=\left|\bar{\Pi}U\Pi\right|^{2}.$

Together with 2.1, the sub-multiplicativity of unitarily invariant norms on
finite-rank operators let us conclude that
${|\kern-1.72218pt|\kern-1.72218pt|}{\Pi-\left|\Pi
U\Pi\right|^{2}{|\kern-1.72218pt|\kern-1.72218pt|}}\leq\xi^{2}$. Next we need
to use this bound on ${|\kern-1.72218pt|\kern-1.72218pt|}{\Pi-\left|\Pi
U\Pi\right|^{2}}{|\kern-1.72218pt|\kern-1.72218pt|}$, and create a bound on
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi-\left|\Pi
U\Pi\right|\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$.

Consider a function $f(x)=\sum_{n=1}^{\infty}a_{n}x^{n}$, where $a_{n}>0$ and
$f(1)<\infty$. For any finite-rank operator $0\leq X\leq 1$, we can use the
triangle inequality and submultiplicativity of
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\cdot\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
to derive a Jensen-like inequality

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|f(X)\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\sum_{n=1}^{\infty}a_{n}X^{n}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\sum_{n=1}^{\infty}a_{n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|X^{n}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\sum_{n=1}^{\infty}a_{n}{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|X\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}^{n}=f\left({\left|\kern-1.72218pt\left|\kern-1.72218pt\left|X\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\right).$

If we let $a_{n}=\Gamma(n-1/2)/2\sqrt{\pi}n!$, then we get $f(x)=1-\sqrt{1-x}$
for $x\in[0,1]$. If we let $X=\Pi-\left|\Pi U\Pi\right|$, then applying the
above gives

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi-\left|\Pi
U\Pi\right|\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|f\left(\Pi-\left|\Pi
U\Pi\right|^{2}\right)\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq
f\left({\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi-\left|\Pi
U\Pi\right|^{2}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\right)$
$\displaystyle\leq f(\xi^{2}).$

We note that $x/2\leq f(x)\leq x$, which means that this bound improves upon
the bound trivially given by the contractivity of $\Pi U\Pi$,

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi-\left|\Pi
U\Pi\right|\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi-\left|\Pi
U\Pi\right|^{2}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\xi^{2}.$

For the purposes of tightness, consider a two-dimensional Hilbert space, and a
Hamiltonian $H$ and unitary $U$ given by

$\displaystyle H=\begin{pmatrix}0&\\\
&\Delta\end{pmatrix}\qquad\text{and}\qquad
U=\begin{pmatrix}\cos\phi&\sin\phi\\\ -\sin\phi&\cos\phi\end{pmatrix}.$

In the operator norm $\left\|\left[U,H\right]\right\|=\Delta\sin\phi$ and
$\left\|\Pi-\left|\Pi U\Pi\right|\right\|=1-\cos\phi$, which saturates the
above bound. ∎

Using these bounds we can now construct a ground symmetry $\tilde{U}$ by
pinching $U$ with respect to $\Pi$, and then restoring unitarity on the ground
space.

######  Lemma 2.3 (Approximate symmetries are nearly ground symmetries).

For an $\epsilon$-approximate symmetry $U$ with $\xi:=\epsilon/\Delta\leq 1$,
there exists a ground symmetry $\tilde{U}$ which is close to $U$

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|U-\tilde{U}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq{\xi}{+f(\xi^{2})},$

and closer still in the ground space

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi\left(U-\tilde{U}\right)\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq
f(\xi^{2})\,.$

The first inequality is tight to leading order in $\xi$, and the second is
tight in the operator norm.

###### Proof.

We start by considering the polar of decompositon $\Pi U\Pi=W\left|\Pi
U\Pi\right|$. As the ground space $\mathrm{im}(\Pi)$ is an invariant subspace
of $\Pi U\Pi$, we can take333Such a $W$ could be found by performing the polar
decomposition restricted to the ground space, and padding the unitary out to
act as the identity on the rest of the space. $W$ to also leave the ground
space invariant, $\left[W,\Pi\right]=0$. Given this, we define our ground
symmetry to be $\tilde{U}:=\Pi W\Pi+\bar{\Pi}U\bar{\Pi}$.

We will now consider bounding the distance between $U$ and $\tilde{U}$ block-
wise. The off-diagonal blocks are bounded by 2.1 as

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi\left(\tilde{U}-U\right)\bar{\Pi}+\bar{\Pi}\left(\tilde{U}-U\right)\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi+\bar{\Pi}U\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\xi.$

The bound on the ground space however follows from 2.2

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi\left(\tilde{U}-U\right)\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|W\Pi-W\left|\Pi
U\Pi\right|\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi-\left|\Pi
U\Pi\right|\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq
f(\xi^{2}).$

Finally the fact that $U$ was unchanged on the excited space trivially implies

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}\left(\tilde{U}-U\right)\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}=0.$

Putting everything together, this gives the desired bound

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\tilde{U}-U\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}\left(\tilde{U}-U\right)\Pi+\Pi\left(\tilde{U}-U\right)\bar{\Pi}+\Pi\left(\tilde{U}-U\right)\Pi+\bar{\Pi}\left(\tilde{U}-U\right)\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}\left(\tilde{U}-U\right)\Pi+\Pi\left(\tilde{U}-U\right)\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi\left(\tilde{U}-U\right)\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}\left(\tilde{U}-U\right)\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq\xi+f(\xi^{2}).$

As for tightness, 2.1 gives that
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[H,U\right]\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}/\Delta$
for Hamiltonians of the form $H=\Delta\bar{\Pi}$. If we assume that
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[U,H\right]\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}=\epsilon$,
then applying the pinching inequality gives

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|U-\tilde{U}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\geq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}\left(U-\tilde{U}\right)\Pi+\Pi\left(U-\tilde{U}\right)\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi+\Pi
U\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}=\xi,$

which proves our bound on
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|U-\tilde{U}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
is tight to leading order in $\xi$. The tightness of the norm distance in the
ground space follows directly from the tightness of 2.2. ∎

We will now consider how the existence of nearby ground symmetries allows
twisted commutation relations of approximate symmetries to be pulled down into
the ground space.

######  Theorem 2 (Restriction to the ground space).

For two $\epsilon$-approximate symmetries $U$ and $V$ which approximately
twisted commute

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[U,V\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\delta,$

then if $\xi:=\epsilon/\Delta\leq 1$ there exists unitaries $u$ and $v$ acting
on the ground space which also approximately twisted commute as

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[u,v\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq\delta+2\xi^{2}+4f(\xi^{2})\,.$

###### Proof.

Consider a $\tilde{U}$ and $\tilde{V}$ given by applying 2.3 to $U$ and $V$
respectively, such that

${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
U\Pi-\Pi\tilde{U}\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|},\,{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
V\Pi-\Pi\tilde{V}\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq
f(\xi^{2}).$

Next we consider the twisted commutator of $U$ and $V$, and that of
$\tilde{U}$ and $\tilde{V}$, both projected into the ground space. By
expanding out the twisted commutators we have

$\displaystyle\Pi\left[U,V\right]_{\alpha}\Pi-\Pi\left[\tilde{U},\tilde{V}\right]_{\alpha}\Pi$
$\displaystyle=\left[\Pi U\Pi,\Pi
V\Pi\right]_{\alpha}-\left[\Pi\tilde{U}\Pi,\Pi\tilde{V}\Pi\right]_{\alpha}+\Pi
U\bar{\Pi}\cdot\bar{\Pi}V\Pi-e^{2\pi i\alpha}\Pi
V\bar{\Pi}\cdot\bar{\Pi}U\Pi,$ $\displaystyle=\left(\Pi
U\Pi-\Pi\tilde{U}\Pi\right)\cdot\Pi V\Pi-e^{2\pi
i\alpha}\Pi\tilde{V}\Pi\cdot\left(\Pi U\Pi-\Pi\tilde{U}\Pi\right)$
$\displaystyle~{}\quad+\Pi\tilde{U}\Pi\cdot\left(\Pi
V\Pi-\Pi\tilde{V}\Pi\right)-e^{2\pi i\alpha}\left(\Pi
V\Pi-\Pi\tilde{V}\Pi\right)\cdot\Pi U\Pi$ $\displaystyle~{}\quad+\Pi
U\bar{\Pi}\cdot\bar{\Pi}V\Pi-e^{2\pi i\alpha}\Pi
V\bar{\Pi}\cdot\bar{\Pi}U\Pi.$

Using the triangle inequality, the contractivity of $\Pi U\Pi$ and $\Pi V\Pi$,
and the bound on the off-diagonal blocks from 2.1, we can bound this as
required:

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi\left[U,V\right]_{\alpha}\Pi-\Pi\left[\tilde{U},\tilde{V}\right]_{\alpha}\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left(\Pi
U\Pi-\Pi\tilde{U}\Pi\right)\cdot\Pi
V\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi\tilde{V}\Pi\cdot\left(\Pi
U\Pi-\Pi\tilde{U}\Pi\right)\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle~{}\qquad+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi\tilde{U}\Pi\cdot\left(\Pi
V\Pi-\Pi\tilde{V}\Pi\right)\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left(\Pi
V\Pi-\Pi\tilde{V}\Pi\right)\cdot\Pi
U\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle~{}\qquad+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
U\bar{\Pi}\cdot\bar{\Pi}V\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
V\bar{\Pi}\cdot\bar{\Pi}U\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq 2{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
U\Pi-\Pi\tilde{U}\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+2{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
V\Pi-\Pi\tilde{V}\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle~{}\qquad+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
U\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\cdot{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}V\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi
V\bar{\Pi}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\cdot{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\bar{\Pi}U\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq 4f(\xi^{2})+2\xi^{2}.$

Next we let $u$ and $v$ be the restriction of $\tilde{U}$ and $\tilde{V}$ to
the ground space respectively. As each are ground symmetries, $u$ and $v$ are
both unitaries. If we consider the embedding of operators on the ground space
back into the larger Hilbert space, then we can use the above to bound the
twisted commutator of our ground space unitaries

$\displaystyle{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[u,v\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[u\oplus
0,v\oplus
0\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|[\Pi\tilde{U}\Pi,\Pi\tilde{V}\Pi]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle={\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi[\tilde{U},\tilde{V}]_{\alpha}\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}$
$\displaystyle\leq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\Pi[U,V]_{\alpha}\Pi\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+2\xi^{2}+4f(\xi^{2})$
$\displaystyle\leq{\left|\kern-1.72218pt\left|\kern-1.72218pt\left|[U,V]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}+2\xi^{2}+4f(\xi^{2})$
$\displaystyle\leq\delta+2\xi^{2}+4f(\xi^{2}).$

Note that if we had a set of more than two unitaries, this additive growth in
the twisted commutation value would hold equally for every pair separately. ∎

##  3 Degeneracy lower bounds

In this section we show how twisted pairs of unitary operators can be used to
give lower bounds on the degeneracy of the ground space. We start by
considering an exact twisted pair and the Stone-von Neumann theorem. We will
then show how this argument can be generalized to approximate twisted pairs,
and how a lower bound on the degeneracy follows from an upper bound on the
twisted commutator value. Finally we will see how this can also be extended to
more general collections of twisted commuting operators through the example
case of two twisted pairs that are approximately mutually commuting.

###  3.1 Stone-von Neumann Theorem

Consider a $u$ and $v$ which exactly twisted commute, so that
$uv=e^{2i\pi\alpha}vu$. Let $(\lambda,|\psi\rangle)$ be an eigenpair of $u$.
Using the twisted commutation relation, we see that
$|\psi^{\prime}\rangle:=v|\psi\rangle$ forms a $\lambda
e^{2i\pi\alpha}$-eigenvector. It follows that $v$ forms an isomorphism between
the $\lambda$ and $\lambda e^{2i\pi\alpha}$-eigenspaces of $u$, which allows
us to conclude that their dimensions must be the same. Carrying this argument
forward, we can see that any eigenspaces whose eigenvalues differ by any power
of $e^{2i\pi\alpha}$ must also be isomorphic.

Suppose we take $\alpha\in\mathbb{Q}$, with $\alpha=p/q$ with $p$, $q$
coprime. As we can see in Fig. 1, a simple divisibility argument implies that
the eigenspaces come in isomorphic multiples of $q$, which therefore implies
that the overall dimension of $u$ and $v$ is a multiple of $q$ also.

Figure 1: The action of powers of $v$ on an eigenvector $|\psi\rangle$ of $u$.
On the left $\left[u,v\right]_{1/7}=0$, in the centre
$\left[u,v\right]_{2/7}=0$, and on the right $\left[u,v\right]_{3/7}=0$. Here
the position of the circle represents the corresponding eigenvalue of $u$.

We now generalize this connection between the twisted commutator and the
spectrum of one of the operators to allow for only approximate twisted
commutation.

###  3.2 One twisted pair

Let us first extend the above argument to the case of a single approximate
twisted pair. For simplicity, we consider the case where $\alpha=p/q$ with
$p=1$ and $q=d$, so the corresponding phase in the twisted commutator is
$\eta:=e^{2i\pi/d}$. This is not much of a restriction since if $p>1$ we can
replace $v$ with $v^{\bar{p}}$ where $\bar{p}$ is the modular multiplicative
inverse of $p$ such that $\bar{p}p=1\bmod q$ and then apply the results of the
$p=1$ case. Under this substitution the twisted commutator will grow by at
most a factor of $\lfloor q/2\rfloor$. However, in Appendix B we will show an
alternative method that in fact works for arbitrary $\alpha\in\mathbb{R}$ and
gives tighter bounds than this simple reduction. We also consider without loss
of generality the case where $u$ has at least one $+1$ eigenvalue, which can
always be achieved by redefining $u$ by multiplying by a complex unit phase
factor.

Suppose we have two unitaries $u$ and $v$ such that

$\left\|\left[u,v\right]_{1/d}\right\|=\left\|uv-\eta vu\right\|\leq\delta.$

Our results will show that these operators must, for sufficiently small
$\delta$, be at least $d$-dimensional. To do this we will explicitly show that
$u$ has at least $d$ distinct eigenvalues.

Let $|\psi\rangle$ be a $+1$ eigenvector of $u$, i.e.
$u|\psi\rangle=|\psi\rangle$. Consider the orbit of $|\psi\rangle$ under $v$,
i.e. the states $|j\rangle:=v^{j}|\psi\rangle$ for
$j=-\lfloor\frac{d-1}{2}\rfloor,\dots,\lceil\frac{d-1}{2}\rceil$. These
vectors are precisely the vectors depicted in Figure 1. We first show that
these are approximate eigenstates of $u$.

######  Lemma 3.1 (Change in expectation value: One pair).

The expectation value of $u$ with respect to $|j\rangle$ is approximately
$\eta^{j}$, specifically

$\left|\left\langle
j\middle|u\middle|j\right\rangle-\eta^{j}\right|\leq\left|j\right|\delta.$

###### Proof.

This follows from the twisted commutator of $u$ and $v$ being small. By
expanding the commutator and applying the triangle inequality we can see that
$\left\|uv-\eta vu\right\|\leq\delta$ implies
$\left\|uv^{j}-\eta^{j}v^{j}u\right\|\leq\left|j\right|\delta$. From this we
can see that the expectation value of $|j\rangle$ lies close to $\eta^{j}$:

$\displaystyle\left|j\right|\delta$
$\displaystyle\geq\left\|uv^{j}-\eta^{j}v^{j}u\right\|$
$\displaystyle=\left\|v^{-j}uv^{j}-\eta^{j}u\right\|$
$\displaystyle\geq\left|\left\langle\psi\middle|\left[v^{-j}uv^{j}-\eta^{j}u\right]\middle|\psi\right\rangle\right|$
$\displaystyle\geq\left|\left\langle\psi\middle|v^{-j}uv^{j}\middle|\psi\right\rangle-\eta^{j}\left\langle\psi\middle|u\middle|\psi\right\rangle\right|$
$\displaystyle=\left|\left\langle
j\middle|u\middle|j\right\rangle-\eta^{j}\right|.$

∎

So we can see that the $\\{|j\rangle\\}$ form a set of vectors with
expectation values distributed approximately evenly around the unit circle,
much like the states in the $\delta=0$ case as seen in Fig. 1. To relate these
states to the dimensions of $u$ and $v$, we will now show that there must
exist an eigenvalue of $u$ near the expectation value of each state.

######  Lemma 3.2 (Existence of eigenvalues).

If there exists a state $|x\rangle$ such that

$\left|\left\langle
x\middle|u\middle|x\right\rangle-e^{i\theta}\right|\leq\zeta$

then $u$ possesses a nearby eigenvalue $e^{i\phi}$ such that

$\left|\phi-\theta\right|\leq\cos^{-1}(1-\zeta).$

###### Proof.

The bound on the expectation value with respect to $u$ implies

$\operatorname{Re}\left\langle
x\middle|e^{-i\theta}u\middle|x\right\rangle\geq 1-\zeta.$

As this expectation value is a convex combination of the eigenvalues of $u$,
all of which lie on the unit circle, there must exists an eigenvalue of
$e^{-i\theta}u$ with real value at least $1-\zeta$ (see Fig. 2). This in turn
implies that $u$ possesses an eigenvalue $e^{i\phi}$ such that

$\operatorname{Re}e^{i(\phi-\theta)}=\cos(\phi-\theta)\geq 1-\zeta.$

∎

Figure 2: 3.2 gives that if there exists an expectation value in the blue
region, there must exist an eigenvalue within the minor segment indicated by
the dotted line.

Combining the two above lemmas, we can place a lower bound on the number of
distinct eigenvalues of $u$.

######  Theorem 4.

If $u$ and $v$ are unitaries such that

$\left\|\left[u,v\right]_{1/d}\right\|<\frac{2}{d-1}\Bigl{[}1-\cos\pi/d\Bigr{]},$

then the dimension of each operator is at least $d$.

###### Proof.

From 3.1 we know that $\left|\left\langle
j\middle|u\middle|j\right\rangle-e^{2i\pi
j/d}\right|\leq\left|j\right|\delta$. Applying 3.2 we therefore get that $u$
must have a corresponding eigenvalue $e^{i\phi_{j}}$ where

$\left|\phi_{j}-2j\pi/d\right|\leq\cos^{-1}\left(1-\left|j\right|\delta\right).$

As such we can see that each eigenvalue is within some error of a $d$th root
of unity.

Next we want to find a bound for $\delta$ which ensures that these eigenvalues
must be distinct, by bounding the regions in which these eigenvalues must
exist away from each other. To do this we need
$\left|\phi_{j}-\phi_{k}\right|>0$ for all $j\neq k$. Taking the worst case
over $j\neq k$:

$\displaystyle\left|\phi_{j}-\phi_{k}\right|$
$\displaystyle=\left|\frac{2\pi}{d}(j-k)+\left(\phi_{j}-\frac{2j\pi}{d}\right)-\left(\phi_{k}-\frac{2k\pi}{d}\right)\right|$
$\displaystyle\geq\frac{2\pi}{d}\left|j-k\right|-\left|\phi_{j}-\frac{2j\pi}{d}\right|-\left|\phi_{k}-\frac{2k\pi}{d}\right|$
$\displaystyle\geq\frac{2\pi}{d}-\cos^{-1}\left(1-\left\lceil\frac{d-1}{2}\right\rceil\delta\right)-\cos^{-1}\left(1-\left\lfloor\frac{d-1}{2}\right\rfloor\delta\right)\,.$

Here the last line follows from the fact that $j$ and $k$ cannot both saturate
the worst-case distance of $\lceil\tfrac{d-1}{2}\rceil$. Therefore, the worst
case can be chose without loss of generality to be
$j=\lceil\tfrac{d-1}{2}\rceil$ and $k=-\lfloor\tfrac{d-1}{2}\rfloor$. Using
the concavity of $\cos^{-1}(z)$ over $z\in[0,1]$, we can loosen this to

$\displaystyle\left|\phi_{j}-\phi_{k}\right|$
$\displaystyle\geq\frac{2\pi}{d}-2\cos^{-1}\left(1-\frac{d-1}{2}\,\delta\right)\,.$

Clearly this step is trivial for odd $d$.

Thus we get that a sufficient condition for all of the eigenvalues to be
distinct is that the right-hand side of this inequality is strictly positive,
and therefore we have the equivalent condition

$\cos^{-1}\left(1-\frac{d-1}{2}\,\delta\right)<\frac{\pi}{d}\,.$

Rearranging, we find the specified bound on $\delta$ of

$\delta<\frac{2}{d-1}\Bigl{[}1-\cos(\pi/d)\Bigr{]}.$

∎

Above we have only considered the case $d=1/\alpha$, similar analysis could be
performed for bounds required to certify dimensions $d^{\prime}\not=1/\alpha$.
In Appendix B we describe an algorithm for calculating which dimensions can be
certified for an arbitrary pair of parameters $\alpha$ and $\delta$ — running
this algorithm gives Fig. 3.

Figure 3: The dimension that can be certified, as a function of the twisted
commutator value and twisting parameter, i.e. the minimum possible dimension
of operators $u$ and $v$ for which
$\left\|\left[u,v\right]_{\alpha}\right\|\leq\delta$ as a function of $\alpha$
and $\delta$. The blue crosses indicate the bounds corresponding to degeneracy
$d$ and $\alpha=1/d$, as considered in 4. The algorithm for calculating this
figure is demonstrated in Appendix B, by considering how the certification is
calculated at the turquoise dot ($\alpha=1/4$ and $\delta=1/2$).

###  3.3 Two twisted pairs

Next we are going to argue that the above analysis can be extended to more
general collections of twisted commuting symmetries. By way of example, we are
going to consider the case of two twisted pairs

$\left\|\left[u_{1},v_{1}\right]_{1/d_{1}}\right\|\leq\delta,\qquad\left\|\left[u_{2},v_{2}\right]_{1/d_{2}}\right\|\leq\delta,$

each of which approximately commute

$\left\|\left[u_{1},u_{2}\right]\right\|\leq\gamma,\qquad\left\|\left[u_{1},v_{2}\right]\right\|\leq\delta,\qquad\left\|\left[u_{2},v_{1}\right]\right\|\leq\delta.$

The equivalent of Stone-von Neumann theorem laid our in Section 3.1 gives that
for $\gamma=\delta=0$, the dimension of such operators must be a multiple of
$d_{1}d_{2}$. We are going to give bounds on $\gamma$ and $\delta$ below which
we can prove the dimension to be at least $d_{1}d_{2}$.

Previously we bounded the dimension from below by bounding the number of
distinct eigenvalues. This is possible because these eigenvalues imply the
existence of an orthonormal set of associated eigenvectors. As $u_{1}$ and
$u_{2}$ do not commute, they will not necessarily possess an orthonormal set
of shared eigenvectors. Instead we will have to address these vectors more
directly, constructing _approximate shared eigenvectors_ and proving their
linear independence. First we will see that the approximate commutation of
$u_{1}$ and $u_{2}$ can be used to demonstrate the existence of such a vector.

The existence of approximate shared eigenvectors of approximately commuting
matrices was first proven in generality by Bernstein in Ref. [34]. Whilst
Bernstein considers potentially non-normal matrices, in our case both $u_{1}$
and $u_{2}$ are unitary. In Appendix A we leverage this additional structure
to exponentially tighten the bounds on the approximate shared eigenvectors.
One of the relevant bounds considered in Appendix A gives the following
immediate corollary.

######  Lemma 3.3 (Approximate eigenvector).

There exists a vector $|\psi\rangle$ such that, after multiplying $u_{1}$ and
$u_{2}$ by appropriate phase factor, it is an approximate shared
$+1$-eigenvector of both, namely that

$\left\|u_{1}|\psi\rangle-|\psi\rangle\right\|,\left\|u_{2}|\psi\rangle-|\psi\rangle\right\|\leq\sqrt{\gamma}d_{1}d_{2}/2.$

###### Proof.

Given an assumption that the dimension is at most $d_{1}d_{2}$, this is a
direct application of A.1, which we consider in detail in Appendix A. ∎

As in the case of a single pair, we will then consider the orbit of this
vector under the action of products of $v_{1}$ and $v_{2}$. Let
$|i,j\rangle:=v_{1}^{i}v_{2}^{j}|\psi\rangle$ for
$i=-\left\lfloor\frac{d_{1}-1}{2}\right\rfloor,\ldots,\left\lceil\frac{d_{1}-1}{2}\right\rceil$
and
$j=-\left\lfloor\frac{d_{2}-1}{2}\right\rfloor,\ldots,\left\lceil\frac{d_{2}-1}{2}\right\rceil$.
For convenience once again let $\eta_{i}:=e^{2i\pi/d_{i}}$.

######  Lemma 3.4 (Change in expectation value: two pair).

The states $|i,j\rangle$ are shared approximate eigenstates of $u_{1}$ and
$u_{2}$. Specifically their approximate eigenvalues are the corresponding
powers of $\eta_{1}$ and $\eta_{2}$

$\left|\phantom{\Big{.}}\\!\left\langle
i,j\middle|u_{1}\middle|i,j\right\rangle-\eta_{1}^{i}\right|,\left|\left\langle
i,j\middle|u_{2}\middle|i,j\right\rangle-\eta_{2}^{j}\right|\leq\sqrt{\gamma}d_{1}d_{2}/2+\left(\left|i\right|+\left|j\right|\right)\delta.$

###### Proof.

From 3.3 we have

$\left|\left\langle\psi\middle|u_{1}\middle|\psi\right\rangle-1\right|\leq\sqrt{\gamma}d_{1}d_{2}/2.$

Applying an argument similar to that in 3.1 we can bound the change in
eigenvalue under the action of $v_{c}$ as

$\left|\left\langle
i,0\middle|u_{1}\middle|i,0\right\rangle-\eta_{1}^{i}\left\langle\psi\middle|u_{1}\middle|\psi\right\rangle\right|\leq\left|i\right|\delta.$

Applying the same argument for $v_{2}$ gives

$\left|\left\langle i,j\middle|u_{1}\middle|i,j\right\rangle-\left\langle
i,0\middle|u_{1}\middle|i,0\right\rangle\right|\leq\left|j\right|\delta.$

The triangle inequality allows us to merge these three inequalities, giving
the stated bound. A similar argument can be performed for $u_{2}$. ∎

In the single pair case, we used the expectation values to imply the existence
of nearby eigenvalues. Due to the lack of a shared eigenbasis of $u_{1}$ and
$u_{2}$, we cannot do the same in the two pair case.

The reason that a set of distinct eigenvalues lower bounds the dimension is
that, for normal operators such as unitaries, the eigenvalues imply the
existence of an orthonormal eigenbasis. Instead of proving the existence of
such vectors indirectly through the eigenvalues, we could instead prove our
vectors $\\{|i,j\rangle\\}$ to be linearly independent — this is the approach
we will take.

To this end, we will start by showing two approximate eigenvectors of a
unitary with inconsistent expectation values are approximately orthogonal.

######  Lemma 3.5 (Low overlap).

If two normalized vectors $|x\rangle$ and $|y\rangle$ have expectation values
with some unitary $w$ such that

$\left|\left\langle
x\middle|w\middle|x\right\rangle-e^{i\theta_{x}}\right|\leq\zeta\qquad\text{and}\qquad\left|\left\langle
y\middle|w\middle|y\right\rangle-e^{i\theta_{y}}\right|\leq\zeta$

then the two vectors have a bounded overlap

$\left|\left\langle
x\middle|y\right\rangle\right|\leq\sqrt{2\zeta}\left|\csc\left(\frac{\theta_{y}-\theta_{x}}{4}\right)\right|.$

###### Proof.

Firstly, let $w^{\prime}:=e^{-i\theta_{x}}w$ and
$\theta:=\theta_{y}-\theta_{x}$. Next consider splitting the unit circle into
three arcs $X$, $Y$, and $Z$. We let $X$ and $Y$ be centered on $\theta_{x}$
and $\theta_{y}$ respectively, and define them to be the largest possible
regions such that they remain disjoint. We define $Z$ to be the remaining arc,
as shown in Fig. 4. Note that by convexity any linear combination of
eigenvectors whose eigenvalues lie in $X$ will have an expectation value in
the segment subtended by $X$, and similar for $Y$.

Figure 4: A disc representing the expectation values of vectors with respect
to $w$, as well as the three regions $X$, $Y$, $Z$ into which the disc is
divided. The expectation values with respect to $|x\rangle$ and $|y\rangle$
lie in each of the blue regions.

Now split $|x\rangle$ into two components

$|x\rangle=\sqrt{1-\lambda_{x}}|x_{X}\rangle+\sqrt{\lambda_{x}}|x_{YZ}\rangle,$

where $|x_{X}\rangle$ is in the span of eigenvectors with values in $X$, and
$|x_{YZ}\rangle$ similar for $Y\cup Z$. By definition of $X$, we have

$\operatorname{Re}\left\langle
x_{YZ}\middle|w^{\prime}\middle|x_{YZ}\right\rangle\leq\cos(\theta/2)\leq\operatorname{Re}\left\langle
x_{X}\middle|w^{\prime}\middle|x_{X}\right\rangle\leq 1.$

Next we use the bound on the expectation value.

$\displaystyle\zeta$ $\displaystyle\geq\left|\left\langle
x\middle|w^{\prime}\middle|x\right\rangle-1\right|$ $\displaystyle\geq
1-\operatorname{Re}\left\langle x\middle|w^{\prime}\middle|x\right\rangle$
$\displaystyle=1-(1-\lambda_{x})\operatorname{Re}\left\langle
x_{X}\middle|w^{\prime}\middle|x_{X}\right\rangle-\lambda_{x}\operatorname{Re}\left\langle
x_{YZ}\middle|w^{\prime}\middle|x_{YZ}\right\rangle$ $\displaystyle\geq
1-(1-\lambda_{x})-\lambda_{x}\cos\left(\theta/2\right)$
$\displaystyle=2\lambda_{x}\sin^{2}(\theta/4)$

Thus we conclude that $\lambda_{x}\leq(\zeta/2)\csc^{2}(\theta/4)$. Similarly
if we were to have decomposed $|y\rangle$ into parts contained in $Y$ and $XZ$
as
$|y\rangle=\sqrt{1-\lambda_{y}}|y_{Y}\rangle+\sqrt{\lambda_{y}}|y_{XZ}\rangle$
then $\lambda_{y}\leq(\zeta/2)\csc^{2}(\theta/4)$.

Further decomposing

$|x_{YZ}\rangle=\cos\varphi_{x}|x_{Y}\rangle+\sin\varphi_{x}|x_{Z}\rangle\qquad|y_{XZ}\rangle=\cos\varphi_{y}|y_{X}\rangle+\sin\varphi_{y}|y_{Z}\rangle\,,$

then the inner product has the form

$\displaystyle\left|\left\langle x\middle|y\right\rangle\right|$
$\displaystyle=\Bigl{|}\sqrt{1-\lambda_{x}}\sqrt{\lambda_{y}}\cos\varphi_{y}\left\langle
x_{X}\middle|y_{X}\right\rangle+\sqrt{\lambda_{x}}\sqrt{1-\lambda_{y}}\cos\varphi_{x}\left\langle
x_{Y}\middle|y_{Y}\right\rangle+\sqrt{\lambda_{x}}\sqrt{\lambda_{y}}\sin\varphi_{x}\sin\varphi_{y}\left\langle
x_{Z}\middle|y_{Z}\right\rangle\Bigr{|}$
$\displaystyle\leq\sqrt{1-\lambda_{x}}\sqrt{\lambda_{y}}\cos\varphi_{y}+\sqrt{\lambda_{x}}\sqrt{1-\lambda_{y}}\cos\varphi_{x}+\sqrt{\lambda_{x}}\sqrt{\lambda_{y}}\sin\varphi_{x}\sin\varphi_{y}.$

Using the identity
$\left|A\cos\phi+B\sin\phi\right|^{2}\leq\left|A\right|^{2}+\left|B\right|^{2}$,
we can maximize over $\varphi_{x}$ to get

$\displaystyle\left|\left\langle x\middle|y\right\rangle\right|$
$\displaystyle\leq\sqrt{1-\lambda_{x}}\sqrt{\lambda_{y}}\cos\varphi_{y}+\sqrt{\lambda_{x}}\sqrt{1-\lambda_{y}\cos^{2}\varphi_{y}}.$

Using $\cos\varphi_{y}\leq 1$, we can simplify this bound to

$\displaystyle\left|\left\langle x\middle|y\right\rangle\right|$
$\displaystyle\leq\sqrt{\lambda_{y}}+\sqrt{\lambda_{x}}.$

Applying the $\zeta$-dependent bounds on the $\lambda$ values, we get the
stated bounds. ∎

Now that we have a way of bounding the overlap between our vectors, we need to
determine how low this overlap needs to be before linear independence can be
ensured.

######  Lemma 3.6 (Overlap threshold).

Take a set of normalized vectors $S=\\{|v_{i}\rangle\\}$ for $1\leq i\leq n$.
If the pairwise overlap between any two vectors is bounded $\left|\left\langle
v_{i}\middle|v_{j}\right\rangle\right|<1/(n-1)$ for $i\neq j$, then $S$ is
linearly independent.

###### Proof.

Let $G$ be the Gram matrix associated with $S$. As each of the vectors is
normalized $G_{ii}=1$ for all $i$. As all of the non-diagonal entries are
strictly modulus-bounded by $1/(n-1)$, this matrix is strictly diagonally
dominant, i.e.

$\left|G_{ii}\right|>\sum_{j\neq i}\left|G_{ij}\right|\quad\text{for all }i.$

From the Geshgorin circle theorem, such matrices are non-singular and full
rank, allowing us to conclude that $S$ is linearly independent.

Note that this analysis is tight, i.e. if $\left\langle
v_{i}\middle|v_{j}\right\rangle=-1/(n-1)$ for all $i\neq j$ then $G$ is
singular and $\sum_{i}|v_{i}\rangle=0$. By considering the eigenvectors of
such a Gram matrix, a set of vectors satisfying this can be backed out. ∎

Given this bound, we can finally find the condition for our vectors to be
linearly independent and therefore lower bound the dimension of the space in
which they reside.

######  Theorem 5.

If $u_{1}$, $u_{2}$, $v_{1}$ and $v_{2}$ are unitaries such that they satisfy
the commutation relations

$\left\|\left[u_{1},u_{2}\right]\right\|\leq\gamma\qquad\left\|\left[u_{1},v_{2}\right]\right\|\leq\delta\qquad\left\|\left[u_{2},v_{1}\right]\right\|\leq\delta$

and twisted commutation relations

$\left\|\left[u_{1},v_{1}\right]_{1/d_{1}}\right\|\leq\delta\qquad\left\|\left[u_{2},v_{2}\right]_{1/d_{2}}\right\|\leq\delta$

with $d_{1}\leq d_{2}$ and

$\sqrt{\gamma}d_{1}d_{2}+(d_{1}+d_{2})\delta<\frac{\sin^{2}(\pi/2d_{1})}{(d_{1}d_{2}-1)^{2}},$

then the dimension of each operator is at least $d_{1}d_{2}$.

###### Proof.

From 3.4 we have that our vectors have expectation values bounded near powers
of $\eta_{1}$ and $\eta_{2}$

$\Bigl{|}\left\langle
i,j\middle|u_{1}\middle|i,j\right\rangle-\eta_{1}^{i}\Bigr{|},~{}\Bigl{|}\left\langle
i,j\middle|u_{2}\middle|i,j\right\rangle-\eta_{2}^{j}\Bigr{|}\leq\sqrt{\gamma}d_{1}d_{2}/2+\left(\left|i\right|+\left|j\right|\right)\delta.$

Take a pair of vectors $|i,j\rangle$ and $|i^{\prime},j^{\prime}\rangle$ such
that $i\neq i^{\prime}$. Applying 3.5 with $w=u_{1}$ we get that their overlap
is bounded as

$\displaystyle\left|\left\langle
i,j\middle|i^{\prime},j^{\prime}\right\rangle\right|^{2}$
$\displaystyle\leq\Bigl{[}\sqrt{\gamma}d_{1}d_{2}+2\max\\{\left|i\right|+\left|j\right|,\left|i^{\prime}\right|+\left|j^{\prime}\right|\\}\delta\Bigr{]}\cdot\csc^{2}\left(\frac{\pi(i-i^{\prime})}{2d_{1}}\right).$

Combining this with a similar argument for $u_{2}$, and assuming $d_{1}\leq
d_{2}$, we get that for $(i,j)\neq(i^{\prime},j^{\prime})$

$\displaystyle\left|\left\langle
i,j\middle|i^{\prime},j^{\prime}\right\rangle\right|^{2}$
$\displaystyle\leq\Bigl{[}\sqrt{\gamma}d_{1}d_{2}+(d_{1}+d_{2})\delta\Bigr{]}\csc^{2}\left(\frac{\pi}{2d_{1}}\right)$

Thus we can see that

$\Bigl{[}\sqrt{\gamma}d_{1}d_{2}+(d_{1}+d_{2})\delta\Bigr{]}\csc^{2}\left(\frac{\pi}{2d_{1}}\right)<\frac{1}{(d_{1}d_{2}-1)^{2}}\,.$

implies $\left|\left\langle
i,j\middle|i^{\prime},j^{\prime}\right\rangle\right|<1/(d_{1}d_{2}-1)$ for all
$(i,j)\neq(i^{\prime},j^{\prime})$. By 3.6 this means that the collection of
vectors $\\{|i,j\rangle\\}_{i,j}$ are linearly independent, constructively
proving the dimensionality of the operators in question to be at least
$d_{1}d_{2}$. Rearranging this gives the specified bound. ∎

##  4 Minimum twisted commutation value

In the previous section we considered finding lower bounds on the dimensions
of approximately twisting commuting operators. In the exact case, the Stone-
von Neumann theorem (c.f. 1) tell us that unitaries $x$ and $y$ for which

$\left[x,y\right]_{1/d}=0$

are not only _at least_ $d$-dimensional, but are _a multiple of_
$d$-dimensional. We might therefore hope for a more comprehensive
understanding of twisted commutation that provides more information than
simply a lower bound on the dimension. In this section we will consider the
twisted commutator in the Schatten-Ky Fan norms
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\cdot\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}:=\left\|\cdot\right\|_{(p,k)}$
with $p\geq 2$, and find the minimum possible twisted commutator value as a
function of dimension.

######  Definition 3 (Minimum twisted commutator value).

Let $\Lambda^{(p,k)}_{g,\alpha}$ be the _minimum twisted commutator value_ ,
with respect to the Schatten-Ky Fan ${(}p{,k)}$-norm, over all pairs of
unitary matrices of dimension $g$

$\Lambda_{g,\alpha}^{(p,k)}:=\min_{u,v\in{U}(g)}\left\|\left[u,v\right]_{\alpha}\right\|_{(p,k)}.$

In this language, the Stone-von Neumann theorem gives that
$\Lambda^{(p{,k})}_{g,\alpha}=0$ if and only if $g\alpha\in\mathbb{Z}$. If we
had an understanding of the values of $\Lambda^{(p{,k})}_{g,\alpha}$ where
$g\alpha\notin\mathbb{Z}$, then we could use twisted commutation value as a
way of certifying dimension. In particular, if one thinks of $\alpha$ as
fixed, and one knows the value
$\left\|\left[u,v\right]_{\alpha}\right\|_{(p,k)}$ to be less than
$\Lambda^{(p{,k})}_{g,\alpha}$ for certain dimensions $g$, then these certain
dimensions are ruled out as possible dimensions of $u$ and $v$. In this
section we will explicitly evaluate $\Lambda^{(p{,k})}_{g,\alpha}$ for $p\geq
2$.

To lower bound $\Lambda_{g,\alpha}^{(p{,k})}$, we will utilize techniques from
spectral perturbation theory to bound a related quantity known as the
_spectral distance_. By considering a family of operators which twisted
commute, we will furthermore show this bound to be tight.

######  Definition 4 (Spectral distance).

The _spectral ${(}p{,k)}$-distance_ $d_{{(}p{,k)}}(a,b)$ between two matrices
$a$ and $b$ is the ${(}p{,k)}$-norm of the vector containing the differences
between eigenvalues of the two matrices, minimized over all possible
orderings. If we let $\lambda(x)$ denote the vector of eigenvalues of a
$g\times g$ matrix $x$ then algebraically

$d_{(p,k)}(a,b):=\min_{\sigma\in
S_{g}}\left\|\sigma\left[\lambda(a)\right]-\lambda(b)\right\|_{(p,k)}=\min_{\sigma\in
S_{g}}\left(\sum_{j=1}^{k}\left|\lambda_{\sigma(j)}(a)-\lambda_{j}(b)\right|^{p}\right)^{1/p}\,,$

where the minimization is over all elements $\sigma$ of the permutation group
$S_{g}$ on $g$ symbols.

###  4.1 Frobenius spectral bound

Before attacking the spectral distance, we are first going to restrict
ourselves to the case of the Frobenius norm ($p=2$, $k=g$), where we shall
denote the norm by $\left\|\cdot\right\|_{F}$, the corresponding spectral
distance by $d_{F}(\cdot,\cdot)$, and the twisted commutator minimum by
$\Lambda_{g,\alpha}^{(F)}$. In this special case, the spectral distance
between two normal matrices is bounded by their norm difference.

######  Lemma 4.1 (Wielandt-Hoffman inequality [39]).

For normal matrices $a$ and $b$, $d_{F}(a,b)\leq\left\|a-b\right\|_{F}$.

Once again let $\eta:=e^{2i\pi\alpha}$. Applying Wielandt-Hoffman to
$\Lambda_{g,\alpha}^{(F)}$ we see that the corresponding spectral distance
provides a lower bound,

$\Lambda_{g,\alpha}^{(F)}=\min_{u,v\in U(d)}\left\|v^{\dagger}uv-\eta
u\right\|_{F}\geq\min_{u,v\in U(g)}d_{F}(v^{\dagger}uv,\eta u)=\min_{u\in
U(g)}d_{F}(u,\eta u)\,.$

Though $\left\|v^{\dagger}uv-\eta u\right\|_{F}$ depended on both $u$ and $v$,
$d_{F}(u,\eta u)$ depends only on the spectrum of $u$, making for a much
simpler optimization. This inequality will turn out to be tight for matrices
minimizing the twisted commutator value.

Denote the eigenvalues of $u$ by $\\{e^{i\theta_{j}}\\}$, then the spectral
distance in question is given by

$d_{F}^{2}(u,\eta u):=\min_{\sigma\in
S_{g}}\sum_{j=1}^{g}\left|e^{i\theta_{\sigma(j)}}-e^{i(\theta_{j}+2\pi\alpha)}\right|^{2}=\min_{\sigma\in
S_{g}}\sum_{j=1}^{g}4\sin^{2}\left(\frac{\theta_{\sigma(j)}-\theta_{j}-2\pi\alpha}{2}\right).$

Define $f(\sigma;\theta_{1},\dots,\theta_{g})$ to be the argument of the above
optimization

$\displaystyle
f(\sigma;\theta_{1},\dots,\theta_{g}):=\sum_{j=1}^{g}4\sin^{2}\left(\frac{\theta_{\sigma(j)}-\theta_{j}-2\pi\alpha}{2}\right)$
(1)

such that $d_{F}^{2}(u,\eta
u)=\min_{\sigma}f(\sigma;\theta_{1},\dots,\theta_{g})$ . The optimization of
$d_{F}^{2}(u,\eta u)$ can therefore be reduced to an optimization of
$f(\sigma;\theta_{1},\dots,\theta_{g})$.

We can now break the optimization of $f$ down into two parts. First we will
show that for any assignment of permutation and angles, there exists a cyclic
permutation, and adjusted angles, for which the value of $f$ is the same. This
will allow us to consider a minimizing permutation which has only a single
cycle without loss of generality. Secondly we shall see that, for such a
cyclic permutation, the set of angles which minimize $f$ are those that are
equally distributed around the unit circle. Given these, we will find an
explicit minimum for $f$, and thus for $d_{F}(u,\eta u)$.

######  Lemma 4.2 (Reduction to cyclic permutations).

For a given multi-cycle permutation $\sigma$ and set of angles
$\\{\theta_{j}\\}$, there exists a cyclic permutation $\sigma^{\prime}$ and
set of adjusted angles $\\{\theta_{j}^{\prime}\\}$ such that

$f(\sigma;\theta_{1},\dots,\theta_{g})=f(\sigma^{\prime};\theta_{1}^{\prime},\dots,\theta_{g}^{\prime}).$

###### Proof.

Firstly, our indices can be reordered such that the cycles of $\sigma$ are
contiguous, i.e. in cycle notation

$\sigma=(1~{}\ldots~{}k_{1}-1)\,(k_{1}~{}\ldots~{}k_{2}-1)\ldots(k_{n}~{}\ldots~{}g),$

for some $1<k_{1}\dots<k_{n}\leq g$. (Note that the result is trivially true
if $g=1$, so we restrict to $g>1$.) As $f$ only depends on the difference
between angles whose indices are within the same cycle of $\sigma$, if we
shift all the angles within the same cycle by the same amount, the value of
$f$ will not change. For example if we take the change of angle

$\theta_{j}^{\prime}:=\begin{dcases}\theta_{j}-\theta_{1}&\,\,\,1\leq
j<k_{1}\\\ \theta_{j}-\theta_{k_{1}}&k_{1}\leq j<k_{2}\\\ ~{}\quad\vdots&\\\
\theta_{j}-\theta_{k_{n}}&k_{n}\leq j\leq g.\end{dcases}$

then
$f(\sigma;\theta_{1},\dots,\theta_{g})=f(\sigma;\theta_{1}^{\prime},\dots,\theta_{g}^{\prime})$.
Notice that
$\theta_{1}^{\prime}=\theta^{\prime}_{k_{1}}=\dots=\theta_{k_{n}}^{\prime}=0$
by construction.

We now wish to merge the permutation $\sigma$ into a single cyclic permutation

$\displaystyle\sigma^{\prime}:=(1~{}\ldots~{}g).$ (2)

To do this, the only entries of the permutation which need to be changed are
those at the end of each cycle.

$\displaystyle\hskip 56.9055pt\sigma(k_{1}-1)$ $\displaystyle=1$
$\displaystyle\rightarrow$ $\displaystyle\sigma^{\prime}(k_{1}-1)$
$\displaystyle=k_{1}$ $\displaystyle\sigma(k_{2}-1)$ $\displaystyle=k_{1}$
$\displaystyle\rightarrow$ $\displaystyle\sigma^{\prime}(k_{2}-1)$
$\displaystyle=k_{2}$ $\displaystyle~{}\,\vdots$ $\displaystyle~{}\,\vdots$
$\displaystyle\sigma(g)$ $\displaystyle=k_{n}$ $\displaystyle\rightarrow$
$\displaystyle\sigma^{\prime}(g)$ $\displaystyle=1\,.$

By definition of the adjusted angles however, the only indices that change are
those for which the angles have already been made identical in the previous
step, i.e. $\theta_{\sigma(j)}^{\prime}=\theta_{\sigma^{\prime}(j)}^{\prime}$
for all $j$. As $f$ only depends on $\sigma$ through how it acts on the
angles, this means that this doesn’t alter the value of $f$, therefore
$f(\sigma;\theta_{1}^{\prime},\dots,\theta_{g}^{\prime})=f(\sigma^{\prime};\theta_{1}^{\prime},\dots,\theta_{g}^{\prime})$.
∎

Now that we have addressed the nature of the optimal permutation, namely
showing that it can be taken to be cyclic, we turn out attention to the
optimal angles.

######  Lemma 4.3.

For a given single-cycle permutation $\sigma$, the sets of angles which
optimize $f$, as defined in Eq. 1, correspond to those evenly distributed
around the unit circle, and the difference between adjacent angles
$\theta_{j}$ and $\theta_{\sigma(j)}$ is $2\pi\lfloor d\alpha\rceil/g$, where
$\left\lfloor\cdot\right\rceil$ denotes integer rounding. Moreover the
corresponding minimal value of $f$ is

$\min_{\\{\theta_{j}\\}_{j}}f(\sigma;\theta_{1},\dots,\theta_{g})=2\sqrt{g}\sin\left(\pi\left|\frac{\left\lfloor
g\alpha\right\rceil-g\alpha}{g}\right|\right).$

###### Proof.

Denote both of the terms444In saying there are two such terms we have assumed
$g\geq 3$. If $g=1$ the lemma is trivial ($f$ is constant), and if $g=2$ then
we have double counted in $f_{j}(\theta_{j})$, but our analysis of its minimum
remains valid. in $f$ which depend non-trivially on $\theta_{j}$ by
$f_{j}(\theta_{j})$. Using the double angle formula and the auxiliary angle
method, we can reduce the $\theta_{j}$ dependence to a single sinusoidal term.

$\displaystyle f_{j}(\theta_{j})$
$\displaystyle=4\sin^{2}\left(\frac{\theta_{j}-\theta_{\sigma(j)}-2\pi\alpha}{2}\right)+4\sin^{2}\left(\frac{\theta_{\sigma^{-1}(j)}-\theta_{j}-2\pi\alpha}{2}\right)$
$\displaystyle=4-4\cos\left(2\pi\alpha+\frac{\theta_{\sigma(j)}-\theta_{\sigma^{-1}(j)}}{2}\right)\cos\left(\theta_{j}-\frac{\theta_{\sigma(j)}+\theta_{\sigma^{-1}(j)}}{2}\right)\,.$

We can therefore see that the optimal $\theta_{j}$, leaving all other angles
fixed, satisfies

$\theta_{j}=\left(\theta_{\sigma(j)}+\theta_{\sigma^{-1}(j)}\right)/2~{}\mod{\pi}.$

This implies that
$\theta_{\sigma(j)}-\theta_{j}=\theta_{j}-\theta_{\sigma^{-1}(j)}\mod{2\pi}$,
i.e. $\theta_{j}$ lies in at the ‘midpoint’ of its neighbors, as described by
$\sigma$. By inducting the above argument we find that
$\theta_{\sigma(j)}-\theta_{j}=\theta_{\sigma(k)}-\theta_{k}\mod{2\pi}$ for
all $j,k$ meaning that all adjacent angles are equally spaced around the unit
circle. This means that if we have $g$ angles, and label our indices such that
$\sigma(j)=j+1\mod{g}$, then for some fixed integer $m$, the optimal angles
are of the form

$\displaystyle\theta_{j}=\theta_{1}+2\pi m(j-1)/g.$ (3)

The only free parameter left now is $m$, the spacing between adjacent points.
Plugging these angles into the definition of $f$ we find

$f(\sigma;\theta_{1},\dots,\theta_{g})=2\sqrt{g}\Bigl{|}\sin\bigl{(}\pi\left[m/g-\alpha\right]\bigr{)}\Bigr{|}.$

This is in turn minimized for $m=\left\lfloor g\alpha\right\rceil$, giving the
stated spacing and minima. ∎

As this minimum of $f$ is independent of the permutation $\sigma$, we get an
overall minimum for $f$ for free.

######  Corollary 7.

The minimum twisted commutator value (3) in the Frobenius norm
$\Lambda_{g,\alpha}^{(F)}$ is lower bounded

$\Lambda_{g,\alpha}^{(F)}\geq 2\sqrt{g}\sin\left(\pi\left|\frac{\left\lfloor
g\alpha\right\rceil-g\alpha}{g}\right|\right).$

###### Proof.

This result can be seen by recalling that the definition of $f$ in Eq. 1 gives
that

$\min_{u\in U(g)}d_{F}(u,\eta
u)=\min_{\sigma,\\{\theta_{j}\\}_{j}}f(\sigma,\theta_{1},\dots,\theta_{g}).$

As 4.2 tells us that we can consider cyclic permutations without loss of
generality, we can apply the minimum found in 4.3, giving

$\min_{u\in U(g)}d_{F}(u,\eta
u)=2\sqrt{g}\sin\left(\pi\left|\frac{\left\lfloor
g\alpha\right\rceil-g\alpha}{g}\right|\right).$

Applying the Wielandt-Hoffman theorem (4.1), we get that the above minimum
spectral distance lower bounds the twisted commutator in the Frobenius norm,
as required. ∎

###  4.2 Higher norms and tightness

With the above bound in hand, we now turn our attention to tightness. A
canonical family of operators which exhibit twisted commutation is that of the
_generalized Pauli operators_ , also known as Sylvester’s _clock and shift
matrices_

$C:=\sum_{j}\omega^{j-1}|j\rangle\langle j|,\qquad\qquad S:=\sum_{j}|j\oplus
1\rangle\langle j|$

where $\omega=e^{2i\pi/g}$ is a primitive $g$th root of unity, and $\oplus$
denotes addition modulo $g$. As $S$ simply cyclically permutes the eigenbasis
of $C$, we can see that $S^{\dagger}CS=\omega C$, or
$\left[C,S\right]_{1/g}=0$. By taking appropriate powers these operators can
also yield pairs which twisted commute with a phase that is any power of
$\omega$, specifically we see $\left[C,S^{k}\right]_{k/g}=0$. Suppose we take
such a pair and evaluate the twisted commutator at an arbitrary phase
$\eta=e^{2i\pi\alpha}$. We then find,

$\displaystyle\left\|\left[C,S^{k}\right]_{\alpha}\right\|_{F}$
$\displaystyle=\left\|CS^{k}-\eta S^{k}C\right\|_{F}$
$\displaystyle=\left\|(1-\omega^{k}\eta)CS^{k}\right\|_{F}$
$\displaystyle=\sqrt{g}\left|1-\omega^{k}\eta\right|$
$\displaystyle=2\sqrt{g}\Bigl{|}\sin\bigl{(}\pi\left(\alpha+k/g\right)\bigr{)}\Bigr{|}.$

If we now take $k=-\left\lfloor g\alpha\right\rceil$, then we saturate 7,
proving tightness of the bound on $\Lambda_{g,\alpha}^{(F)}$, allowing us to
conclude

$\displaystyle\Lambda_{g,\alpha}^{(F)}=2\sqrt{g}\sin\left(\pi\left|\frac{\left\lfloor
g\alpha\right\rceil-g\alpha}{g}\right|\right).$

For the above optimizations we restricted ourself to the $p=2$ case of the
Frobenius norm. The nature of the minimizers found allows us to pull this
analysis up into minima for the $p>2$ Schatten norms as well.

######  Theorem 6 (Minimum twisted commutation value).

Suppose that $u$ and $v$ are $g$-dimensional unitaries, then for any $p\geq 2$
the twisted commutator is lower bounded

$\Bigl{\|}\left[u,v\right]_{\alpha}\Bigr{\|}_{(p,k)}\geq
2k^{1/p}\sin\left(\pi\left|\frac{\left\lfloor
g\alpha\right\rceil-g\alpha}{g}\right|\right),$

where $\left\|\cdot\right\|_{(p,k)}$ is the $(p,k)$-Schatten-Ky Fan norm.
Moreover this bound is tight, in that sense that there exist families of
$g$-dimensional unitaries which saturate the above bounds and only depend on
$\left\lfloor g\alpha\right\rceil$, the nearest integer to $g\alpha$.

###### Proof.

By the equivalence of Schatten-Ky Fan norms, the minimum Frobenius norm will
also provide a lower bound for other ${(}p{,k)}$-norms as well. Specifically
for $p\geq 2$ we have

$\displaystyle\left\|M\right\|_{(p,k)}\geq{k^{1/p}}g^{-1/2}\left\|M\right\|_{F}.$

Applying these to the definition of $\Lambda_{g,\alpha}^{(p,k)}$, this bound
gives that
$\Lambda_{g,\alpha}^{(p.k)}\geq{k^{1/p}}g^{-1/2}\Lambda_{g,\alpha}^{(F)}$ for
$p\geq 2$. It turns out that this inequality is saturated by matrices $M$ with
flat spectra, i.e. those proportional to unitaries. It so happens that the
clock and shift operators considered to demonstrate tightness have a twisted
commutator with precisely this property, and therefore also saturate and
demonstrate the tightness of the induced $p{>}2$ bounds. We therefore conclude
that

$\Lambda_{g,\alpha}^{(p,k)}={k^{1/p}}g^{-1/2}\Lambda_{g,\alpha}^{(F)}=2{k^{1/p}}\sin\left(\pi\left|\frac{\left\lfloor
g\alpha\right\rceil-g\alpha}{g}\right|\right).$

∎

Some plots of this bound are shown in Fig. 5.

a) b)

Figure 5: The twisted commutator value minimum (in the operator norm,
$p=\infty$) $\Lambda_{g,\alpha}^{(\mathrm{Op})}$. a) The dependence on the
twisting parameter $\alpha$ for a few fixed dimensions $g$. The presence of
roots at multiples of $1/g$ are those predicted by 1. b) Now fixing the
twisting parameter $\alpha$, the dependence on the dimension $g$ is shown.
Note that $g$ can only take integer values, indicated by the circles and
pluses, with the continuous lines simply intended to guide the eye. The dotted
black line indicates an $\alpha$-independent upper bound on
$\Lambda_{g,\alpha}^{(\mathrm{Op})}$ given by applying the bound
$\left|x-\left\lfloor x\right\rceil\right|\leq 1/2$.

##  5 Applications and open questions

We now discuss several avenues for improvements, generalizations, refinements,
and applications of these ideas.

###  5.1 Local Hamiltonians

In this paper the only assumption we made about our Hamiltonian $H$ was the
presence of a spectral gap. A natural additional structure to impose is that
$H$ be a many-body Hamiltonian: decompose our Hilbert space into a tensor
product of many smaller Hilbert spaces, and let our Hamiltonian take the form

$H=\sum_{k}h_{k}$

where each term $h_{k}$ acts non-trivially on a constant number of these
tensor factor spaces. Additional to this we could also impose that the factors
on which it acts are geometrically local as well. Under this special case it
may be that either the bounds on degeneracy certification might be able to be
improved, or we might be able to prove the existence of degeneracy witnesses
with additional structure, e.g. such witnesses might act in a geometrically
local fashion.

###  5.2 Topologically ordered systems

While the notions of approximate symmetry and degeneracy of a ground band are
both robust to small perturbations, naïvely one can only consider
perturbations of a strength no larger than the gap. For topologically ordered
systems [18] however, we can afford much larger perturbations under certain
locality assumptions.

Under the influence of local perturbations, the low-energy band structure,
most notably the ground space degeneracy, is robust even if the overall
strength of the perturbation is extensive [40]. Moreover, any symmetries which
witnesses this degeneracy can be quasi-adiabatically continued [41] into
approximate symmetries which witness the degeneracy of the ground band in the
perturbed system. It is in this sense that the existence of degeneracy
witnesses can be considered robust to even rather strong perturbations, at
least for the ground band.

The family of _abelian quantum double models_ possess symmetries supported on
quasi-1D regions which satisfy twisted commutation relations related to the
braid and fusion rules of the underlying anyons [42]. More general models such
as non-abelian/twisted quantum doubles [42, 43, 44], and Levin-Wen string net
models [45] are all believed to possess symmetries which satisfy more general
commutation-like relations based on more general notions of commutation. One
possible example is the twist product [46] which only commutes the two
operators on part of the system, braiding them together.

$\Bigl{(}\sum_{i}A_{i}\otimes
A_{i}^{\prime}\Bigr{)}\infty\Bigl{(}\sum_{j}B_{j}\otimes
B_{j}^{\prime}\Bigr{)}:=\sum_{ij}A_{i}B_{j}\otimes
B_{j}^{\prime}A_{i}^{\prime}.$

An obvious extension of this work is to take various properties of these
underlying systems implied by this commutation-like relations, and see if they
too carry through into the regime of _approximate_ relations.

In a recent paper, Bridgeman et. al. sought to classify the phases of 2D
topologically ordered spin systems belonging to the same phase as abelian
quantum doubles [35]. This was done by numerically optimizing twisted pairs of
symmetries. This optimization was done over a tensor network [47, 48] ansatz
of quasi-1D operators known as matrix product operators. For two operators $L$
and $R$, supported on intersecting quasi-1D regions, the cost function takes
the form

$C(L,R;\alpha)\propto\epsilon_{L}^{2}+\epsilon_{R}^{2}+\delta^{2}$

where $\epsilon_{L}:=\left\|\left[L,H\right]\right\|_{F}$,
$\epsilon_{R}:=\left\|\left[R,H\right]\right\|_{F}$, and
$\delta=\left\|\left[L,R\right]_{\alpha}\right\|_{F}$.

Minimizing $C(L,R;\alpha)$ over $L$ and $R$ for a fixed $\alpha$, they found
that in the abelian quantum doubles the minimizers were unitary, and that both
$\epsilon_{L}$ and $\epsilon_{R}$ vanish to within numerical accuracy, leaving
only the twisted commutator value $\delta$. By observing the values of
$\alpha$ for which the minimum cost is low, they hoped to classify the
topological phases of the underlying Hamiltonian. By 2 we know that, at least
to within numerical accuracy, the ribbon operators found restrict down to
ground symmetries with the same twisted commutation relations. In Fig. 6 we
compare, for the $\mathbb{Z}_{5}$ quantum double model, their numerically
obtained values of this twisted commutator $\delta_{\textrm{min}}$ with the
minimal possible twisted commutator $\Lambda^{(F)}_{5,\alpha}$, showing close
agreement and lending support to the efficacy of this numerical method.

Figure 6: The twisted commutator value for ribbon operators on the
$\mathbb{Z}_{5}$ quantum double model, as calculated using the algorithm of
[35], as compared to the minimum possible twisted commutator value in
$5$-dimensions. Note that the difference between the two plots is no more than
$3\times 10^{-13}$.

###  5.3 Quantum codes

One class of systems for which twisted commuting symmetries play a special
role are quantum codes, in which they can be interpreted as logical operators
[49, 19, 50]. For a quantum code encoding $N$ codewords, the logical algebra
must correspond to $\text{Mat}_{N}(\mathbb{C})$, which necessarily contains a
pair of operators $X$ and $Z$ such that $\left[X,Z\right]_{1/N}=0$; indeed the
algebra generated by any two such operators $X$ and $Z$ is itself
$\text{Mat}_{N}(\mathbb{C})$.

While the existence of logical operators which $\alpha=1/N$ twisted commute
can be ensured, we might only see and expect operators with twisted
commutations characteristic of smaller ground spaces if we restrict the
locality of these operators. Though the logical algebra is given by
$\text{Mat}_{N}(\mathbb{C})$, this space often naturally decomposes into a
tensor product decomposition: the logical qudits. By geometrically restricting
where on the system the operators can act, we can often restrict which factors
the logical operators have nontrivial commutation relations with. This is the
case for celebrated examples such as the toric code [42]. This can be seen
above in Fig. 6, where the logical operators are restricted to string-like
regions that are only sensitive to one $\text{Mat}_{5}(\mathbb{C})$ factor of
the larger $\text{Mat}_{25}(\mathbb{C})$ logical algebra; one of the two
5-level qudits. In the same way that Ref. [35] sought to use the existence of
twisted commuting symmetries to classify topological phases, how this
existence varies with respect to the geometry imposed on these operators might
provide a tool to probe what portion of the logical algebra is accessible on
certain regions.

In the language of quantum codes, our results can be interpreted as bounds
below which approximate logical operators imply the existence of a certain
number of code words. A possible avenue for future work is whether there
exists bounds below which not only can the number of codestates be bounded,
but reliable encoding, decoding, and error correction can all be performed
with these approximate logical operators. Understanding when information
stored in such states is approximately preserved, as opposed to exactly
preserved [51], could have interesting applications in approximate quantum
error correction.

### Acknowledgements

We thank Jacob Bridgeman for fruitful comments, and for computing the
numerical data for Fig. 6 using the algorithm of Ref. [35]. For the use of
American English in this paper, CTC apologises to the Commonwealth of
Australia. This work was supported by the Australian Research Council via EQuS
project number CE11001013 and STF was supported by an Australian Research
Council Future Fellowship FT130101744.

## References

  * [1] H. Weyl, “Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung),” Mathematische Annalen 71, 4, 441–469, (1911).
  * [2] P. Rosenthal, “Are Almost Commuting Matrices Near Commuting Matrices?,” The American Mathematical Monthly 76, 925, (1969).
  * [3] P. R. Halmos, “Some unsolved problems of unknown depth about operators on Hilbert space,” Proceedings of the Royal Society of Edinburgh, Section: A Mathematics 76, 1, 67–76, (1976).
  * [4] S. Szarek, “On almost commuting Hermitian operators,” Rocky Mountain Journal of Mathematics 20, 583–591, (1990).
  * [5] K. R. Davidson, “Almost commuting hermitian matrices,” Mathematica Scandinavica 56, 222, (1985).
  * [6] I. D. Berg and K. R. Davidson, “Almost commuting matrices and a quantitative version of the Brown-Douglas-Fillmore theorem,” Acta Mathematica 166, 121–161, (1991).
  * [7] H. Lin, “Almost commuting selfadjoint matrices and applications,” in Operator algebras and their applications, 193–223, Fields Institute Communications, Vol. 13, (1997).
  * [8] I. Kachkovskiy and Y. Safarov, “Distance to normal elements in C*-algebras of real rank zero,” Journal of the American Mathematical Society 29, 61–80, arXiv:1403.2021, (2015).
  * [9] P. Friis and M. Rørdam, “Almost commuting self-adjoint matrices - a short proof of Huaxin Lin’s theorem,” Journal für die reine und angewandte Mathematik 1996, 479, 121–131, (1996).
  * [10] M. B. Hastings, “Making Almost Commuting Matrices Commute,” Communications in Mathematical Physics 291, 321–345, arXiv:0808.2474, (2009).
  * [11] D. Voiculescu, “Asymptotically commuting finite rank unitary operators without commuting approximants,” Acta Scientiarum Mathematicarum 45, 429–431, (1983).
  * [12] R. Exel and T. Loring, “Almost commuting unitary matrices,” in Proceedings of the American Mathematical Society, 106, 913–913, (1989).
  * [13] R. Exel and T. A. Loring, “Invariants of almost commuting unitaries,” Journal of Functional Analysis 95, 364–376, (1991).
  * [14] M.-D. Choi, “Almost Commuting Matrices Need not be Nearly Commuting,” Proceedings of the American Mathematical Society 102, 529, (1988).
  * [15] H. Lin, “Almost Commuting Unitaries and Classification of Purely Infinite Simple C*-Algebras,” Journal of Functional Analysis 24, 1–24, (1998).
  * [16] T. J. Osborne, “Almost commuting unitaries with spectral gap are near commuting unitaries,” arXiv:0809.0602, (2008).
  * [17] T. A. Loring and A. P. W. Sørensen, “Almost commuting orthogonal matrices,” Journal of Mathematical Analysis and Applications 420, 1051–1068, arXiv:1311.4575, (2014).
  * [18] X.-G. Wen, “Topological Order: From Long-Range Entangled Quantum Matter to a Unified Origin of Light and Electrons,” ISRN Condensed Matter Physics 2013, 1–20, arXiv:1210.1281, (2013).
  * [19] J. Preskill, Quantum Error Correction.  Cambridge University Press, Cambridge, (2013).
  * [20] B. J. Brown, D. Loss, J. K. Pachos, C. N. Self, and J. R. Wootton, “Quantum memories at finite temperature,” Reviews of Modern Physics 88, 045005, arXiv:1411.6643, (2016).
  * [21] L. Landau, E. Lifshitz, V. Berestetskii, and L. Pitaevskii, Course of Theoretical Physics.  Pergamon Press, (1951).
  * [22] B. Brown, S. T. Flammia, and N. Schuch, “Computational difficulty of computing the density of states,” Physical Review Letters 107, arXiv:1010.3060, (2011).
  * [23] C. T. Chubb and S. T. Flammia, “Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time,” 1–32, arXiv:1502.06967, (2015).
  * [24] Y. Huang, “A polynomial-time algorithm for approximating the ground state of 1D gapped Hamiltonians,” arXiv:1406.6355v3, (2014).
  * [25] J. Yang and H.-k. Du, “A note on commutativity up to a factor of bounded operators,” Proceedings of the American Mathematical Society 132, 1713–1721, (2004).
  * [26] B. C. Hall, Quantum Theory for Mathematicians, 267 of Graduate Texts in Mathematics.  Springer New York, (2013).
  * [27] J. Rosenberg, “A selective history of the Stone-von Neumann theorem,” in Contemporary Mathematics, 331–353, (2004).
  * [28] M. Said, “Almost Commuting Elements in Non-Commutative Symmetric Operator Spaces,” (2014).
  * [29] S. Eilers and R. Exel, “Finite dimensional representations of the soft torus,” Proceedings of the American Mathematical Society 130, 727–732, arXiv:math/9810165, (1998).
  * [30] R. Exel, “The soft torus and applications to almost commuting matrices,” Pacific Journal of Mathematics 160, 207–217, (1993).
  * [31] L. Babai and K. Friedl, “Approximate representation theory of finite groups,” in Proceedings 32nd Annual Symposium of Foundations of Computer Science, 733–742, IEEE Comput. Soc. Press, (1991).
  * [32] K. Friedl, “Near-representations of finite groups,” (2003).
  * [33] C. Moore and A. Russell, “Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups,” SIAM Journal on Discrete Mathematics 29, 182–197, arXiv:1009.6230, (2015).
  * [34] A. R. Bernstein, “Almost Eigenvectors for Almost Commuting Matrices,” SIAM Journal on Applied Mathematics 21, 232–235, (1971).
  * [35] J. C. Bridgeman, S. T. Flammia, and D. Poulin, “Detecting Topological Order with Ribbon Operators,” arXiv:1603.02275, (2016).
  * [36] R. Bhatia, Matrix Analysis, 169 of Graduate Texts in Mathematics.  Springer New York, (1997).
  * [37] R. Schatten, Norm Ideals of Completely Continuous Operators.  Springer Berlin, Heidelberg, (1960).
  * [38] J. Von Neuman, “Some matrix inequalities and metrization of matric spaces,” Tomsk Univ. Rev. 1, 286–299, (1937).
  * [39] A. J. Hoffman and H. W. Wielandt, “The variation of the spectrum of a normal matrix,” Duke Mathematical Journal 20, 37–39, (1953).
  * [40] S. Bravyi, M. B. Hastings, and S. Michalakis, “Topological quantum order: Stability under local perturbations,” Journal of Mathematical Physics 51, 093512, arXiv:1001.0344, (2010).
  * [41] M. B. Hastings and X.-G. Wen, “Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance,” Physical Review B 72, 045141, arXiv:cond-mat/0503554, (2005).
  * [42] A. Kitaev, “Fault-tolerant quantum computation by anyons,” Annals of Physics 303, 2–30, arXiv:quant-ph/9707021, (2003).
  * [43] Y. Hu, Y. Wan, and Y.-S. Wu, “Twisted Quantum Double Model of Topological Phases in Two–Dimension,” Physical Review B 87, 125114, arXiv:1211.3695, (2012).
  * [44] R. Dijkgraaf and E. Witten, “Topological gauge theories and group cohomology,” Communications in Mathematical Physics 129, 393–429, (1990).
  * [45] M. A. Levin and X.-G. Wen, “String-net condensation: A physical mechanism for topological phases,” Physical Review B 02139, arXiv:cond-mat/0404617, (2004).
  * [46] J. Haah, “An Invariant of Topologically Ordered States Under Local Unitary Transformations,” Communications in Mathematical Physics 342, 771–801, arXiv:1407.2926, (2016).
  * [47] J. C. Bridgeman and C. T. Chubb, “Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks,” arXiv:1603.03039, (2016).
  * [48] R. Orús, “A practical introduction to tensor networks: Matrix product states and projected entangled pair states,” Annals of Physics 349, 117–158, arXiv:1306.2164, (2014).
  * [49] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information 10th Anniversary Edition.  Cambridge University Press, Cambridge, (2011).
  * [50] E. Knill, R. Laflamme, and L. Viola, “Theory of Quantum Error Correction for General Noise,” Physical Review Letters 84, 2525–2528, arXiv:quant-ph/9604034, (2000).
  * [51] R. Blume-Kohout, H. K. Ng, D. Poulin, and L. Viola, “Information-preserving structures: A general framework for quantum zero-error information,” Physical Review A 82, 062306, arXiv:1006.1358, (2010).
  * [52] K. Glashoff and M. M. Bronstein, “Almost-commuting matrices are almost jointly diagonalizable,” arXiv:1305.2135, (2013).
  * [53] F. Gygi, J.-L. Fattebert, and E. Schwegler, “Computation of Maximally Localized Wannier Functions using a simultaneous diagonalization algorithm,” Computer Physics Communications 155, 1–6, (2003).
  * [54] M. Congedo, B. Afsari, A. Barachant, and M. Moakher, “Approximate Joint Diagonalization and Geometric Mean of Symmetric Positive Definite Matrices,” Public Library of Science, 10, 4, (2015).
  * [55] D. Eynard, A. Kovnatsky, and M. M. Bronstein, “Laplacian colormaps: a framework for structure-preserving color transformations,” Computer Graphics Forum 33, 215–224, arXiv:1311.0119, (2014).
  * [56] C. Pearcy and A. Shields, “Almost commuting matrices,” Journal of Functional Analysis 33, 332–338, (1979).
  * [57] S. H. Schanuel, “A combinatorial problem of Shields and Pearcy,” Proceedings of the American Mathematical Society 65, 185–185, (1977).
  * [58] A. Gyárfás and J. Lehel, “Covering and coloring problems for relatives of intervals,” Discrete Mathematics 55, 167–180, (1985).

##  Appendix A Approximate shared eigenvectors for approximately commuting
matrices

In this section we will show that for two approximately commuting matrices, an
approximate shared eigenvector exists. This problem has been considered before
by Bernstein [34], who showed the following result.

######  Theorem 8 ([34]).

Take $A$ and $B$ to be complex matrices of dimension $n\geq 2$. If
$\left\|B\right\|\leq 1$, and for some $\delta>0$ we have

$\left\|\left[A,B\right]\right\|\leq\frac{\delta^{n}(1-\delta)}{1-\delta^{n-1}},$

then for each eigenvalue $\lambda$ of $A$, there exists a $\mu$ and normalized
$|x\rangle$ such that

$\left\|A|x\rangle-\lambda|x\rangle\right\|,\left\|B|x\rangle-\mu|x\rangle\right\|\leq\delta.$

Notice above the required bound on the commutator scales like
${\mathcal{O}(\delta^{n})}$ for small $\delta$. Below we will improve this
dimension scaling by adding the additional assumption that one of the matrices
is normal, allowing us to bring this down to a
${\mathcal{O}(\delta^{2}/n^{2})}$ dependence. First we will state the more
general result, which only requires one of the matrices to be normal, followed
by a more specialized result which applies when both matrices are normal.

The existence of an entire basis of shared approximate eigenvectors is closely
related to approximate joint diagonalization, a problem that has been widely
consideredand has found application in fields such as quantum chemistry [53],
machine learning [54] and image processing [55]. This literature is too vast
to review in this appendix, but see Ref. [52] for a discussion of the
relationship between approximately commuting matrices and joint
diagonalization. Techniques similar to those used below have also been used in
Ref. [56] to address the related problem of constructing nearby exactly
commuting operators, in the case in which one matrix is Hermitian. Whilst this
analysis gives better bounds than those presented below, it leverages a
combinatorical construction [57] that explicitly uses the reality of the
eigenvalues, and therefore cannot be directly applied to the case we will
consider in which one matrix is normal, but not necessarily Hermitian.

Take $A$ and $B$ to be $n\times n$ matrices. Let $A$ be normal, with an
eigenvalue decomposition $A=\sum_{i}\lambda_{i}|i\rangle\langle i|$. Next take
$\lambda$ to be a specific eigenvalue of $A$. Let $I_{0}$ be the singleton set
containing the index corresponding to $\lambda$, or all these indices if
$\lambda$ is degenerate. Define $I_{k}$ to be all the indices whose
eigenvalues are within some radius $r>0$ in the complex plane (to be chosen
later) of those in $I_{k-1}$, i.e.

$I_{k}:=\left\\{i\,\middle|\,\exists j\in
I_{k-1}:\left|\lambda_{i}-\lambda_{j}\right|\leq r\right\\}.$

Clearly this sequence becomes fixed after at most $n$ terms, and so let
$I:=I_{n}$ be this fixed point. Intuitively $I$ can be thought of as the
indices corresponding to eigenvalues which form a cluster around $\lambda$
where every eigenvalue in the cluster is linked to at least one other by a
disk of radius $r$ in the complex plane.

By construction this set has two properties we require. First it is bounded
away from any other index,

$i\in I,j\notin I\implies\left|\lambda_{i}-\lambda_{j}\right|>r$

Second, because all of the eigenvalues corresponding to elements in $I$ have
nearby neighbors in $I$, this means that the diameter of the disk containing
all of the eigenvalues in $I$ has a diameter bounded by at most $nr$,

$i\in I\implies\left|\lambda_{i}-\lambda\right|\leq nr\,.$

Next let $V$ be the space spanned by the eigenvectors whose indices lies in
$I$,

$V:=\operatorname{Span}\left\\{|i\rangle\middle|\,i\in I\right\\}.$

Denoting the orthogonal complement of $V$ by $\bar{V}$, then we can decompose
both $A$ and $B$ into blocks on $V\oplus\bar{V}$ as

$A=\begin{pmatrix}A_{V}&\\\ &A_{\bar{V}}\end{pmatrix}\qquad\text{and}\qquad
B=\begin{pmatrix}B_{VV}&B_{\bar{V}V}\\\
B_{V\bar{V}}&B_{\bar{V}\bar{V}}\end{pmatrix}.$

######  Lemma A.1.

If $\left\|\left[A,B\right]\right\|\leq\epsilon$, with $A$ normal and
decomposed as above, then $A_{V}$ is close to scalar, and the off-diagonal
blocks of $B$ are bounded as

$\left\|A_{V}-\lambda\mathbbm{1}_{V}\right\|\leq
nr\qquad\text{and}\qquad\left\|B_{\bar{V}V}\right\|\leq n\epsilon/2.$

###### Proof.

Given that $A$ is normal, we can see that $A_{V}$ is approximately scalar due
to the bound between eigenvalues in $I$:

$\displaystyle\left\|A_{V}-\lambda\mathbbm{1}_{V}\right\|=\max_{i\in
I}\left|\lambda_{i}-\lambda\right|\leq nr.$

Next, using the fact that the operator norm dominates any component of a
matrix, we can simply evaluate the relevant component of the commutator to
bound elements of $B$:

$\displaystyle\epsilon$ $\displaystyle\geq\bigl{\|}\left[A,B\right]\bigr{\|}$
$\displaystyle\geq\left|\langle i|\left[A,B\right]|j\rangle\right|$
$\displaystyle=\left|\langle i|\left[AB-BA\right]|j\rangle\right|$
$\displaystyle=\left|\lambda_{i}-\lambda_{j}\right|\cdot\left|\left\langle
i\middle|B\middle|j\right\rangle\right|\,.$

 In the eigenbasis of $A$, the components of $B_{\bar{V}V}$ correspond to
$\left\langle i\middle|B\middle|j\right\rangle$ for $i\notin I$, $j\in I$. By
construction of $I$ we have that $\left|\lambda_{i}-\lambda_{j}\right|>r$, and
so

$\left|\left\langle
i\middle|B\middle|j\right\rangle\right|\leq\frac{\epsilon}{\left|\lambda_{i}-\lambda_{j}\right|}<\frac{\epsilon}{r}.$

This implies therefore that
$\left\|B_{\bar{V}V}\right\|_{\text{max}}<\epsilon/r$, where
$\left\|\cdot\right\|_{\max}$ denotes the elementwise max-norm. Using the fact
that the operator norm exceeds the max-norm by at most the square root of the
number of elements, we get

$\left\|B_{\bar{V}V}\right\|\leq\left\|B_{\bar{V}V}\right\|_{\text{max}}\times\sqrt{\dim
V\times\dim\bar{V}}.$

Given that $\dim V+\dim\bar{V}=n$, we have that $\dim V\times\dim\bar{V}\leq
n^{2}/4$, and so

$\left\|B_{\bar{V}V}\right\|<n\epsilon/2r\,.$

∎

Using these bounds, we can now put bounds on an approximate shared
eigenvector. Imposing normality on both matrices, we can even impose the
stricter requirement that both of the approximate eigenvalues are in fact
exact eigenvalues.

######  Theorem A.1 (Shared approximate eigenvector).

Suppose that $A$ and $B$ are $n\times n$ matrices, such that $A$ is normal and
$\left\|\left[A,B\right]\right\|\leq\epsilon$. For any $\lambda$ which is an
eigenvalue of $A$, there exists a normalized $|u\rangle$ and $\mu$ such that

$\left\|A|u\rangle-\lambda|u\rangle\right\|,\left\|B|u\rangle-\mu|u\rangle\right\|\leq
n\sqrt{\epsilon/2}.$

If $B$ is also normal, then for any $\lambda$ which is an eigenvalue of $A$,
there exists a $\nu$ which is also an eigenvalue of $B$ and normalized
$|w\rangle$ such that

$\left\|A|w\rangle-\lambda|w\rangle\right\|,\left\|B|w\rangle-\nu|w\rangle\right\|\leq
n\sqrt{\epsilon}.$

###### Proof.

Take $|u\rangle$ to be a right eigenvector of $B_{VV}$ (contained within $V$),
of eigenvalue $\mu$. By A.1, this then gives that the relevant errors with
respect to $A$ and $B$ behave as:

$\displaystyle\left\|A|u\rangle-\lambda|u\rangle\right\|$
$\displaystyle=\left\|A_{V}|u\rangle-\lambda|u\rangle\right\|$
$\displaystyle\left\|B|u\rangle-\mu|u\rangle\right\|$
$\displaystyle=\left\|B_{VV}|u\rangle-\mu|u\rangle+B_{\bar{V}V}|u\rangle\right\|$
$\displaystyle=\left\|(A_{V}-\lambda\mathbbm{1})|u\rangle\right\|$
$\displaystyle=\left\|B_{\bar{V}V}|u\rangle\right\|$
$\displaystyle\leq\left\|A_{V}-\lambda\mathbbm{1}\right\|$
$\displaystyle\leq\left\|B_{\bar{V}V}\right\|$ $\displaystyle\leq nr$
$\displaystyle<n\epsilon/2r\,.$

If we now let $r=\sqrt{\epsilon/2}$, we get the stated overall bound of
$n\sqrt{\epsilon/2}$.

For the case of both matrices being normal, we can show that any approximate
eigenvalue must lie near an exact eigenvalue. Taking $|w\rangle$ once again to
be a right eigenvector of $B_{VV}$ with eigenvalue $\nu^{\prime}$ (for a
different value of $r$ to $|u\rangle$), we can see that

$\displaystyle\left\|B|w\rangle-\nu^{\prime}|w\rangle\right\|\leq
n\epsilon/2r\qquad\implies\qquad\langle
w|(B-\nu^{\prime})^{\dagger}(B-\nu)|w\rangle\leq n^{2}\epsilon^{2}/4r^{2}.$

As $(B-\nu^{\prime})^{\dagger}(B-\nu^{\prime})$ is positive semi-definite, the
existence of such a $|w\rangle$ implies
$(B-\nu^{\prime})^{\dagger}(B-\nu^{\prime})$ possesses an eigenvalue at most
$n^{2}\epsilon^{2}/4r^{2}$. By the normality of $B$, this implies in turn that
$B$ contains an eigenvalue $\nu$ such that $\left|\nu-\nu^{\prime}\right|\leq
n\epsilon/2r$. Using this we can see that the error with respect to $B$ gains
a factor of $2$

$\displaystyle\left\|B|w\rangle-\nu|w\rangle\right\|\leq\left\|B|w\rangle-\nu^{\prime}|w\rangle\right\|+\left|\nu-\nu^{\prime}\right|\leq
n\epsilon/r.$

Now taking $r=\sqrt{\epsilon}$, we find the stated bound of
$n\sqrt{\epsilon}$. ∎

##  Appendix B An algorithm for the certifiable degeneracy of a twisted pair

In this appendix we sketch how, for a given pair of parameters $\alpha$ and
$\delta$, we can calculate the minimum possible dimension of unitaries $u$ and
$v$ such that
${\left|\kern-1.72218pt\left|\kern-1.72218pt\left|\left[u,v\right]_{\alpha}\right|\kern-1.72218pt\right|\kern-1.72218pt\right|}\leq\delta.$
Lemmas 3.1 and 3.2 give that for all $j\in\mathbb{Z}$, there exists an
eigenvalue $e^{i\phi_{j}}$ of $u$ such that

$\left|\phi_{j}-2\pi\alpha j\right|\leq\cos^{-1}(1-\left|j\right|\delta).$

The question now is to find the minimum number of eigenvalues such that at
least one lies in each of the above arcs. This is known as the _transversal
number_ , and can be efficiently calculated by a greedy algorithm [58]. We now
sketch this algorithm for the example parameters $\alpha=1/4$ and $\delta=1/2$
(indicated by the turquoise dot in Fig. 3).

The first thing to note is that these arcs are trivial for
$\delta\left|j\right|\geq 2$, in that they are the entire unit circle. For
this reason we need only consider a finite number of arcs for $j=-\lfloor
2/\delta\rfloor,\ldots,\lfloor 2/\delta\rfloor$. In our case this corresponds
$j=-3,\dots,3$. Below we have drawn these non-trivial arcs, omitting the
trivial $j=0$ arc.

Next we note that the $j=0$ arc is simply a point, implying that $u$ must
contain a $+1$ eigenvalue. Given this, any arc containing $+1$ can be thrown
away (indicated in red below), allowing us to unfold our arcs on a circle into
intervals on a line.

We then take the intervals to be sorted by end-point. Considering each
interval in order, we place an eigenvalue at the end of each interval as
necessary, indicated as a green line below. Note that any interval which
already contains an included eigenvalue when we arrive at it can be ignored,
indicated by the red interval below.

Including the already found eigenvalue at $+1$, this gives us the minimum
number of points necessary to satisfy each arc. Applying the algorithm for a
large number of points, we can plot the certified degeneracy as in Fig. 3.