# Complete homotopy invariants for translation invariant symmetric quantum
walks on a chain

C. Cedzich  Institut für Theoretische Physik, Leibniz Universität Hannover,
Appelstr. 2, 30167 Hannover, Germany  Institut für Theoretische Physik,
Universität zu Köln, Zülpicher Straße 77, 50937 Köln, Germany  T. Geib
Institut für Theoretische Physik, Leibniz Universität Hannover, Appelstr. 2,
30167 Hannover, Germany  C. Stahl  Institut für Theoretische Physik, Leibniz
Universität Hannover, Appelstr. 2, 30167 Hannover, Germany  L. Velázquez
Departamento de Matemática Aplicada & IUMA, Universidad de Zaragoza, María de
Luna 3, 50018 Zaragoza, Spain  A. H. Werner  QMATH, Department of Mathematical
Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen,
Denmark,  NBIA, Niels Bohr Institute, University of Copenhagen, Denmark  R. F.
Werner  Institut für Theoretische Physik, Leibniz Universität Hannover,
Appelstr. 2, 30167 Hannover, Germany

###### Abstract

We provide a classification of translation invariant one-dimensional quantum
walks with respect to continuous deformations preserving unitarity, locality,
translation invariance, a gap condition, and some symmetry of the tenfold way.
The classification largely matches the one recently obtained
(arXiv:1611.04439) for a similar setting leaving out translation invariance.
However, the translation invariant case has some finer distinctions, because
some walks may be connected only by breaking translation invariance along the
way, retaining only invariance by an even number of sites. Similarly, if walks
are considered equivalent when they differ only by adding a trivial walk,
i.e., one that allows no jumps between cells, then the classification
collapses also to the general one. The indices of the general classification
can be computed in practice only for walks closely related to some translation
invariant ones. We prove a completed collection of simple formulas in terms of
winding numbers of band structures covering all symmetry types. Furthermore,
we determine the strength of the locality conditions, and show that the
continuity of the band structure, which is a minimal requirement for
topological classifications in terms of winding numbers to make sense, implies
the compactness of the commutator of the walk with a half-space projection, a
condition which was also the basis of the general theory. In order to apply
the theory to the joining of large but finite bulk pieces, one needs to
determine the asymptotic behaviour of a stationary Schrödinger equation. We
show exponential behaviour, and give a practical method for computing the
decay constants.

##  1 Introduction

The topological classification of quantum matter has recently attracted a lot
of attention [31, 32, 15, 57, 54, 25, 29, 30, 45]. It seems that this
perspective provides us with some system properties which are stable beyond
expectations. Whatever more detailed question one might ultimately wish to
investigate, understanding this classification is as essential as a first step
as knowing about continents before studying a map in an atlas. The basic
pattern of classification, and at the same time the guarantee for its
stability, is typically homotopy theory. That is, we consider two systems to
be equivalent, or “in the same topological phase”, if one can be deformed
continuously into the other while retaining some key properties. The
classification depends critically on these constraints. The typical ones are:
discrete symmetries, a spectral gap and some finite range condition
(locality). In the discrete time setting, where dynamics is in discrete steps,
unitarity is a further constraint. For the description of bulk matter,
translation invariance is also often imposed. For translation invariant
systems one can go to momentum space, where the unitary time step or, in the
continuous time case the Hamiltonian can be diagonalized for each quasi-
momentum separately, leading to a vector bundle over the Brillouin zone.
Locality amounts to a smoothness condition for this bundle, and symmetry and
gap conditions also translate easily. However, in this setting some of the
most interesting phenomena are absent, namely all those relating to boundary
effects, when two bulk systems in different phases are joined. Folklore has it
that when these bulk phases can only be joined by closing a spectral gap on
the way, then the gap must “close at the boundary”, i.e., we expect
eigenvalues or modes at the boundary. Plausible as this may seem, proving such
statements is another matter. Since it involves a non-translation invariant
situation, the vector bundle classification is no longer available, and while
translation invariant systems (say, with finite range) are described by
finitely many parameters, the space of possible deformations becomes vastly
larger.

For the case of one dimensional discrete time systems (“quantum walks”) [22,
14, 28, 13, 2] we have provided a classification in terms of three independent
indices
$(\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W),\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}(W),\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W))$
taking values in a certain index group depending on the symmetries imposed
[11]. The classification makes no assumption on translation invariance and is
shown to be complete in the sense that two walks can be deformed into each
other if and only if these indices coincide. This classification is mostly in
agreement with the intuitions of the heuristic literature about translation
invariant systems [36, 34, 6, 8, 9], where these triples are of the form
$(-n,0,n)$. It also sharpens the stability properties of the classification.
In particular, in contrast to the continuous time case, there are walks which
differ only in a finite region, but can still not be deformed into each other,
i.e., local perturbations are not necessarily “gentle”. The index
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}(W)$ measures exactly
this difference.

To our surprise we found that some aspects of the seemingly simpler,
translation invariant subcase presented additional difficulties. First, one
would like to have a straightforward formula for the indices in the
translation invariant case. These formulas existed in the solid state
literature, but we had to connect them to the general classification of walks
in [11].

Second, the completeness problem had to be addressed (Sect. 3). The theory in
[11] asserts a complete classification, meaning that walks with equal indices
can actually be deformed into each other. But when these walks are translation
invariant, it is not a priori clear whether this deformation can be chosen to
preserve translation invariance as well. In fact, we show below that this is
only true for two of the five symmetry types with non-trivial invariant. For
the remaining three we introduce an additional binary homotopy invariant,
which together with the index from [11] is complete. The additional invariant
turns out to be unstable in several ways: It trivializes, when we allow
regrouping of neighbouring cells, i.e., breaking the translation invariance to
invariance only under even translations. The same happens if we allow addition
of trivial walks (those that act separately and equally in every cell), as is
customary in “stable” homotopy. Thus allowing either stabilizing with trivial
additions or period-2 regrouping the index from [11] is complete even in the
translation invariant setting.

Third, the general theory used a very weak locality condition, allowing the
amplitudes for long jumps to decay like $|x|^{-1-\varepsilon}$. In the
translation invariant setting the decay of jump amplitudes should translate
into a smoothness property of the band structure, but which? We show in Sect.
2 that, while locality in the sense of a norm limit of banded matrices
translates exactly into continuity, the locality condition of [11] translates
to the weaker property “quasi-continuity” of the bands. It is a challenge to
state index formula in this setting. We carefully state these as winding
numbers, which only require continuity, not differentiability of the walk
unitary as a function on the Brillouin zone (the most common case). In the
quasi-continuous case this would be replaced by radial limits of winding
numbers of analytic functions with a discontinuous boundary behaviour.

Finally, we had discussed in [11] how the theory, which is set up for infinite
systems, actually applies “approximately” to finite systems. Would protected
boundary eigenvalues appear near the interface between two long but finite
intervals of distinct bulk phases? The crucial quantity here is the
exponential behaviour of solutions of the stationary Schrödinger equation for
the translation invariant versions of the bulk. This is a system of linear
recursion relations, which cannot in general be solved for the highest term,
so the standard theory of exponential behaviour of solutions to finite
difference equations does not immediately apply. Nevertheless, exponential
behaviour is shown in full generality in Sect. 4.

In several contexts (e.g., [11, 23]) we have seen that walks exhibit non-
trivial additional invariants compared to the Hamiltonian case. However, in
the translation invariant case the difference is not so pronounced. The
essential gap condition then implies that the “effective Hamiltonian” $H_{\rm
eff}=i\log W$ is well-defined with a branch cut on the negative real axis.
This provides a continuous (hence homotopy compatible) mapping between the
discrete and the continuous time case. Therefore, Theorems from the literature
on Hamiltonian systems can be taken over. Conversely, our results of Sects. 2
and 3 apply to the Hamiltonian case without further ado.

###  1.1 Connection to the literature

Topological phenomena are well-studied in many areas of physics, and
consequently there are many settings in which related questions are
investigated, some belonging to different disciplines and scientific cultures.
Therefore, we give a perhaps unusually extended (and slightly subjective)
description of known and potential connections, including pointers to the
literature. We are fully aware that we cannot give full justice to this rich
field, and apologize for any serious omissions.

Our own point of departure was in the quantum information community
(mathematical physics division). For many years the Hannover group has enjoyed
a close collaboration with the experimental group in Bonn [3, 1, 14], who
realize quantum walks of neutral atoms in an optical lattice. Naturally, this
has partly determined our framework. Interest in this community was initially
in long time asymptotics (ultimately with algorithms in mind) and in recent
years in the possibility to recast some phenomena of interest in solid state
physics for quantum simulation in a completely controlled environment.

Some of the main connections of our work to work done in related fields are
the following:

  * •

Most of the physics literature on topological phases is for free fermion
systems in the continuous time (Hamiltonian) case [4, 27, 65, 33, 31, 32, 57,
54, 51, 44, 43, 26]. In our paper the Hilbert space is a straightforward
abstracted version of a system Hilbert space with basis vectors labelled by
the discrete position and internal excitations of a walking atom. In contrast,
for a free fermion system it is a space of modes of elementary excitations of
a many particle system, whose basis vectors label creation/annihilation of
both particles and holes (Nambu space). Therefore the particle-hole symmetry
is built into the structure from the outset, whereas it may or may not hold in
our setting.

  * •

The solid state literature is rather uneven in its level of rigour. Also, as
we found in retrospect, argumentation for general statements is not
emphasized, and often not given in detail, although the authors could have
done so. We are far from criticizing this, but, as a complementary approach
follow a different tack, in order to achieve the kind of clarity we require as
mathematical physicists, and in the process to spare mathematically inclined
readers some frustration. We are also in a collaboration [7] with a colleague
closer to the solid state community, to straighten out conceptual differences.

  * •

We are working in the discrete time case, with a single unitary operator $W$
defining the dynamical step. This often arises in the Floquet setting, in
which $W$ is one period of a periodically driven Hamiltonian system. Of
course, it can be argued that the experimental system of our partners is
precisely of this type. In previous work [23, 11] we found additional
topological invariants in comparison to the Hamiltonian case, i.e. a non-
trivial interplay of the locality, gap and unitarity requirements. The
difference in the current paper, which is concerned with the translation
invariant case only, is not so great. In fact, the basic index formulas ((24),
(28), (42), (43), (55)) can be found in the literature (we thank a referee for
tracking (55) in [44]), as applied to the “effective Hamiltonian” $H_{\rm
eff}=-i\log{W}$. This works in the translation invariant case, because there
can be no eigenvalues in the spectral gap of $W$ at $-1$, so there are no
problems with the branch cut of the logarithm. Yet, we choose to work on the
level of unitaries, also to establish a direct connection to the general
theory in [11].

  * •

These formulas are not the main result of our paper. In fact, we have been
aware of (most of) them since the beginning of our project, when we took
inspiration from the first papers concerned with the topological
classification of walks [36, 34, 35, 6, 8, 9, 39]. Our point here is rather
more subtle, namely to explore the “completeness” of these invariants: Thus
equality of invariants of two walks should imply that they can be deformed
into each other, while keeping the relevant structures (gap, symmetry,
locality) intact. Proving completeness is the way to show that the
classification job has been finished, and no hidden obstructions have been
overlooked. However, the completeness question is very sensitive to a change
of setting. On the one hand, it is surprising that the complete classification
of non-translation invariant walks [11] is essentially determined by the
(prima facie) much simpler translation invariant version of the question:
Every class can be realized by a local perturbation of two translation
invariant walks cut in half and joined together. On the other hand, new
classes might arise in the translation invariant case, because two such walks
could be deformable into each other, but only by breaking the translational
symmetry. In fact, as we show in this paper, this does happen for the symmetry
classes D (Prop. 3.3), BDI (Lem. 3.11), but not for DIII (Prop. 3.15), CII
(Lem. 3.13), and AIII (see beginning of Sect. 3.3.2). However, all additional
invariants disappear if we allow grouping of two neighbouring cells, i.e.,
deformations which break translational symmetry and are only invariant under
even translations.

  * •

There is an interesting alternative way to look at Floquet systems with
symmetry. What we are considering is only the unitary step operator $W$, i.e.,
the result of Hamiltonian driving over a whole period, and the classification
of such operators. However, as pointed out to us by J. Asboth, one could also
be interested in the homotopy classification of the entire driving process, or
“protocol”. Of course, in a setting with discrete symmetries this only really
makes sense, when the driving process satisfies the symmetry along the whole
way. With time symmetric driving this gives a special role to the unitary
operator at half-period. In the experimental system we had in mind this
symmetry in the driving process is definitely not respected. Rather,
“topological protection” is engineered in the same sense as “overprotection of
children”: many unintended influence can ruin it. This is (partly) different
in the free fermion case: One important symmetry (particle-hole) is satisfied
anyway, and also time reversal is sometimes naturally obeyed in the absence of
magnetic fields. A clear recent indication that discussing the protocol rather
than the overall Floquet operator $W$ came in [52, 38]. They study “loops” for
which $W={\leavevmode\rm 1\mkern-5.4muI}$, and get non-trivial classification.
Of interest is also [53], and we are in the process of looking for further
possibilities [7].

  * •

In contrast to much of the literature, our paper concerns only 1D lattice
systems. This may look very constrained, but on the other hand, we allow not
just finite jumps, but give a formulation that allows the longest possible
tails for the jump amplitudes. This is closely related to notions of locality
[21] that will be crucial for finding an efficient theory in higher dimension.
Locality as a kind of bound on the jumps allowed in a single walk step is well
captured by a so-called coarse structure [48], and its associated Roe
C*-algebra. The main natural choices in one-dimension relate to either
uniformly finite jump lengths (banded matrices) or to finite, but possibly
site dependent jump lengths, which amounts to a compactness condition
(“essential locality”) introduced in [11]. It would seem plausible that in the
translation invariant case these coincide, but as we show in Sect. 2 a
subtlety remains, so that we find (Prop. 2.2)that certain translation
invariant walks with discontinuous band structure are nevertheless susceptible
to the classification of [11]. We also take some care to formulate index
formulas for merely continuous band structures, i.e., in a purely topological
way, not requiring derivatives.

  * •

In the mathematical literature the classification of topological insulators is
usually done in terms of K-theory [31, 41, 55, 58, 42, 52, 37, 18]. A built-in
feature of K-theory is homotopy stabilization, by which addition of trivial
systems is considered as a neutral operation not changing the K-group
classification. That this stabilization makes a difference for walks is
demonstrated by the additional invariants we derive in our setting. These are
“unstabilized homotopy” invariants, but disappear, when added trivial systems
are allowed to be included in a homotopy path Sect. 1.5.

###  1.2 Recap of the general theory

Before delving into the translation invariant case, let us provide a brief
overview of the setting and results of our index theory for symmetric quantum
walks in one spatial dimension [11]. We introduce the systems we consider,
attribute topological invariants and discuss their stability under different
classes of perturbations. Also, we review some of the hallmark results of [11]
like the gentle decoupling theorem and the completeness of the invariants.

The Hilbert spaces of the quantum systems described by the theory in [11] are
assumed to have the form
${\mathcal{H}}=\bigoplus_{x\in{\mathbb{Z}}}{\mathcal{H}}_{x}$, where each
${\mathcal{H}}_{x}$ is a finite-dimensional Hilbert space which we refer to as
the cell at position $x$. For $a\in{\mathbb{Z}}$ we denote by $P_{\geq a}$ the
projection onto the subspace $\bigoplus_{x\geq a}{\mathcal{H}}_{x}$ and often
abbreviate $P=P_{\geq 0}$.

On ${\mathcal{H}}$, we consider discrete, involutive symmetries which act
locally in each cell, i.e., unitary or anti-unitary operators which, by
Wigner’s theorem, square to a phase times the identity and which commute with
each $P_{\geq a}$. The set of such operators forms an abstract group which in
the setting we consider consists either only of the identity, the identity and
a single involution or the Klein four-group. In particular, we always choose
trivial multiplication phases for the symmetries, i.e. we assume that they
commute exactly. Apart from their square and their unitary or antiunitary
character, the symmetries are distinguished by their relations with
“symmetric” operators, i.e. unitary or hermitean operators $W$ or $H$ that
“satisfy the symmetries”. Concretely, we restrict our attention to the
following symmetries which are frequently considered in solid-state physics:

  * particle-hole symmetry $\eta$, which is antiunitary satisfying $\eta W\eta^{*}=W$, resp. $\eta H\eta^{*}=-H$,

  * time reversal symmetry $\tau$, which is antiunitary satisfying $\tau W\tau^{*}=W^{*}$, resp. $\tau H\tau^{*}=H$,

  * chiral symmetry $\gamma$, which is unitary satisfying $\gamma W\gamma^{*}=W^{*}$ resp. $\gamma H\gamma^{*}=-H$.

