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 sample is binary and that the partition constraint holds, then 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

Solver selection and install extras are the same for every example: see Using the Examples and Solving Overview. The default is dwave-cpu, and a non-default solver will not reproduce the canonical result.

Canonical output

example-smoke validates both interpreters produce valid == 1 with --seed 42 --solver dwave-cpu. The smoke test is invariant-based – it checks validity, not exact output.