PYTHON · NUMPY

Every spin at once

A frustrated triangle needs three colours, so a coloured sweep changes about a third of a spin per tick. Pin an all-at-once update just hard enough that its law is within one percent of the Boltzmann law. How many spins does it change per tick?

Price a parallel update rule at the accuracy it is used at, and decide when updating every spin on one clock edge is a speed-up over updating one colour class at a time.

01Challenge

An annealing chip updates all of its spins on every clock edge, where a fabric that colours its graph spends one edge per colour class. Make the all-at-once rule accurate enough to trust as a sampler, then decide whether its parallelism survives.

Predict firstA frustrated triangle needs three colours, so a coloured sweep changes about a third of a spin per tick. Pin an all-at-once update just hard enough that its law is within one percent of the Boltzmann law. How many spins does it change per tick?

02Model

Two Japanese annealing chips, STATICA and its successor Amorphica, can update every spin on the same clock edge, and that is the headline: no colouring and no waiting. Lesson 10 showed that the schedule is part of the model, because changing which spins move on which tick changes the law the fabric settles into. Resampling every spin at once from the previous state is the extreme case, and it samples a law of its own. Stochastic cellular automata repair it with two changes. Each spin sees half of its field, and each spin is pulled toward the value it already holds, with a strength called the pinning. The law that results has a closed form, and as the pinning grows it approaches the Boltzmann law. How it approaches is the whole story. Divide the automaton's weight by the Boltzmann weight and what remains is a product with one factor per spin, each of the form one plus e to the minus twice the pinning. So the distance from Boltzmann falls as e to the minus twice the pinning, and to bring it down to some small distance the pinning has to suppress every flip by about that same factor. The parallelism is paid for in stillness. A coloured sweep pays nothing of the kind: it is exact at any speed and costs one tick per colour class. Measured exactly on ten-spin graphs, cost counted as ticks per independent sample, updating every spin at once wins at a distance of ten percent on fully connected graphs and on cold sparse ones, and loses by four to twenty-nine times at one percent and by forty-three to two hundred and ninety-four times at a tenth of a percent. The chips were built to find ground states, where a rough law can serve. The price appears when the same machine is asked to sample.

03Guided practice

Write the automaton's law in closed form, check it against the kernel's own stationary law, then find the pinning that brings it within one percent of Boltzmann and count how many spins it changes per tick there.

04Feedback

PASS WHEN You priced a parallel rule at the accuracy it is used at. Updating every spin at once moves more spins than the coloured sweep only while its answer is wrong by several percent; below that, the pinning that makes it right is the pinning that holds it still.

If your run fails, check:

The closed form is exp(BETA/2 times the sum of H[i] s[i]) times one 2 cosh per spin, whose argument is half the spin's field plus the pinning times the spin's own value.
If the control fails even at q = 0, check the factor of one half: the automaton sees half of each field, in the exponent's first term and inside every cosh.
If the control passes and the table looks wrong, the distance must be measured against boltzmann(), not against the automaton's own law.

05Retrieve & space

Updating every spin from the previous state samples a different law; stochastic cellular automata repair it by halving each field and pinning each spin toward its own value.
The automaton's distance from the Boltzmann law falls as e to the minus twice the pinning, so reaching a small distance needs a pinning of about half the logarithm of a constant over that distance.
At that pinning every flip is suppressed by about the target distance, so each tenfold gain in accuracy costs about tenfold in motion.
A coloured sweep is exact at any speed and pays one tick per colour class; it pays nothing for accuracy.
Updating every spin at once wins at coarse accuracy where colouring is expensive, on fully connected or cold graphs, and loses at one percent on every graph measured.

06Mastery & project

Given a parallel sampling rule and the accuracy an application needs, state the setting at which the rule's speed must be measured, and name the comparison that decides whether its parallelism is a speed-up.

Take a hardware update rule that trades accuracy for parallelism, find the setting at which its law reaches the accuracy your application needs, and report its ticks per independent sample there against a coloured sweep on the same graph.

← The ceiling on a body Conditioning bandwidth, and what is still open →

PYTHON · NUMPY

Every spin at once

Three p-bits in a triangle, updated all at once with a pinning you choose. One closed form decides everything the lesson measures.

You read

the arrays and values already in scope

You change

the code you write in each cell

Fixed

the dataset and the checks that grade you