open-standards/wai/wai-quantum/docs/landscape.md

Energy-landscape jobs

A job of this kind gives no circuit. It states an energy over variables of three states, and asks for a state of low energy:

E(s) = − Σ_{i<j} W_ij s_i s_j − Σ_i b_i s_i + c · Σ_i |s_i|,    s_i ∈ {−1, 0, +1}

The couplings are −1, 0 or +1, the fields and the cost are whole numbers, and the state 0 is "left out", at its own price. A machine that takes such a job settles: each cell adds up the pull of the cells it is coupled to and moves to the state that pull favours, with or without randomness, until the whole comes to rest. wai-quantum landscape is that settling model in software, so that a job, its answer and what the answer costs can be read, run and checked on any machine.

It is a classical emulation. Its cells are three-state values sampled with classical random draws, and nothing in it is a quantum effect. Every answer says so.

The job form, the answer and the seam a GPU or an FPGA board runs behind are the extension quantum-landscape. The results, and the script that checks them, are in quantum-conformance/landscape.

A program

A program is text in epuML: one statement a line, with vars first and the line that says how to run last.

cat > three.epuml <<'PROGRAM'
# Three people, one quarrel: 0 and 1 want opposite teams, 1 and 2 the same.
vars 3
cost 1
oppose 0 1
agree 1 2
solve
PROGRAM
wai-quantum landscape run three.epuml --demo-key                  # the answer, its energy, every arrangement checked, the work, the priced joules
wai-quantum landscape run three.epuml --seed 7 --temperature 0.5 --demo-key
wai-quantum landscape run three.epuml --temperature 0 --demo-key  # the deterministic mode, from random starts
wai-quantum landscape run three.epuml --demo-key --json > job.json
wai-quantum verify job.json
echo 'vars 2
oppos 0 1
solve' > typo.epuml
wai-quantum landscape run typo.epuml --demo-key                   # exits 1

The last run is refused: Line 2: opposis not a statement epuML knows. Did you meanoppose?. A job that ran exits 0 whatever its verdict, and a program that cannot run exits 1 with that one sentence.

The statements are vars, agree, oppose, couple, weight, pin, lean, field and cost, then minimize [steps=S] or solve [t0=T] [restarts=R] [steps=S]. minimize is temperature 0 from every variable at 0, and stops when the state comes to rest. solve runs from random starts, cooling to 0, and keeps the lowest energy found. Lines beginning #! are comments to the language that say what a program means and how to check an answer against the problem it was written for: an answer can reach the lowest energy and still not solve the problem.

What an answer holds