For each group of symmetries, the information on the square and the unitary or
antiunitary character of each symmetry together with the relations with
symmetric operators constitute a symmetry type. These symmetry types establish
the so-called tenfold way [4]. A unitary or hermitean operator on
${\mathcal{H}}$ is called admissible for a symmetry type, if it satisfies the
relations of the symmetry type and is essentially gapped, i.e., possesses only
finitely degenerate eigenvalues in a small neighborhood around the symmetry-
invariant points $\pm 1$ in the unitary and $0$ in the hermitean case. A key
assumption for the classification is, that the symmetries are balanced
locally, i. e. in each cell there exists a strictly gapped, admissible unitary
(Hermitian) [11].

The physical systems we are concerned with in [11] and in the current paper
are quantum walks, i.e. unitary operators $W$ that additionally satisfy a
locality condition. In many earlier papers, this locality condition is
formulated as a finite upper bound on the jump length, in which case we call
$W$ strictly local. If, more generally, $P_{\geq a}-W^{*}P_{\geq a}W$ is a
compact operator for all $a$, we call $W$ essentially local, and this standing
assumption from [11] will also be true for all walks in this paper (see,
however, Sect. 2).

Using elementary group theory we assign an abelian symmetry group
$\mathbf{I}(\textnormal{{S}})$ to each symmetry type S [11]. The symmetry
types with $\mathbf{I}(\textnormal{{S}})$ non-trivial are displayed in Table
2. Vaguely speaking, a topological classification then assigns to each system
admissible for a symmetry type S an element of the corresponding index group
$\mathbf{I}(\textnormal{{S}})$, such that this classification is stable under
a certain class of perturbations. To find such a classification for admissible
unitaries, we first realize that the eigenspaces at $\pm 1$ of such operators
are invariant under the action of the symmetries and therefore play a special
role: we assign elements
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{+}(W)$ and
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}(W)$ of
$\mathbf{I}(\textnormal{{S}})$ to the $+1$\- and $-1$-eigenspaces of unitaries
$W$ admissible for S, respectively. An analogous construction for admissible
Hermitean operators assigns an element
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(H)\in\mathbf{I}(\textnormal{{S}})$
to the symmetry-invariant $0$-eigenspace of $H$. Basic properties of these
symmetry indices are that they are additive with respect to direct sums of
operators and prove to be invariant under gentle perturbations, i.e., they are
constant along norm-continuous paths $t\mapsto W_{t}$ for which every $W_{t}$
is admissible.

The sum
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)=\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{+}(W)+\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}(W)$
is called the symmetry index of $W$, and one quickly argues that, in contrast
to $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{\pm}$,
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)$ is invariant not only
under gentle but also under compact perturbations, i.e. admissible operators
$W^{\prime}$ for which $W-W^{\prime}$ is compact. This theory of classifying
admissible unitary operators by the symmetry indices
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{\pm}$ works independently
of any cell structure of the Hilbert space ${\mathcal{H}}$.

Taking into account such a cell structure, one can argue that physically
relevant perturbations are local, i.e. supported on a finite number of cells.
It is therefore important to find a classification of physical systems which
is stable under such local perturbations. In the Hamiltonian case this is
straightforward, since every compact and therefore every local perturbation
$H^{\prime}$ of $H$ is automatically gentle along the path $t\mapsto
tH^{\prime}+(1-t)H$. The unitary case, however, is more involved as one can
easily construct compact perturbations of a given unitary operator which are
not gentle.

To nevertheless find such a classification for admissible walks, in [11] we
introduced further invariants which are defined in terms of the cell structure
of ${\mathcal{H}}$: even though not unitary, by the locality condition the
operators $P_{\geq a}WP_{\geq a}$ and $P_{<a}WP_{<a}$ are essentially unitary
on the respective half chains, i.e. $W^{*}W-{\leavevmode\rm 1\mkern-5.4muI}$
and $WW^{*}-{\leavevmode\rm 1\mkern-5.4muI}$ are compact on $P_{\geq
a}{\mathcal{H}}$ and $P_{<a}{\mathcal{H}}$. Realizing that the imaginary part
of an essentially unitary operator is hermitean, we define the invariants
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W):=\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(P_{\geq
a}WP_{\geq a})\equiv\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(\Im
m(P_{\geq a}WP_{\geq a}))$ with $a\in{\mathbb{Z}}$, and similarly for
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$.
They are independent of $a$ and invariant with respect to gentle and compact
perturbations. Furthermore, like for the “spectral” invariants
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{\pm}$ we have
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)=\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)+\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$.
An overview of the indices defined in [11] is provided in Table 1.

$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{+}(W_{L})$ | $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{+}(W_{R})$ | $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{+}(W)$
---|---|---
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}(W_{L})$ | $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}(W_{R})$ | $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}(W)$
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$ | $\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$ | $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)$
Table 1: A summary of the symmetry indices of a gently decoupled walk
$W=W_{L}\oplus W_{R}$ as introduced in [11]. Here, the quantities in the upper
left quadrant are neither invariant under gentle nor under compact
perturbations whereas their row and column sums in the bottom row and the
right column are.

These “spatial” symmetry indices allow to prove a bulk-boundary-
correspondence: whenever two translation invariant bulks $W_{L}$ and $W_{R}$
are in different topological phases, a crossover walk $W$ between them hosts
topologically protected eigenfunctions. The number of these eigenfunctions is
lower bounded by
$|\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)|=|\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{L})-\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{R})|$
and, as we prove in Sect. 4 of the present paper, for translation invariant
walks they are exponentially localized near the boundary.

Another way to split an admissible walk $W$ into a left and a right half
$W_{L}$ and $W_{R}$, respectively, is to decouple gently, i.e. to find a
gentle perturbation of $W$ such that $W^{\prime}=W_{L}\oplus W_{R}$. The
existence of such decouplings is guaranteed by the gentle decoupling theorem
for which a necessary and sufficient condition is the vanishing of the
Fredholm index of $PWP$, a condition satisfied by every admissible unitary
[11]. Moreover, due to its gentleness, such a decoupling preserves all
symmetry indices discussed so far, whereas $W\mapsto PWP+({\leavevmode\rm
1\mkern-5.4muI}-P)W({\leavevmode\rm 1\mkern-5.4muI}-P)$ preserves only
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W),\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$
and $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)$.

This existence of gentle decoupling plays an essential role when discussing
the completeness of the topological invariants: having proved that all
symmetry indices are invariant under gentle perturbations evokes the question,
whether the converse is also true, i.e. whether two systems which share the
same values for the symmetry indices can always be deformed into each other
along an admissible path. Clearly, the set of symmetry indices suitable for a
classification depends on the perturbations one allows for. In [11], we
answered the completeness question in the affirmative for the following
settings:

  * (I)

All walks with respect to gentle perturbations and independent invariants
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits},\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits},\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}$

  * (II)

All walks with respect to both gentle and compact perturbations and
independent invariants
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits},\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$.

  * (III)

All admissible unitaries with respect to gentle perturbations and independent
invariants
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{+},\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}$.

In this paper we restrict our attention to translation invariant systems. For
such systems, the gap condition implies that the indices
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{\pm}(W)$ and therefore
also $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)$ vanish. Thus,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$
or, equivalently,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$
provides the full information on the classification of such systems.

S | $\eta^{2}$ | $\tau^{2}$ | $\gamma^{2}$ | $\mathbf{I}(\textnormal{{S}})$ | $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits$
---|---|---|---|---|---
D | ${\leavevmode\rm 1\mkern-5.4muI}$ |  |  | ${\mathbb{Z}}_{2}$ | $d\,{\mathop{\rm mod}\nolimits}2$
AIII |  |  | ${\leavevmode\rm 1\mkern-5.4muI}$ | ${\mathbb{Z}}$ | $\mathop{\rm tr}\nolimits\gamma$
BDI | ${\leavevmode\rm 1\mkern-5.4muI}$ | ${\leavevmode\rm 1\mkern-5.4muI}$ | ${\leavevmode\rm 1\mkern-5.4muI}$ | ${\mathbb{Z}}$ | $\mathop{\rm tr}\nolimits\gamma$
CII | $-{\leavevmode\rm 1\mkern-5.4muI}$ | $-{\leavevmode\rm 1\mkern-5.4muI}$ | ${\leavevmode\rm 1\mkern-5.4muI}$ | $2{\mathbb{Z}}$ | $\mathop{\rm tr}\nolimits\gamma$
DIII | ${\leavevmode\rm 1\mkern-5.4muI}$ | $-{\leavevmode\rm 1\mkern-5.4muI}$ | $-{\leavevmode\rm 1\mkern-5.4muI}$ | $2{\mathbb{Z}}_{2}$ | $d\,{\mathop{\rm mod}\nolimits}4$
Table 2: The non-trivial symmetry types of the tenfold way where the first
column gives the label of the Cartan classification [4]. The index groups
$\mathbf{I}(\textnormal{{S}})$ are calculated explicitly in [11]. The last
column gives an explicit expression for the symmetry index of finite-
dimensional realizations of the symmetry type.

###  1.3 Translation invariance and band structure

In the translation invariant case the cells ${\mathcal{H}}_{x}$ all need to be
identical so that
${\mathcal{H}}=\bigoplus{\mathcal{H}}_{x}\cong\ell^{2}({\mathbb{Z}})\otimes{\mathcal{H}}_{0}$.
We will assume that the symmetry operators in each cell are likewise all
equal. Then, an operator $W\in{\mathcal{B}}({\mathcal{H}})$ is called
translation invariant if it commutes with the translations or, equivalently,
if

$(W\psi)(x)=\sum_{y}W(y)\psi(x-y)$ (1)

for some operators $W(y):{\mathcal{H}}_{0}\to{\mathcal{H}}_{0}$. For strictly
local walks only finitely many $W(y)$ are non-zero. The above convolution can
be turned into a product by the Fourier transform
${\mathcal{F}}:\ell^{2}({\mathbb{Z}})\to{\mathcal{L}}^{2}([-\pi,\pi],dk/(2\pi))$
with the convention

$({\mathcal{F}}\psi)(k)=\sum_{x}e^{ikx}\psi(x).$ (2)

We use the same notation for ${\mathcal{F}}\otimes{\leavevmode\rm
1\mkern-5.4muI}_{d}$, or ${\mathcal{H}}_{0}$-valued $\psi$. Of course, the
interval $[-\pi,\pi]$, or Brillouin zone, or momentum space, just serves as a
parametrization of the circle, and the Fourier transforms of sufficiently
rapidly decaying $\psi$ will be continuous with periodic boundary conditions.
Then, the walk is determined by the function $k\mapsto\widehat{W}(k)\in U(d)$
via

$({\mathcal{F}}W\psi)(k)=\widehat{W}(k)({\mathcal{F}}\psi)(k)\
,\quad\widehat{W}(k)=\sum_{x}e^{ikx}W(x)$ (3)

For a strictly local walk $\widehat{W}$ is a matrix valued Laurent polynomial
in the variable $\exp(ik)$. For rapidly decreasing $W(x)$ we get smooth
$\widehat{W}$, see Sect. 2 for more details.

A complete homotopy classification that does not demand any symmetries or gap
conditions is provided by the index (${\mathop{\rm ind}\nolimits}\,$) of a
quantum walk, thoroughly studied in the case of strictly local walks in [23]
and extended to essentially local walks in [11]. In this general case the
alluded index is given in terms of the Fredholm index (${\mathop{\rm
ind}\nolimits}\,_{F}$) of $PWP$, in fact ${\mathop{\rm
ind}\nolimits}\,(W)=-{\mathop{\rm ind}\nolimits}\,_{F}(PWP)$. For translation
invariant $W$ this becomes the total winding number of the quasi-energy
spectrum around the Brillouin zone:

######  Definition 1.1.

Let $W$ be a translation invariant quantum walk with Fourier transform
$\widehat{W}(k)$. Then, its index is given by the winding number of
$\det\widehat{W}(k)$ around the origin, which in the case of a continuously
differentiable $\widehat{W}(k)$ is given by

${\mathop{\rm ind}\nolimits}\,(W)=\frac{1}{2\pi
i}\int_{-\pi}^{\pi}\mskip-10.0mudk\left(\frac{\partial}{\partial
k}\log\det\widehat{W}(k)\right).$ (4)

Yet, for the theory we develop in this paper, ${\mathop{\rm
ind}\nolimits}\,(W)$ automatically vanishes by the existence of essential gaps
in the spectrum [11, Proposition VII.1].

Now, turning to the classification of translation invariant walks with
symmetries, we need to express the symmetry conditions in terms of
$\widehat{W}$. These are then given by

$\eta\widehat{W}(k)\eta^{*}=\widehat{W}(-k),\
\qquad\tau\widehat{W}(k)\tau^{*}=\widehat{W}(-k)^{*},\
\mbox{and}\qquad\gamma\widehat{W}(k)\gamma^{*}=\widehat{W}(k)^{*},$ (5)

where the operators $\eta,\tau,\gamma$ denote the one-cell symmetries acting
on ${\mathcal{H}}_{0}\simeq{\mathbb{C}}^{d}$. Note that the anti-unitarily
implemented symmetries flip the sign of $k$. This is necessary to guarantee
that the position basis elements, i.e. $\exp(ik)$, are invariant under the
symmetries.

As a finite-dimensional, $k$-dependent unitary matrix, $\widehat{W}(k)$ can be
diagonalized, i.e.

$\widehat{W}(k)=\sum_{\alpha=1}^{d}e^{i\omega_{\alpha}(k)}Q_{\alpha}(k),$ (6)

where $\omega_{\alpha}(k)$ are the quasi-energies and $Q_{\alpha}$ the band
projections.

$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$k$$\omega(k)$$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$k$$\omega(k)$$\gamma$$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$k$$\omega(k)$$\gamma$$\eta$$\tau$
Figure 1: Examples for band structures with different symmetries. Left: A walk
with non-trivial index ${\mathop{\rm ind}\nolimits}\,$. It becomes clear, that
a non-trivial index is not consistent with a gap condition [11]. Middle: A
walk which is only chiral symmetric. The arrow denotes the action of $\gamma$
on the spectrum of an admissible walk. Right: A walk with all three
symmetries.

Many questions, e.g., the spreading of wave packets under the walk [2], can be
answered by studying the eigenvalues of $\widehat{W}(k)$ as a function of $k$.
For the topological classification, however, they are completely irrelevant.
Not even the details of the individual band projections $Q_{\alpha}(k)$ play a
role, but only the collective projections expressing the distinction of
spectra in the lower vs. the upper half plane:

######  Lemma 1.2.

Let $W$ be a gapped translation invariant walk of any symmetry type, and let

$Q(k)=\sum_{\alpha,\,\omega_{\alpha}(k)\in(0,\pi)}\,Q_{\alpha}(k)$ (7)

be the band projection for the upper half plane. Then, there is a continuous
path $[0,1]\ni t\mapsto W_{t}$ of gapped, translation invariant walks
satisfying the same symmetries as $W$, such that $W_{0}=W$, and
$\widehat{W}_{1}(k)=iQ(k)-i({\leavevmode\rm
1\mkern-5.4muI}-Q(k))=:\widehat{W}_{\flat}(k)$, the flat-band walk associated
with $W$.

###### Proof.

Let $S^{1}_{\varepsilon}$ denote the unit circle without an open disc of
radius $\varepsilon$ around each of $+1$ and $-1$. We choose $\varepsilon$ so
that the spectrum of $W$ is contained in $S^{1}_{\varepsilon}$. Now consider a
continuous function $f:[0,1]\times S^{1}_{\varepsilon}\to
S^{1}_{\varepsilon}$, which we write as $f_{t}(z):=f(t,z)$, such that
$f_{0}(z)=z$ and $f_{1}(z)=\operatorname{sign}(\Im mz)i$. For keeping the
symmetry properties we also demand $f_{t}(\overline{z})=\overline{f_{t}(z)}$.
Then, we define $W_{t}=f_{t}(W)$ in the continuous functional calculus. With
this all the mentioned properties are preserved, and the analogue of (6) reads

