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

Figure 1: (Left) Lattice construction begins with the Voronoi partition of the plane with respect to a set of seed points (black points) sampled uniformly from \mathbb{R}^2. (Center) However, we want the Voronoi partition of the torus, so we tile the seed points into a three by three grid. The boundaries of each tile are shown in light grey. (Right) Finally, we identify edges corresponding to each other across the boundaries to produce a graph on the torus. — Figure 1: (Left) Lattice construction begins with the Voronoi partition of the plane with respect to a set of seed points (black points) sampled uniformly from $\mathbb{R}^2$. (Center) However, we want the Voronoi partition of the torus, so we tile the seed points into a three by three grid. The boundaries of each tile are shown in light grey. (Right) Finally, we identify edges corresponding to each other across the boundaries to produce a graph on the torus.

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] ¹ 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

Figure 2: Different valid three-edge-colourings of an amorphous lattice. Colors that differ from the leftmost panel are highlighted in the other panels.

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

$Figure 3: (Left) The ground state flux sector and bond sector for an amorphous lattice. Bond arrows indicate the direction in which u_{jk} = +1. Plaquettes are coloured blue when \hat{\phi}_i = -1 (-i) for even/odd plaquettes and orange when \hat{\phi}_i = +1 (+i) for even/odd plaquettes. (Centre) To transform this to the target flux sector (all +1/+i), we first flip any u_{jk} that are between two fluxes. This leaves a set of isolated fluxes that must be annihilated. Then, these are paired up as indicated by the black lines. (Right) A* search is used to find paths (coloured plaquettes) on the dual lattice between each pair of fluxes and the corresponding u_{jk} (shown in black) are flipped. One flux will remain because the starting and target flux sectors differed by an odd number of fluxes.$

Figure 3: (Left) The ground state flux sector and bond sector for an amorphous lattice. Bond arrows indicate the direction in which $u_{jk} = +1$. Plaquettes are coloured blue when $\hat{\phi}_i = -1$ ($-i$) for even/odd plaquettes and orange when $\hat{\phi}_i = +1$ ($+i$) for even/odd plaquettes. (Centre) To transform this to the target flux sector (all $+1$/$+i$), we first flip any $u_{jk}$ that are between two fluxes. This leaves a set of isolated fluxes that must be annihilated. Then, these are paired up as indicated by the black lines. (Right) A* search is used to find paths (coloured plaquettes) on the dual lattice between each pair of fluxes and the corresponding $u_{jk}$ (shown in black) are flipped. One flux will remain because the starting and target flux sectors differed by an odd number of fluxes.

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

[1]

T. Hodson, P. D’Ornellas, and G. Cassella, Koala: Kitaev on Amorphous Lattices, (2022).

[2]

N. P. Mitchell, L. M. Nash, D. Hexner, A. M. Turner, and W. T. M. Irvine, Amorphous topological insulators constructed from random point sets, Nature Phys 14, 380 (2018).

[3]

Q. Marsal, D. Varjas, and A. G. Grushin, Topological Weaire-Thorpe Models of Amorphous Matter, Proc. Natl. Acad. Sci. U.S.A. 117, 30260 (2020).

[4]

M. Florescu, S. Torquato, and P. J. Steinhardt, Designer Disordered Materials with Large, Complete Photonic Band Gaps, Proceedings of the National Academy of Sciences 106, 20658 (2009).

[5]

C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, The Quickhull Algorithm for Convex Hulls, ACM Trans. Math. Softw. 22, 469 (1996).

[6]

P. Virtanen et al., SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python, Nature Methods 17, 3 (2020).

[7]

G. Voronoi, 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).

[8]

D. F. Watson, Computing the n-Dimensional Delaunay Tessellation with Application to Voronoi Polytopes*, The Computer Journal 24, 167 (1981).

[9]

K. Appel and W. Haken, Every Planar Map Is Four Colorable, in (1989).

[10]

V. V. G, On an Estimate of the Chromatic Class of a p-Graph, Discret Analiz 3, 25 (1964).

[11]

S. Skulrattanakulchai, 4-edge-coloring graphs of maximum degree 3 in linear time, Inf. Process. Lett. 81, 191 (2002).

[12]

P. G. Tait, Remarks on the Colouring of Maps, in Proc. Roy. Soc. Edinburgh, Vol. 10 (1880), pp. 501–503.

[13]

N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas, Efficiently Four-Coloring Planar Graphs, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (1996), pp. 571–575.

[14]

P. J. Heawood, Map Colouring Theorems, Quarterly Journal of Mathematics 322 (n.d.).

[15]

R. M. Karp, 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.

[16]

S. Alouneh, S. Abed, M. H. Al Shayeji, and R. Mesleh, A Comprehensive Study and Analysis on SAT-Solvers: Advances, Usages and Achievements, Artif Intell Rev 52, 2575 (2019).

[17]

S. A. Cook, 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.

[18]

L. A. Levin, Universal Sequential Search Problems, Problemy Peredachi Informatsii 9, 115 (1973).

[19]

P. E. Hart, N. J. Nilsson, and B. Raphael, 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.↩︎