open-standards/wai/quantum-conformance/landscape

Energy-landscape jobs: conformance and results

For the extension quantum-landscape. Reference: wai_quantum::quantum_landscape and wai-quantum landscape. Everything here is the output of a command named below, on the code at the commit that holds it. Every count is deterministic: the same command gives the same bytes on any machine. Wall-clock time is not, and it is kept apart.

file	what	made by
vectors.json	the conformance set a member is held to, §7 of the extension	wai-quantum landscape vectors
table.json, table.md	the scale table, below	wai-quantum landscape table --out DIR
timing.json	that table's wall-clock seconds a run, on one machine	the same command
trial-assignment.json	a trial outside the job form, below	wai-quantum landscape trial-assignment
native-wasm.txt	the browser build against the command line	wai-web/demo/verify_landscape_wasm.mjs, verify_landscape_page.mjs
stated-result.md, reproduce.sh	a stated result, and the script that checks it

These are classical runs on a classical emulator, and nothing in them is a quantum effect.

The worked examples

Fourteen programs, in wai-quantum/src/quantum_landscape/programs/. At seeds 1 to 20 each one marked as working is solved every time, and each one marked as failing fails every time, for its stated reason (job::tests).

example	variables	what it shows	result
talks	12	three states: room A, room B or left out	lowest energy −10, reached at all 1,000 seeds tried
clusters	8	signed clustering with a quarrel no split can settle	lowest energy −1, reached
selection	14	six of fourteen that belong together	lowest energy −9, and the planted six
chain	8	the deterministic mode with one end held	settles to the one lowest arrangement
assign-2x2	4	assignment written as sums, 2×2	both lowest states are assignments
blocks	64	eight blocks of eight: too many arrangements to check	the planted pattern, with 200 sweeps a start
assign-3x3	9	the same construction, 3×3	fails: 21 lowest states, only 6 of them assignments
colour-six	6	three colours, six regions	fails: none of the 6 lowest states is a colouring
colour-four	4	three colours, four regions	fails: neither of the 2 lowest states is a colouring
piles	8	two equal piles	fails: quantising to signs loses the sizes, and the answer has energy −7 on the weights as declared, against −130
cold-constraint	4	2×2 assignment at temperature 0	fails: never rests, flipping between two states
cold-start	12	the talks at temperature 0, from all 0	misses: stays at 0, energy 0 against −10
too-costly	14	the six of fourteen at too high a cost	fails: leaving everything out is the one lowest state
typo	3	a misspelt statement	refused: Line 6: opposis not a statement epuML knows. Did you meanoppose?

Where the truth exists and a program has its own check, every lowest arrangement is graded against it. That is how assign-3x3 fails even when a run's answer happens to be an assignment: the landscape does not express the problem.

Native and WebAssembly

wai-web/demo/verify_landscape_wasm.mjs sends the same request to wai-quantum landscape call and to the browser build, and compares the bytes: every example at its own temperature, at 0, at 0.5 and at a temperature given as text, a replay of 2,000 seeds each, whole answers for 11 seeds, a sweep and a comparison. 700 answers the same bytes, 0 different, 104,000 seeded runs. In Chrome, verify_landscape_page.mjs repeats the replays in the browser's own engine: 84 of 84 answers the same bytes, 19,500 seeded runs (native-wasm.txt). The command line gives the same bytes on x86-64 Linux, arm64 Linux and arm64 macOS (stated-result.md).

Two pinned digests hold this in the repository's checks. job::tests::every_platform_gives_the_same_bits covers every worked example at three temperatures over 20 seeds, on Linux x86-64 and arm64, macOS arm64 and wasm32-wasip2 under wasmtime, in debug and release builds. landscape_jobs_are_the_native_bits_in_wasm runs the browser build's own, over 3 seeds, in wai-web-wasm.yml.

The scale table

Four families, 8 to 128 variables (dense to 64), 5 instances each, 20 runs an instance and method, at 8 starts of 40 sweeps and of 320. Every method in a row has the budget of the sampling mode's run, where one operation is one coupling read, one cell updated or one move considered, whoever does it. The target is the exact lowest energy up to 16 variables, then a planted answer, or the best that long runs of simulated annealing and tabu search found, which proves nothing.

Who reached the target more often, row by row, against the best of the three classical methods:

the sampling mode	ahead	tied	behind	of
at the default start	2	45	21	68
at the hot start, the largest row of couplings	0	38	30	68