$\widehat{W}_{t}(k)=f_{t}\bigl{(}\widehat{W}(k)\bigr{)}=\sum_{\alpha=1}^{d}f_{t}\Bigl{(}e^{i\omega_{\alpha}(k)}\Bigr{)}Q_{\alpha}(k).$
(8)

∎

Clearly, for flat-band walks we have $W^{2}=-{\leavevmode\rm 1\mkern-5.4muI}$,
i.e., $W^{*}=-W$. In what follows, we use this as a characterization for
“flat-band unitaries” independently of any walk-context and the notion of
bands. Note that such continuous transformation also leaves essential locality
of a walk under consideration invariant [11]. For translation invariant walks
with continuous band structure we show this explicitly in Prop. 2.1.

Hence, for the purposes of homotopy classification it is equivalent to study
either $\widehat{W}(k)$ or the band projections $Q(k)$ of $\widehat{W}(k)$.
The symmetry conditions for these read

$\eta Q(k)\eta^{*}={\leavevmode\rm 1\mkern-5.4muI}-Q(-k),\ \qquad\tau
Q(k)\tau^{*}=Q(-k),\ \mbox{and}\qquad\gamma Q(k)\gamma^{*}={\leavevmode\rm
1\mkern-5.4muI}-Q(k).$ (9)

These are directly equivalent to (5) for the flat-band walk $W_{\flat}$. Fig.
1 shows typical examples of band structures together with the action of the
symmetries.

###  1.4 Standard Example: The Split-Step Walk

Introduced in [36], this example is also treated in [34, 6, 8, 62], and many
other papers. Many aspects of the current paper can be demonstrated in this
example in their simplest form, which is why we introduce it early on. Some of
its features can be explored with an interactive web-based tool [59].

The coin space is two-dimensional, so a basis for ${\mathcal{H}}$ is labelled
$|x,s\rangle$ with $x\in{\mathbb{Z}}$ and $s=\pm 1$. We introduce two separate
shift operations, $S_{\uparrow}$, the right shift of the spin-up vectors and
$S_{\downarrow}$, the left shift of the spin-down vectors. Explicitly,
$S_{\downarrow}|x,-\rangle=|x-1,-\rangle$ and
$S_{\uparrow}|x,+\rangle=|x+1,+\rangle$, while leaving the opposite spins
invariant, respectively. The split-step walk is then defined as

$W=BS_{\downarrow}AS_{\uparrow}B,$ (10)

where $B=\bigoplus_{\mathbb{Z}}R(\theta_{1}/2)$ and
$A=\bigoplus_{\mathbb{Z}}R(\theta_{2})$ are standard real rotation matrices
acting sitewise at each $x\in{\mathbb{Z}}$.

The symmetry of the model is of type BDI (see Table 2), where $\eta$ denotes
the complex conjugation in position space (i.e., $\eta
z|x,s\rangle=\bar{z}|x,s\rangle$ $\forall z\in{\mathbb{C}}$), and the chiral
symmetry acts like $\sigma_{1}$ (i.e., $\gamma|x,s\rangle=|x,-s\rangle$). The
symmetry condition readily allows for non-translation invariant examples: In
(10), take $A=\bigoplus_{x}A_{x}$ and $B=\bigoplus_{x}B_{x}$ to be unitary
operators, where each $A_{x}$, $B_{x}$ is admissible and acts sitewise on
${\mathcal{H}}_{x}$. This is of importance when speaking of bulk-boundary
correspondence, since a system in which two different phases are joined is per
definition non-translation invariant.

In the form of (10) it is straightforward to see that the admissibility of the
$A_{x}$, $B_{x}$ suffices for the admissibility of $W$. The phase diagram for
the index
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$
is shown in Fig. 2. The main differences to the diagrams in [36] are the
signs, which is connected to the difference of methods. In [36] phase
boundaries are identified by tracking the number of bound states of compound
walks. This is an intrinsically unsigned quantity, so positive and negative
changes cannot be distinguished. In contrast, our approach demands also the
determination of the symmetry index in the eigenspace, which is a signed
integer quantity. This is crucial for the agreement with the bulk theory, in
which the chiral index is a (signed) winding number.

An important feature of the index is that it allows to predict the emergence
of eigenvectors at the boundary of two bulk systems in different phases (i.e.
that have differing
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$)
that are joined (bulk-boundary correspondence). The split-step walk
demonstrates this in a very simple way, by making use of decouplings: To
decouple the split-step walk, we replace one of the coins $A_{0}$ with a
splitting coin, which forbids transition from the left to the right side and
vice versa. Note that the family of BDI-admissible unitary operators on
${\mathbb{C}}^{2}$ consists precisely of the rotation matrices $R(\theta)$ and
$\pm\sigma_{1}$, which are in different connected components. This allows for
_non-gentle_ decouplings, which leave
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits$ and
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
invariant, but change
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}_{+}$
and
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}_{-}$
[11]. Only the splitting coin chosen from the rotations, $A_{0}=\pm
R(\pi/2)=\pm i\sigma_{2}$ is a gentle perturbation, which implies that
eigenvalues at $+1$ (and $-1$) come in pairs with opposing chirality (see Fig.
2).

$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$-\pi$$-\frac{\pi}{2}$$0$$\frac{\pi}{2}$$\pi$$\theta_{1}$$\theta_{2}$$\bf{1}$$\bf{\text{-}1}$$\bf
0$$\bf
0$$A_{0}=-i\sigma_{y}$$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{+}$$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{-}$$\mathop{\hbox{\raisebox{3.59998pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$$\mathop{\hbox{\raisebox{3.59998pt}{$\scriptstyle\leftharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$$\bf{1}$$\bf{\text{-}1}$$\bf{\text{-}1}$$\bf{1}$
Figure 2: Left: Parameter plane with symmetry index
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
for the split-step walk. Middle: Winding of the upper right component of $W$
in chiral eigenbasis (see Prop. 3.9) for the values
$(\theta_{1},\theta_{2})=(\pi/8,-\pi/4)$ (black dot in the left picture).
Right: Eigenfunctions for the same values, after decoupling with
$A_{0}=-i\sigma_{y}$. The labels in the quadrants denote the indices according
to Tab. 1.

###  1.5 Dependence on cell structure

The homotopy classification we are aiming at is an equivalence relation of the
type “$W_{1}$ can be transformed into $W_{2}$”. It clearly depends very
sensitively to what kind of transformations are allowed. Allowing additional
operations coarsens the equivalence relation. Therefore, our strategy in the
following will be not to allow these operations at first. This leads to a
finer classification of translation invariant walks than our general theory.
Apart from continuous deformations there are three operations we need to
consider, all of which are related to reorganizing the cell structure. Our
general theory is naturally insensitive to the first two, and has a
predictable behaviour under the third.

####  1.5.1 Regrouping

For the general theory outlined in Sect. 1.2 the details of cell structure are
irrelevant: the local Hilbert spaces may have different dimensions, and
nothing changes, if we decide to consider two neighbouring cells together as a
new single cell. Translation invariance makes sense only if the cells all have
the same dimension. Similarly, only regrouping operations done uniformly
throughout the lattice can be considered, like always grouping cell
${\mathcal{H}}_{2x}$ together with cell ${\mathcal{H}}_{2x+1}$. The main
change introduced by this operation is a change in the definition of the
translations: After regrouping effectively only translations by an even number
of sites are considered. This makes a big difference, if we demand that
translation invariance be conserved on a deformation path. Specifically, it
might be impossible to deform $W_{1}$ into $W_{2}$ keeping translation
invariance, but it might be possible to do so by breaking the translation
invariance and keeping only the weaker requirement of period-2 translation
invariance. We will see examples of this below.

For later use we record $\widehat{W}$ for a regrouped walk with the simple
pair-regrouping indicated above. For the regrouped walk we have the double
cell dimension, and vectors $\psi\in{\mathcal{H}}$ get split into

$\psi_{r}(x)=\begin{pmatrix}\psi_{e}(x)\\\
\psi_{o}(x)\end{pmatrix}=\begin{pmatrix}\psi(2x)\\\ \psi(2x+1)\end{pmatrix}.$
(11)

The regrouped walk $W_{r}$ acts in position space by convolution with

$W_{r}(x)=\begin{pmatrix}W(2x)&W(2x-1)\\\ W(2x+1)&W(2x)\end{pmatrix},$ (12)

and by taking the Fourier transform we get

$\widehat{W}_{r}(k)=H(k/2)\begin{pmatrix}\widehat{W}\bigl{(}\frac{k}{2}\bigr{)}&0\\\
0&\widehat{W}\bigl{(}\frac{k}{2}+\pi\bigr{)}\end{pmatrix}H(k/2)^{*},\qquad\text{where}\qquad
H(k)=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\ e^{-ik}&-e^{-ik}\end{pmatrix}.$
(13)

a)b)

$\oplus$

$\oplus$

$\oplus$

$\oplus$

$\oplus$

$\oplus$

c)d) Figure 3: Visualization of the different transformations of the cell
structure discussed in Sect. 1.5. The red boxes indicate the different choices
of unit cells: a) original cell structure, b) pairwise regrouped cells, c)
addition of a trivial walk, d) skew cut cells.

####  1.5.2 Adding trivial walks

A second operation which one might consider for transforming $W_{1}$ into
$W_{2}$ is adding trivial systems, which have to be returned unchanged after
the transformation. A walk $W^{0}$ is said to be “trivial” in this context if
it acts cell-wise, i.e. there is no propagation between cells. Note that this
condition immediately implies
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W^{0})=0$.
In this case, although $W_{1}$ could not be transformed into $W_{2}$, it might
be possible that “there are trivial walks $W_{1}^{0}$ and $W_{2}^{0}$ so that
$W_{1}\oplus W_{1}^{0}$ can be continuously deformed into $W_{2}\oplus
W_{2}^{0}$”. It is one of the basic features of our general theory that
indices add up for direct sums of walks, and also that the value of the index
lies in a group. Together, this implies a cancellation law, so that allowing
the addition of trivial walks does not change the general classification. Note
that since this classification is a complete homotopy invariant, walks that
can be deformed into each other after adding trivial ones can actually be
deformed into each other when a breaking of translation invariance is allowed
on the way. Later, in the discussion of completeness, we will show that such
trivial walks indeed always exist.

There is a general construction for turning an invariant which is additive
over direct sums (with values in a semigroup) into a group-valued invariant
with cancellation law. This is called the Grothendiek group of the semigroup,
and is a standard ingredient of K-theory.

####  1.5.3 Time frames and skew recutting of cells

Suppose a walk can be written as $W=W_{1}W_{2}$, i.e., there are two kinds of
steps which alternate. Then there is a closely related walk
$W^{\prime}=W_{2}W_{1}$, alternating the same two steps, but beginning with
the other one. In this sense the two walks differ by a choice of “time frame”
[8]. For the long time behaviour there should be little difference, and indeed
the spectra are the same, because $W^{\prime}=W_{1}^{*}WW_{1}$. Hence,
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits_{\pm}$ are left invariant.
But since
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
is sensitive to the cell structure $W$ is defined on, it might change under
such operation, if $W_{1}$ does not act site-wise, i. e. $[W_{1},P_{\geq
0}]\neq 0$. Consider for example the split-step walk, with
$W_{1}=BS_{\downarrow}\sqrt{A}$ and $W_{2}=\sqrt{A}S_{\uparrow}B$.
$W^{\prime}$ is of the same form as $W$, with $\theta_{1}$ and $\theta_{2}$ as
well as $S_{\uparrow}$ and $S_{\downarrow}$ swapped. This results in a
$\pi/2$-clockwise rotation of the index-plane in Fig. 2 and hence, trivial
phases become non-trivial and vice versa. The dependence on the cell structure
is also easily obtained from the example in Fig. 3 (bottom-right). Assume the
original walk to act locally in each cell, i.e., $\ker(PWP)=0$ on
$P{\mathcal{H}}$. Then the new cell structure produces a non-trivial kernel of
$PW^{\prime}P$ on $P{\mathcal{H}}$ and hence,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
might change.

##  2 Essential locality and continuity of band structure

As for all Fourier transforms, decay properties of $W(x)$ translate into
smoothness conditions on $\widehat{W}$. We refer to such conditions as
locality conditions, since they express the idea that in a single step the
walker cannot go very far, or at least, that the amplitude for very long jumps
goes down sufficiently fast. Some condition of this kind is needed to make the
theory non-trivial: Without a localization requirement along the path any two
unitaries could be continuously connected (see Sect. 2.3.2 for an example of
the kind of locality violation this may imply). In order to classify as many
systems as possible, one would like to assume as little smoothness/locality as
possible. For the classification of band structures the natural smoothness
condition appears to be continuity of $\widehat{W}$. Indeed, the formulas
discussed below are often in terms of winding numbers, which are well-defined
assuming just continuity. On the other hand, it is easy to see that with
admission of discontinuities no classification is possible. We show here
(Prop. 2.1) that in the translation invariant setting this is the same as
saying that the walk operator can be uniformly approximated by walks with
strictly finite jump length. This will be our standing assumption in the
sequel.

Of course, we verify also that this condition implies “essential locality” as
used in the the general theory [11]. Surprisingly, however, it turns out that
the converse is not true: There are essentially local, translation invariant
walks such that $\widehat{W}$ is not continuous. Nevertheless these are
covered by the general classification, so we conclude that winding numbers can
also be extended as good topological classifiers beyond continuous curves!
This generalization has been noted before, leading to the notion of “quasi-
continuous” [40] functions on the circle. We discuss this in Sect. 2.2. While
this distinction may be a subtlety of little practical value, it needs to be
taken seriously, when one wants to go to higher lattice dimensions. It is not
completely clear what locality conditions are appropriate then, and lead to a
manageable theory. Basically, one needs to fix a “coarse structure” [47, 48],
and for this, too, the one-dimensional case already has two natural options:
These are “approximability by walks with uniformly finite jump length” and the
“essential locality”, which in the translation invariant case map to
continuity and quasi-continuity of $\widehat{W}$, respectively.

###  2.1 Approximation by strictly local operators

We begin with a general result which relates smoothness conditions on
$\widehat{W}$ to locality properties of the corresponding $W$:

######  Proposition 2.1.

Let $A\in{\mathcal{B}}({\mathcal{H}})$,
${\mathcal{H}}=\ell^{2}({\mathbb{Z}})\otimes{\mathcal{H}}_{0}$ be translation
invariant with Fourier transform $\widehat{A}$. Then the following are
equivalent:

  * (1)

$A$ can be approximated in norm by strictly local operators.

  * (2)

$A$ can be approximated in norm by translation invariant operators $A_{n}$
with $\widehat{A}_{n}\in{\cal C}^{\infty}$.

  * (3)

$k\mapsto\widehat{A}(k)$ is a continuous function with periodic boundary
conditions.

If $A$ is unitary, the approximating operators in (2) can be chosen to be
unitary and admissible for all symmetries under consideration. Moreover, if
one of the above conditions is fulfilled, $A$ is essentially local, i.e.
$[P,A]$ is compact, where $P=P_{\geq 0}$ denotes the projection onto the
positive positions.

###### Proof.

(3)$\Rightarrow$(1): This is basically the Stone-Weierstraß Theorem [61, 63],
which immediately implies that the algebra of trigonometric polynomials is
sup-norm dense in the set of continuous functions. Detailed error estimates
are provided by the theory of Fourier series [17, Sect. 1.4]. There it is
shown that, for any continuous function $\widehat{A}(k)$ on the circle, a
suitable sequence of truncations of the Fourier series, for example, those
given by the Fejér kernels $\widehat{A}_{n}(k)$, converge uniformly to the
given function. The same estimates work also for matrix valued functions,
providing us with a sequence $A_{n}$ of strictly local operators such that
$\|A_{n}-A\|\leq\varepsilon_{n}\to 0$.

