Adjudicating Tangled Terminal States on Tiny Graphs With Three Different Approaches

Tangled is based on the assumption that quantum supremacy can be achieved by sampling the output distributions of a D-Wave quantum computer after a quantum quench. This claim depends on us not being able to effectively spoof this output using some other approach.

I’ve been using three different approaches so far to adjudicate Tangled terminal states. Here I’ll describe what they are, and compare their results on the teeny tiny three- and four-vertex graphs!

Approach #1

The thing I started with is a numerical Schrodinger Equation solver. This approach only works for tiny game graphs as the compute time grows exponentially with vertex count, so will not be an option as the graphs get bigger. I won’t describe this one too much as it’s pretty basic and it’s not relevant to anything of the size we are ultimately after. I’ll include results from its use for the tiny graphs just to double check agreement but post that we won’t be able to use it! If you want to, you could code this up yourself, it’s not that hard, it’s just solving the Schrodinger Equation numerically by integrating forward in time.

Approach #2

My main debugging workhorse right now is a specially tuned simulated thermal annealing (SA) variant run on the classical s=1 limit of the Hamiltonian

SA is a heuristic algorithm for first generating an approximation to a low-temperature Boltzmann distribution (over the states whose energies are given by the above expression) and then drawing samples from it. The Boltzmann distribution here could be ‘similar enough’ to the probability distribution after the quantum quench to get most/all the terminal state adjudications right — we’re about to check this!

The variant I’m using is based on the D-Wave simulated annealing code with a specific choice of annealing schedule that they came up with that is supposed to reproduce the hardware distribution as closely as possible. I’ve been using it pretty extensively.

Investigating the performance of this approach carefully is important as the D-Wave quantum supremacy claim requires this (and any other classical approach!) to fail for large graphs. I think it will, but if it does, we need to measure this and explain why it’s failing.

Approach #3

The ground truth for Tangled terminal state adjudication, the mighty D-Wave Advantage2.4 system, using the multiple embedding approach I described in my previous post. Note that there’s another thing that I think will improve the results from the hardware, which is a function they call SpinReversalTransformComposite, but in my case it’s not working — I think there is a bug in the code somewhere — hopefully the D-Wave folks can find and fix it soon! What this thing does is average over a specific kind of noise that is present in these kinds of processors, and I see evidence from my early runs that the specific noise this thing removes is present.

We’ve got three different approaches locked and loaded to evaluate Tangled terminal states. Let’s see how they do!

Evaluating Tangled Scores for All 162 Terminal States for The Three Vertex Graph

I adjudicated all 162 terminal states of the three-vertex graph using the three different approaches I listed above. For the SA algorithm, I drew a huge number (N=10,000,000) of samples per problem (why not, it’s cheap). The width of the distribution around each answer is proportional to the square root of N, so with a huge N like this we’re pretty sure we are getting something close to the true mean of the distributions around each problem.

For the D-Wave Advantage2.4 quantum computer, I embedded each 3-variable problem in 346 parallel places on each chip and gathered N=1,000 samples from each run, giving a total of 346,000 samples per problem. This is quite a bit fewer than the SA run, but that was overkill anyway!

Here’s the results for the scores for all 162 problems. I’m displaying this as a stacked histogram using 200 bins to cover the entire range of possible scores -2<R<+2. You can see good agreement for the computed scores for all states for all three methods. The green dashed lines are the borders that distinguish draws from wins, and you can see none of the methods return scores that are close to these borders, so all three agree on the adjudications of all of the states.

I suspect that the reason there’s some deviation for the quantum annealing results (say around zero and ± 1) is noise on the individual bias terms (these are supposed to be zero for Tangled, but if a vertex is not connected to any others, even a small non-zero bias will get amplified), which would be averaged over with the SpinReversalTransformComposite thing. As soon as they fix whatever the bug is there I’ll re-run and see if I’m right!

I ran all three solver methods to adjudicate all 162 terminal states for the three-vertex graph. This is a stacked histogram with the results using 200 bins. Also included are green dotted lines denoting the border between wins and draws (anything in between the green lines is a draw). You can see that all solvers agree on win/loss/draw for all terminal states.

What Terminal States Are Near ±2/3?

I looked at which states were the ones scoring ±2/3 — these are the states nearest the draw line. The two unique states giving scores of + 2/3 and -2/3 respectively are [0, 1, 2, 2, 3, 2] and [0, 1, 2, 3, 2, 2].

I worked out the energies, correlations and influence scores for the top graph (state [0, 1, 2, 2, 3, 2]) (bottom one is similar but correlation between 0 and 1 is negative, correlation between 0 and 2 and 1 and 2 are positive, and influence is zero except for site 2 where it's positive).

Evaluating Tangled Scores for All 8748 Terminal States for The Four Vertex Graph

I adjudicated all 8748 terminal states of the four-vertex graph using the same three approaches. Here’s what I got.

Same as the previous graph, except for all 8748 terminal states for the four-vertex graph. As before, all three agree on all adjudications. This used 400 bins to cover the entire score range -4<R<+4.

Here’s a close-up of the scores near the ±2/3 area. You can see that the quantum annealing ones are kind of spreading out vs the more tightly scored responses from the other two solvers. I am pretty sure this is due to small bias errors in disconnected variables.

Closer view of the scores near the draw line. Also 400 bins but on a smaller range -1<R<+1.

What Terminal States Are Near ±2/3?

I looked at which states were the ones creeping up to the draw line. They are the same kind of thing as before; namely these eight states (just showing the unique ones, the total number is 8*12 counting the symmetries):

Same kind of deal -- the frustrated states give a bunch of degenerate ground states which adds up to the scores near ±2/3.

All of these problems have disconnected variables that will be susceptible to bias noise. I suspect that the QC results will be cleaner and match the other solvers better for these cases once I get the SpinTransformComposite thing working, because all of these have ‘floating bits’ that aren’t connected to anything and these will be vulnerable to noise on the h terms.

Summary of Results

I adjudicated all Tangled terminal states for both three- and four-vertex complete game board graphs using three different approaches — a numerical Schrodinger Equation solver, a specially tuned simulated annealing approach run on the s=1 Hamiltonian, and a D-Wave Advantage2.4 system using multiple embeddings. I found 100% agreement between all three for all terminal states for both graphs. There was excellent agreement in detail between the three, with some noise arising in the case of the quantum annealer from what I suspect is single variable bias noise, which is particularly dangerous for vertices that are not coupled to any other vertices. I was unable to easily remote this noise source as the function that is supposed to do it was not working together with my multiple embedding scheme.

Here are files that contain the adjudication results, which can be used as ground truth for Tangled on these two graphs (all three methods agree on all states!).

They are pickle files of python dictionaries with the terminal state as a string as key, and value the adjudication as a string (one of ‘red’, ‘blue’ or ‘draw’).

Here’s the three vertex and the four vertex complete graph adjudications!