Introduction

XQVM is a hardware-agnostic virtual machine for quantum computing. It is the module within the Aglais platform responsible for expressing binary optimisation models and objective functions. The current scope targets X-quadratic models for quantum annealers (QUBO/Ising formulations).

Think of it as LLVM for quantum computing: write a problem once, compile it to XQVM bytecode, and run it on any supported backend.

Goals

• Hardware-agnostic – write a problem once, run it on any supported backend.
• Unified bytecode – a common intermediate representation for binary optimisation problems targeting quantum annealers.
• Embeddable – the core VM and bytecode crates support no_std + alloc, enabling deployment in WASM runtimes, bare-metal environments, and Substrate pallets.

Workspace Crates

The project is organised into five Rust crates:

Architecture at a Glance

XQVM is a stack-based interpreter with a 256-slot register file. The value stack holds i64 integers. Registers hold typed values (RegVal): integers, integer vectors, QUBO/Ising models (XqmxModel), model vectors, and candidate solutions (XqmxSample). A dedicated loop stack drives RANGE/ITER iteration.

The instruction set comprises 93 instructions across 14 categories: control flow, register I/O, stack manipulation, arithmetic, comparison, logical, bitwise, allocators, vector operations, index math, coefficient access, grid operations, high-level constraints, and energy evaluation.

The opcode table (opcodes! x-macro in crates/bytecode/src/types/table.rs) is the single source of truth. The Opcode enum, Instruction enum, mnemonic strings, operand arity, codec, and builder methods are all derived from it.

Programs are serialised as a jump table followed by a raw instruction stream. Each instruction is an opcode byte followed by its operands in big-endian byte order.

What This Book Covers

• Getting Started – installation, building, and running your first program.
• CLI Reference – the xq command-line tool.
• VM Architecture – stack, registers, loops, I/O, and the execution model.
• Assembly Language – the .xqasm syntax.
• Instruction Set Reference – all 93 instructions with full semantics.
• Bytecode Format – the binary wire format.
• Builder API – programmatic bytecode construction in Rust.
• Pallet Integration – running XQVM on-chain via a Substrate pallet.
• Examples – worked examples including a Travelling Salesman Problem.

License

Licensed under the GNU Affero General Public License v3.0 or later.

Getting Started

This chapter walks through installing the toolchain, building the project, and running your first XQVM program.

Prerequisites

# Install Rust (stable)
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# Install development tools (clippy, rustfmt, taplo, cargo-deny, cargo-nextest)
make deps

Build

cargo build --release

The xq binary is placed at target/release/xq.

A Minimal Program

Create a file called add.xqasm:

; push two integers and add them
PUSH 10
PUSH 32
ADD
HALT

Assemble and run:

xq asm add.xqasm -o add.xqb
xq run add.xqb

Expected output:

stack (bottom to top):
  42

The program pushes 10 and 32 onto the stack, adds them, and halts. The result (42) remains on the stack and is printed by xq run.

Inspect the Bytecode

Disassemble the compiled program to see its binary encoding:

xq dism add.xqb

This prints a human-readable listing with byte offsets and decoded instructions.

Run Assembly Directly

Use the --text flag to skip the separate assembly step:

xq run --text add.xqasm

Using Calldata and Outputs

Programs can receive input via calldata and write results to output slots:

; Read calldata[0] into r0, write it to output[0]
PUSH 0
INPUT r0
PUSH 0
OUTPUT r0
HALT

xq run --text program.xqasm --calldata 42 --outputs 1

Expected output:

outputs:
  [0] = Int(42)

Next Steps

• Learn the full CLI Reference
• Understand the VM Architecture
• Browse the Assembly Language syntax
• See the complete Instruction Set Reference
• Walk through the TSP Example for a real-world use case

First Problem

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

What Happened

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Toolchain Map

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Ways to Use XQuad

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Quadratic Models

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Three Programs

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Backends

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Modelling Lifecycle

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Inputs and Model Shape

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Expressions

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Objectives

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Constraints

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Control Flow

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Outputs and Decoding

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Compiling

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Running Programs

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Verification

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Solving Overview

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Local Solvers

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

D-Wave QPU

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Quip Network

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Energy and Precision

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Examples

Graph problems

Examples that encode graph cuts, colouring, covers, independent sets, and tours.

• Max-Cut – Find a 2-colour partition of a weighted graph that maximises the cut weight.
• Graph Coloring – Assign colours to graph nodes so adjacent nodes do not share a colour.
• Maximum Independent Set – Select the largest subset of graph nodes with no selected edge between them.
• Vertex Cover – Select the smallest vertex subset that covers every graph edge.
• Travelling Salesman Problem – Find the shortest Hamiltonian tour through a random symmetric distance matrix.

Selection and packing

Examples that select subsets, cover demands, pack bins, and balance integer weights.

• Knapsack – Select items that maximise value while respecting a capacity constraint.
• Bin Packing – Pack items into the minimum number of fixed-capacity bins.
• Set Cover – Select the minimum set collection whose union covers the universe.
• Weighted Set Cover – Select sets with capacities to cover element demands at minimum cost.
• Number Partition – Split positive integers into two subsets with nearly equal sums.
• Portfolio Optimization – Select a fixed-size portfolio while penalising higher-order risk interactions.

Satisfiability and higher-order

Examples that reduce clauses and higher-order pseudo-Boolean objectives to quadratic models.

• Max-3-SAT – Find the assignment that satisfies the maximum number of 3-literal clauses.
• Cubic Optimization – Minimise a cubic pseudo-Boolean objective through HOBO degree reduction.
• Quartic Optimization – Minimise a degree-4 pseudo-Boolean objective through two-stage REDUCE chaining.

Using the Examples

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Max-Cut

Source: examples/maxcut/README.md

Find a 2-colour partition of a weighted graph that maximises the total weight of edges crossing the partition.

QUBO formulation

• Input: num_nodes (int), edges (Vec of flat (i, j, w) triples, 3*|E| entries)
• Model: n binary variables, one per node. x[v] in {0, 1} selects the side of the cut.
• Objective: for each edge (i, j, w), add -w*(x_i + x_j) and +2w*x_i*x_j. Minimising this minimises -sum w*[x_i != x_j], i.e. maximises the cut.

DSL methods used

• problem.input() – declare typed calldata inputs
• problem.define_model() – allocate binary XQMX model
• problem.stow() – bind intermediate computations to named registers
• problem.range() – emit RANGE loops
• model.linear[i].add() – accumulate linear bias on variable i
• model.quadratic[i, j].add() – accumulate quadratic coupling between variables i and j
• problem.output() – declare typed output slots
• problem.sample.getline() – read a row from the sample bitstring

Pipeline overview

1. CP (xqcp) – build a random weighted complete graph, declare binary variables (one per node), and add linear/quadratic QUBO terms per edge.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks constraints and computes energy
6. Decode – decoder extracts the 2-colour partition

Usage

uv run python examples/maxcut/runner.py --seed 42
uv run python examples/maxcut/runner.py --n 6 --seed 7 -o /tmp/mc.json

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Graph Coloring

Source: examples/graph_coloring/README.md

Assign one of C colors to each node of an undirected graph such that no two adjacent nodes share the same color (proper C-coloring).

QUBO formulation

• Input: number of nodes N, number of colors C, edge list
• Model: N*C binary variables in an N x C grid. x[v,c] = 1 if node v gets color c.
• Objective: energy 0 for any valid C-coloring; minimise constraint violations.
• Constraints:
  • One-hot per node: sum_c x[v,c] = 1 (ONEHOTR, penalty 200)
  • Exclusion per (edge, color): x[u,c] + x[v,c] <= 1 (EXCLUDE, penalty 200)

Encoding strategy

ONEHOTR applies the one-hot row constraint directly: for each node v, a single ONEHOTR instruction constrains all C variables in that row to sum to 1.

EXCLUDE is applied per (edge (u,v), color c) pair via a nested range loop. The 2D coordinates (u, c) and (v, c) are resolved to flat indices using IDXGRID: u * num_colors + c and v * num_colors + c.

DSL methods used

• problem.define_model(size=N*C, rows=N, cols=C) – 2D grid model layout
• model.apply_onehot_row(node, penalty) – ONEHOTR per node
• model.apply_exclude((u, c), (v, c), penalty) – EXCLUDE per edge per color

Pipeline overview

1. CP (xqcp) – generate a random graph, declare an N x C binary grid, and add ONEHOTR constraints per node plus EXCLUDE constraints per (edge, color) pair.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks one-hot and exclusion constraints and computes energy
6. Decode – decoder extracts the color assignment per node

Usage

uv run python examples/graph_coloring/runner.py --seed 42
uv run python examples/graph_coloring/runner.py --n 6 --colors 3 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Maximum Independent Set

Source: examples/max_independent_set/README.md

Find the largest subset of nodes in an undirected graph such that no two selected nodes share an edge.

QUBO formulation

• Input: number of nodes N, edge list
• Model: N binary variables. x_i = 1 if node i is in the independent set.
• Objective: minimise -sum(x_i) (maximise set size)
• Constraints: per edge (i,j): x_i + x_j <= 1 (SLACK + EQUALITY)

Each edge inequality is encoded via SLACK + EQUALITY. A single binary slack variable s (capacity = 1) converts x_i + x_j <= 1 into the equality x_i + x_j + s = 1, and EQUALITY adds the penalty P*(x_i + x_j + s - 1)^2.

Slack variable indices start at num_nodes and are allocated one per edge.

DSL methods used

• problem.vec() – allocate untyped vector registers for indices and coefficients
• problem.slack(indices, coeffs, start_index, capacity) – append one slack entry per edge
• model.apply_equality(indices, coeffs, target, penalty) – EQUALITY constraint

Pipeline overview

1. CP (xqcp) – generate a random graph, declare binary variables (one per node), and encode each edge independence constraint via SLACK + EQUALITY.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks edge independence constraints and computes energy
6. Decode – decoder extracts the selected nodes

Usage

uv run python examples/max_independent_set/runner.py --seed 42
uv run python examples/max_independent_set/runner.py --n 7 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Vertex Cover