(1)$\Rightarrow$(2, unitarity)$\Rightarrow$(3): Since the Fourier transform of
a strictly local operator is a trigonometric polynomial, (1) obviously implies
(2). While the choice of the Cesàro approximants $\widehat{A}_{n}$ given by
the Fejér kernels guarantees that $A_{n}$ will satisfy the same symmetries as
$A$, and will be hermitian if $A$ is, unitarity is not preserved, and it is
unclear whether one can modify $A_{n}$ to be strictly unitary. On the other
hand, $\sup_{k}\|\widehat{A}_{n}(k)^{*}\widehat{A}_{n}(k)-{\leavevmode\rm
1\mkern-5.4muI}\|=\|A_{n}^{*}A_{n}-{\leavevmode\rm 1\mkern-5.4muI}\|\leq
2\varepsilon_{n}$, so the inverse square root
$\widehat{M}_{n}(k)=(\widehat{A}_{n}(k)^{*}\widehat{A}_{n}(k))^{-1/2}$ is
infinitely differentiable, since it can be obtained by applying a convergent
power series to a polynomial. Moreover,
$\widehat{U}_{n}(k)=\widehat{A}_{n}(k)\widehat{M}_{n}(k)$ is unitary and
converges in norm to $A$. Being the polar isometry of an admissible operator,
$\widehat{U}_{n}(k)$ is also admissible. Admissibility for $\eta$ follows
trivially, since $\widehat{M}_{n}(k)$ is a real function of an admissible
operator. For any of the conjugating symmetries $\sigma\in\\{\gamma,\tau\\}$
we get

$\sigma U=\sigma
A(A^{*}A)^{-1/2}=A^{*}(AA^{*})^{-1/2}\sigma=((AA^{*})^{-1/2}A)^{*}\sigma=U^{*}\sigma.$
(14)

For any $A$ allowing such approximation it follows that $\widehat{A}$ is
continuous as the norm limit of continuous functions. Note, that convergence
of $A_{n}\rightarrow A$ in norm also implies convergence of the spectra.
Therefore, any gap of $A$ eventually becomes a gap for $A_{n}$ for large
enough $n$.

Now suppose $A$ is strictly local. Consider the commutator
$[P,A]=PA({\leavevmode\rm 1\mkern-5.4muI}-P)-({\leavevmode\rm
1\mkern-5.4muI}-P)AP$ as a block matrix with respect to the cell decomposition
${\mathcal{H}}=\bigoplus{\mathcal{H}}_{x}$. It contains only terms between the
subspaces ${\mathcal{H}}_{x}$ and ${\mathcal{H}}_{y}$, where $x\geq 0$ and
$y<0$, or conversely $x<0$ and $y\geq 0$. Moreover, since $A$ is local, there
are only non-zero blocks with $|x-y|\leq N$. Since there are only finitely
many such pairs $(x,y)$ we conclude that $[P,A]$ is a finite rank operator.
When $A$ is approximated in norm by such operators, $[P,A]$ is approximated in
norm by finite rank operators, hence compact. ∎

For the homotopy classification of translation invariant quantum walks we will
restrict ourselves to walks, which fulfil the conditions of Prop. 2.1. This
guarantees that we never leave the set of essentially local walks and as we
show below the classification of such systems already turns out to be
complete.

###  2.2 Quasi-continuity

Let us, however, state what the condition of essential locality exactly
translates to in terms of the band structure. We need to express that $[P,W]$
is a compact operator, which is equivalent to the compactness of the two
operators $PW({\leavevmode\rm 1\mkern-5.4muI}-P)$ and $({\leavevmode\rm
1\mkern-5.4muI}-P)WP$. These are the off-diagonal quadrants of $W$ in a
representation of $W$ as a doubly infinite matrix of $d\times d$ blocks. By
translation invariance the $(x,y)$-block is $W(x-y)$.

Relabelling $y\mapsto y^{\prime}=-y$ for the quadrant with indices $y<0\leq x$
leads to a block Hankel matrix $M$, i.e., a matrix whose block entries
$M(x,y^{\prime})$ are labelled by $x\geq 0$, $y^{\prime}>0$, and
$M(x,y^{\prime})=m(x+y^{\prime})$ depends only on $(x+y^{\prime})$. The
characterization of compact Hankel matrices with scalar entries is achieved by
a classic result known as Hartman’s Theorem [24]. It says that the numbers
$m(x)$ are Fourier coefficients of a continuous function. Hartmann’s Theorem
generalizes to block matrices. This is called the “vectorial” case in [40,
Ch.2], where the relevant result is Thm. 4.1, and allows even for block
entries that are operators between distinct, possibly infinite Hilbert spaces.
The conclusion is entirely the same, i.e., we get that there is a continuous
matrix valued function $k\mapsto\widehat{M}$ on $[-\pi,\pi]$ with periodic
boundary condition, whose Fourier coefficients for $x\geq 0$ equal $W(x)$.

The notion of quasi-continuity arises from the peculiar way in which we have
to combine two such conditions. The function spaces involved are the matrix
valued versions of $L^{\infty}$, the Banach algebra of essentially bounded
measurable functions on the unit circle, its subalgebra $C$ of continuous
functions, and $H^{\infty}$, the subalgebra with vanishing Fourier
coefficients for negative indices. A (possibly matrix valued) function $f$ is
called quasi-continuous, if $f=g+h$, with $g\in C$ and $h\in H^{\infty}$, and
such a decomposition also holds for $f^{*}$ [40]. Indeed, this is the required
property: We have, on the one hand,
$\widehat{W}=\widehat{M}+(\widehat{W}-\widehat{M})\in
C+\overline{H^{\infty}}$, because only the negative Fourier coefficients can
be non-zero. On the other, evaluating the compactness condition for the second
block, we get the analogous condition for $W(x)$ with $x<0$, which means that
$\widehat{W}^{*}\in C+\overline{H^{\infty}}$. Hence $\widehat{W}$, or
equivalently each of its entries is quasi-continuous.

We summarize this discussion in the following proposition.

######  Proposition 2.2.

Let $A\in{\mathcal{B}}({\mathcal{H}})$, with
${\mathcal{H}}=\ell^{2}({\mathbb{Z}})\otimes{\mathcal{H}}_{0}$,
${\mathcal{H}}_{0}$ finite dimensional, be translation invariant and
$\widehat{A}$ its Fourier transform. Then the following are equivalent:

  * (1)

$A$ is essentially local.

  * (2)

$\widehat{A}$ is quasi-continuous.

Of course, it is a basic fact of this theory that there are quasi-continuous
functions which are not continuous. For a rough sketch how counterexamples
arise, note that, for a continuous function $f\in C$, $f(k)$ traces out a
curve in the complex plane, and the $H^{\infty}$ condition makes this the
boundary of the image of the unit disk under an analytic function. On the
other hand, the Riemann mapping theorem also works for open sets which are not
bounded by a continuous curve. So discontinuous examples are constructed in
terms of the boundary values of analytic functions mapping the open unit disk
to some such wild region. To build an essentially local walk with
discontinuous $\widehat{W}$ we disregard the symmetry conditions for the
moment, and take $\dim{\mathcal{H}}_{0}=1$, i.e., the scalar case. Then we set
$\widehat{W}(k)=\exp\bigl{(}i\Im mf(e^{ik})\bigr{)}$, where $f$ is a conformal
mapping with continuous real part, but only quasi-continuous imaginary part
(see [19, p.377] for an explicit example).

Winding numbers still make sense as the limit of the winding numbers of curves
just to the inside of the boundary [56, 40]. They also coincide with the
(negative) Fredholm index of $PWP$ [16], i.e. with the index from Def. 1.1. In
the above example we get ${\mathop{\rm ind}\nolimits}\,W=0$, because
$\widehat{W}(k)=\exp\bigl{(}-\Re
ef(e^{ik})\bigr{)}\exp\bigl{(}f(e^{ik})\bigr{)}$. Here the first factor is
positive and hence does not contribute to any winding. The second is the
boundary value of a function which is analytic in the open disk, so its
generalized winding number, evaluated close to the boundary, vanishes.

###  2.3 Examples

####  2.3.1 Exponentials

Consider an essentially local Hamiltonian $H$, and define $W=\exp(iHt)$, for
$t\in{\mathbb{R}}$. Then $W$ is also essentially local, because $[P,H]$
compact means that the images of $P$ and $H$ commute in the Calkin algebra
(bounded operators modulo compact ones), which implies the same for $W$.
Another way to put the statement is that the essentially local operators form
a C*-algebra, so functions of the (multivariate) continuous functional
calculus will always map essentially local arguments to essentially local
operators.

For translation invariant operators with continuous bands this implication is
even simpler, namely that the continuity of $k\mapsto\widehat{H}(k)$ implies
the continuity of $k\mapsto\exp(i\widehat{H}(k)t)$. Note, however, that no
such conclusion is available for strictly local Hamiltonians and their
exponentials.

####  2.3.2 Contracting the shift

The bilateral shift on $\ell^{2}({\mathbb{Z}})$ is the fundamental example of
a strictly local, translation invariant walk, which cannot be contracted to
the identity, while keeping (strict) locality. In fact, the index (4) of one-
dimensional walks can be understood as the “shift content” of $W$, and at the
same time labels the homotopy classes of walks for deformations keeping strict
locality. Here we revisit this example and show that one can also not contract
the shift to the identity under the assumption of mere essential locality.
This follows also from the extension of index theory in [11], which
establishes the index as a Fredholm index. But how badly does essential
locality fail on a deformation path?

The Fourier matrix of the shift $|x\rangle\mapsto|x+1\rangle$ is given by
$\widehat{W}(k)=\exp(ik)$. A natural attempt to contract this to the identity,
i.e., to make “fractional steps” on the lattice, is by the operator family
$W_{\lambda}$ with

$\widehat{W}_{\lambda}(k)=e^{i\lambda k}{\leavevmode\rm 1\mkern-5.4muI},$ (15)

where $0<\lambda<1$. These interpolate between the identity ($\lambda=0$) and
the shift ($\lambda=1$) in a norm-continuous way. Despite appearances this is
not a continuous function of $k$, since for this we also require periodic
boundary conditions (or else our result would depend on the arbitrary choice
of fundamental domain $[k_{0},k_{0}+2\pi]$). Indeed (15) jumps from
$\exp(-i\lambda\pi)$ to $\exp(+i\lambda\pi)$, as $k$ crosses from $-\pi$ to
$\pi$. However, $W_{\lambda}$ is also not essentially local for any $\lambda$.

To see this, take the inverse Fourier transform to get the spatial convolution
kernel

$W_{\lambda}(x)=\frac{\sin(\pi\lambda)}{\pi}\,\frac{(-1)^{x}}{\lambda-x}.$
(16)

We have to decide whether $PW_{\lambda}({\leavevmode\rm 1\mkern-5.4muI}-P)$ is
compact. In order to bring it into a more familiar form we introduce the
operator $S:P{\mathcal{H}}\to({\leavevmode\rm 1\mkern-5.4muI}-P){\mathcal{H}}$
given by $(S\psi)(x)=\psi(-1-x)$, and find

$\bigl{(}PW_{\lambda}({\leavevmode\rm
1\mkern-5.4muI}-P)S\psi\bigr{)}(x)=\frac{\sin(\pi\lambda)}{\pi}\,\sum_{y\geq
0}\frac{(-1)^{x+y}}{x+y+1-\lambda}\psi(y).$ (17)

Up to the prefactor and the conjugation by the unitary operator multiplying
with alternating signs, this is a “generalized Hilbert matrix”, which has been
studied in detail in the 50s. It was found [49, Thm. 5] that it has a
continuous spectral component for all $\lambda\in(0,1)$, and hence cannot be
compact. So indeed $W_{\lambda}$ is not essentially local for any
$0<\lambda<1$.

####  2.3.3 Decay properties of walk matrix elements

We can write a general walk as $(W\psi)(x)=\sum_{y}W(x,y)\psi(y)$, where
$W(x,y):{\mathcal{H}}_{y}\to{\mathcal{H}}_{x}$, and wave functions are written
in terms of their local components $\psi=\bigoplus_{x}\psi(x)$. Strict
locality means that $W(x,y)=0$ for $|x-y|>L$, for some $L$. More generally one
could look at decay properties like

$\|W(x,y)\|\leq c\,|x-y|^{-\alpha},$ (18)

whenever $x\neq y$. In the translation invariant case, this can be specialized
by setting $W(x,y)=W(x-y)$.

A simple sufficient criterion is obtained by computing the Hilbert-Schmidt
norm of $PW({\leavevmode\rm 1\mkern-5.4muI}-P)$. If this is finite, this
operator is compact, and a similar criterion for $({\leavevmode\rm
1\mkern-5.4muI}-P)WP$ gives the compactness of $[P,W]=PW({\leavevmode\rm
1\mkern-5.4muI}-P)-({\leavevmode\rm 1\mkern-5.4muI}-P)WP$. We get

$\displaystyle\|PW({\leavevmode\rm 1\mkern-5.4muI}-P)\|_{2}^{2}$
$\displaystyle=$ $\displaystyle\sum_{x\geq 0>y}\mathop{\rm tr}\nolimits
W(x,y)^{*}W(x,y)\leq d\sum_{x\geq 0>y}\|W(x,y)\|^{2}$ (19) $\displaystyle\leq$
$\displaystyle cd\sum_{x\geq 0>y}|y-x|^{-2\alpha}=cd\sum_{n=1}^{\infty}n\cdot
n^{-2\alpha},$ (20)

where in (19) we used that $\|A\|_{2}^{2}\leq d\|A\|^{2}$ for a complex
$d\times d$-matrix $A$, and in (20) that there are exactly $n$ terms with
$x-y=n$ in the first sum. The estimate converges if $1-2\alpha<-1$, i.e.,
$\alpha>1$. This is exactly the condition we get in the translation invariant
case for $\sum_{x}\|W(x)\|<\infty$, which implies uniform convergence of
$\widehat{W}_{N}(k)=\sum_{|x|\leq N}W(x)e^{ikx}$ to $\widehat{W}(k)$ and,
therefore, by the uniform convergence theorem will imply the continuity of
$\widehat{W}$.

To summarize, $\alpha>1$ in (18) is sufficient for essential locality. This is
optimal, because the interpolated shift gives a counterexample with
$\alpha=1$.

##  3 Homotopy classification for translation invariant systems

In our setting, we distinguish two different kinds of symmetry types with non-
trivial index group: those with index group isomorphic to ${\mathbb{Z}}$ and
those with index groups isomorphic to ${\mathbb{Z}}_{2}$. Bearing in mind the
convention of trivial multiplication phases of the symmetries, the symmetry
types with index group ${\mathbb{Z}}$ are distinguished by the presence of a
chiral symmetry which squares to $+{\leavevmode\rm 1\mkern-5.4muI}$, as can be
read off from Table 2. The index group ${\mathbb{Z}}_{2}$ is obtained for the
symmetry types where there is no chiral symmetry or where it squares to
$-{\leavevmode\rm 1\mkern-5.4muI}$.

In this section we will first examine the only symmetry type without chiral
symmetry, i.e. symmetry type D. In a later section we consider the symmetry
types which include a chiral symmetry, where DIII plays a special role.
Although having a ${\mathbb{Z}}_{2}$-valued index group we treat it together
with the symmetry types with $\gamma^{2}=+{\leavevmode\rm 1\mkern-5.4muI}$,
since the chiral symmetry strongly influences the structure of symmetric
unitaries also in that case.

In both cases we obtain a homotopy classification which we prove to be
complete in the sense that translation invariant walks with equal indices are
deformable into each other along an admissible path of translation invariant
walks. However, we caution the reader that for
$\textnormal{{S}}=\textnormal{{D}},\textnormal{{BD}}\textnormal{I}$ additional
invariants appear if we insist on a given cell structure. Regrouping of the
cells or adding trivial systems allows us to trivialize these additional
invariants. Additionally, we prove concrete index formulas for all symmetry
types.

As already mentioned in the introduction, there is a continuous mapping
between translation invariant quantum walks and “effective Hamiltonians”. The
homotopy classification is therefore the same in both settings, and in
particular the completeness results derived in this section carry over to
effective Hamiltonians.

###  3.1 Particle-hole symmetric walks

Consider the case of symmetry type D, with only the particle-hole symmetry
$\eta$ and $\eta^{2}={\leavevmode\rm 1\mkern-5.4muI}$. In this case the index
is just a parity. By Lem. 1.2 we can restrict consideration to flat-band
walks, which are equivalently given by the continuous family of band
projections $Q(k)$ satisfying

$\eta Q(k)\eta={\leavevmode\rm 1\mkern-5.4muI}-Q(-k).$ (21)

By this equation we only need to specify $Q(k)$ for $k\in[0,\pi]$, and (21)
imposes no constraint on $Q(k)$ for $0<k<\pi$. However, at the end points we
get projections with a special property.

######  Definition 3.1.

Let $\eta$ be an antiunitary operator on a finite dimensional Hilbert space
${\mathcal{H}}$ with $\eta^{2}={\leavevmode\rm 1\mkern-5.4muI}$. Then we call
a projection $Q$ $\eta$-flipped if $\eta Q\eta+Q={\leavevmode\rm
1\mkern-5.4muI}$. The set of such projections will be denoted by
${\mathcal{P}}_{\eta}$.