Simulated annealing is the strongest method here: it is the best of the three, or level with the best, in 64 of the 68 rows, and it is ahead of the default start in 20 where the default start is ahead of it in 2. The two rows where the sampling mode is ahead of all three are ahead by one run of a hundred (clusters at 64 variables and 320 sweeps, sparse-glass at 32 and 40), which chance gives. Simulated annealing leads where it matters, at the larger sizes. At the default budget, at the largest size of each family:

family	variables	default start	hot start	deterministic	simulated annealing	tabu search	greedy descent
clusters	128	46 of 100	0	0	79	7	0
sparse-glass	128	36	0	0	71	5	0
dense-glass	64	81	4	0	97	54	91
selection	128	100	100	100	100	100	100

The deterministic mode, at temperature 0 from random starts, is far behind on all but the selection family, which is easy for everyone.

timing.json has wall-clock seconds a run on one shared machine. They depend on how each method here is written, and say nothing about a device, so they are not a result.

What the table does not say. The operation count says nothing about what an operation costs in hardware, or about running cells side by side, which a machine would do and these methods do not.

The starting temperature

A solve with no t0 starts at the square root of the mean couplings a variable has, and at least 1. On instance 99 of three families at 32 and 64 variables, which the table's rows do not use, 40 runs at each start:

held-out instance	lowest found	default start: runs at the lowest	hot start: runs at the lowest	start 1: runs at the lowest
clusters, 32	−16	2: 40 of 40	9: 28	40
clusters, 64	−26	2: 28	8: 1	40
sparse-glass, 32	−19	2.449: 33	13: 15	38
sparse-glass, 64	−51	2.449: 40	12: 4	40
dense-glass, 32	−128	5.568: 39	31: 23	39
dense-glass, 64	−362	7.937: 38	63: 0	40

The hot start, the largest row of couplings, is far too hot at 64 variables, and worse at every size here. The default was chosen with this section in view, and it is not the best start: a start of 1 does at least as well on all six, better on three of them (by 2 to 12 runs of 40), and on clusters at 64 by a wide margin. It stays where it is because it depends on the instance, and a fixed start of 1 would be too cold for a landscape of larger fields. No instance here shows that; it is a judgement. wai-quantum landscape sweep tries the temperatures on a program of your own.

Assignment with a {0, +1} domain

wai-quantum landscape trial-assignment, outside the job form: the same assignment landscape, with each cell limited to 0 or +1. 40 runs a size, 8 starts of 60 sweeps.

grid	lowest states (assignments among them)	three states	{0, +1}
2×2	2 (2)	40 of 40	40 of 40
3×3	21 (6)	15	40
4×4	1,344 (24)	1	40
5×5	too many to check	0	40
6×6		0	40
8×8		0	40

So a {0, +1} domain fixes feasibility: the lowest states become exactly the assignments. It does not fix costs. With costs of 0 or 1 a cell, on 80 random instances, it found the cheapest assignment every time the cheapest cost 0, and never found a valid assignment when the cheapest cost more: the couplings are fixed at 1, so the constraint's weight is 1, and a cost of 1 ties with leaving a row empty. Costed assignment would need couplings above 1 or fractional fields, and this model has neither. The domain itself is a change to the cell, so it is a trial and not a kernel.

The joule line

On the twelve talks: 13,440 accumulates × about 0.41 pJ = about 5.5 nJ, priced. The same run's 320 sweeps need at least 320 clocks on that board, which draws about 3.1 W whatever it does: about 9.9 µJ of board power the priced line leaves out. A run's joules are not measured here, because no meter is attached to a run here.

A member's conformance

A member is held to vectors.json as §7 of the extension says, and the host finds its parity by running its kernels there: settle bit for bit for a bit-exact settle kernel, every vector it takes, and it takes every vector whose field bound is at most 2³¹ − 1; chains bit for bit for a bit-exact sampling kernel, the same way; otherwise the statistical battery, thirteen workloads of 20,000 chains each, each block's final states against its exact distribution. wai-quantum/tests/landscape_conformance.rs reads the file as a member's checker would, from the file alone, and holds both parts to kernels that are wrong in one way each. The vectors refuse a dropped carry in a 32 by 32 product, a cut point compared by its high word, fields held in 16 or 32 bits, a check of the fields that forgets the couplings, cells last to first, a draw counter that starts again at each of a device's windows of sweeps, a run that stops after one window, chains past the first 64 left alone, a settle whose cells past 64 or 256 never move or that reports its end a sweep late, and a member that declines below the line. The battery passes the reference's own kernel, one that colours its cells properly and one that takes its cells last to first, and refuses kernels that move cells all at once, even then odd, ignore the schedule or keep only its end, clamp the table at 5, sample the last sweep, hold their fields in 16 or 32 bits, or leave cells from the fifth on where they started.