Source: examples/vertex_cover/README.md

Find the minimum subset of vertices such that every edge in an undirected graph has at least one endpoint in the subset.

QUBO formulation

• Input: number of nodes N, edge list
• Model: N binary variables. x_v = 1 if vertex v is in the cover.
• Objective: minimise sum(x_v)
• Constraints: per edge (i,j): x_i + x_j >= 1 (ATLEAST with k=1)

The at-least-1 constraint is encoded directly with ATLEAST. For each edge, ATLEAST allocates one slack variable at model.size and adds the penalty P*(x_i + x_j - 1 - s)^2, where s in {0,1} accounts for the case when both endpoints are selected (sum = 2).

DSL methods used

• problem.vec() – allocate a vector register for the two endpoint indices per edge
• model.apply_atleast(indices, k, penalty) – ATLEAST constraint with k=1

Pipeline overview

1. CP (xqcp) – generate a random graph, declare binary variables (one per vertex), and encode per-edge coverage constraints via ATLEAST.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks edge coverage constraints and computes energy
6. Decode – decoder extracts the selected vertices

Usage

uv run python examples/vertex_cover/runner.py --seed 42
uv run python examples/vertex_cover/runner.py --n 7 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Travelling Salesman Problem

Source: examples/tsp/README.md

Find the shortest Hamiltonian tour through N cities given a random symmetric distance matrix.

QUBO formulation

• Input: num_cities (int), distance_matrix (Vec, flat upper triangle, n*(n-1)/2 entries)
• Model: an n x n binary grid. x[i, p] = 1 means city i is at tour position p.
• Objective: sum of distances between consecutive positions in the tour.
• Constraints: one-hot row (each city at exactly one position) and one-hot column (each position holds exactly one city), both with penalty 100.

DSL methods used

• problem.input() – declare typed calldata inputs
• problem.define_model() – allocate binary 2D grid XQMX model
• problem.stow() – bind intermediate computations to named registers
• problem.range() – emit RANGE loops
• model.quadratic[(city_i, pos), (city_j, pos)].add() – accumulate quadratic coupling using 2D grid coordinates
• model.apply_onehot_row() – ONEHOTR constraint per city
• model.apply_onehot_col() – ONEHOTC constraint per position
• problem.output() – declare typed output slots
• problem.sample.colfind() – find the row index with value 1 in a given column

Pipeline overview

1. CP (xqcp) – build a random symmetric distance matrix, declare an n x n binary grid, and add quadratic distance terms plus one-hot row/column constraints.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks one-hot row/column constraints and computes energy
6. Decode – decoder extracts the tour as a sequence of city indices

Usage

uv run python examples/tsp/runner.py --seed 42
uv run python examples/tsp/runner.py --n 5 --seed 7 -o /tmp/tsp.json

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Knapsack

Source: examples/knapsack/README.md

The 0/1 Knapsack problem: given N items with integer weights and values, select a subset maximising total value subject to a weight capacity constraint.

QUBO formulation

• Input: N item weights and values, capacity W
• Model: N binary variables. x_i = 1 means item i is selected.
• Objective: minimise -sum(v_i * x_i)
• Constraints: capacity sum(w_i * x_i) <= W (SLACK + EQUALITY)

The inequality is encoded via SLACK + EQUALITY. SLACK appends binary slack variable entries (s_j with coefficients 2^j) to the index and coefficient vectors, converting the inequality to the equality sum(w_i*x_i) + sum(s_j*2^j) = W. EQUALITY then adds the penalty term P*(sum(a_k*x_k) - W)^2 to the QUBO.

DSL methods used

• problem.vec() – allocate untyped vector registers for indices and coefficients
• problem.slack(indices, coeffs, start_index, capacity) – append slack entries
• model.apply_equality(indices, coeffs, target, penalty) – EQUALITY constraint

Pipeline overview

1. CP (xqcp) – generate random item weights and values, declare binary variables, and encode the capacity inequality via SLACK + EQUALITY.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks capacity constraint and computes energy
6. Decode – decoder extracts the item selection

Usage

uv run python examples/knapsack/runner.py --seed 42
uv run python examples/knapsack/runner.py --n 6 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Bin Packing

Source: examples/bin_packing/README.md

Pack N items with given integer sizes into the minimum number of bins, each with a fixed capacity C.

QUBO formulation

• Input: N item sizes (Vec), number of bins B, bin capacity C
• Model: N*B binary variables in an N x B grid. x[i,b] = 1 if item i is placed in bin b.
• Objective: minimise sum_{i,b} x[i,b] (proxy for number of bins used)
• Constraints:
  • Assignment per item i: sum_b x[i,b] = 1 (EQUALITY with unit coefficients)
  • Capacity per bin b: sum_i s_i * x[i,b] <= C (SLACK + EQUALITY)

The capacity inequality is encoded by appending binary slack variable entries to the column index/coefficient vectors, converting it to a weighted equality.

DSL methods used

• problem.vec() – allocate untyped vector registers for indices and coefficients
• problem.slack(indices, coeffs, start_index, capacity) – append slack entries
• model.apply_equality(indices, coeffs, target, penalty) – EQUALITY constraint

Pipeline overview

1. CP (xqcp) – generate random item sizes, declare an N x B binary grid, and add EQUALITY assignment constraints per item plus SLACK + EQUALITY capacity constraints per bin.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks assignment and capacity constraints and computes energy
6. Decode – decoder extracts the bin assignments

Usage

uv run python examples/bin_packing/runner.py --seed 42
uv run python examples/bin_packing/runner.py --n 5 --bins 4 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Set Cover

Source: examples/set_cover/README.md

Given a universe of E elements and a collection of S sets, find the minimum sub-collection whose union equals the universe.

QUBO formulation

• Input: number of elements E, number of sets S, coverage membership matrix (flat Vec of E*S entries, covers[e][s] = 1 if set s covers element e)
• Model: S binary variables. x_s = 1 if set s is selected.
• Objective: minimise sum(x_s)
• Constraints: per element e: sum_{s: covers[e][s]=1} x_s >= 1 (ATLEAST with k=1)

For each element, the encoder iterates over all sets and uses a branch to conditionally push only covering set indices into the element’s index vector. ATLEAST then enforces that at least one covering set is selected.

DSL methods used

• problem.vec() – allocate a vector register for each element’s covering set indices
• problem.branch(cond, arm, default) – conditional VECPUSH based on coverage membership
• model.apply_atleast(indices, k, penalty) – ATLEAST constraint with k=1

Pipeline overview

1. CP (xqcp) – generate a random coverage matrix, declare binary variables (one per set), and encode per-element coverage constraints via conditional branching and ATLEAST.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks coverage constraints and computes energy
6. Decode – decoder extracts the selected sets

Usage

uv run python examples/set_cover/runner.py --seed 42
uv run python examples/set_cover/runner.py --num-sets 6 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Weighted Set Cover

Source: examples/weighted_set_cover/README.md

A generalisation of Set Cover where each set s has a coverage capacity cap[s] and each element e has a demand demand[e]. The goal is to select sets of minimum total cost such that the total capacity of covering selected sets meets each element’s demand.

QUBO formulation

• Input: number of elements E, number of sets S, set costs, set capacities, element demands, coverage membership matrix
• Model: S binary variables. x_s = 1 if set s is selected.
• Objective: minimise sum(cost[s] * x_s)
• Constraints: per element e: sum_{s: covers[e][s]=1} cap[s] * x_s >= demand[e] (ATLEASTW)

For each element, a branch conditionally pushes (set index, capacity) pairs into per-element index/coefficient vectors, then ATLEASTW enforces the weighted threshold.

DSL methods used

• problem.vec() – allocate vector registers for covering set indices and capacities
• problem.branch(cond, arm, default) – conditional VECPUSH based on coverage membership
• model.apply_atleastw(indices, coeffs, k, penalty) – ATLEASTW constraint

Pipeline overview

1. CP (xqcp) – generate a random weighted coverage instance, declare binary variables (one per set), and encode per-element weighted demand constraints via conditional branching and ATLEASTW.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks weighted demand constraints and computes energy
6. Decode – decoder extracts the selected sets

Usage

uv run python examples/weighted_set_cover/runner.py --seed 42
uv run python examples/weighted_set_cover/runner.py --num-sets 6 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Number Partition

Source: examples/number_partition/README.md

Given N positive integers, find a way to split them into two subsets of equal sum (or as close as possible if an exact split does not exist).

QUBO formulation

• Input: N positive integers a_i
• Model: N binary variables. x_i = 1 puts number a_i in subset A.
• Objective: minimise P * (sum(a_i * x_i) - S/2)^2 where S = sum(a_i)

An exact partition exists when S is even and the penalty evaluates to zero. The QUBO minimiser finds the balanced partition when one exists, or the most balanced split when the total is odd.

DSL methods used

• problem.vec() – allocate untyped vector registers for indices and coefficients
• model.apply_equality(indices, coeffs, target, penalty) – EQUALITY constraint

Pipeline overview

1. CP (xqcp) – generate random positive integers, declare binary variables (one per number), and encode the half-sum equality constraint via EQUALITY.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks the partition constraint and computes energy
6. Decode – decoder extracts the subset assignment

Usage

uv run python examples/number_partition/runner.py --seed 42
uv run python examples/number_partition/runner.py --n 8 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Portfolio Optimization

Source: examples/portfolio_opt/README.md

Select a portfolio of exactly B assets from N candidates to maximise expected return while penalising higher-order risk cross-interactions.

QUBO formulation

• Input: N asset returns, cubic risk interactions (i, j, k, sigma), budget B
• Model: N binary variables. x_i = 1 if asset i is selected.
• Objective: -sum(r_i * x_i) + sum(sigma_ijk * x_i * x_j * x_k) – first term maximises return (minimising its negation), second penalises correlated three-asset risk interactions.
• Constraints: budget sum(x_i) = B (EQUALITY with unit coefficients, penalty 200)

Encoding strategy

Return terms are linear: ADDLINE(i, -r_i) per asset.

Cubic risk terms (i, j, k, sigma) are degree-reduced:

1. REDUCE(i, j, P_AUX) -> w (Rosenberg enforcement for w = x_i * x_j)
2. ADDQUAD(w, k, sigma) (sigma * w * x_k = sigma * x_i * x_j * x_k)

Budget constraint builds uniform-coefficient index/coeff vecs then calls EQUALITY with target = B and penalty = 200. EQUALITY is emitted after all objective (body) actions because it lands in the constraint section.

DSL methods used

• model.reduce(var_a, var_b, p_aux) – HOBO degree reduction for cubic risk terms
• problem.vec() – allocate index/coefficient vecs for the budget constraint
• model.apply_equality(indices, coeffs, target, penalty) – budget EQUALITY

Pipeline overview

1. CP (xqcp) – generate random returns and cubic risk interactions, declare binary variables, degree-reduce risk terms via REDUCE, and add a budget EQUALITY constraint.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks budget constraint and computes energy
6. Decode – decoder extracts the selected assets

Usage

uv run python examples/portfolio_opt/runner.py --seed 42
uv run python examples/portfolio_opt/runner.py --n 6 --budget 3 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Max-3-SAT

Source: examples/max3sat/README.md

Given M clauses of 3 positive literals over N binary variables, find the assignment that satisfies the maximum number of clauses.

QUBO formulation

• Input: N binary variables, M clauses of 3 positive literals
• Model: N binary variables. x_v in {0, 1}.
• Objective: minimise sum over clauses of P*(1-x_i)(1-x_j)(1-x_k)

A clause (i,j,k) is violated when all three variables are 0. Expanding the product (dropping the constant term):

P*(-x_i - x_j - x_k + x_i*x_j + x_i*x_k + x_j*x_k - x_i*x_j*x_k)

The cubic term -P*x_i*x_j*x_k is degree-reduced via REDUCE(i, j) -> w, introducing one auxiliary variable w per clause with Rosenberg enforcement P_AUX*(x_i*x_j - 2*x_i*w - 2*x_j*w + 3*w). The cubic term becomes the quadratic term -P*w*x_k.

DSL methods used

• model.reduce(var_a, var_b, p_aux) – HOBO degree reduction; returns a RegLoad holding the auxiliary variable index for chaining into quadratic terms

Pipeline overview

1. CP (xqcp) – generate random 3-literal clauses, declare binary variables, and degree-reduce the cubic violation terms via REDUCE.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks constraints and computes energy
6. Decode – decoder extracts the variable assignment

Usage

uv run python examples/max3sat/runner.py --seed 42
uv run python examples/max3sat/runner.py --n 8 --m 10 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Cubic Optimization

Source: examples/cubic_opt/README.md

Minimise a cubic pseudo-Boolean objective over binary variables via single-stage HOBO degree reduction.

QUBO formulation

• Input: N binary variables, M cubic interaction terms (i, j, k, c)
• Model: N binary variables. Linear bias -1 per variable rewards selection, creating tension with the positive cubic terms.
• Objective: sum(c_t * x_i * x_j * x_k) - sum(x_v)

Each cubic term (i, j, k, c) is degree-reduced to quadratic via:

1. REDUCE(i, j, P_AUX) -> w – allocates auxiliary variable w with Rosenberg enforcement P_AUX*(x_i*x_j - 2*x_i*w - 2*x_j*w + 3*w)
2. ADDQUAD(w, k, c) – adds c*w*x_k = c*x_i*x_j*x_k to the QUBO

DSL methods used

• model.reduce(var_a, var_b, p_aux) – single-stage HOBO degree reduction

Pipeline overview

1. CP (xqcp) – generate random cubic interaction terms, declare binary variables with linear bias, and degree-reduce each cubic term via REDUCE.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks constraints and computes energy
6. Decode – decoder extracts the variable assignment

Usage

uv run python examples/cubic_opt/runner.py --seed 42
uv run python examples/cubic_opt/runner.py --n 5 --m 4 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Quartic Optimization

Source: examples/quartic_opt/README.md

Minimise a degree-4 pseudo-Boolean objective via two-stage REDUCE chaining.

QUBO formulation

• Input: N binary variables, M quartic interaction terms (i, j, k, l, c)
• Model: N binary variables. Linear bias -1 per variable rewards selection, creating tension with the positive quartic terms.
• Objective: sum(c_t * x_i * x_j * x_k * x_l) - sum(x_v)

Each quartic term (i, j, k, l, c) is encoded via two-stage REDUCE:

1. w = REDUCE(i, j, P_AUX) – introduces auxiliary w; w approximates x_i*x_j.
2. v = REDUCE(w, k, P_AUX) – introduces auxiliary v; v approximates w*x_k = x_i*x_j*x_k. Here w is the variable index returned from the first REDUCE.
3. ADDQUAD(v, l, c) – adds c*v*x_l = c*x_i*x_j*x_k*x_l to the QUBO.

Each quartic term allocates 2 auxiliary variables. With M terms, the model grows by 2*M variables beyond the original N.

DSL methods used

• model.reduce(var_a, var_b, p_aux) – two chained HOBO degree reductions; the RegLoad returned by the first REDUCE is passed as var_a to the second

Pipeline overview

1. CP (xqcp) – generate random quartic interaction terms, declare binary variables with linear bias, and two-stage degree-reduce each quartic term via chained REDUCE.
2. Assemble – .xqasm text to bytecode via xquad.asm
3. Encode – run encoder on chosen XQVM to produce the XQMX model
4. Sample – solver runs SA/QPU/GPU over the model
5. Verify – verifier checks constraints and computes energy
6. Decode – decoder extracts the variable assignment

Usage

uv run python examples/quartic_opt/runner.py --seed 42
uv run python examples/quartic_opt/runner.py --n 6 --m 3 --interpreter rust

Choosing a solver

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.

Cookbook

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Permutations

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Selection Under Budget

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Assignment

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Mutual Exclusion

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Soft vs Hard Constraints

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Penalty-Weight Tuning

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Integer Scaling

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

XQVM Reference

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

VM Architecture

XQVM is a stack-based bytecode interpreter. A running VM holds four pieces of mutable state:

block-beta
  columns 2
  block:header:2
    columns 1
    title["XQVM State"]
  end
  A["Stack"] B["Vec‹i64›, max 8192 items (LIFO operand stack)"]
  C["Register File"] D["[RegVal; 256], indexed r0--r255"]
  E["Loop Stack"] F["Vec‹LoopFrame› for RANGE/ITER iteration"]
  G["Calldata / Outputs"] H["Vec‹RegVal› -- read-only inputs (INPUT) and writable output slots (OUTPUT)"]

  style title fill:none,stroke:none
  style A text-align:left
  style C text-align:left
  style E text-align:left
  style G text-align:left

Design Principles

• Stack-based computation – arithmetic and comparisons operate on an integer stack. This keeps the instruction set simple and compact.
• Typed register file – registers hold polymorphic RegVal values (integers, vectors, models, samples). Type checking happens at runtime.
• No heap / no pointers – there is no explicit memory allocation. Vectors and models grow dynamically within registers. Programs cannot address raw memory.
• Deterministic execution – given the same program, calldata, and configuration, the VM always produces the same output. There are no random instructions or non-deterministic operations.
• Embeddable – the VM crate supports no_std + alloc, enabling deployment in WASM runtimes and bare-metal environments.

Chapters

• Operand stack – the i64 value stack
• Register file – the 256-slot typed register array
• Loop Stack – range and iterator loop frames
• Calldata and Outputs – external I/O slots
• Execution Model – the fetch-decode-execute cycle

Operand Stack

The operand stack is the primary workspace for computation. It holds i64 signed 64-bit integers and is used by arithmetic, comparison, logical, and bitwise instructions.

Properties

Operations

• Push – PUSH1–PUSH8 push constants. LOAD pushes a register’s integer value. COPY duplicates the top element.
• Pop – most instructions implicitly pop their operands. POP explicitly discards the top element.
• Swap – SWAP exchanges the top two elements.
• Clear – SCLR removes all elements.

Stack Diagrams

Throughout this documentation, stack effects are written as:

$$[\ldots, a, b] \to [\ldots, r]$$

• \(\ldots\) represents elements below the operands.
• Rightmost = top of stack.
• \(b\) is popped first (it was pushed last).
• \(r\) is the result pushed after the operation.

Errors

• StackUnderflow – popping from an empty stack or when there are fewer elements than the instruction requires.
• StackOverflow – pushing when the stack already contains 8,192 items.

Interaction with Registers

The stack holds only i64 integers. Richer types (models, vectors, samples) live exclusively in registers. The bridge between them:

• LOAD reg – pushes a register’s Int value onto the stack.
• STOW reg – pops a stack value into a register as Int.

To move non-integer values, use INPUT/OUTPUT with calldata and output slots.

Register File

The register file is a fixed array of 256 slots, indexed r0 through r255. Each slot holds a typed RegVal value.

Properties

RegVal Variants

Type Checking

Register access is type-checked at runtime. Instructions that expect a specific variant (e.g. LOAD expects Int, VECPUSH expects VecInt, SETLINE expects Model) will produce a RegisterType error if the register holds a different variant. The error message includes the expected and actual type names.

XqmxModel Structure

A model represents a QUBO/Ising/discrete Hamiltonian:

XqmxModel {
    domain: Domain,                      // Binary | Spin | Discrete(k)
    size: usize,                         // number of variables
    linear: BTreeMap<usize, i64>,        // bias terms h_i
    quadratic: BTreeMap<(usize,usize), i64>,  // coupling terms J_{ij}
    rows: usize,                         // grid rows (set by RESIZE)
    cols: usize,                         // grid cols (set by RESIZE)
}

Coefficients are stored sparsely. Missing entries read as 0; setting a coefficient to 0 removes it from the map.

XqmxSample Structure

A sample holds a vector of variable assignments:

XqmxSample {
    domain: Domain,        // must match the model's domain
    values: Vec<i64>,      // one value per variable
}

Memory Management

There is no garbage collector. Registers hold their values until explicitly overwritten. Use DROP reg to reset a register to Int(0), releasing any heap allocation (models, vectors, samples) it held.

Loop Stack