Since $Q$ and $\eta Q\eta$ obviously have the same dimension, ${\mathcal{H}}$
must be even dimensional, and we write $\dim{\mathcal{H}}=2d$.

The basic observation about ${\mathcal{P}}_{\eta}$ is that it has two
connected components, described in the following Lemma.

######  Lemma 3.2.

In the setting of Def. 3.1 let $Q,Q^{\prime}\in{\mathcal{P}}_{\eta}$.
Introduce orthonormal systems $\phi_{\alpha}\in Q{\mathcal{H}}$ and
$\phi^{\prime}_{\alpha}\in Q^{\prime}{\mathcal{H}}$ ($\alpha=1,\ldots,d$)
spanning these spaces, and extend them to bases of ${\mathcal{H}}$ by setting
$\phi_{\alpha+d}=\eta\phi_{\alpha}$ and
$\phi^{\prime}_{\alpha+d}=\eta\phi^{\prime}_{\alpha}$. Let
$M_{\alpha\beta}=\langle\phi_{\alpha},\phi^{\prime}_{\beta}\rangle$ for
$\alpha,\beta=1,\ldots,2d$, and consider $s(Q,Q^{\prime})=\det M$. Then

  * (1)

When $Q^{\prime}=NQN^{*}$ with $N$ unitary and $N\eta=\eta N$,
$s(Q,Q^{\prime})=\det N$.

  * (2)

$s(Q,Q^{\prime})s(Q^{\prime},Q^{\prime\prime})=s(Q,Q^{\prime\prime})$.

  * (3)

$s(Q,Q^{\prime})$ is independent of the choice of $\phi_{\alpha}\in
Q{\mathcal{H}}$ and $\phi^{\prime}_{\alpha}\in Q^{\prime}{\mathcal{H}}$.

  * (4)

$s(Q,Q^{\prime})=\pm 1$.

  * (5)

$s(Q,Q^{\prime})$ depends continuously on $Q$ and $Q^{\prime}$.

  * (6)

$s(Q,Q^{\prime})=1$ if and only if $Q$ and $Q^{\prime}$ can be connected
continuously inside ${\mathcal{P}}_{\eta}$.

###### Proof.

Until (3) is established, consider $s(Q,Q^{\prime})$ as a quantity which
depends not just on $Q$ and $Q^{\prime}$, but also on the bases chosen. Then
(1) is basically a reformulation of the definition: suppose
$Q^{\prime}=NQN^{*}$, then $\phi^{\prime}_{\alpha}=N\phi_{\alpha}$ and
therefore $M=N$.

(2) This is a direct consequence of
$\det(M^{\prime}M)=\det(M^{\prime})\det(M)$.

(3) It suffices to consider the case $Q=Q^{\prime}$ with two arbitrary choices
of bases, and to show that $s(Q,Q^{\prime})=1$. Indeed, the chain rule (2)
then implies the independence of $s(Q,Q^{\prime})$ on the choice of basis for
$Q^{\prime}$ by setting $Q^{\prime\prime}=Q^{\prime}$, and similarly for the
independence on the basis of $Q$.

Suppose $Q=Q^{\prime}$. Then $M$ is the unitary matrix describing the basis
change from $\phi_{\alpha}$ to another basis $\phi_{\alpha}^{\prime}$, and is
of the block matrix form

$M=\begin{pmatrix}V&0\\\ 0&\overline{V}\end{pmatrix},$ (22)

where $V_{\alpha\beta}=\langle\phi_{\alpha},\phi^{\prime}_{\beta}\rangle$ for
$\alpha,\beta=1,\ldots,d$, and $\overline{V}$ denotes the elementwise complex
conjugate. Clearly, in this case $\det M=1$.

(4) To any basis $\phi_{\alpha}$ for $Q{\mathcal{H}}$ we can associate an
$\eta$-real basis $\psi_{\alpha}$ for ${\mathcal{H}}$ by setting
$\psi_{\alpha}=(\phi_{\alpha}+\eta\phi_{\alpha})/\sqrt{2}$ and
$\psi_{\alpha+d}=i(\phi_{\alpha}-\eta\phi_{\alpha})/\sqrt{2}$ for
$\alpha=1,\ldots,d$ and the corresponding $\psi^{\prime}_{\alpha}$ and
$\psi^{\prime}_{\alpha+d}$ in terms of $\phi^{\prime}_{\alpha}$. The basis
change between $\psi$ and $\phi$ and between $\psi^{\prime}$ and
$\phi^{\prime}$ is then given by a fixed matrix $D=D^{\prime}$. We then get
$M=D^{*}\widetilde{M}D$, where
$\widetilde{M}_{\alpha\beta}=\langle\psi_{\alpha},\psi^{\prime}_{\beta}\rangle$
is real. Hence $\det M=|\det D|^{2}\det\widetilde{M}$ is also real.

(5) This is obvious, because the basis $\phi_{\alpha}$ can be chosen to depend
continuously on $Q$, for example by projecting and re-orthogonalizing.

(6) The if part is clear from (4) and (5). For the converse, consider the real
bases $\psi$ and $\psi^{\prime}$, related by
$\psi^{\prime}_{\alpha}=\sum_{\beta}\widetilde{M}_{\beta\alpha}\psi_{\beta}$,
where $\det\widetilde{M}=1$. Since ${\rm SO}(2d)$ is connected, we can find a
continuous family $M(t)$ with $M(0)={\leavevmode\rm 1\mkern-5.4muI}$ and
$M(1)=\widetilde{M}$. In this way we get a continuous family of bases
$\psi(t)$. By applying $D$ we get $\phi_{\alpha}(t)$ and hence $Q(t)$
connecting $Q=Q(0)$ and $Q^{\prime}=Q(1)$. ∎

This can also be written in terms of Pfaffians: Fix a real basis, and express
the projection $Q\in{\mathcal{P}}_{\eta}$ in terms of
$U_{Q}=iQ-i({\leavevmode\rm 1\mkern-5.4muI}-Q)$. Then, since $\eta
U_{Q}\eta=U_{Q}$, $U_{Q}$ is real. Moreover, $U_{Q}^{*}=-U_{Q}$, so $U_{Q}$ is
antisymmetric. Hence the Pfaffian ${\mathop{\rm pf}\nolimits}(U_{Q})$ of
$U_{Q}$ is well defined and real. Since ${\mathop{\rm
pf}\nolimits}(A)^{2}=\det(A)$, ${\mathop{\rm pf}\nolimits}(U_{Q})$ has modulus
$1$, and ${\mathop{\rm pf}\nolimits}(U_{Q})=\pm 1$ for every $\eta$-flipped
projection $Q$. That sign by itself has no meaning, because it depends on the
real basis chosen. This dependence is governed by the identity ${\mathop{\rm
pf}\nolimits}(RAR^{T})=\det(R){\mathop{\rm pf}\nolimits}(A)$, in particular
for orthogonal $R$. Comparing with the proof it is clear that with an
orthogonal transformation of determinant $(-1)$ one switches between the two
connected components. To summarize: in the setting of the Lemma,

${\mathop{\rm pf}\nolimits}(U_{Q})=s(Q,Q^{\prime}){\mathop{\rm
pf}\nolimits}(U_{Q^{\prime}}).$ (23)

######  Proposition 3.3.

Let $W_{1}$ and $W_{2}$ be translation invariant walks with continuous bands
on the same cell structure satisfying the assumptions of symmetry type D for
the same symmetry operator $\eta$. Let $Q_{i}(k)$ ($i=1,2$) denote the
eigenprojections of $\widehat{W}_{i}(k)$ for the upper half plane. Then
$Q_{i}(0)$ and $Q_{i}(\pi)$ are $\eta$-flipped projections. Between these,
consider the four signs $s(\cdot,\cdot)$ in the following diagram:

$Q_{1}(0)$$Q_{1}(\pi)$$Q_{2}(0)$$Q_{2}(\pi)$$s_{1}$$s_{2}$$s_{0}$$s_{\pi}$

Then $W_{1}$ and $W_{2}$ are homotopic in the set of such walks if and only if
$s_{0}=1$ and $s_{\pi}=1$. Moreover, $s_{i}$ determines the invariants
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{i})$
according to the formula

$(-1)^{\textstyle\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)}=s(Q(0),Q(\pi))=\frac{\operatorname{pf}(W(0))}{\operatorname{pf}(W(\pi))}.$
(24)

Note that a similar formula was found by Kitaev for the Majorana number of a
translation invariant gapped Hamiltonian on a finite chain [33].

###### Proof.

(1) Clearly the condition $s_{0}=1=s_{\pi}$ is necessary for homotopy by Lem.
3.2 (6), since a homotopy between $W_{1}$ and $W_{2}$ necessarily needs to
continuously connect $\widehat{W}_{1}(k)$ and $\widehat{W}_{2}(k)$, and the
band projections are continuous functions of $\widehat{W}_{i}(\\{0,\pi\\})$
into ${\mathcal{P}}_{\eta}$.

(2) For the converse we first show that, when $s_{\pi}=1$, i.e., when
$Q_{1}(\pi)$ and $Q_{2}(\pi)$ are homotopic in ${\mathcal{P}}_{\eta}$, we can
deform $W_{1}$ in such a way that we even have $Q_{1}(\pi)=Q_{2}(\pi)$, but
leave $Q_{1}(0)$ unchanged. To this end consider a homotopy of $Q_{1}(\pi)$
and $Q_{2}(\pi)$, in the form of a continuous curve $k\mapsto V_{k}\in
SO(2d)$, for $k\in[0,\pi]$ such that $V_{0}={\leavevmode\rm 1\mkern-5.4muI}$
and $V_{\pi}Q_{1}(\pi)V_{\pi}^{*}=Q_{2}(\pi)$. Moreover, we extend this to
negative values by setting $V_{-k}=V_{k}$. Then consider the walks $W_{t}$,
$t\in[0,1]$ with

$\widehat{W}_{t}(k)=V_{(1-t)k}\widehat{W}_{1}(k)V_{(1-t)k}^{*}.$ (25)

First of all this notation makes consistent use of $W_{1}$ since this equation
is an identity for $t=1$. Moreover, it gives a continuous family of
D-symmetric walks, $\widehat{W}_{0}(0)=\widehat{W}_{1}(0)$, and
$\widehat{W}_{0}(\pi)=\widehat{W}_{2}(\pi)$. The band projections are then
connected as claimed. By replacing $W_{1}$ with $W_{0}$ we may hence assume
without loss that $Q_{1}(\pi)=Q_{2}(\pi)$. With a completely analogous
construction we can achieve $Q_{1}(0)=Q_{2}(0)$.

(3) What we are now left with are two norm-continuous curves of rank $d$
projections in ${\mathbb{C}}^{2d}$ with fixed end points $Q_{1}(0)=Q_{2}(0)$
and $Q_{1}(\pi)=Q_{2}(\pi)$, where $2d$ is the local cell dimension. These can
be considered as two curves on the so called Grassmannian manifold
$Gr_{d}({\mathbb{C}}^{2d})$, that is, the manifold of $d$-dimensional
subspaces of ${\mathbb{C}}^{2d}$. By Lem. 3.4 below, this manifold is simply
connected and hence the two paths of projections and therefore the walks
$W_{1}$ and $W_{2}$ are homotopic.

(4) For the first equality in (24) first note that $s_{1}s_{\pi}s_{2}s_{0}=1$,
whence $s_{0}=s_{\pi}$ is equivalent to $s_{1}=s_{2}$. Now assume $s_{0}=1$.
Then $W_{1}$ and $W_{2}$ are homotopic iff $s_{\pi}=1$ iff $s_{1}=s_{2}$. For
the case of $s_{0}=-1$ let $N$ be the unitary that, in the basis of Lem. 3.2
for $Q=Q_{2}(0)$, swaps $\phi_{1}$ and $\phi_{d+1}$ and acts as the identity
on the complement. Then $\eta N=N\eta$ and $\det N=-1$. Now instead of
$\widehat{W}_{2}$ consider $\widehat{W}_{2}^{\prime}=N^{*}\widehat{W}_{2}N$.
Conjugation with $N$ leaves $s_{2}$ invariant, but changes both signs
$s_{0}=s_{\pi}$. Hence we are left with the case above:
$s_{1}=s_{2}\Leftrightarrow\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{1})=\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{2}^{\prime})$.
Since
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
is also invariant under conjugation with local unitaries,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{2})=\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{2}^{\prime})$
and hence
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{i})$
and $s_{i}$ label the same classes. Equation (24) just translates between
${\mathbb{Z}}_{2}$ considered as an additive or multiplicative group,
respectively. For the correct assignment of invariants consider a walk with
constant $Q(k)=Q(0)$. This clearly has $s(Q(0),Q(\pi))=1$ and the
corresponding walk $W$ acts locally in each cell, which, by the assumption of
balanced cells, implies
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(W)=0$. The second identity
follows from (23). ∎

The following lemma is a well known result from the theory of homogeneous
spaces. To give a self contained description, however, we state it here and
also give a sketch of a proof, with references to more detailed descriptions.

######  Lemma 3.4.

The Grassmannian manifold $Gr_{n}({\mathbb{C}}^{d})$ is simply connected.

###### Sketch of proof .

$Gr_{n}({\mathbb{C}}^{d})$ is known to be isomorphic to the homogeneous
space$SU(d)/\left(SU(n)\times SU(d-n)\right)$ [5]. The fundamental group of
this space can be computed using the exact homotopy sequence of the fibration
$p\colon SU(d)\to SU(d)/(SU(n)\times SU(d-n))$, with fibre $SU(n)\times
SU(d-n)$, where $p$ is the natural quotient map (for further reading see e. g.
[60]). For any such fibration there is the so called “homotopy sequence of a
fibration”, which is exact [50, Thm 11.48]. In our case, by
$\pi_{0}(SU(d))=\\{0\\}=\pi_{1}(SU(d))$ (considered as a single-element set or
the trivial group), this gives rise to the exact sequence

$\displaystyle\\{0\\}\to\pi_{1}\bigl{(}SU(d)/(SU(n)\times
SU(d-n))\bigr{)}\to\pi_{0}\bigl{(}SU(n)\times SU(d-n)\bigr{)}\to\\{0\\},$ (26)

which implies

$\displaystyle\pi_{1}\bigl{(}Gr_{n}({\mathbb{C}}^{d})\bigr{)}=\pi_{0}\left(SU(n)\times
SU(d-n)\right)=\\{0\\},$ (27)

since $SU(n)\times SU(d-n)$ is connected. ∎

####  3.1.1 Berry phase

For continuously differentiable walks, the symmetry index is connected to the
Berry phase of the upper bands [36]:

######  Corollary 3.5.

When $\widehat{W}$ is continuously differentiable,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$
can also be written as twice the Berry phase for the upper bands, i.e.

$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)\equiv\frac{1}{\pi
i}\int_{-\pi}^{\pi}\mskip-10.0mudk\
\sum_{\alpha=1}^{d}\Bigl{\langle}\phi_{\alpha}(k),\,\frac{d\phi_{\alpha}(k)}{dk}\Bigr{\rangle}\quad{\mathop{\rm
mod}\nolimits}2.$ (28)

###### Proof.

The continuous differentiability of $\widehat{W}(k)$ transfers to $Q(k)$.
Hence, we find a continuously differentiable basis
$\\{\phi_{\alpha}(k)\\}_{\alpha=1}^{d}$ for $Q(k){\mathcal{H}}$. By (21) and
similar to Lem. 3.2 this can be extended to a continuously differentiable
basis of ${\mathcal{H}}$ by setting $\phi_{\alpha+d}(k)=\eta\phi_{\alpha}(-k)$
and therefore gives rise to a continuously differentiable family of unitaries
$M(k)$, such that $Q(k)=M(k)QM(k)^{*}$. Now, by (24), we have
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)=\log\det
M(\pi)/(i\pi)$, where it does not matter which branch we choose, since it will
be evaluated ${\mathop{\rm mod}\nolimits}2$. Using $\frac{d}{dk}(\log\det
M(k))=\mathop{\rm tr}\nolimits(M^{*}(k)\frac{dM(k)}{dk})$ this can be
expressed as

