4 The Amorphous Kitaev Model

# Methods

This section describes the novel methods we developed to simulate the AK model including lattice generation, bond colouring and the inverse mapping between flux sector and gauge sector. All results and figures herein were generated with Koala [1].

## Voronisation

The lattices we use are Voronoi partitions of the torus [2–4]. We start by sampling *seed points* uniformly on the torus. As most off the shelf routines for computing Voronoi partitions are defined on the plane rather than the torus, we tile our seed points into a \(3\times3\) or \(5\times5\) grid] ^{1} before calling a standard Voronoi routine [5] from the Python package Scipy [6]. Finally, we convert the lattice defined by the central cell into a toroidal lattice. We do this by reassigning edges that cross the boundaries to connect to the corresponding point within the lattice, yielding a trivalent lattice on the torus. We encode our lattices with edge lists \([(i,j), (k,l)\ldots]\). The information about which edges crossed the boundaries is stored in an additional 2D vector \(\vec{v} \in \{-1,0,+1\}^2\) for each edge that encodes the sense in which it crosses the periodic boundary conditions. This is equivalent to how the edge would leave the unit cell were the system to tile the plane, see appendix A.4 for more detail. The graph generated by a Voronoi partition of a 2D surface is always planar. This means that no edges cross each other when the graph is embedded into the plane. It is also trivalent in that every vertex is connected to exactly three edges [7,8].

## Colouring the Bonds

To be solvable, the AK model requires that each edge in the lattice be assigned a label \(x\), \(y\) or \(z\), such that each vertex has exactly one edge of each type connected to it, a three-edge-colouring. This problem must be distinguished from that considered by the famous four-colour theorem [9]. The four-colour theorem is concerned with assigning colours to the **vertices** of planar graphs, such that no vertices that share an edge have the same colour.

For a graph of maximum degree \(\Delta\), \(\Delta + 1\) colours are always enough to edge-colour it. An \(\mathcal{O}(mn)\) algorithm exists to do this for a graph with \(m\) edges and \(n\) vertices [10]. Graphs with \(\Delta = 3\) are known as cubic graphs. Cubic graphs can be four-edge-coloured in linear time [11]. However, we need a three-edge-colouring of our cubic graphs, which turns out to be more difficult. Cubic, planar, *bridgeless* graphs can be three-edge-coloured if and only if they can be four-face-coloured [12]. Bridges are edges that connect otherwise disconnected components. An \(\mathcal{O}(n^2)\) algorithm exists for these [13]. However, it is not clear whether this extends to cubic, **toroidal** bridgeless graphs.

A four-face-colouring is equivalent to a four-vertex-colouring of the dual graph, see appendix A.4. So if we could find a four-vertex-colouring of the dual graph we would be done. However, vertex-colouring a toroidal graph may require up to seven colours [14]! The complete graph of seven vertices \(K_7\) is a good example of a toroidal graph that requires seven colours.

Luckily, some problems are easier in practice. Three-edge-colouring cubic toroidal graphs is one of those things. To find colourings, we use a Boolean Satisfiability Solver or SAT solver. A SAT problem is a set of statements about a set of boolean variables \([x_1, x_2\ldots]\), such as “\(x_1\) or not \(x_3\) is true”. A solution to a SAT problem is an assignment \(x_i \in {0,1}\) that satisfies all the statements [15]. General purpose, high performance programs for solving SAT problems have been an area of active research for decades [16]. Such programs are useful because, by the Cook-Levin theorem [17,18], any NP problem can be encoded (in polynomial time) as an instance of a SAT problem. This property is what makes SAT one of the subset of NP problems called NP-Complete. It is a relatively standard technique in the computer science community to solve NP problems by first transforming them to SAT instances and then using an off-the-shelf SAT solver. The output of this can then be mapped back to the original problem domain.

Whether graph colouring problems are in NP or P seems to depend delicately on the class of graphs considered, the maximum degree and the number of colours used. It is therefore possible that a polynomial time algorithm may exist for our problem. However, using a SAT solver turns out to be fast enough in practice that it is by no means the rate limiting step for generating and solving instances of the AK model. In appendix A.4 I detail the specifics of how I mapped edge-colouring problems to SAT instances and show a breakdown of where the computational effort is spent, the majority being on matrix diagonalisation.