The loop stack manages RANGE and ITER loop state. Each active loop pushes a frame; NEXT either advances the loop or pops the frame when iteration completes.

Loop Frames

Each frame records:

• Kind – Range or Iter.
• body_start – byte offset of the first instruction after RANGE/ITER. This is where NEXT seeks back to on each iteration.

Range Loops

LoopKind::Range {
    current: i64,    // current iteration value
    end: i64,        // exclusive upper bound (start + count)
}

RANGE pops count and start from the stack. The loop iterates current from start to end - 1 (where end = start + count, wrapping). On each NEXT, current is incremented. If current < end, execution seeks back to body_start; otherwise the frame is popped and execution falls through.

PUSH 5       ; start = 5
PUSH 3       ; count = 3
RANGE        ; iterates current = 5, 6, 7
  LVAL r0    ; r0 ← Int(current)
  ; ... body ...
NEXT

Iterator Loops

LoopKind::Iter {
    elements: IterElements,  // slice copy of vec[start..end]
    start_offset: usize,     // original `start` index, used by LIDX
    index: usize,            // current position within `elements`
}

enum IterElements {
    Int(Vec<i64>),
    Xqmx(Vec<XqmxModel>),
}

ITER reg pops end_idx, then start_idx, validates that reg holds VecInt or VecXqmx, and copies vec[start_idx..end_idx] into a new frame with index = 0. The slice is duplicated so that mutations to the source vec inside the loop body do not affect what LVAL sees.

On each NEXT, index is incremented. If index < elements.len(), execution seeks back to body_start; otherwise the frame is popped.

; Assume r1 holds VecInt([10, 20, 30, 40, 50])
PUSH 1
PUSH 4
ITER r1            ; iterate r1[1..4] -> values 20, 30, 40
  LVAL r2          ; r2 -> Int(20), Int(30), Int(40)
  LIDX r3          ; r3 -> Int(1), Int(2), Int(3) (absolute positions)
  ; ... body ...
NEXT

ITER errors with IndexOutOfBounds if either index is negative, exceeds vec.len(), or if start_idx > end_idx.

LVAL – Reading the Loop Value

LVAL reg copies the current loop value into a register:

• Range: reg ← Int(current)
• Iter over VecInt: reg ← Int(elements[index]) (the slice copy, not the source vec)
• Iter over VecXqmx: reg ← Model(elements[index]) (cloned)

The element type is preserved: iterating over a VecXqmx yields Model values, not integers. Because elements is a slice copy taken at ITER time, mutating the source vec inside the loop body never changes what subsequent LVAL calls return.

LIDX – Reading the Loop Index

LIDX reg copies the current loop index into a register:

• Range: reg ← Int(current) (identical to LVAL because Range values are themselves indices).
• Iter: reg ← Int(start_offset + index) – the absolute position in the source vec, not the 0-based slice position. This lets loop bodies reach back into the source vec by absolute index even after slicing.

Nesting

Loops can be nested to arbitrary depth. Each RANGE or ITER pushes a new frame. LVAL and NEXT always operate on the innermost (most recently pushed) frame.

PUSH 0
PUSH 3
RANGE              ; outer loop: 0, 1, 2
  LVAL r0
  PUSH 0
  PUSH 4
  RANGE            ; inner loop: 0, 1, 2, 3
    LVAL r1
    ; r0 = outer value, r1 = inner value
  NEXT
NEXT

Errors

• NoActiveLoop – NEXT or LVAL with an empty loop stack.
• RegisterType – ITER on a register that is not VecInt or VecXqmx.

Calldata and Outputs

Calldata and output slots provide the interface between the VM and the host environment. They allow programs to receive input and return results without direct access to external systems.

Calldata (Input)

Calldata is a read-only array of RegVal values, set before execution begins. Programs access calldata via the INPUT instruction:

PUSH 0       ; slot index
INPUT r0     ; r0 ← calldata[0]

Any RegVal variant can be passed as calldata: integers, vectors, models, and samples. This enables multi-program pipelines where one program’s output model becomes another program’s input.

Setting Calldata (Rust API)

#![allow(unused)]
fn main() {
let mut vm = Vm::new();
vm.set_calldata(vec![
    RegVal::Int(42),
    RegVal::VecInt(vec![1, 2, 3]),
    RegVal::Model(my_model),
]);
}

Setting Calldata (CLI)

xq run program.xqb --calldata 10,20,30

The CLI --calldata flag only supports integer values. For richer types, use the Rust API.

Output Slots

Output slots are a writable array of RegVal values, initialised to Int(0). Programs write to output slots via the OUTPUT instruction:

PUSH 0       ; slot index
OUTPUT r0    ; outputs[0] ← r0

Reading Outputs (Rust API)

#![allow(unused)]
fn main() {
let mut vm = Vm::new();
vm.set_output_slots(4);
vm.run(&program)?;

for (i, val) in vm.outputs().iter().enumerate() {
    println!("[{i}] = {val:?}");
}
}

Reading Outputs (CLI)

xq run prints all non-default output slots after execution:

xq run program.xqb --outputs 4

outputs:
  [0] = Int(42)

Pipeline Pattern

Calldata and outputs enable multi-program pipelines. A common pattern in the TSP example:

1. Encoder receives N and distances as calldata, outputs a QUBO model.
2. Verifier receives the model and a sample as calldata, outputs energy and validity.
3. Decoder receives the sample as calldata, outputs the tour.

Each program runs in its own Vm instance. The host (Rust code or pallet) marshals outputs from one VM into calldata for the next.

Errors

• CallDataIndex – INPUT with an index ≥ calldata length.
• OutputIndex – OUTPUT with an index ≥ output slot count.

Execution Model

This chapter describes how the VM fetches, decodes, and executes instructions.

Fetch-Decode-Execute Cycle

The VM processes instructions in a loop:

1. Check step limit → error if exceeded
2. Increment step counter
3. Fetch next instruction from the instruction stream
4. Decode the opcode byte and operands
5. Dispatch to the handler for that instruction
6. Handle the control flow result:
   - Continue  → advance to next instruction
   - Halt      → stop execution
   - Jump(lbl) → seek to jump_table[lbl].start
   - Seek(off) → seek to byte offset (used by NEXT)
7. Repeat from step 1

Instruction Stream

The instruction stream is a cursor over the program’s raw bytecode. It decodes one instruction at a time, advancing the cursor past the opcode byte and its operands. The stream supports seeking to arbitrary byte offsets for jumps and loop backs.

Each decoded instruction yields:

• Byte offset – position in the bytecode buffer.
• Optional label – if a jump table entry starts at this offset.
• Instruction – the fully decoded instruction with typed operands.

Step Counting

The VM maintains a step counter that increments after every instruction dispatch. A configurable step limit (default: 10,000,000) prevents runaway programs. When the limit is reached, execution stops with a StepLimitExceeded error.

#![allow(unused)]
fn main() {
let mut vm = Vm::new();
vm.set_step_limit(1_000_000);  // custom limit
// set_step_limit(0) sets the limit to u64::MAX (effectively unlimited)
}

The step counter is accessible after execution via vm.steps(), which reports the actual number of instructions executed. This is used by the pallet for weight refunds.

Control Flow Results

Each instruction handler returns a StepResult that tells the execution loop what to do next:

Tracing

The VM supports optional step-by-step tracing via the Tracer trait. When tracing is enabled, the VM captures state before and after each instruction:

#![allow(unused)]
fn main() {
pub struct StepState<'a> {
    pub pos: usize,                     // byte offset
    pub step: u64,                      // step count
    pub instruction: &'a Instruction,   // decoded instruction
    pub stack: &'a [i64],               // current stack
    pub read_regs: &'a [(u8, RegVal)],  // registers read
    pub written_regs: &'a [(u8, RegVal)], // registers written
    pub loop_depth: usize,              // nesting level
}
}

Two built-in tracer implementations are provided:

• TextTracer – human-readable aligned columns, written to any Write target.
• JsonTracer – one JSON object per step (JSONL format).

When tracing is disabled (NoopTracer), the tracer code is eliminated by dead code optimisation, adding zero overhead to execution.

Error Handling

Runtime errors carry the byte offset (pos) of the faulting instruction, enabling precise error reporting. When the std feature is enabled, errors can be converted to miette::Diagnostic with a disassembled listing highlighting the faulting instruction.

Assembly Language

XQVM programs are written in a simple assembly language and stored in .xqasm files. The assembler (aglais-xqvm-asm crate, invoked via xq asm) parses the source, resolves labels, and emits compact bytecode.

Overview

• Line-oriented format: one instruction per line.
• Comments start with ; and run to end of line.
• Mnemonics are case-insensitive (PUSH, push, Push all work).
• Labels use numeric .N syntax (.0, .1, .42).
• Registers use r<digits> syntax (r0, r255).
• Integer literals may be signed decimal or 0x-prefixed hexadecimal.

Quick Example

; Compute 10 + 32 = 42
PUSH 10
PUSH 32
ADD
HALT

Assembly Syntax

This page defines the complete syntax of the XQVM assembly language, derived from the canonical PEG grammar in crates/asm/src/grammar.pest.

Line Structure

Each source line has the form:

[label_def:] [INSTRUCTION [operands...]] [; comment]

All three parts are optional. Blank lines and comment-only lines are valid.

Examples

                        ; blank line (valid)
; this is a comment     ; comment-only line
PUSH 42                 ; instruction only
.0: TARGET              ; label + instruction
.1:                     ; label only (anchors a jump target)
LOAD r0                 ; register operand
JUMP .0                 ; label reference operand

Comments

Comments begin with ; and extend to the end of the line. They can appear on their own or after an instruction:

; full-line comment
PUSH 10  ; inline comment

Mnemonics

Instruction mnemonics are case-insensitive ASCII identifiers. All of these are equivalent:

PUSH 42
push 42
Push 42

The assembler recognises all 93 XQVM instruction mnemonics. PUSH is a special mnemonic that accepts an integer operand and automatically selects the smallest PUSH1–PUSH8 encoding. PUSHC is an alias for PUSH.

Operands

Three operand types exist:

Registers

r0, r1, r2, ..., r255