$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)\equiv\frac{1}{\pi
i}\int_{0}^{\pi}\mskip-10.0mudk\sum_{n=1}^{2d}\Bigl{\langle}\phi_{n}(k),\,\frac{d\phi_{n}(k)}{dk}\Bigr{\rangle}\quad{\mathop{\rm
mod}\nolimits}2,$ (29)

which evaluates to the claimed formula, if we plug in the definition of
$\phi_{\alpha+d}(k)$. ∎

####  3.1.2 Completeness

The completeness result in [11] tells us that walks that have the same indices
are homotopic. Prop. 3.3, however, seems to contradict this by describing two
walks $W_{1}$, $W_{2}$ with the same indices as non-homotopic if
$s_{0}=s_{\pi}=-1$. This difference is a consequence of the restriction to the
cell structure which is fixed by the (minimal) translations that translation
invariance refers to. Our general theory and the completeness result therein
is entirely independent of translation invariance. Therefore, changing the
assumptions by adding translation invariance with respect to a fixed cell
structure one can expect additional invariants which reveal an even finer
structure of the set of admissible walks. As Prop. 3.3 shows, this is indeed
the case. Yet, if we only demand homotopies to respect translation invariance
with respect to shifts by an even number of sites, e.g. by regrouping
neighbouring even and odd sites as if putting up domino tiles (see Fig. 3 and
Sect. 1.5.1), the additional invariant is rendered useless, i.e. the regrouped
walks become homotopic on the coarser lattice:

######  Lemma 3.6.

Let $W_{1}$ and $W_{2}$ be translation invariant walks with continuous bands
on the same cell structure satisfying the assumptions of symmetry type D for
the same symmetry operator $\eta$. Assume that
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{1})=\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W_{2})$,
which by Prop. 3.3 means that $s_{1}=s_{2}$. This does not fix the values of
$s_{0}$ and $s_{\pi}$, but only their equality. Then:

  * (1)

After regrouping neighbouring cells pairwise, the regrouped walks $W_{1,r}$
and $W_{2,r}$ are homotopic.

  * (2)

There are trivial (i.e., cell-wise acting), D-admissible walks $W_{1}^{0}$ and
$W_{2}^{0}$ such that $W_{1}\oplus W_{1}^{0}$ and $W_{2}\oplus W_{2}^{0}$ are
homotopic.

###### Proof.

(1) Let $s=s_{0}=s_{\pi}$, which are equal by $s_{1}s_{2}s_{0}s_{\pi}=1$ and
$s_{1}=s_{2}$. If $s=1$, $W_{1}$ and $W_{2}$ are homotopic on the original
lattice by Prop. 3.3. This transfers to the regrouped lattice in the obvious
way. Suppose now, that $s=-1$. As a first step transform $W_{1}$ and $W_{2}$
into their corresponding flat-band, as described in Lem. 1.2. We get
$\widehat{W}_{j}(k)=i(2Q_{j}(k)-{\leavevmode\rm 1\mkern-5.4muI})$, with
$j=1,2$. Then, by Lem. 3.2 (1), there are unitaries $N,M$, commuting with
$\eta$, with $\det N=\det M=-1$ s.t.
$\widehat{W}_{2}(0)=N\widehat{W}_{1}(0)N^{*}$ and
$\widehat{W}_{2}(\pi)=M\widehat{W}_{1}(\pi)M^{*}$. Relabelling a walk $W$ as
shown in Fig. 3 leads to a regrouped walk $W_{r}$ which has Fourier transform
$\widehat{W}_{r}(k)$ as given by (13). Then, if $W_{1}$ and $W_{2}$ are
related as above, $\widehat{W}_{1,r}(0)$ and $\widehat{W}_{2,r}(0)$ are
related by conjugation with $N_{r}=H(0)(N\oplus M)H(0)^{*}$. Hence
$s_{0,r}=\det(N_{r})=\det N\det M=1$. For $s_{\pi,r}$, note that by (24)
$s_{1}$ and $s_{2}$ are invariant under regrouping, since the right symmetry
index
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
does not change under such operation. Therefore, by
$s_{0}s_{1}s_{\pi}s_{2}=1$, which also holds for the regrouped walks, we get
$s_{\pi,r}=s_{0,r}=1$ and hence $W_{1}$ and $W_{2}$ are connected by a
period-2 homotopy.

(2) Now let $W_{i}^{0}=\bigoplus_{\mathbb{Z}}\widehat{W}_{i}(0)$ be the walk,
which is block diagonal, with $\widehat{W}_{i}(0)$ acting locally in each cell
and $\widetilde{W}_{i}=W_{i}\oplus W_{i}^{0}$. Then $W_{i}^{0}$ clearly
fulfils the right symmetry condition and has trivial symmetry index
($s_{i}=1$). We get $\widetilde{s}_{0}=s_{0}^{2}=1$ ($=\widetilde{s}_{\pi}$)
and hence $\widetilde{W}_{1}$ and $\widetilde{W}_{2}$ are homotopic by Prop.
3.3. ∎

####  3.1.3 Example: Building bridges

The phenomenon of period two homotopies for walks of type D also occurs in the
split-step walk $W(\theta_{1},\theta_{2})$ (see Sect. 1.4). As the phase
diagram indicates by the white lines between the plaquettes, it is not
possible to continuously connect two split-step walks from two plaquettes with
the same phase, e. g. $W_{0}=W(\theta_{1},\theta_{2})$ and
$W_{1}=W(\theta_{1},\theta_{2}+\pi)$, by varying the two parameters
$\theta_{1},\theta_{2}$. Also leaving the class of split-step walks while
keeping the cell structure fixed does help: to see this, we restrict ourselves
to flat-band walks (centers of the plaquettes), since any two walks can always
be deformed to the respective flat-band candidates in their plaquettes. We
then get $W_{0}=-W_{1}$, which for flat-band walks implies

$Q_{1}(k)={\leavevmode\rm 1\mkern-5.4muI}-Q_{0}(k).$ (30)

The intertwining unitary for $k=0,\pi$ is then always of the form
$M=U\sigma_{x}U^{*}$, which yields $s_{0}=s_{\pi}=-1$. Hence, sticking to two
dimensional cells, $W_{0}$ and $W_{1}$ are not homotopic. If we now regroup
the cell structure, (30) remains true. But now an intertwining unitary is of
the form $M=U(\sigma_{x}\otimes{\leavevmode\rm 1\mkern-5.4muI}_{2})U^{*}$,
which has $\det M=+1$.

$\theta_{2}$$\theta_{1}$ Figure 4: The “Bridge over troubled gap closings”
vizualizing the homotopy (31) of trivial walks with respect to the period-two
regrouping. Without the regrouping, and hence the breaking of translation
symmetry, all symmetry preserving paths would have to contain a gapless walk,
because the end points of the bridge are related by $s_{0}=-1$. In particular,
paths in the split-step parameter plane (Fig. 2) have to cross a white line.

For an explicit example consider $W_{0}=W(0,\pi/2)=-i\sigma_{y}$ and
$W_{1}=W(0,-\pi/2)=i\sigma_{y}$. A homotopy between the two regrouped versions
is then given by

$W_{t}=\begin{pmatrix}0&-\cos(\pi t)&-\sin(\pi t)&0\\\ \cos(\pi
t)&0&0&\sin(\pi t)\\\ \sin(\pi t)&0&0&-\cos(\pi t)\\\ 0&-\sin(\pi t)&\cos(\pi
t)&0\end{pmatrix}.$ (31)

###  3.2 Chiral reduction

In contrast to D, the symmetry types AIII, BDI, CII and DIII all contain a
chiral symmetry. The admissibility condition for this chiral symmetry leads to
a particular structure for admissible operators with respect to the eigenbasis
of $\gamma$. Combining this structure with the flattening of the bands (see
Lem. 1.2 and the accompanying discussion) leads to a process which we call the
_chiral reduction_. We begin with discussing the structure of chirally
symmetric unitaries:

######  Lemma 3.7.

Let ${\mathcal{H}}$ be a Hilbert space equipped with a chiral symmetry
$\gamma$ with $\gamma^{2}=(-1)^{s}{\leavevmode\rm
1\mkern-5.4muI},s\in\\{0,1\\}$, whose $\pm i^{s}$-eigenspaces
${\mathcal{H}}_{\pm}$ have the same dimension. Let $U$ be a unitary operator
which is admissible for this symmetry, i. e. $\gamma U=U^{*}\gamma$. With
respect to the decomposition
${\mathcal{H}}={\mathcal{H}}_{+}\oplus{\mathcal{H}}_{-}$, these operators can
be written in blocks as

$\displaystyle\gamma=i^{s}\begin{pmatrix}{\leavevmode\rm 1\mkern-5.4muI}&0\\\
0&-{\leavevmode\rm 1\mkern-5.4muI}\end{pmatrix}\ \mbox{and}\
U=\begin{pmatrix}A&B\\\ C&D\end{pmatrix}$ (32)

with

$\displaystyle A$ $\displaystyle=A^{*}$ $\displaystyle BB^{*}+A^{2}$
$\displaystyle={\leavevmode\rm 1\mkern-5.4muI}$ $\displaystyle D$
$\displaystyle=D^{*}$ $\displaystyle B^{*}B+D^{2}$
$\displaystyle={\leavevmode\rm 1\mkern-5.4muI}$ (33) $\displaystyle C$
$\displaystyle=-B^{*}$ $\displaystyle AB-BD$ $\displaystyle=0$

Then

  * (1)

$B$ has a bounded inverse iff $U$ has proper gaps at $1$ and $-1$.

  * (2)

$B$ is Fredholm iff $U$ has an essential gap.

  * (3)

$U$ is a flat-band unitary, i. e. $U^{2}=-{\leavevmode\rm 1\mkern-5.4muI}$,
iff $A=D=0$ and $B$ is unitary.

Note that by the assumption that each cell is balanced, the condition that the
dimensions of ${\mathcal{H}}_{+}$ and ${\mathcal{H}}_{-}$ agree is
automatically fulfilled in our walks setting.

###### Proof.

The algebraic relations between the blocks are direct consequences of the
admissibility and the unitarity. Consider the hermitian operator

$\Im mU=\frac{1}{2i}(U-U^{*})=\begin{pmatrix}0&-iB\\\ iB^{*}&0\end{pmatrix}.$
(34)

Clearly, it is invertible iff $B$ is invertible. Moreover, this is equivalent
to the absence of any eigenvalues $z$ or other spectrum in a strip $|\Im
mz|<\varepsilon$. This proves (1). Stating (1) for the image $\lceil U\rceil$
of $U$ in the Calkin algebra is exactly (2). (3) is a direct consequence of
the flat-band condition $U=-U^{*}$. ∎

For the homotopy classification it turns out to be useful to consider flat-
band walks only, since the classification of admissible unitaries $U$ then
reduces to the classification of the upper right matrix blocks $B$, which are
also unitary and have an effectively smaller symmetry group. Note that the
flat-band condition $U^{2}=-{\leavevmode\rm 1\mkern-5.4muI}$ guarantees a
proper gap for $U$. Therefore we do not need to impose such condition on $B$.
Since the flattening procedure will be important when we discuss completeness
of the invariants in Sect. 3.3.2, we will take a closer look at it in the
context of the chiral eigenbasis in Sect. 3.3.1.

In case of AIII no further symmetries are present and the problem reduces to
the homotopy classification of essentially local unitaries $B$ with no further
restriction. As will be made explicit later, this task is completely covered
by the index for quantum walks (see Sect. 1.3, [23]). Adding a second (and
hence also a third) symmetry yields different conditions on $B$, depending on
the symmetry type this new symmetry belongs to. We will always choose to add
the particle-hole symmetry $\eta$. For the cases BDI, DIII and CII $\eta$
takes the form

$\eta=\begin{pmatrix}\eta^{\prime}&0\\\
0&\eta^{\prime}\end{pmatrix}\qquad\text{or}\qquad\eta=\begin{pmatrix}0&\eta^{\prime}\\\
\eta^{\prime}&0\end{pmatrix},$ (35)

where the first case is present for the symmetry types BDI (with $\eta^{\prime
2}={\leavevmode\rm 1\mkern-5.4muI}$) and CII (with $\eta^{\prime
2}=-{\leavevmode\rm 1\mkern-5.4muI}$) and the second case covers type DIII
(with $\eta^{\prime 2}={\leavevmode\rm 1\mkern-5.4muI}$). The new symmetry
conditions for $B$ are then $\eta^{\prime}B\eta^{\prime*}=B$ for BDI and CII
and $\eta^{\prime}B\eta^{\prime*}=-B^{*}$ for DIII. The block form of $\eta$
is a consequence of the commutation relations between the symmetries: In order
to commute with the chiral symmetry in its eigenbasis, $\eta$ has to either
leave the $\gamma$-eigenspaces invariant (for $\gamma^{2}={\leavevmode\rm
1\mkern-5.4muI}$) or swap them (for $\gamma^{2}=-{\leavevmode\rm
1\mkern-5.4muI})$. Of course, a priori the two blocks of $\eta$ might not be
the same, but we can always choose bases in the $\gamma$-eigenspaces
separately to obtain (35). The three reducible cases are collected in Tab. 3.

The chiral reduction seems to raise a contradiction in the cases of BDI and
CII, since they seem to reduce to D and C, which both have different index
groups than BDI and CII. This contradiction is resolved by the gap condition.
Since we don’t have to impose this on $B$, more homotopies are allowed, and
hence the classification changes. In the case of DIII the chiral reduction
leads to a new symmetry type, which is not contained in the tenfold way. This
raises the question which other new types might be considerable, a question
that will be tackled in [12].

S |  BDI |  DIII |  CII
---|---|---|---
$\textnormal{{S}}{}^{\prime}$ | $\eta^{\prime}B\eta^{\prime*}=B$ | $\eta^{\prime}B\eta^{\prime*}=-B^{*}$ | $\eta^{\prime}B\eta^{\prime*}=B$
$\eta^{\prime 2}$ | ${\leavevmode\rm 1\mkern-5.4muI}$ | ${\leavevmode\rm 1\mkern-5.4muI}$ | $-{\leavevmode\rm 1\mkern-5.4muI}$
Table 3:  Reduction procedure for chiral symmetry types.

###  3.3 Index formulas for chiral symmetric walks

Before we start the discussion of index formulas for translation invariant
walks, let us first sharpen a result from [11]. Recall that a bounded operator
$A$ is said to be a Fredholm operator, if it is invertible up to a compact
error, i.e., there is $B$ with $AB-{\leavevmode\rm 1\mkern-5.4muI}$ and
$BA-{\leavevmode\rm 1\mkern-5.4muI}$ both compact. In this case the Fredholm
index of $A$ is defined as

${\mathop{\rm ind}\nolimits}\,_{\mathrm{F}}A=\dim\ker A-\dim\ker A^{*}.$ (36)

The following Lemma connects the symmetry index of operators of symmetry type
AIII, BDI or CII to the Fredholm index of a certain matrix block. The symmetry
index of such operators $U$ is given by

$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(U)=\mathop{\rm
tr}\nolimits_{\mathcal{N}}\gamma,$ (37)

where $\mathcal{N}=\ker(U-U^{*})$ [11].

######  Lemma 3.8.

Let $U$ be an essentially local unitary operator of symmetry type AIII, BDI or
CII with an essential gap at $\pm 1$ (not necessarily flat-band) in the form
(32). Then

$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(U)=-{{\mathop{\rm
ind}\nolimits}\,_{\mathrm{F}}}(B).$ (38)

###### Proof.

The kernel of the matrix on the right hand side of (34) is the set of vectors
of the form $\phi_{1}\oplus\phi_{2}$ such that $B^{*}\phi_{1}=0$ and
$B\phi_{2}=0$, i.e., the space

$\mathcal{N}=\ker(U-U^{*})=\ker(B^{*})\oplus\ker(B).$ (39)

The chiral operator $\gamma$ acts on the first summand as $+{\leavevmode\rm
1\mkern-5.4muI}$ and on the second as $-{\leavevmode\rm 1\mkern-5.4muI}$, so
that on this subspace

$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(U)=\mathop{\rm
tr}\nolimits_{\mathcal{N}}\gamma=\dim\ker(B^{*})-\dim\ker(B)=-{\mathop{\rm
ind}\nolimits}\,_{\mathrm{F}}(B).$ (40)

∎

For symmetry type CII this automatically yields an even number since the
reduced symmetry with $\eta^{\prime 2}=-{\leavevmode\rm 1\mkern-5.4muI}$
forces the kernel of $B$ (and $B^{*}$) to be even dimensional [64]. Note, that
(38) is a generalized version of the index for quantum walks [23, 11], which
provides a complete homotopy classification for essentially local unitaries
without any gap condition and without considering symmetries.

