The Computational Cost of Using the Schrodinger Equation to Adjudicate Terminal States in Tangled

For an M-player Tangled game with N vertices and E edges, the upper bound on the number of terminal states is 2 * (N choose M) * 3ᴱ, exponential in the number of edges.

For anything but tiny graphs, adjudicating all the terminal states and storing the results in a lookup table becomes intractable. For example, the Tesseract graph has 16 vertices and 32 edges. For a two-player game, this gives something like 4x10¹⁷ terminal states. Even taking into account symmetries, the number is too large to use tabular methods. And this is still a tiny graph on the scale of where we are headed!

This is bad… but there’s another exponential cost lurking in Tangled. Evaluating who won from each terminal state requires solving the Schrodinger equation with N qubits, giving O(2ᴺ) scaling in both required memory and compute time — each vertex added doubles the required memory and compute time.

To get a feeling for what these costs are for real graphs, I timed how long it takes to evaluate a terminal state by integrating the Schrodinger equation for some tiny graphs with increasing vertex counts.

I considered the following six graphs:

From left to right: Graph 1, two vertices, 1 edge; graph 2, 3 vertices, 3 edges; graph 3, 4 vertices, 6 edges; graph 4, 6 vertices, 6 edges; graph 5 (Petersen graph), 10 vertices, 15 edges; and finally graph 6, the Tesseract graph, 16 vertices, 32 edges.

Here are the resultant runtimes for evaluating one terminal state for each of them. I couldn’t run graph 6 on my computer as it required more memory than I had (32GB), and it would have taken a long time anyway!

Runtimes for evaluating one terminal state for the graphs above.

Same data in graph form, with an exponential trend line overlaid.

Just to know who won a single Tangled game on a 16-vertex graph would take (at least using my current set-up) around a day of compute — that is, if I added some RAM so that the problem would fit in memory!

The much smaller 10-vertex graph takes about seven minutes to evaluate a single game. Of course, my code isn’t the best you can do, but the point is that no matter how optimized you make it, simulating the evolution of a quantum system is hard — as far as we know (this is the basis of the whole distinction between quantum and classical computers) you can’t get rid of that pesky exponential!

Note for experts: the annealing process is chosen to be fast enough to be in the middle ground between adiabatic and diabatic transition. This ‘fast anneal’ process means that the system’s evolution is coherent and (I think?) the full quantum evolution needs to be taken into account. There are more advanced classical techniques for calculating who won from a Tangled terminal state, such as Density Matrix Renormalization Group (DMRG), but even the best most optimized of these currently tops out at simulating about 60 qubits. For Tangled, we can play on arbitrary graphs and so can push far beyond those limits.