A lowercase r followed by 1–3 decimal digits. Valid range: r0–r255.

Integer Literals

42          ; positive decimal
-99         ; negative decimal
+7          ; explicit positive
0xFF        ; hexadecimal (0x prefix)
0x0         ; hex zero

Integers are signed i64 values. Decimal and hexadecimal (0x prefix) formats are supported. An optional + or - sign may precede the digits.

Label References

.0, .1, .42, .255

A dot followed by one or more decimal digits. Label references are used as operands for JUMP and JUMPI instructions.

Labels

Labels are defined either with the .N: shorthand or the explicit TARGET .N directive:

.0: NOP            ; shorthand: define label .0 at this position
.1:                ; label on its own line (useful for readability)

TARGET .2          ; explicit form: identical to ".2:"
HALT

Both forms compile to the same bytecode: the assembler emits an inline TARGET opcode at the label position and records the position in the jump table. .0: and TARGET .0 are interchangeable spellings for the same operation; pick whichever reads better in context. Defining the same label with both forms is a DuplicateLabel error, the same as defining .N: twice.

A bare TARGET (no operand) emits a raw Target opcode without binding any label. That’s useful only for hand-built bytecode where you do not need a corresponding jump destination; user-facing programs should use the labelled forms.

Labels must be defined before or after they are referenced – both forward and backward references are resolved by the assembler. Every label used as a JUMP/JUMPI target must be defined somewhere in the program.

The assembler converts labels to jump table entries. At runtime, JUMP .N looks up the byte offset of label .N in the jump table and seeks the instruction stream to that position (which is the byte holding the inline TARGET).

Whitespace

Spaces and tabs between tokens are ignored. Lines are separated by \n or \r\n. Indentation is purely cosmetic and has no semantic meaning. A common convention is to indent loop bodies:

PUSH 0
PUSH 10
RANGE
  LVAL r0
  LOAD r0
  PUSH 2
  MUL
  POP
NEXT

Error Reporting

The assembler uses miette for rich terminal diagnostics. Errors include the source file name, line/column numbers, and a snippet highlighting the problematic token:

Error: unknown mnemonic
  ┌─ program.xqasm:3:1
  │
3 │ INVALID_MNEMONIC r0
  │ ^^^^^^^^^^^^^^^^ unknown instruction

Assembly Examples

This page presents annotated XQVM assembly programs, from simple to complex.

Hello, Stack

Push two numbers, add them, and halt. The result remains on the stack.

PUSH 10        ; stack: [10]
PUSH 32        ; stack: [10, 32]
ADD            ; stack: [42]
HALT

Conditional Branch

Skip an instruction if a condition is true:

PUSH 5
PUSH 10
GT             ; 5 > 10 ? → 0 (false)
JUMPI .0       ; condition is 0, so we fall through
PUSH 99        ; this executes (condition was false)
.0: TARGET
HALT

Countdown Loop

Count down from 3 to 0 using a range loop:

PUSH 3         ; start = 3
PUSH 0         ; accumulator in r0
STOW r0

PUSH 0
PUSH 3
RANGE          ; iterate 0, 1, 2
  LVAL r1      ; r1 = loop value
  LOAD r0
  LOAD r1
  ADD
  STOW r0      ; r0 += r1
NEXT

LOAD r0        ; push accumulated value (0+1+2 = 3)
HALT

Fibonacci Sequence

Compute the first N Fibonacci numbers and store them in a vector:

; N is passed as calldata[0]
PUSH 0
INPUT r0       ; r0 = N

VEC r1         ; r1 = empty vec

; Push first two values
PUSH 0
VECPUSH r1     ; vec = [0]
PUSH 1
VECPUSH r1     ; vec = [0, 1]

; Compute remaining values
PUSH 2
LOAD r0
SUB            ; count = N - 2
STOW r2

PUSH 0
LOAD r2
RANGE
  LVAL r3      ; r3 = loop index (unused, just for iteration)
  VECLEN r1
  DEC
  STOW r4      ; r4 = last index

  LOAD r4
  DEC
  VECGET r1    ; stack: fib[n-2]
  LOAD r4
  VECGET r1    ; stack: fib[n-2], fib[n-1]
  ADD           ; stack: fib[n]
  VECPUSH r1   ; append to vec
NEXT

; Output the vector
PUSH 0
OUTPUT r1
HALT

Building a QUBO Model

Create a simple 3-variable QUBO and set coefficients:

; Allocate a 3-variable binary model
PUSH 3
BQMX r0

; Set linear coefficients: h = [-1, -2, -3]
PUSH 0
PUSH -1
SETLINE r0     ; linear[0] = -1

PUSH 1
PUSH -2
SETLINE r0     ; linear[1] = -2

PUSH 2
PUSH -3
SETLINE r0     ; linear[2] = -3

; Set quadratic coefficient: J[0,1] = 4
PUSH 0
PUSH 1
PUSH 4
SETQUAD r0     ; quad[0,1] = 4

; Output the model
PUSH 0
OUTPUT r0
HALT

Grid with One-Hot Constraints

Set up a 2x3 grid model with one-hot constraints on each row:

; 6 variables in a 2x3 grid
PUSH 6
BQMX r0
PUSH 2         ; rows
PUSH 3         ; cols
RESIZE r0

; One-hot constraint on each row with penalty = 100
PUSH 0
PUSH 2
RANGE
  LVAL r1
  LOAD r1
  PUSH 100
  ONEHOTR r0
NEXT

; Output
PUSH 0
OUTPUT r0
HALT

Instruction Set Reference

This section documents all 93 XQVM instructions, organised by category. Each instruction page includes the opcode byte, mnemonic, operands, stack effect, register effect, and a prose description.

Notation

• Stack diagrams – \([\ldots, a, b] \to [\ldots, r]\), where rightmost = top. \(b\) is popped first.
• reg – the u8 operand encoded in the instruction byte stream, identifying a register slot (r0–r255).
• label – a u16 index into the jump table.
• Assignments use \(\leftarrow\) (register write) and \(\to\) (stack push).
• Iverson brackets – \([P]\) equals \(1\) if \(P\) is true, \(0\) otherwise.
• Wrapping – all integer arithmetic uses wrapping semantics on i64 (no panic on overflow; result truncated to 64 bits).

Register Effect Modes

• read – register contents are inspected but not changed.
• write – register is replaced wholesale with a new value.
• mutate – register’s existing value is modified in-place (e.g. appending to a vec, incrementing a coefficient).

RegVal – The Register Value Type

Each of the 256 registers holds one variant of RegVal:

Type mismatches at runtime produce a RegisterType error with the expected and actual variant names.

Reserved Opcodes

The following byte values are unassigned gaps; the decoder rejects them as illegal:

0x0D, 0x19, 0x35

All other byte values outside the assigned ranges are likewise illegal.

Control Flow

Instructions for branching, looping, and program termination.

Branching

JUMP and JUMPI use label indices, not raw byte offsets. The label index maps to a byte range via the program’s jump table. At the assembly level, labels are written as .N (e.g. .0, .1); the assembler resolves them to indices automatically and picks the narrowest encoding:

• JUMP1 / JUMPI1 (0x80 / 0x81) use a single-byte u8 label index. The assembler emits these whenever the label id is < 256, so most programs will use them exclusively (each call site saves one byte).
• JUMP2 / JUMPI2 (0x02 / 0x03) use a two-byte u16 label index. The assembler falls back to these only for labels with id >= 256.

The assembly source still spells these as JUMP .N and JUMPI .N; the narrow-vs-wide selection happens at assembly time and is transparent to authors. Disassembled output, on the other hand, shows the explicit form (JUMP1 .N, JUMP2 .N, etc.) so the round-tripped source preserves the exact wire encoding.

TARGET must appear at every label destination. It is a no-op at runtime but serves as a validation marker – the VM verifies that jump targets land on TARGET instructions. The assembler inserts a TARGET automatically wherever a label is placed, so authors do not normally type it by hand. Two equivalent spellings produce the same bytecode:

; Shorthand: label form
.0: HALT

; Explicit form: TARGET directive bound to a label
TARGET .0
HALT

Both compile to [TARGET, HALT]. Use whichever is clearer in context. A bare TARGET (with no operand) emits a raw Target opcode without binding any label; that is only useful for direct bytecode construction and most user programs should prefer one of the label-bearing forms.

Looping

XQVM provides two loop primitives:

Range Loops

RANGE pops \(n\) and \(s\) from the stack and creates a loop frame that iterates current from \(s\) to \(s + n - 1\). Use LVAL inside the loop body to copy the current value into a register, and NEXT to advance:

PUSH 0       ; start
PUSH 10      ; count
RANGE
  LVAL r0    ; r0 = current iteration value (0, 1, ..., 9)
  ; ... loop body ...
NEXT

Iterator Loops

ITER takes a register holding a VecInt or VecXqmx plus two stack operands start_idx and end_idx (with end_idx on top), and iterates over the half-open slice vec[start_idx..end_idx]:

PUSH 0       ; start_idx
PUSH 4       ; end_idx
ITER r1      ; r1 must hold a VecInt or VecXqmx
  LVAL r2    ; r2 = current element (from the slice copy)
  LIDX r3    ; r3 = absolute position in r1 (start_idx + index)
  ; ... loop body ...
NEXT

Both indices must satisfy \(0 \le \text{start} \le \text{end} \le \text{vec.len()}\); otherwise ITER raises IndexOutOfBounds. To iterate the entire vec, push \(\text{start} = 0\) and \(\text{end} = \text{vec.len()}\) (use VECLEN for the latter).

ITER copies the slice into the loop frame at the time it runs, so subsequent in-loop mutations of the source vec via VECSET/VECPUSH are not visible to LVAL or LIDX. This makes loop bodies safe to mutate the register they iterate over.

Loops can be nested. Each RANGE or ITER pushes a frame onto the loop stack; NEXT pops the frame when the loop completes.

Loop Index vs. Loop Value

LVAL reads the current loop value: the integer being iterated for RANGE loops, or the actual vec element for ITER loops. LIDX reads the current loop index into the iteration source instead. The two opcodes have overlapping but distinct semantics:

Use LIDX inside an ITER loop when you need to know where the current element lives in the source vec – typically for index-based lookups or constraint generation. With slicing, LIDX reports the absolute index in the source vec, not the 0-based position within the slice:

PUSH 2       ; iterate r1[2..5]
PUSH 5
ITER r1
  LIDX r2    ; r2 = 2, 3, 4 (absolute position in r1)
  LVAL r3    ; r3 = element value at that position
  ; ... loop body uses both r2 and r3 ...
NEXT

Calling either LIDX or LVAL outside any active loop produces a NoActiveLoop runtime error.

Register I/O

Instructions for moving data between the stack, register file, calldata, and output slots.

Stack-Register Bridge

The stack holds only i64 integers. To move richer types (models, vectors, samples) into and out of the VM, use INPUT and OUTPUT with the calldata and output slot arrays.

LOAD and STOW bridge the stack and register file for integer values only. LOAD errors if the register does not hold Int – it will not silently coerce other types.

Memory Management

DROP is the only way to explicitly free a register’s allocation. Setting a register to \(\text{Int}(0)\) releases any model, vector, or sample that was previously stored there. This is important for controlling memory usage in long-running programs.

Stack Manipulation

Instructions for pushing constants, duplicating, swapping, and removing stack elements.

PUSH Size Selection

In assembly, you write a single PUSH mnemonic with an integer literal:

PUSH 42       ; assembler selects PUSH1 (fits in i8)
PUSH 1000     ; assembler selects PUSH2 (fits in i16)
PUSH -1       ; assembler selects PUSH1 (0xFF sign-extends to -1)

The assembler (and the InstructionBuilder::push() method) automatically selects the smallest PUSH1–PUSH8 variant that faithfully represents the value. This keeps bytecode compact: small constants use 2 bytes total, while the full 8-byte PUSH8 is only emitted for values that require all 64 bits.

The encoding is big-endian and sign-extended. For example, PUSH1 0xFF decodes as \(-1_{i64}\), not \(255_{i64}\).

Arithmetic

All operations are on i64 with wrapping semantics (no overflow trap).

None of these instructions have register effects.

Wrapping Semantics

All arithmetic uses Rust’s wrapping_* methods on i64. This means overflow silently wraps around rather than trapping. For example:

• \(\texttt{i64::MAX} + 1\) wraps to \(\texttt{i64::MIN}\)
• \(\lvert\texttt{i64::MIN}\rvert\) wraps to \(\texttt{i64::MIN}\) (not a positive number)
• \(\texttt{i64::MIN} \cdot (-1)\) wraps to \(\texttt{i64::MIN}\)

Division and Remainder

DIV and MOD both error with DivisionByZero when the divisor is zero. Division truncates toward zero (Rust’s default integer division behaviour).

Bit Length

BITLEN pops a value and pushes the number of bits needed to represent it in binary: \(\lfloor\log_2(a)\rfloor + 1\). Returns 0 for non-positive inputs.

Examples: BITLEN(1) = 1, BITLEN(7) = 3, BITLEN(8) = 4, BITLEN(255) = 8.

Comparison

Results are \(1_{i64}\) (true) or \(0_{i64}\) (false). All comparisons are signed.

None of these instructions have register effects.

The Iverson bracket notation \([P]\) equals \(1\) if \(P\) is true, \(0\) otherwise.

Boolean Convention

XQVM uses the integer convention for booleans: \(0\) is false, any non-zero value is true. Comparison instructions always produce exactly \(1\) or \(0\), making them directly usable as JUMPI conditions or logical operands.

Logical Boolean

Operands are treated as booleans: \(0\) is false, any non-zero value is true. Results are \(1_{i64}\) or \(0_{i64}\).

None of these instructions have register effects.

Logical vs. Bitwise

These instructions perform logical (boolean) operations. For bitwise operations on the raw i64 bit pattern, see the Bitwise instructions (BAND, BOR, BXOR, BNOT).

The key difference: \(\text{NOT}; 5 = 0\) (logically false), while \(\text{BNOT}; 5 = \mathord{\sim}5\) (bitwise complement, a large negative number).

Bitwise

Operate on raw i64 bit patterns.

None of these instructions have register effects.

Shift Behaviour

• SHL performs a signed left shift. Bits shifted out of the high end are discarded. The shift amount must be in \([0, 64)\).
• SHR performs an arithmetic (sign-preserving) right shift, not a logical shift. The sign bit is replicated, so negative values stay negative and \(\mathit{i64}{::}\mathit{MIN} \gg 1\) halves the magnitude instead of producing a positive result. This matches Rust’s i64 >> b operator and Python’s >> on integers, and it is what xq-py (spec/xqvm/ISA.md) prescribes. Where logical (zero-filling) right shift is required, mask with BAND first.
• Both shift instructions error with InvalidShift if \(b\) is outside \([0, 64)\).

Allocators

Instructions for creating quantum/combinatorial objects (models, samples) and vectors in registers.

Model Allocators

All model allocators create an XqmxModel with empty linear and quadratic coefficient maps. The parameter \(n\) determines the number of variables.

Sample Allocators

Samples hold a vector of variable assignments. The default value depends on the domain: \(0\) for binary and discrete, \(-1\) for spin. Because the discrete domain is symmetric around zero (\(\{-k, \ldots, k{-}1\}\)), the default \(0\) is always in-domain.

Vec Allocators

Domain Types

Vector Operations

Instructions for reading, writing, and querying register-held vectors.

Type Requirements

• VECPUSH, VECGET, and VECSET require the register to hold VecInt.
• VECLEN accepts both VecInt and VecXqmx.
• SLACK requires both registers to hold VecInt. It appends (does not overwrite) so that item variables and slack variables coexist in one vec pair. If cap <= 0, no elements are appended.
• All indexing operations perform bounds checking and error with IndexOutOfBounds on violation.

Example

VEC r0          ; r0 = empty VecInt
PUSH 10
VECPUSH r0      ; r0 = [10]
PUSH 20
VECPUSH r0      ; r0 = [10, 20]
PUSH 0
VECGET r0       ; stack = [..., 10]

SLACK Details

SLACK indices coeffs pops capacity (top) then start_index from the stack. It computes \(S = \lfloor\log_2(\text{capacity})\rfloor + 1\) and appends:

• To indices: \([\text{start}, \text{start}+1, \ldots, \text{start}+S-1]\)
• To coeffs: \([1, 2, 4, \ldots, 2^{S-1}]\)

This generates binary-weighted slack variables for inequality-to-equality conversion. Combined with EQUALITY, it enforces knapsack-style capacity constraints without manual coefficient loops.

VEC r5            ; indices
VEC r6            ; coeffs
; ... populate with item indices and weights ...
PUSH 3            ; start_index (first slack var index)
PUSH 10           ; capacity
SLACK r5 r6       ; appends 4 slack entries (floor(log2(10))+1 = 4)

Index Math

Utilities for mapping 2-D coordinates to flat array indices. All arithmetic is wrapping on i64.

None of these instructions have register effects.

Use Cases

IDXGRID

Computes the row-major flat index:

$$\text{index} = \text{row} \cdot \text{cols} + \text{col}$$

Used to convert 2-D grid coordinates to a flat index for models with grid dimensions set by RESIZE. For example, in a TSP with \(N\) cities and \(N\) positions, variable \(x[\text{city}][\text{position}]\) maps to flat index \(\text{city} \cdot N + \text{position}\).

IDXTRIU

Computes the upper-triangular packed index:

$$\text{index} = \frac{j \cdot (j - 1)}{2} + i \qquad (i \le j)$$

Used to index into the upper triangle of a symmetric matrix. For a pair of variables \((i, j)\) with \(i \le j\), the upper-triangular index gives a unique position in a packed representation. This is useful for iterating over quadratic coefficient pairs without double-counting.

Coefficient Access

Read and write the linear (bias) and quadratic (coupling) coefficients of a Model register. Missing entries read as \(0\); writes create the entry on the first call. All coefficient values are i64; reg must hold Model.

Linear Coefficients

Quadratic Coefficients

Sparse Storage

Coefficients are stored in sparse BTreeMap structures:

• Linear: \(\text{BTreeMap}\langle\text{usize}, \text{i64}\rangle\) keyed by variable index.
• Quadratic: \(\text{BTreeMap}\langle(\text{usize}, \text{usize}), \text{i64}\rangle\) keyed by variable pair.

Missing entries implicitly have value \(0\). Setting a coefficient to \(0\) removes it from the map, keeping memory usage proportional to the number of non-zero terms.

Key Normalisation

Quadratic coefficient keys are normalised so that \(i \le j\). Calling SETQUAD or ADDQUAD with \(i > j\) silently swaps the indices. This means \(\text{quad}[3, 5]\) and \(\text{quad}[5, 3]\) refer to the same entry.

Grid Operations

A model can optionally be given 2-D grid dimensions so that variables are addressed as \((\text{row}, \text{col})\) with flat index \(\text{row} \cdot \text{cols} + \text{col}\). reg must hold Model.

Grid Model

Grid dimensions are metadata attached to a model; they do not change the underlying coefficient storage. After calling RESIZE, the grid instructions (ROWFIND, COLFIND, ROWSUM, COLSUM) and constraint instructions (ONEHOTR, ONEHOTC) interpret linear coefficients as a 2-D matrix.

For example, a TSP with 4 cities uses a \(4 \times 4\) grid where \(x[\text{city}][\text{pos}]\) maps to flat index \(\text{city} \cdot 4 + \text{pos}\):

PUSH 16        ; size = 4 * 4
BQMX r0        ; allocate binary model
PUSH 4         ; rows = 4
PUSH 4         ; cols = 4
RESIZE r0      ; set grid dimensions

Search and Aggregation

ROWFIND and COLFIND perform linear scans over sparse coefficient entries in the specified row or column. They return the first match or \(-1\) if no entry matches the search value.

ROWSUM and COLSUM sum all linear coefficients in a row or column. These are useful for verifying constraint satisfaction (e.g. checking that exactly one variable is set in a one-hot row).

High-Level Constraints