Let us now consider translation invariant walks with continuous band
structure. Then, by assumption the chiral symmetry acts cell-wise. So we have
two $d$-dimensional eigenspaces for each cell, in which $\gamma$ acts as in
(32). This structure survives Fourier transformation, so that

$\widehat{W}(k)=\begin{pmatrix}\widehat{A}(k)&\widehat{B}(k)\\\
-\widehat{B}^{*}(k)&\widehat{D}(k)\end{pmatrix}.$ (41)

The essential gap assumption demands that each $\widehat{W}(k)$ has a gap, so
by Lem. 3.7 $\widehat{B}(k)$ is non-singular for all $k$. Continuity of
$\widehat{W}(k)$ trivially transfers to continuity of $\widehat{B}(k)$, and
therefore, the formula (42) in the following proposition makes sense. It
connects our symmetry index
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
and our formulation of the bulk-boundary-correspondence to the earlier
literature [6], where the formula was already given.

######  Proposition 3.9.

Let $W$ be a translation invariant walk with continuous bands, satisfying the
assumptions of Sect. 1.2, of symmetry type AIII, BDI or CII. Then

$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)={\mathop{\rm
wind}}\bigl{(}k\mapsto\det\widehat{B}(k)\bigr{)},$ (42)

where ${\mathop{\rm wind}}$ denotes the winding number of an origin-avoiding
$2\pi$-periodic continuous function in the complex plane. When $\widehat{W}$
is continuously differentiable this can also be written as

$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)=\frac{1}{2\pi
i}\int_{-\pi}^{\pi}\mskip-10.0mudk\ \mathop{\rm
tr}\nolimits\Bigl{(}\widehat{B}^{-1}(k)\frac{d\widehat{B}(k)}{dk}\Bigr{)}.$
(43)

###### Proof.

Let $P=P_{\geq 0}$ be the half space projection, then
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)=\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(PWP)$
[11]. We now apply Lem. 3.8 to the essentially unitary operator $PWP$ to get
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)=-{\mathop{\rm
ind}\nolimits}\,_{\mathrm{F}}(PBP)$. Now the half-space compression of a
translation invariant operator (in this case $B$) is a Toeplitz operator,
which is Fredholm iff its “symbol” $\widehat{B}(k)$ is invertible. By a
classic result [20, 10] the Fredholm index is then the winding number of its
determinant relative to the origin. This is the formula given in the
proposition.

In the differentiable case we can represent the winding number of $f$ as the
integral of the logarithmic derivative of $f$, and use the differentiation
formula for determinants to get (43). ∎

For an interactive tool, illustrating (42) for the split-step walk, see [59].

####  3.3.1 Flattening the band structure

The flattening of the band structure, described in 1.3 can also be done
directly in the basis of Lem. 3.7. Since $B$ is non-singular, its polar
isometry is unitary. The polar isometry also shares the symmetry conditions
with $B$. Hence, continuously interpolating between $B$ and its polar
isometry, together with an appropriate deformation of $A$ and $D$ does the
job. This raises the question, if the flattening construction from Lem. 1.2
and the one sketched above are compatible. Indeed, they are essentially the
same: Consider a translation invariant walk in the chiral eigenbasis (see
(41)). Then, it suffices to flatten the finite dimensional matrix
$\widehat{W}(k)$ for each $k$ (we will omit the $k$ dependence and the hat for
readability). Let
$B=\sum_{i=1}^{d}\beta_{i}{|\phi_{i}\rangle\langle\psi_{i}|}$ be the singular
value decomposition of $B$, where $\\{\phi_{i}\\}$ ($\\{\psi_{i}\\}$) is an
orthonormal basis for ${\mathcal{H}}_{+}$ (${\mathcal{H}}_{-}$) and since $B$
is non-singular we have $\beta_{i}>0$. For non-degenerate $\beta_{i}$’s (3.7)
immediately implies $A$ ($D$) to be diagonal in the basis $\\{\phi_{i}\\}$
($\\{\psi_{i}\\}$), with eigenvalues $a_{i}=d_{i}=\pm\sqrt{1-\beta_{i}^{2}}$.
Since we can diagonalize $A$ ($D$) in each degenerate block this is also true
for degenerate singular values $\beta_{i}$. To summarize: we have

$B=\sum_{i=1}^{d}\beta_{i}{|\phi_{i}\rangle\langle\psi_{i}|},\
A^{2}=\sum_{i=1}^{d}(1-\beta_{i}^{2}){|\phi_{i}\rangle\langle\phi_{i}|}\
\text{and}\
D^{2}=\sum_{i=1}^{d}(1-\beta_{i}^{2}){|\psi_{i}\rangle\langle\psi_{i}|}.$ (44)

The eigenvalues $\lambda_{n}$ of $W$ then evaluate to

$\lambda_{n}=\pm\sqrt{1-\beta_{i}^{2}}\pm i\beta_{i}.$ (45)

Hence, flattening the band structure by deforming the eigenvalues to $\pm i$
is equivalent to deforming all $\beta_{i}$ to $1$ and therefore to deforming
$B$ to its polar isometry.

Having established the explicit flattening construction in the chiral
eigenbasis, let us use the structure to connect the index for chiral symmetric
walks with the index for particle-hole walks:

######  Corollary 3.10.

When $\widehat{W}$ is a continuously differentiable flat-band walk
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$
can also be written as twice the Berry phase for the upper band, i.e.

$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)=\frac{2}{2\pi
i}\int_{-\pi}^{\pi}\mskip-10.0mudk\
\sum_{\alpha=1}^{d}\Bigl{\langle}\phi_{\alpha}(k),\,\frac{d\phi_{\alpha}(k)}{dk}\Bigr{\rangle}.$
(46)

###### Proof.

For flat-band walks, the eigenvectors corresponding to eigenvalues $+i$ can be
chosen to be of the form

$\phi_{\alpha}(k)=1/\sqrt{2}\begin{pmatrix}-i\widehat{B}(k)\chi_{\alpha}\\\
\chi_{\alpha}\end{pmatrix},$ (47)

where $\\{\chi_{\alpha}\\}_{\alpha=1}^{d}$ is any orthonormal basis for
${\mathcal{H}}_{-}$ (independent of $k$). Now in (43) $\mathop{\rm
tr}\nolimits\Bigl{(}\widehat{B}^{*}(k)\frac{d\widehat{B}(k)}{dk}\Bigr{)}$
evaluates to

$\mathop{\rm
tr}\nolimits\Bigl{(}\widehat{B}^{*}(k)\frac{d\widehat{B}(k)}{dk}\Bigr{)}=\sum_{\alpha=1}^{d}\Bigl{\langle}\widehat{B}(k)\chi_{\alpha},\frac{d\widehat{B}(k)}{dk}\chi_{\alpha}\Bigr{\rangle}=2\sum_{\alpha=1}^{d}\Bigl{\langle}\phi_{\alpha}(k),\frac{d\phi_{\alpha}(k)}{dk}\Bigr{\rangle},$
(48)

which is twice the Berry connection for the upper band. ∎

####  3.3.2 Completeness

For symmetry type AIII the index classification of translation invariant walks
with a fixed cell structure is complete. Each walk $W$ defines a loop
$\widehat{W}(k)$ in the unitary group $U(2d)$, which in the flat-band case is
completely characterized by the unitary loop $\widehat{B}(k)\in U(d)$. There
are then no further restrictions on $\widehat{B}(k)$ and hence completeness
follows from the classic result, that two unitary loops are homotopic iff the
winding numbers of their determinants coincide. Such continuous deformation
automatically preserve locality on the way. In the case of strict locality
this was already shown in [23]. For essentially local walks this follows from
Prop. 2.1, as the continuity of a loop guarantees for the essential locality
of the corresponding walk.

For the symmetry types BDI and CII we also have to take care of the particle-
hole symmetry. Let
$c\colon[-\pi,\pi)\to{\mathbb{C}},\,c(k)=\det(\widehat{B}(k))$. The symmetry
condition on $B$ (see Tab. 3) then implies

$c(k)=\overline{c(-k)}.$ (49)

The effect of this restriction is, that similar to D,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}$
is no longer complete for a fixed cell structure. Indeed, consider e. g. the
BDI-symmetric walks with constant loops $B_{1}(k)=1$ and $B_{2}(k)=-1$, which
both yield walks with trivial symmetry index on the cells
${\mathcal{H}}_{x}={\mathbb{C}}^{2}$. But it is clearly not possible to
transform them into each other, without violating the gap condition for the
corresponding walks (Lem. 3.7), since such path would have to cross the origin
for $k\in\\{0,\pi\\}$. This example indicates an additional invariant, similar
to the _regrouping-invariant_ in case D.

######  Lemma 3.11.

Let $W_{1}$ and $W_{2}$ be two translation invariant walks with continuous
bands on the same cell structure. Assume $W_{1}$ and $W_{2}$ to be admissible
for the same symmetries of type BDI, with ${\mathop{\rm
wind}}(c_{1})={\mathop{\rm wind}}(c_{2})$, where
$c_{i}(k)=\det\widehat{B}_{i}(k)$. Then $W_{1}$ and $W_{2}$ are homotopic iff
$\operatorname{sign}(c_{1}(0))=\operatorname{sign}(c_{2}(0))$.

###### Proof.

As a first step, we deform both walks to their respective flat-band forms to
reduce the problem to the upper right blocks $\widehat{B}_{i}(k)$ in the
chiral eigenbasis. Since $\widehat{B}_{i}(k)$ is then unitary, $c_{i}(k)$ lies
on the unit circle for all $k$. In particular we have $c_{i}(k)=\exp(2\pi
ia_{i}(k))$, with $a(k)\in{\mathbb{R}}$ and
$a_{i}(\pi)=a_{i}(-\pi)+{\mathop{\rm wind}}(c_{i})$. Moreover the symmetry
condition (49) implies $c_{i}(k)=\pm 1$ for $k\in\\{0,\pm\pi\\}$ and the
corresponding $\widehat{B}_{i}(k)$ to be orthogonal with respect to an
$\eta^{\prime}$ invariant basis. In order to deform $\widehat{W}_{1}$ into
$\widehat{W}_{2}$ it is now enough to only consider the paths $k\mapsto
c_{i}(k)$ for $k\in[0,\pi]$, since the second half of the loop is then
determined by (49) and we have to show, that these two paths are homotopic. To
do so we need that the two endpoints can be connected by a continuous path
inside the set of orthogonal matrices. A necessary and sufficient condition
for this is $c_{1}(0)=c_{2}(0)$ and $c_{1}(\pi)=c_{2}(\pi)$, since the
connected components of the orthogonal group are labeled by the values $\pm 1$
of the determinant. If this is fulfilled, we are left with a closed loop in
the unitary group, which by ${\mathop{\rm wind}}(c_{1})={\mathop{\rm
wind}}(c_{2})$ does not wind around the origin and is therefore contractible.
Moreover, if $c_{1}(k=0)=c_{2}(k=0)$, the same already follows for $k=\pi$: by
symmetry it is $a(k)+a(-k)=\text{const.}=2a(0)$ and therefore ${\mathop{\rm
wind}}(c)=2(a(\pi)-a(0))$. This gives $c(\pi)=(-1)^{p}c(0)$, with
$p={\mathop{\rm wind}}(c){\mathop{\rm mod}\nolimits}2$, which is the same for
both $c_{i}$. ∎

Similar to the case of symmetry type D, the additional invariant can be
trivialized, by either regrouping neighbouring cells once or by adding trivial
systems to the respective walks under consideration:

######  Lemma 3.12.

Consider the setting of Lem. 3.11. Then:

  * (1)

After regrouping neighbouring cells pairwise, the regrouped walks $W_{1,r}$
and $W_{2,r}$ are homotopic.

  * (2)

There are trivial (i.e., cell-wise acting), BDI-admissible walks $W_{1}^{0}$
and $W_{2}^{0}$ such that $W_{1}\oplus W_{1}^{0}$ and $W_{2}\oplus W_{2}^{0}$
are homotopic.

###### Proof.

If we regroup a given walk once, according to (13), we get
$c_{r}(k)=c(k/2)c(k/2+\pi)$ and hence
$c_{r}(0)=c(0)c(\pi)=c(0)^{2}(-1)^{p}=(-1)^{p}$, which only depends on the
winding number and is therefore the same for $W_{1}$ and $W_{2}$.

Now let $W_{i}^{0}=\bigoplus_{\mathbb{Z}}\widehat{W}_{i}(0)$ be the walk,
which is block diagonal, with $\widehat{W}_{i}(0)$ acting locally in each
cell. It fulfils the right symmetry and has trivial symmetry index. We get
$\widetilde{c}_{i}(0)=c_{i}(0)^{2}>0$, where $\widetilde{c}_{i}(k)$ denotes
the determinant of the upper right chiral block of $W_{i}\oplus W_{i}^{0}$.
Now, since
$\operatorname{sign}(\widetilde{c}_{1}(0))=\operatorname{sign}(\widetilde{c}_{2}(0))$,
$W_{1}\oplus W_{1}^{0}$ and $W_{2}\oplus W_{2}^{0}$ are homotopic. ∎

Note that the construction of the trivial walks is exactly the same as for
symmetry type D (Lem. 3.6).

For symmetry type CII the additional regrouping invariant does not appear:

######  Lemma 3.13.

Let $W$ be a translation invariant walk with continuous bands of symmetry type
CII. Then $\operatorname{sign}(c(0))=\operatorname{sign}(c(\pi))=1$. Moreover,
two translation invariant walks $W_{1},W_{2}$, which are admissible for the
same symmetries of type CII on the same cell structure are homotopic iff
${\mathop{\rm wind}}(c_{1})={\mathop{\rm wind}}(c_{2})$.

###### Proof.

Consider again the flat-band case, where $\widehat{B}(k)$ is unitary. For
$k\in\\{0,\pi\\}$, $\widehat{B}(k)$ commutes with $\eta^{\prime}$, with
$\eta^{\prime 2}=-{\leavevmode\rm 1\mkern-5.4muI}$. This implies
$\det(\widehat{B}(0))=\det(\widehat{B}(\pi))=1$: Let $B\phi=\lambda\phi$, with
$B$ finite dimensional and commuting with $\eta^{\prime}$, Then
$B\eta^{\prime}\phi=\overline{\lambda}\eta^{\prime}\phi$ such that the non-
real eigenvalues of $B$ come in complex conjugate pairs. Since $\eta^{\prime
2}=-{\leavevmode\rm 1\mkern-5.4muI}$ any real eigenvalue occurs with an even
multiplicity and we get $\det(B)=1$.

The rest of the proof is now similar to the proof of Lem. 3.11 and the only
thing we need to show is, that the set of finite dimensional unitaries which
commute with a given $\eta^{\prime}$ is connected. Consider such a unitary
$B$. Since the eigenvalues of $B$ come in complex conjugate pairs, we can
continuously shift each pair to $+1$, without changing the eigenvectors, and
thus keeping the symmetry. Hence, every such unitary is connected to the
identity. Note that the only difference to the reduced symmetry condition for
symmetry type BDI is the even dimensional $-1$-eigenspace which makes such
deformations possible. ∎

###  3.4 Symmetry type DIII

In the case of symmetry type DIII, Lem. 3.8 does not apply. In fact, due to
the effective symmetry of $B$ after the chiral reduction process
($\eta^{\prime}B\eta^{\prime*}=-B^{*}$), the Fredholm index of $B$ always
evaluates to zero. For such operators, there is, however, a similar invariant
[58]. It is defined for odd symmetric Fredholm operators, i. e. Fredholm
operators $T$ satisfying $(IK)T(IK)^{*}=T^{*}$, with $I$ being a real unitary
with $I^{2}=-{\leavevmode\rm 1\mkern-5.4muI}$, and $K$ the complex conjugation
with respect to a suitable basis. For such operators the index is defined as
the parity of the dimension of the kernel, i.e.

${\mathop{\rm ind}\nolimits}\,_{2}(T)=\dim(\ker(T))\>{\mathop{\rm
mod}\nolimits}\ 2,$ (50)

which is a complete homotopy invariant and invariant under compact
perturbations that respect the odd symmetry [58]. The following Lemma connects
the symmetry index of a unitary operator of symmetry type DIII given by
$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(U)=\dim\mathcal{N}\
{\mathop{\rm mod}\nolimits}\ 4$, with $\mathcal{N}$ defined in (39), with
${\mathop{\rm ind}\nolimits}\,_{2}$:

