Analysis of Adjudication of Terminal States for Small Graphs
I like the ‘fixed vertex’ variant of Tangled. I don’t think the freedom to choose your vertex adds anything to the game. So from now on, unless explicitly otherwise stated, all the results I’ll show are for the fixed token placement variant. The vertex placement can be found here for the graphs analyzed in this post.
I’ll go through the results graph by graph, highlighting anything interesting.
Graph 11 — The Ridiculously Small Graph
The Ridiculously Small Graph (RSG) has only 9 unique terminal states (two edges, three possible values per edge). I ran simulated annealing with 1,000,000 samples per problem (yes I know massive overkill), the Schrödinger Equation solver with both 5 and 50 nanosecond anneal times, and hardware-based quantum annealing with 100,000 samples and 5 ns anneal time on the D-Wave Advantage 2.6. The results are shown below. The green vertical dashed lines are the borders between draws (|score| < 0.5) and wins for red (score > 0.5) or blue (score < -0.5). All four agree on Tangled scores for all terminal states.
Graph 2 — The Complete Graph on 3 Vertices
The complete graph on 3 vertices (AKA K₃) has 27 unique terminal states. Using the same solvers and parameters as the previous graph, again they all agree on scores.
Graph 20 — Glued Triangles
The ‘glued triangles’ graph has 135 unique terminal states. Again I see agreement on all scores, but we are starting to see a bit of difference between the two different anneal times for the Schrödinger Equation. This is expected as the faster you sweep the more you excite higher energy levels and there’s an expectation that the resultant samples will give different scores. There are also clumps of simulated annealing solutions around ±4/3 that don’t have corresponding annealing solutions — see the next graph for an explanation of this!
Graph 3 — The Complete Graph on 4 Vertices
The complete graph on 43 vertices (AKA K₄) has 405 unique terminal states. Again I see agreement on all scores.
If I change the y-axis scale, you can see that there are clumps of simulated annealing results at ±4/3 that don’t have corresponding Schrodinger Equation results. This specific clump I discussed in an earlier blog post (“A Very Interesting Type of State”). This is a type of situation where simulated annealing and quantum evolution give different answers for the score. It doesn’t matter here as these states evaluate to ±1 and ±2 for the quantum version, so the score doesn’t change, but the actual numerical values for these terminal states for the score do change.
Graph 19 — The Barbell Graph
The barbell graph has 2,187 unique terminal states. Here is the smallest graph where we start to see disagreement among the solvers — there are 163 states where at least one of the four (simulated annealing, the two Schrödinger solutions with different annealing times, and the hardware-based quantum annealing solutions) disagrees with the others. There are 133 states where the simulated annealing solution disagrees with the 5 ns quantum annealing solution. So 6.1% of the states give a mismatch between simulated and quantum annealing, which is already pretty significant.
Focusing on the area around the draw lines, you can see that the anneal time for the Schrödinger Equation is starting to make a difference, with the quantum annealing results showing the same pattern as the fast anneal Schrödinger solutions.
The Bigger Small Graphs — 18, 12, and 17
For now, I’ll leave these without doing the terminal state analysis as (a) it would eat up my limited QC hardware budget to run them and (b) I think the result for Graph 19 should be sufficient to take the next step here and train agents on both the simulated annealing terminal state evaluations and the hardware-based quantum annealing solutions and see what I’m looking for (a performance difference between these).