These instructions inject QUBO penalty terms for common combinatorial constraints, expanding into linear and quadratic coefficient deltas automatically. The model register must hold a Model in model mode. Grid-based opcodes (ONEHOTR, ONEHOTC) require grid dimensions pre-set by RESIZE. Vec-based opcodes (EQUALITY, ATLEAST, ATLEASTW, REDUCE) operate on arbitrary variable sets. All coefficients are i64.

0x70 – ONEHOTR reg

Stack: \([\ldots, \text{row}, \text{penalty}] \to [\ldots]\) Register effect: mutate

Pop penalty, then row. Apply the one-hot constraint over all variables in grid row row:

$$H \mathrel{+}= \text{penalty} \cdot \left(\sum_c x_{\text{row},c} - 1\right)^2$$

Expanding (binary variables: \(x^2 = x\)):

$$\text{linear}[\text{row} \cdot \text{cols} + c] \mathrel{+}= -\text{penalty} \qquad \forall; c \in [0, \text{cols})$$

$$\text{quad}[\text{row} \cdot \text{cols} + c_i,; \text{row} \cdot \text{cols} + c_j] \mathrel{+}= 2 \cdot \text{penalty} \qquad \forall; c_i < c_j$$

0x71 – ONEHOTC reg

Stack: \([\ldots, \text{col}, \text{penalty}] \to [\ldots]\) Register effect: mutate

Pop penalty, then col. One-hot over all variables in grid column col:

$$\text{linear}[r_i \cdot \text{cols} + \text{col}] \mathrel{+}= -\text{penalty} \qquad \forall; r_i \in [0, \text{rows})$$

$$\text{quad}[r_i \cdot \text{cols} + \text{col},; r_j \cdot \text{cols} + \text{col}] \mathrel{+}= 2 \cdot \text{penalty} \qquad \forall; r_i < r_j$$

0x72 – EXCLUDE reg

Stack: \([\ldots, i, j, \text{penalty}] \to [\ldots]\) Register effect: mutate

Pop penalty, then \(j\), then \(i\). Add mutual-exclusion: penalise \(x_i = 1\) and \(x_j = 1\) simultaneously.

$$\text{quad}[i, j] \mathrel{+}= \text{penalty}$$

0x73 – IMPLIES reg

Stack: \([\ldots, i, j, \text{penalty}] \to [\ldots]\) Register effect: mutate

Pop penalty, then \(j\), then \(i\). Add implication \(i \Rightarrow j\): penalise \(x_i = 1\) with \(x_j = 0\).

$$H \mathrel{+}= \text{penalty} \cdot x_i \cdot (1 - x_j) = \text{penalty} \cdot x_i - \text{penalty} \cdot x_i \cdot x_j$$

$$\text{linear}[i] \mathrel{+}= \text{penalty}$$

$$\text{quad}[i, j] \mathrel{+}= -\text{penalty}$$

0x74 – EQUALITY model indices coeffs

Stack: \([\ldots, \text{target}, \text{penalty}] \to [\ldots]\) Register effect: read indices, coeffs; mutate model

Pop penalty, then target. Read variable indices from indices (VecInt) and coefficients from coeffs (VecInt). Expand the weighted equality constraint into QUBO terms on model:

$$H \mathrel{+}= P \cdot \left(\sum_k a_k \cdot x_{\text{idx}_k} - b\right)^2$$

Expanding:

$$\text{linear}[\text{idx}_k] \mathrel{+}= P \cdot a_k \cdot (a_k - 2b) \qquad \forall; k$$

$$\text{quad}[\text{idx}_k, \text{idx}_m] \mathrel{+}= 2P \cdot a_k \cdot a_m \qquad \forall; k < m$$

The constant term \(P \cdot b^2\) is dropped. EQUALITY is the general form of ONEHOTR/ONEHOTC — setting all \(a_k = 1\) and \(b = 1\) produces the same expansion.

0x75 – ATLEAST model indices

Stack: \([\ldots, k, \text{penalty}] \to [\ldots]\) Register effect: read indices; mutate model (grows size)

Pop penalty, then \(k\). Read variable indices from indices. Enforce \(\sum x_i \ge k\) by allocating \(S = \lfloor\log_2(N - k)\rfloor + 1\) slack variables at model.size and applying an EQUALITY expansion with target \(k\):

$$\sum_i x_{\text{idx}i} - \sum{j=0}^{S-1} 2^j \cdot s_j = k$$

Error ValueError if \(k \le 0\) or \(k > N\).

0x76 – ATLEASTW model indices coeffs

Stack: \([\ldots, k, \text{penalty}] \to [\ldots]\) Register effect: read indices, coeffs; mutate model (grows size)

Pop penalty, then \(k\). Same as ATLEAST but with arbitrary weights from coeffs. Enforces \(\sum w_i \cdot x_i \ge k\). The slack count is computed from \(\text{max_excess} = \sum w_i - k\).

Error ValueError if \(k \le 0\) or lengths of indices and coefficients differ.

0x77 – REDUCE model

Stack: \([\ldots, \text{var_a}, \text{var_b}, P_{\text{aux}}] \to [\ldots, w]\) Register effect: mutate model (grows size)

Pop \(P_{\text{aux}}\), then \(\text{var_b}\), then \(\text{var_a}\). Allocate auxiliary variable \(w\) at model.size. Add Rosenberg enforcement terms constraining \(w = x_a \cdot x_b\):

$$\text{quad}[\text{var_a}, \text{var_b}] \mathrel{+}= P_{\text{aux}}$$

$$\text{quad}[\text{var_a}, w] \mathrel{+}= -2 P_{\text{aux}}$$

$$\text{quad}[\text{var_b}, w] \mathrel{+}= -2 P_{\text{aux}}$$

$$\text{linear}[w] \mathrel{+}= 3 P_{\text{aux}}$$

Push \(w\) (the auxiliary index). Enables chaining for higher-order terms: reduce a quartic \(x_i x_j x_k x_l\) by calling REDUCE twice to get \(w_1 = x_i x_j\) then \(w_2 = w_1 x_k\), and finish with ADDQUAD on \((w_2, x_l)\).

Usage Pattern

Constraint instructions are designed to work with grid models. A typical pattern for a TSP:

; Allocate model and set grid
PUSH 16
BQMX r0
PUSH 4
PUSH 4
RESIZE r0

; Apply one-hot constraints on each row and column
PUSH 0
PUSH 4
RANGE
  LVAL r1
  LOAD r1
  PUSH 100       ; penalty weight
  ONEHOTR r0     ; each city visits exactly one position
NEXT

PUSH 0
PUSH 4
RANGE
  LVAL r1
  LOAD r1
  PUSH 100
  ONEHOTC r0     ; each position has exactly one city
NEXT

Energy Evaluation

0x7F – ENERGY model sample

Stack: \([\ldots] \to [\ldots, E]\) Register effect: read – both model and sample are read-only

This is the only instruction with two register operands.

The model register must hold a Model and the sample register must hold a Sample. Both checks are strict: a RegisterType error is raised if either register holds the wrong kind of value. The previous “model-as-sample” shortcut, where a Model could appear in the sample slot and have its linear table read as variable assignments, was removed in QUI-410 to align with spec/xqvm/HLF.md and the xq-py reference.

To populate a sample with concrete variable assignments, construct an XqmxSample in the host (via aglais_xqvm_vm::XqmxSample) and pass it to the program through a calldata slot, then INPUT it into a register before calling ENERGY. xq-rs does not currently expose a bytecode opcode to mutate sample values in-place.

Hamiltonian

Evaluates the quadratic Hamiltonian:

$$E = \sum_{i} \text{linear}[i] \cdot x_i ;+; \sum_{i < j} \text{quad}[i,j] \cdot x_i \cdot x_j$$

The result is pushed as i64. Arithmetic uses wrapping semantics on overflow.

Errors

• RegisterType – if model is not a Model or sample is not a Sample.
• SizeMismatch – if \(\lvert\text{sample}\rvert \neq \text{model.size}\).

Example

; Build a 2-variable binary model in r0:
;   linear[0] = 3, linear[1] = -2, quad[0,1] = 5.
PUSH 2
BQMX r0

PUSH 0
PUSH 3
SETLINE r0
PUSH 1
PUSH -2
SETLINE r0

PUSH 0
PUSH 1
PUSH 5
SETQUAD r0

; A freshly-allocated binary sample is initialised to all zeros, so
; H(0, 0) = 0.
PUSH 2
BSMX r1

ENERGY r0 r1
HALT

In this example, the sample is [0, 0] and the Hamiltonian evaluates to \(E = 0\). To exercise a non-zero assignment, construct an XqmxSample in host code with XqmxSample::new(Domain::Binary, vec![1, 1]) and INPUT it into r1 before calling ENERGY.

Opcode Reference

Concise reference table for every opcode in the XQVM bytecode format. Derived directly from conformance/opcodes.yaml, which is kept in sync with the Rust opcodes! x-macro and the Python Opcode enum.

For the normative bytecode specification, see spec/xqvm/SPEC.md.

Columns:

• Code – wire-encoding byte.
• Mnemonic – uppercase assembly name.
• Operands – post-opcode operand layout; empty for no-operand instructions.
• Stack – stack effect as pop → push; 0 → 1 means one value produced.
• Description – single-sentence semantic summary.

Reserved wire bytes (rejected by the decoder as illegal): 0x0D, 0x19, 0x35.

Total: 93 opcodes.

Control Flow

Register I/O

Stack Manipulation

Arithmetic

Comparison

Logical Boolean

Bitwise

Allocators

Index Math

XQMX Coefficient Access

XQMX Grid

XQMX High-Level Constraints

Special

Bytecode Format

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Verifier

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

CLI Reference

The xq binary is the unified command-line interface for XQVM. It provides three subcommands:

Installation

Build from source:

cargo build --release

The binary is at target/release/xq.

General Usage

xq <COMMAND> [OPTIONS] [ARGS]
xq --help
xq <COMMAND> --help

xq run

Execute XQVM bytecode or assembly source with optional tracing.

Usage

xq run [OPTIONS] <FILE>

Arguments

Options

Examples

Run bytecode

xq run program.xqb

Run assembly directly