######  Lemma 3.14.

Let $U$ be an essentially gapped unitary of symmetry type DIII. Then

$\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(U)=2\ {\mathop{\rm
ind}\nolimits}\,_{2}(I^{*}B),$ (51)

where $I$ is a real unitary with $I^{2}=-{\leavevmode\rm 1\mkern-5.4muI}$ and
$B$ is the upper right block of the decomposition given in (32).

###### Proof.

From the DIII-admissibility condition in Table 3, (39) yields

$\dim\mathcal{N}=2\ \dim\ker(B),$ (52)

and hence $\mathop{\mathrm{s}\mkern-1.0mu\mathrm{i}}\nolimits(U)=2\dim\ker(B)\
{\mathop{\rm mod}\nolimits}\ 4$. By [58, Proposition 1], an operator $T$ is
odd symmetric with respect to $I$, iff $T=I^{*}\widetilde{B}$, for a skew-
symmetric operator $\widetilde{B}$. Choosing a basis in which
$\eta^{\prime}=K$ we have $B^{T}=-B$, where $B^{T}$ denotes the matrix
transpose with respect to this basis. Thus, in this basis $I^{*}B$ is odd
symmetric with respect to any real unitary $I$ with $I^{2}=-{\leavevmode\rm
1\mkern-5.4muI}$. By the invertibility of $I$ we have
$\dim\ker(B)=\dim\ker(I^{*}B)$, which completes the proof. ∎

$\mathcal{A}$$\widehat{B}(0)$$\widehat{B}(\pi)$$\widehat{B}(k)$$\widehat{B}_{c}(k)$$\widehat{B}_{c^{\prime}}(k)$
Figure 5: Visualization of two antisymmetric closures. The path
$\widehat{B}(k)$, for $k\in[0,\pi]$ is depicted in red. The two different
antisymmetric closures $\widehat{B}_{c}(k)$ and $\widehat{B}_{c^{\prime}}(k)$,
for $k\in[\pi,2\pi]$, are depicted in blue. Their difference is a closed path
inside the antisymmetric manifold (blue loop).

In [58, Sect. 4] also an odd symmetric Gohberg-Krein theorem is derived. It
states, that ${\mathop{\rm ind}\nolimits}\,_{2}$ of an odd symmetric Toeplitz
operator (with continuous symbol, compare with Prop. 3.9) is equal to the
spectral flow of its symbol modulo $2$.

Here we give an alternative derivation of the right symmetry index of DIII
symmetric walks in terms of a winding number. In order to derive the index
formula, we combine ideas from the two previous sections. Roughly speaking, we
on the one hand start with the same quantity as for other chiral walks
($\det(\widehat{B})$) but on the other, only the path for $k\in[0,\pi]$
matters, similar to symmetry type D.

######  Proposition 3.15.

Let $W$ be a translation invariant walk of symmetry type DIII with continuous
bands, and let $\widehat{B}(k)$ be the component of the chiral reduction (41).
Then, there is a continuous closed curve $[0,2\pi]\ni
k\mapsto\widehat{B}_{c}(k)$ of operators such that
$\widehat{B}(k)=\widehat{B}_{c}(k)$ for $k\in[0,\pi]$ and $\widehat{B}_{c}(k)$
antisymmetric and non-singular for $k\in[\pi,2\pi]$. Let
$c(k)=\det\widehat{B}_{c}(k)$ be the corresponding closed curve in
${\mathbb{C}}$. Then ${\mathop{\rm wind}}(c)\ {\mathop{\rm mod}\nolimits}\ 2$
is a complete homotopy invariant and

$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)\equiv
2\ {\mathop{\rm wind}}(c)\quad{\mathop{\rm mod}\nolimits}4.$ (53)

###### Proof.

For a translation invariant walk $\widehat{W}(k)$ the reduced symmetry
condition for $\widehat{B}$ gives $\widehat{B}(k)=-\widehat{B}(-k)^{T}$, in an
$\eta^{\prime}$\- invariant basis. Hence $\widehat{B}(0)$ and
$\widehat{B}(\pi)$ are antisymmetric and non-singular but not necessarily real
matrices. Since the manifold of antisymmetric non-singular matrices
$\mathcal{A}$ is connected [66], we can find a continuous connection from
$\widehat{B}(\pi)$ to $\widehat{B}(0)$, which gives the antisymmetric closure
$\widehat{B}_{c}$ described in the proposition.

We have to show that ${\mathop{\rm wind}}(c)\ {\mathop{\rm mod}\nolimits}2$ is
independent of the antisymmetric closure we choose. So let
$\widehat{B}_{c}(k)$ and $\widehat{B}_{c^{\prime}}(k)$ be two different
closures. By concatenating the two closure segments (see Fig. 5) we get a
closed path in $\mathcal{A}$. The winding number of its determinant will be
${\mathop{\rm wind}}(c)-{\mathop{\rm wind}}(c^{\prime})$. Hence we need to
show that any closed path in $\mathcal{A}$ has even winding number. Indeed,
for $A\in\mathcal{A}$ we have $\det A={\mathop{\rm pf}\nolimits}(A)^{2}$ where
also ${\mathop{\rm pf}\nolimits}(A)\neq 0$. Hence, for a closed path
${\mathop{\rm wind}}\bigl{(}\det A(\cdot)\bigr{)}=2{\mathop{\rm
wind}}\bigl{(}{\mathop{\rm pf}\nolimits}A(\cdot)\bigr{)}\in 2{\mathbb{Z}}$.

For a continuous deformation of $\widehat{B}$ the end points $\widehat{B}(0)$
and $\widehat{B}(\pi)$ in $\mathcal{A}$ move continuously, so the closures can
also be made to change continuously by considering as deformed closures those
obtained by joining the deformations of $\widehat{B}(0)$ and
$\widehat{B}(\pi)$ to the original closure. Hence ${\mathop{\rm wind}}(c)$ is
a homotopy invariant. It is also a complete invariant. To see this, we can
first deform each walk to a flat band one. Moreover, we can choose the
antisymmetric closure to be unitary, since for a flat-band walk the
$\widehat{B}(k)$ are unitary and the restriction of $\mathcal{A}$ to unitary
elements remains connected [66]. We choose it so that ${\mathop{\rm
wind}}(c)\in\\{0,1\\}$, and $\widehat{B}_{c}(3\pi/2)=A$ for some fixed
$A\in\mathcal{A}$. By including parts of the antisymmetric closure as initial
and final segments of $\widehat{B}$ we deform to a path with
$\widehat{B}(0)=\widehat{B}(\pi)=A$. In this normal form no closure operation
is needed, and ${\mathop{\rm wind}}(c)$ is just the winding number of the
determinant of a closed path in the unitary group. Since the fundamental group
of the unitary group is ${\mathbb{Z}}$, equality of ${\mathop{\rm wind}}(c)$
implies that two walks can be deformed into each other.

To get formula (53) it now suffices to check it on a generating example. The
case of trivial index is straightforward: if
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)=0$,
$W(k)$ is homotopic to a trivial walk with $c(k)=c$ for all $k$ and therefore
$2\ {\mathop{\rm wind}}(c)\equiv 0\ {\mathop{\rm mod}\nolimits}4$.
A non-trivial generating example for symmetry type DIII is given by

$\widehat{B}(k)=\begin{pmatrix}0&-e^{-ik}\\\ e^{ik}&0\end{pmatrix},$ (54)

with $\eta^{\prime}=K$ being the complex conjugation. A possible closure is
then given by $-ie^{ik}\sigma_{2}$, where $\sigma_{2}$ denotes the second
Pauli matrix. Then ${\mathop{\rm wind}}(c)=1$, in accordance with the claimed
formula, since, by $W^{2}=-{\leavevmode\rm 1\mkern-5.4muI}$,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)=\ker\bigl{(}\Im
m(PWP)\bigr{)}=\ker\bigl{(}-iPWP\bigr{)}=2$. ∎

For continuously differentiable bands, we then get an index formula with two
contributions. A Berry type integral, stemming from the winding of the
determinant of $\widehat{B}(k)$ (compare Cor. 3.10) and the quotient of
Pfaffians, resembling the invariant for D-walks (Prop. 3.3). For DIII-
symmetric superconductors a formula similar to (55) was derived in [44].

######  Corollary 3.16.

Let $W$ be a flat-band walk of symmetry type DIII. When $\widehat{W}$ is
continuously differentiable,
$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)$
can be written in a Berry phase type formula minus a correction term, i. e.

$\mathop{\hbox{\raisebox{4.49997pt}{$\scriptstyle\rightharpoonup$}}\mathop{\mathrm{s}\mkern-1.0mu\textup{\i}}\nolimits}(W)\equiv\frac{2}{\pi
i}\left(\int_{0}^{\pi}dk\sum_{\alpha=1}^{d}\Bigl{\langle}\phi_{\alpha}(k),\frac{d\phi_{\alpha}(k)}{dk}\Bigr{\rangle}-\log\left(\frac{\operatorname{pf}(\widehat{B}(\pi))}{\operatorname{pf}(\widehat{B}(0))}\right)\right)\quad{\mathop{\rm
mod}\nolimits}4.$ (55)

###### Proof.

The winding integral of $c$ has two contributions, one from
$\det(\widehat{B}(k))$, for $k\in[0,\pi]$ and one from the antisymmetric
closure for $k\in[\pi,2\pi]$. The first summand is the integral over the Berry
connection, according to Cor. 3.10. We already showed, that, evaluated
${\mathop{\rm mod}\nolimits}2$, the second contribution is independent of
which closure we choose. Hence it depends only on the endpoints and evaluates
to the correction term in (55), if we use $\det(A)=\operatorname{pf}(A)^{2}$
and $\widehat{B}(2\pi)=\widehat{B}(0)$. ∎

##  4 Decay properties of boundary eigenfunctions

In this section we consider a translation invariant walk $W$ with strictly
finite propagation. Suppose we have joined it with another walk on the
negative half axis, so we possibly get some eigenfunctions $\phi$ for
eigenvalue $\pm 1$. We claim that in this case $|\phi(x)|\leq\lambda^{x}$ as
$x\to\infty$. Knowing the decay rate is crucial for applications of the theory
to finite systems (see Sect. 9 in [11]): When the bulk does not extend all the
way to $+\infty$ but only has length $L$ we still expect to find eigenvalues
near $\pm 1$, whose distance from $\pm 1$ is of the order $\lambda^{L}$.

Restricting, without loss, to the eigenvalues at $+1$, we have to characterize
the solutions of the equation $(W-{\leavevmode\rm 1\mkern-5.4muI})\phi(x)=0$
for $x\geq 0$, where we assumed the transition region to lie somewhere on the
negative half-axis and does not intersect with $x=0$. This is a
${\mathbb{C}}^{d}$-valued linear recursion relation of finite order which,
however, is not explicit usually: Using (1) we cannot simply solve for the
highest occurring $\psi(y)$, because $W(x)$ need not be invertible for the
lowest value of $x$ where this is non-vanishing. Nevertheless, one can usually
find an appropriate selection of components of
$\phi(x),\phi(x+1),\ldots,\phi(x+r)$ for which the recursion can be solved by
iterating a fixed matrix. This is called the transfer matrix method. But does
it always work? Consider, e.g., a walk in which one component of
${\mathbb{C}}^{d}$ is simply left invariant. Then this component in $\phi(x)$
drops out of the equation altogether, so we can say nothing about decay. In
this case, we can also make eigenfunctions on the whole line, so the gap
condition is violated. This means that we have to turn a spectral condition
(existence of the gap) into an algebraic property (existence of a transfer
matrix).

Even if we cannot directly turn the eigenvalue equation into a matrix
iteration, we can try the exponential ansatz $\phi(x)=\lambda^{x}\phi_{0}$.
Using (1), the eigenvalue equation $W\phi(x)=\phi(x)$ then becomes

$\displaystyle\widetilde{W}(\lambda)\phi_{0}$ $\displaystyle=$
$\displaystyle\phi_{0},\qquad\text{where}$ (56)
$\displaystyle\widetilde{W}(\lambda)$ $\displaystyle=$
$\displaystyle\sum_{y}W(y)\lambda^{-y}.$ (57)

Comparison with (6) implies that
$\widehat{W}(k)=\widetilde{W}\bigl{(}e^{-ik}\bigr{)}$, so $\widetilde{W}$ is
an analytic continuation of $\widehat{W}$ from the unit circle to the unit
disc. Clearly, a necessary condition for solving (56) is
$\det(\widetilde{W}(\lambda)-{\leavevmode\rm 1\mkern-5.4muI})=0$, which is an
algebraic equation for $\lambda$. The following proposition confirms that the
strategy based on the exponential ansatz is indeed valid.

######  Proposition 4.1.

Let $W$ be a strictly local translation invariant quantum walk with spectral
gap at $1$. Let $\phi\in{\mathcal{H}}$ satisfy $(W-{\leavevmode\rm
1\mkern-5.4muI})\phi(x)=0$ for $x\geq 0$. Then, there are vectors
$\phi_{\lambda,i}\in{\mathbb{C}}^{d}$, and exponents
$m_{\lambda,i}\in{\mathbb{N}}$ so that, for $x\geq 0$,

$\phi(x)=\sum_{\lambda}\sum_{i}x^{m_{\lambda,i}}\lambda^{x}\
\phi_{\lambda,i},$ (58)

where $\lambda$ runs over the finite set of solutions of
$\det\bigl{(}\widetilde{W}(\lambda)-{\leavevmode\rm 1\mkern-5.4muI}\bigr{)}=0$
with $|\lambda|<1$, and, for each $\lambda$, $i$ runs from $1$ to the
algebraic multiplicity of the zero.

###### Proof.

Let $\psi=(W-{\leavevmode\rm 1\mkern-5.4muI})\phi$, which is a function
vanishing for $x\geq 0$. Let
$\widetilde{\psi}(\lambda)=\sum_{x<0}\psi(x)\lambda^{-x}$, which is absolutely
convergent and analytic for $|\lambda|<1$. The boundary value
$\widetilde{\psi}(e^{-ik})=\widehat{\psi}(k)$ is the Fourier transform of
$\psi$. Now pick some $x\geq 0$ and a vector $\chi\in{\mathbb{C}}^{d}$, and
let $\delta_{x}\otimes\chi\in{\mathcal{H}}$ be the vector equal to $\chi$ at
$x$ and zero otherwise. Then

$\displaystyle\langle\chi|\phi(x)\rangle$ $\displaystyle=$
$\displaystyle\langle\delta_{x}\otimes\chi|(W-{\leavevmode\rm
1\mkern-5.4muI})^{-1}\psi\rangle=\int\frac{dk}{2\pi}e^{-ikx}\langle\chi|(\widehat{W}(k)-{\leavevmode\rm
1\mkern-5.4muI})^{-1}\widehat{\psi}(k)\rangle$ (59) $\displaystyle=$
$\displaystyle\frac{i}{2\pi}\int\\!du\
u^{x}\Bigl{\langle}{\chi}\Bigm{|}{(\widetilde{W}(u)-{\leavevmode\rm
1\mkern-5.4muI})^{-1}\,\frac{1}{u}\widetilde{\psi}(u)}\Bigr{\rangle},$ (60)

where we have substituted $u=e^{-ik}$, and the integral is around the unit
circle. Now $u^{x}$ and $u^{-1}\widetilde{\psi}(u)$ are analytic on the unit
disc, and $(\widetilde{W}(u)-{\leavevmode\rm 1\mkern-5.4muI})^{-1}$ is
analytic except at the points where the operator
$(\widetilde{W}(u)-{\leavevmode\rm 1\mkern-5.4muI})$ becomes singular. These
are the solutions of $\det\bigl{(}\widetilde{W}(u)-{\leavevmode\rm
1\mkern-5.4muI}\bigr{)}=0$, the order of the pole being at most the order of
the algebraic multiplicity of this zero. Hence by the Residue Theorem, we can
write the integral as a sum of evaluations of $u^{x}$, and possibly some
derivatives of $u^{x}$, at $u=\lambda$. ∎

#### Example

Let us confirm Prop. 4.1 with the split-step example (Sect. 1.4). Eigenvectors
of a decoupled version are determined by solving the eigenvalue equations
$W\phi=s\phi$ and $\gamma\phi=\chi\phi$ ($s,\chi=\pm 1$) as a recursion