• The label: what kind of run this is, word for word.
• What ran it: the member's id, its class, the kernel, and how far that kernel is held to the reference.
• The state and its energy. The energy is worked out from the program, not taken from the member, and it is exact.
• The truth, up to 16 variables: every arrangement checked, the lowest energy, how many hold it, and, where the program has a check, how many of those pass it.
• The verdict: solved, missed, failed or unchecked, with a sentence.
• The work: sweeps, accumulates (one read of one coupling into one cell's field), cell updates and random draws.
• The joules, priced: below.
• The replay digest. The same program, seed and temperature give the same digest on any machine.

The examples that fail

wai-quantum landscape examples                       # each with what it is there to show
wai-quantum landscape run --example assign-3x3 --demo-key
wai-quantum landscape run --example colour-four --demo-key
wai-quantum landscape run --example piles --demo-key
wai-quantum landscape run --example cold-constraint --demo-key

Six of the fourteen examples work. Eight do not, on purpose, because they show what this model cannot do. Three interchangeable options are not three states: the state 0 is "left out", so colouring a map fails. Sizes are not kept: a coupling is a sign, so two equal piles fail. Assignment written as sums works for a 2×2 grid and not for a 3×3, where 21 arrangements share the lowest energy and only 6 are assignments. A constraint at temperature 0 flips between two states and never rests. Too high a cost makes leaving everything out the lowest state. A typing mistake is refused.

A failure is reported as one, and a landscape that does not express its problem fails even when a run's answer happens to pass the check, because every lowest arrangement is graded.

The temperature

A solve with no t0 starts at the square root of the mean couplings a variable has, and at least 1. Each answer's mode_words says so.

wai-quantum landscape sweep --example talks --seeds 5 --demo-key    # the same program at each temperature, with the same budget
wai-quantum landscape sweep --example talks --seeds 5 --temperatures 0,0.5,2 --demo-key

That default is a choice with data behind it. On held-out instances, a start at the largest row of couplings is far too hot. It is not the best start on every family, and the table's start_temperature shows where it is beaten.

Classical methods on the same instance

wai-quantum landscape compare --example talks --seeds 5 --demo-key
wai-quantum landscape instance clusters 64 0 > clusters-64.epuml    # any instance of the table, as a program
wai-quantum landscape compare clusters-64.epuml --seeds 2 --demo-key
wai-quantum landscape table --quick --out quick > /dev/null         # the published table's form, small; the whole table without --quick

compare runs the emulator and simulated annealing, tabu search and greedy descent on the same three-state energy, each with the same budget of operations a run. One operation is one coupling read, one cell updated or one move considered, whoever does it. The table is published as it comes out: simulated annealing leads on the larger instances of it (the results).

The operation count is not a machine's time, and it says nothing of cells that settle side by side.

The joules

A run here is not metered. Its line is its count of accumulates, multiplied by a rate measured elsewhere, with the rate's source named beside it:

	pJ per accumulate	from
temperature 0	about 0.16	one FPGA board, a dense 64-cell test design at 100 MHz, the slope of power against clock speed
above temperature 0	about 0.41	the same board: about 0.25 more, from paired readings at one temperature, 0.25, on a design that updates all its cells at once
for scale	about 0.03	a published 2014 figure for one 8-bit integer add in 45 nm logic: a reference point, not a model of any processor, with no term for sampling

So the figure says what the work would come to on that board, and nothing of what the machine that ran the job spent. Both board rates are differences that cancel the board's own draw of about 3.1 W, so a small job prices low, and every answer says by how much. These are the numbers of one board and one meter. In the terms of energy-measurement the figure's class is ModelBased and the published add's Estimator.

A member with a meter puts its reading beside the priced figures, under joules.metered.

From code

use wai_quantum::quantum_landscape::job::run_text;

fn main() {
    let answer = run_text("vars 2\noppose 0 1\nsolve\n", 7).unwrap();
    println!("{} at energy {}: {}", answer["state"], answer["energy"], answer["summary"]);
}

The module is wai_quantum::quantum_landscape, behind the feature quantum_landscape, which needs no dependency beyond the crate's own, so it runs everywhere the engine does. quantum_engine and full both turn it on, and wai re-exports it. job::call takes the job form's JSON request, and applies every limit of the extension before anything runs.

In a page, the browser build answers the same request: QuantumEngine.landscape(op, request) seals the answer with the page's key, and QuantumEngine.landscape_answer(op, request) gives the bytes without a seal. wai-web/demo/landscape.html is the page.

On a GPU

The kernels run on a GPU too, as members the host certifies and checks like any other:

feature	member	lanes	parity it can earn
quantum_landscape_webgpu	quantum_landscape::webgpu: Metal, Vulkan or DX12 through WebGPU	32-bit: it declares a field bound of 2³¹ − 1, cells and couplings within a 32nd of a storage binding, and 4,194,304 entries of cut points a sweep	bit-exact for both kernels within that capacity; its coloured kernel, a colour class of cells at once, statistical at most
quantum_landscape_cuda	quantum_landscape::cuda: an NVIDIA GPU, compiled at run time	64-bit fields; it declares 4,194,304 entries of cut points a sweep, which no job reaches	bit-exact for both kernels within that capacity
quantum_landscape_metal	quantum_landscape::metal: an Apple GPU, macOS	64-bit fields; it declares 4,194,304 entries of cut points a sweep, which no job reaches	bit-exact for both kernels within that capacity

A parity in this table is what a member can earn, not what any one device has: the host finds it on each device, every time it certifies one, within the capacity the member declares and at that capacity's edges, and states both in every answer.

The settle kernel runs one thread a cell and one dispatch a sweep. The sampling kernel runs one thread a chain, its cells in the reference's order, with the reference's draws and the cut points the host works out for the fields the cells can reach (at most 4P + n a sweep, counted in the job's operations and memory): so its bits are the reference's, and many chains run side by side, the starts of a run and the seeds of a sweep, a comparison or a replay. A member runs a window of sweeps a dispatch and waits for each before it sends the next.

A workload's field bound is the largest field any state can give a cell, max_i (|b_i| + deg_i). Each member declares its capacity (Member::capacity) and the host runs it on nothing past it. Placing a job, the host passes over a member whose kernel for the job is not certified, one whose capacity the workload does not fit, and one that fails the job or whose answer its checks refuse, and names each under refusals; offered last, the reference answers what the others did not.

use wai_quantum::quantum_landscape::{job, member, webgpu, MAX_JOB_BYTES};
use serde_json::json;

let gpu = webgpu::discover().into_iter().find_map(Result::ok).expect("a GPU");
let placed = [member::certify(&gpu).unwrap(), member::Certified::reference()];
let answer = job::call_placed(&placed, "run", &json!({ "program": "vars 2\noppose 0 1\nsolve\n" }), MAX_JOB_BYTES).unwrap();
// answer["member"] names what ran the job and the parity the host found for the kernel it used;
// answer["refusals"], if any, names each member passed over, with why.

A member can carry a meter: with_meter takes the engine's run meter, and wai::sink_meter::RunCounter makes one of a machine's own on-chip counter: the graphics rail through IOReport on macOS, and the board through NVML on Linux once NVML has shown itself plausible (RunCounter::nvml). It reads the counter through each call and gives a figure only from a window in which the counter was live and which lasted the profile's minimum, labelled OnChipCounter with the uncertainty the operator declares and the meter's own terms beside it. The figure is the whole rail or board over the call's window: the run's work, the device's idle draw and any other work on the device then. No share is attributed to the run, and the answer says so: joules.metered.scope states it, and the label says a reading is there, and what it covers, only in an answer that has one. Over a run of several calls the figures and the windows are added up. A reading stands for a run only where every call carried that run alone; elsewhere metered is null.

A member of your own

A member is what runs the kernels: the trait quantum_landscape::member::Member. The reader, the truth, the energy, the checks, the verdict, the replay digest and the seal stay on the host, and do not trust it: the host checks every answer a member returns, and finds its parity by running its kernels on the conformance set (member::certify). A member says nothing of its own parity. The extension states what a member takes and returns, what the host checks, and what each parity takes.

A member declares what its kernels hold, once, as fixed numbers (member::Member::capacity, a capacity::Capacity): its cells and couplings; on each side of temperature 0, its largest field, field bound and cost; above 0, how many cut points a sweep it holds or how wide a span of uncertain fields; how many sweeps a run; and how many chains a call, which is a batch and not a limit: the host splits a job, and certification every vector, into calls of that many. The host declines for it exactly the jobs past those numbers (Capacity::admits, a function of the job and the numbers alone). It certifies it on every vector and battery workload within them, and on vectors it generates from them by rule (Capacity::generate): every cell count at and beside a power of two, every call size to 32 chains and each band of a wavefront, the longest row, fields at each lane's wrap points, a corner with every number at its most, a run past a 24-bit draw index, and workloads at exactly each number declared. It states the numbers in every answer: member.capacity, and a sentence in the label. A member that refuses or fails a case within its capacity loses the grade, and one that declares less than the floor (capacity::floor, what the conformance set's core cases need: 32 cells, fields to ±40, a cost of 8, a run of 5,000 sweeps and so on) is not certified at all.

Then the host audits it. For every answer from a kernel graded bit-exact, it runs again on the reference, in every call, the call's last chain and one chain of each seed's run in it, drawn afresh with a key the host makes at start, before the next call: on the job's own thread at the job's priority, and on as many of the audit's threads as are free, a quarter of the host's cores and 4 at most over the whole process, each at a low priority (run::audit_threads); and the reference's settle as far as a budget of 2²⁴ of the work the host asked for (the whole settle past that one job in 8). Each audited answer says what was checked (audit). At the first difference it demotes the member to uncertified for both kernels, answers that job from the reference with the member named under refusals, and every later answer says so (member.demoted). The demotion is kept under the member's id and fingerprint (member::Demotions, in the file WAI_LANDSCAPE_DEMOTIONS names, or a link's target: kept at once in a file of its own beside it and merged under a lock waited for at most 5 s; read, with every demotion in a file of its own, at every certification, which then rewrites the file as a demotion would), so certifying again does not clear it; where that file cannot be read or rewritten, has a second name, or is reached by a link in a sticky folder anyone may write, no kernel is graded bit-exact. A kernel graded statistical is placed only where a job asks for it ("parity": "statistical"), and its answers say what the grade rests on: the battery's workloads alone, which a fault at a count of cells they do not run, or a law near the exact one, can pass.

use wai_quantum::quantum_landscape::capacity::{Capacity, Limits};

// A board of 64 cells whose sampling registers hold fields to ±524,287 and a cost to 1,048,575,
// and whose table holds a window of 8,192 fields a temperature; at temperature 0, any field.
let board = Capacity {
    cells: Some(64),
    above_zero: Limits { field: Some(524_287), field_bound: None, cost: Some(1_048_575) },
    uncertain_span: Some(8_192),
    ..Capacity::NONE
};