## Mapping between flux sectors and bond sectors

In the AK model, going from the bond sector to flux sector is done simply from the definition of the fluxes

\[ \phi_i = \prod_{(j,k) \; \in \; \partial \phi_i} i u_{jk}.\]

The reverse, constructing a bond sector \(\{u_{jk}\}\) that corresponds to a particular flux sector \(\{\Phi_i\}\) is not so trivial. The algorithm I used, shown visually in fig. 3 is this:

Fix the gauge by choosing some arbitrary \(u_{jk}\) configuration. In practice, we use \(u_{jk} = +1\). This chooses an arbitrary one of the four topological sectors.

Compute the current flux configuration and how it differs from the target. Consider any plaquette that differs from the target as a defect.

Find any adjacent pairs of defects and flip the \(u_{jk}\) between them. This leaves a set of isolated defects.

Pair the defects up using a greedy algorithm and compute paths along the dual lattice between each pair of plaquettes using the A* pathfinding algorithm [19]. Flipping the corresponding set of bonds transports one flux to the other and annihilates both.

Next Section: Results

# Bibliography

*Koala: Kitaev on Amorphous Lattices*, (2022).

*Amorphous topological insulators constructed from random point sets*, Nature Phys

**14**, 380 (2018).

*Topological Weaire-Thorpe Models of Amorphous Matter*, Proc. Natl. Acad. Sci. U.S.A.

**117**, 30260 (2020).

*Designer Disordered Materials with Large, Complete Photonic Band Gaps*, Proceedings of the National Academy of Sciences

**106**, 20658 (2009).

*The Quickhull Algorithm for Convex Hulls*, ACM Trans. Math. Softw.

**22**, 469 (1996).

*SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python*, Nature Methods

**17**, 3 (2020).

*Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites.*, Journal für die reine und angewandte Mathematik (Crelles Journal)

**1908**, 97 (1908).

*Computing the n-Dimensional Delaunay Tessellation with Application to Voronoi Polytopes**, The Computer Journal

**24**, 167 (1981).

*Every Planar Map Is Four Colorable*, in (1989).

*On an Estimate of the Chromatic Class of a p-Graph*, Discret Analiz

**3**, 25 (1964).

*4-edge-coloring graphs of maximum degree 3 in linear time*, Inf. Process. Lett.

**81**, 191 (2002).

*Remarks on the Colouring of Maps*, in

*Proc. Roy. Soc. Edinburgh*, Vol. 10 (1880), pp. 501–503.

*Efficiently Four-Coloring Planar Graphs*, in

*Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing*(1996), pp. 571–575.

*Map Colouring Theorems*, Quarterly Journal of Mathematics 322 (n.d.).

*Reducibility Among Combinatorial Problems*, in

*Complexity of Computer Computations*, edited by R. E. Miller, J. W. Thatcher, and J. D. Bohlinger (Springer US, Boston, MA, 1972), pp. 85–103.

*A Comprehensive Study and Analysis on SAT-Solvers: Advances, Usages and Achievements*, Artif Intell Rev

**52**, 2575 (2019).

*The Complexity of Theorem-Proving Procedures*, in

*Proceedings of the Third Annual ACM Symposium on Theory of Computing*(Association for Computing Machinery, New York, NY, USA, 1971), pp. 151–158.

*Universal Sequential Search Problems*, Problemy Peredachi Informatsii

**9**, 115 (1973).

*A Formal Basis for the Heuristic Determination of Minimum Cost Paths*, IEEE Transactions on Systems Science and Cybernetics

**4**, 100 (1968).

To see why we sometimes need to tile to \(5\times 5\), consider the left panel of fig. 1. At the boundaries some of the edges emanate out to infinity. In the middle panel we see that tiling to \(3\times 3\) removes the infinite edges emanating from the central cell. This is necessary in order to transform this to a toroidal graph since we do not allow a vertex to be located at the point at infinity. For very small lattices, there can sometimes still be infinite edges emanating from the central cell. This is generally fixed by going to a \(5\times 5\) tiling.↩︎