xq run --text program.xqasm

Pass calldata

xq run program.xqb --calldata 10,20,30

Enable tracing

# Text trace to stderr
xq run program.xqb --trace

# JSON trace to a file
xq run program.xqb --trace --trace-format json --trace-file trace.jsonl

Custom limits

# Unlimited execution
xq run program.xqb --step-limit 0

# Low limit for testing
xq run program.xqb --step-limit 1000

Output

After execution, xq run prints:

1. Outputs – all non-default output slots with their index and value.
2. Stack – any values remaining on the stack (bottom to top).

outputs:
  [0] = Int(42)
  [1] = VecInt([1, 2, 3])
stack (bottom to top):
  7

Tracing

Text Format

Human-readable aligned columns showing each step:

• Step number
• Byte offset
• Instruction mnemonic and operands
• Stack state
• Register reads and writes
• Loop depth

JSON Format (JSONL)

One JSON object per step, suitable for machine processing:

{"step":1,"pos":0,"instruction":"PUSH1","stack":[42],"reads":[],"writes":[],"loop_depth":0}

Error Reporting

Runtime errors include the faulting instruction with a disassembled context listing:

Error: stack underflow
  ┌─ program.xqb:0x0003
  │
  │     PUSH1          42
  │ --> ADD                  ← stack underflow here
  │     HALT

xq asm

Assemble an XQVM assembly source file into binary bytecode.

Usage

xq asm <INPUT> [-o <OUTPUT>] [--stdout]

Arguments

Options

Examples

# Assemble to default output (program.xqb)
xq asm program.xqasm

# Assemble to a specific output file
xq asm program.xqasm -o build/program.xqb

# Pipe bytecode to another tool
xq asm program.xqasm --stdout | xq dism

Output

On success, prints a summary to stderr:

assembled 12 instructions (28 bytes) -> program.xqb

Error Reporting

Assembly errors include source file location and a highlighted snippet:

Error: unknown mnemonic
  ┌─ program.xqasm:3:1
  │
3 │ BADOP r0
  │ ^^^^^ unknown instruction

xq dism

Disassemble XQVM bytecode into a human-readable listing.

Usage

xq dism [FILE]

Arguments

Examples

# Disassemble a file
xq dism program.xqb

# Disassemble from stdin (pipe from assembler)
xq asm program.xqasm --stdout | xq dism

Output Format

The disassembler prints one line per instruction with byte offsets and decoded operands. Jump targets from the jump table are shown as .0, .1, etc.

0x0000: .0: TARGET
0x0001:     PUSH1          42
0x0003:     JUMP           .0

• Byte offset (0x0000:) – position in the instruction stream.
• Label (.0:) – jump table label, if one starts at this offset.
• Instruction – mnemonic and decoded operands.
• PUSH values – shown as sign-extended decimal integers.

Verify

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Runtime Limits

This page summarises the fixed and configurable limits of the XQVM runtime.

Fixed Limits

Configurable Limits

Setting the step limit to 0 sets it to u64::MAX (effectively unlimited).

Pallet Limits

When running in the Substrate pallet, additional limits apply:

Error Types

All runtime errors include the byte offset (pos) of the faulting instruction for precise diagnostics. The full error enum is defined in crates/vm/src/error.rs.

Embedding Overview

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Builder API

The InstructionBuilder provides a fluent Rust API for constructing XQVM bytecode programmatically, without going through the text assembler.

Basic Usage

#![allow(unused)]
fn main() {
use aglais_xqvm_bytecode::InstructionBuilder;

let mut b = InstructionBuilder::new();
b.emit_push(10)
 .emit_push(32)
 .emit_add()
 .emit_halt();

let program = b.build().unwrap();
}

Labels

Labels are opaque handles. Create them with label(), anchor them with place(), and reference them in emit_jump()/emit_jump_if(). Both forward and backward references work.

Backward Reference

#![allow(unused)]
fn main() {
use aglais_xqvm_bytecode::InstructionBuilder;

let mut b = InstructionBuilder::new();
let loop_top = b.label();

b.emit_push(3);
b.place(loop_top);      // anchor label at this position
b.emit_push(-1);
b.emit_add();
b.emit_copy();
b.emit_jump_if(loop_top);    // backward jump to loop_top
b.emit_pop();
b.emit_halt();

let program = b.build().unwrap();
}

Forward Reference

#![allow(unused)]
fn main() {
use aglais_xqvm_bytecode::InstructionBuilder;

let mut b = InstructionBuilder::new();
let done = b.label();

b.emit_push(0);
b.emit_jump_if(done);        // forward jump -- target not yet placed
b.emit_push(42);
b.place(done);           // anchor here
b.emit_halt();

let program = b.build().unwrap();
}

PUSH Auto-Sizing

emit_push(val) automatically selects the smallest PUSH1–PUSH8 instruction:

#![allow(unused)]
fn main() {
b.emit_push(0);         // emits PUSH1 (2 bytes)
b.emit_push(42);        // emits PUSH1 (2 bytes)
b.emit_push(1000);      // emits PUSH2 (3 bytes)
b.emit_push(i64::MAX);  // emits PUSH8 (9 bytes)
}

Register Operations

Most register instructions have a corresponding method:

#![allow(unused)]
fn main() {
use aglais_xqvm_bytecode::{InstructionBuilder, Register};

let mut b = InstructionBuilder::new();
b.emit_push(42)
 .emit_stow(Register(0))     // r0 ← Int(42)
 .emit_load(Register(0))     // push r0's value
 .emit_bqmx(Register(1))     // allocate QUBO model in r1
 .emit_halt();
}

DROP is available as emit_drop():

#![allow(unused)]
fn main() {
b.emit_drop(Register(5));  // r5 ← Int(0)
}

ENERGY

The emit_energy() method takes two register operands:

#![allow(unused)]
fn main() {
b.emit_energy(Register(0), Register(1));  // ENERGY r0 r1
}

Raw Instruction Emit

For instructions without a dedicated method, use emit():

#![allow(unused)]
fn main() {
use aglais_xqvm_bytecode::{InstructionBuilder, Instruction};

let mut b = InstructionBuilder::new();
b.emit(Instruction::Copy {})
 .emit(Instruction::Halt {});
}

Build Errors

build() validates all labels and returns errors for:

• UnplacedLabel – a label was used in a JUMP/JUMPI but never placed.
• UnusedLabel – a label was placed but never referenced by any jump.

#![allow(unused)]
fn main() {
let mut b = InstructionBuilder::new();
let ghost = b.label();
b.emit_jump(ghost).emit_halt();
assert!(b.build().is_err());  // UnplacedLabel
}

Jump Table Construction

build() automatically constructs the jump table from placed labels. Each label becomes a jump table entry with a byte range [start, end) covering its basic block. The jump table is included in the final Program.

#![allow(unused)]
fn main() {
let mut b = InstructionBuilder::new();
let l0 = b.label();
let l1 = b.label();
b.place(l0).emit_nop().emit_jump(l1).place(l1).emit_halt();

let program = b.build().unwrap();
assert_eq!(program.jump_table().len(), 2);
}

Pallet Integration

XQVM can run on-chain as a Substrate pallet. The pallet provides two extrinsics: one to store programs and one to execute them. This chapter describes the pallet’s interface, configuration, and weight model.

Configuration

The pallet is configured via the Config trait:

#![allow(unused)]
fn main() {
#[pallet::config]
pub trait Config: frame_system::Config {
    type RuntimeEvent: From<Event<Self>>
        + IsType<<Self as frame_system::Config>::RuntimeEvent>;

    /// Maximum size of a stored XQVM program in bytes.
    type MaxProgramSize: Get<u32>;

    /// Maximum number of calldata entries (i64 values).
    type MaxCallDataLen: Get<u32>;

    /// Maximum number of output slots.
    type MaxOutputSlots: Get<u32>;

    /// Maximum step limit per execution.
    type MaxStepLimit: Get<u64>;

    /// Weight charged per XQVM execution step (ref_time component).
    type WeightPerStep: Get<Weight>;

    type WeightInfo: WeightInfo;
}
}

Configuration Constants

Storage

Programs are keyed by their Blake2-256 hash for deduplication. Storing the same bytecode twice is rejected with ProgramAlreadyExists.

Extrinsics

store_program (call index 0)

Store an XQVM program on-chain.

Parameters:

Behaviour:

1. Validate the bytecode by decoding it as a Program.
2. Compute the Blake2-256 hash.
3. Check for duplicates.
4. Store the bytecode and record the owner.
5. Emit ProgramStored.

Errors: InvalidBytecode, ProgramAlreadyExists.

execute (call index 1)

Execute a stored XQVM program.

Parameters:

Behaviour:

1. Validate step_limit ≤ MaxStepLimit and output_slots ≤ MaxOutputSlots.
2. Look up the program by hash.
3. Create a VM, configure calldata, outputs, and step limit.
4. Execute the program.
5. Collect integer outputs.
6. Emit ProgramExecuted with actual steps used and outputs.
7. Refund unused weight.

Weight model:

Weight is pre-charged based on step_limit:

pre_charged = execute_base + WeightPerStep * step_limit

After execution, actual weight is calculated from the real step count:

actual = execute_base + WeightPerStep * steps_used

The difference is refunded via PostDispatchInfo. This means users pay only for the instructions actually executed, not the worst-case limit.

Errors: ProgramNotFound, StepLimitTooHigh, TooManyOutputSlots, and any VM runtime error (mapped from aglais_xqvm_vm::Error).

Events

Error Mapping

VM runtime errors are mapped to pallet errors:

Calldata Limitations

The pallet’s execute extrinsic only supports i64 calldata values (not models, vectors, or samples). For richer input types, programs must construct them internally or receive them through a different mechanism.

Workflow

A typical on-chain workflow:

1. Off-chain: Assemble the program with xq asm.
2. On-chain: Call store_program with the bytecode.
3. On-chain: Call execute with calldata and desired output slots.
4. Off-chain: Read the ProgramExecuted event to get outputs.

Conformance

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Glossary

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Stability

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.

Spec Index

This page is not yet written. QUI-977 will replace this stub with task-focused documentation for this topic.