QubitFlow method: objective, circuit, search and verification

01The problem

There are n jobs, with 4 ≤ n ≤ 6. Job j has a positive whole-number cost c_j and a non-negative value v_j, with at most two decimal places. A plan chooses some jobs, written as a bit string x with x_j = 1 when job j is chosen. The goal is the plan with the greatest total value whose total cost stays within a whole-number budget B ≥ 0. This is the 0/1 knapsack problem, kept small on purpose so every answer can be checked exhaustively.

V (x) = \sum_{j} v_{j} x_{j}, C (x) = \sum_{j} c_{j} x_{j}, maximise V (x) subject to C (x) \leq B

Value, cost and the constraint

02Objective and penalty

QAOA minimises an energy, so the constraint is folded into the objective as a penalty on how far a plan is over budget:

E (x) = - V (x) + λ \cdot \max (0, C (x) - B), λ = \sum_{j} v_{j} + 1

Energy of a plan; lower is better

Why the penalty is safe. Costs and the budget are whole numbers, so a plan that is over budget is over by at least 1. Its energy is therefore at least $- \sum v_{j} + λ = 1$ . Every plan within budget has energy $- V (x) \leq 0$ , and the empty plan is always within budget. So every valid plan has strictly lower energy than every over-budget plan, and the lowest-energy plan is the best valid plan. An automated test checks this on 300 random inputs.

The circuit uses the energy divided by λ, so valid plans lie in (−1, 0] and the penalty part is a whole number:

H (x) = \frac{E (x)}{λ} = - \frac{V (x)}{λ} + \max (0, C (x) - B)

Normalised cost function, the diagonal of the cost operator

The max(0, ·) penalty is applied directly as a diagonal phase, which is exact in a state-vector simulation. Running it on physical hardware would need slack qubits or a quadratic penalty. QubitFlow does not model that.

03Encoding

Each job is one qubit, so the 2ⁿ computational basis states are exactly the 2ⁿ plans: 16 to 64 of them. Basis index x stores job j in bit j. On screen, plans are written in job order with job 1 first (for example 011000 means jobs 2 and 3), which is the reverse of Qiskit’s little-endian display.

04The circuit

QubitFlow uses the Quantum Approximate Optimization Algorithm (QAOA) of Farhi, Goldstone and Gutmann [1], with the standard X mixer. Starting from the uniform superposition, each of p layers applies a cost phase and then a mixer:

| ψ (γ, β) ⟩ = \prod_{k = 1}^{p} e^{- i β_{k} \sum_{j} X_{j}} e^{- i γ_{k} H} {| + ⟩}^{\otimes n}

QAOA state for p layers

The cost layer multiplies the amplitude of plan x by $e^{- i γ H (x)}$ . The mixer applies $e^{- i β X} = \cos β \cdot I - i \sin β \cdot X$ to every qubit; this is Qiskit’s RX(2β). The X terms commute, so the order of the qubits inside a mixer layer does not matter. The mixer only moves amplitude between plans that differ in one job.

05Simulation

The simulator stores all 2ⁿ complex amplitudes in two Float64Array buffers (real and imaginary parts) and applies the operations above exactly. Probabilities are squared magnitudes. Each angle setting costs about p·n·2ⁿ arithmetic operations, so a 6-job search takes a few milliseconds in a browser.

Correctness is checked against an independent implementation. A Python script builds every circuit as dense 2ⁿ×2ⁿ matrices with numpy, taking the mixer as a matrix exponential from an eigendecomposition, and the TypeScript amplitudes must match it to within 10⁻¹⁰. Further tests check normalisation over 200 random layers and known gate identities.

Because the simulation touches all 2ⁿ amplitudes, it can never be faster than simply enumerating the 2ⁿ plans. QubitFlow makes no speed-up claim.

06Choosing the angles

The angle search is bounded and fully deterministic:

Grid. For one layer, 49 values of γ in [0, 4π] by 12 values of β in [0, π). That is 588 trials. β and β + π differ only by a global phase, and (γ, β) → (−γ, −β) gives the conjugate state with identical probabilities, so this box covers everything. γ spans two periods of the whole-number penalty phase.
Refinement. Nelder–Mead [4] starts from the best grid point, kept inside the box and limited to 60 evaluations.
More layers. Each extra layer starts from the better of two points: the INTERP extension of the previous angles [3], or the previous angles padded with a zero layer, which reproduces the previous score exactly. Nelder–Mead then refines from there. Adding a layer can therefore never make the result worse.

The search does not minimise the plain mean energy ⟨H⟩. It minimises the conditional value at risk (CVaR) of the energy with α = 0.3 [2]:

{CVaR}_{α} = \frac{1}{α} \sum_{x in order of increasing H} \min (p_{x}, remaining mass) \cdot H (x)

The mean energy of the lowest-energy 30% of the outcome distribution

The reason is empirical, not cosmetic. With a large penalty, the plain mean is dominated by over-budget plans and pushes the state towards cheap plans, often the empty plan. On the development set, the plain-mean search found the optimal plan only 6.3% of the time; CVaR with α = 0.3 found it 72.3% of the time. The value of α and the γ range were chosen once, on that development set, and were then frozen.

07Reading out a plan

The final state is sampled 1,024 times by default. A seeded mulberry32 generator drives inverse-CDF sampling, so the same seed always draws the same shots. The candidate is the most frequently sampled plan, the “most likely bitstring” rule used in IBM’s QAOA tutorial [5]. Ties go to the higher simulated probability, then the lower index.

QubitFlow deliberately does not take the best-scoring sample instead. With 1,024 shots over at most 64 plans, that would quietly become a classical search over almost every plan. Picking the most frequent sample keeps the candidate a pure output of the circuit.

08Verification

Exact checker. It enumerates all 2ⁿ plans and keeps the best valid one, breaking ties by lower cost and then lower index. In tests it agrees with a separate dynamic-programming knapsack solver on 600 random inputs and with Python’s itertools on the fixtures.
Greedy baseline. It takes jobs in order of value per unit cost while they fit, comparing ratios exactly with whole-number cross-multiplication.
Independence. The QAOA code runs in its own Web Worker and never imports the exact checker. A test reads the source files and fails if that ever changes.
Grading. Each plan is reported with its value, its cost, whether it is within budget, and its gap from the optimum. The verdict text is generated from those numbers, including when the circuit does worse than greedy.

Test runs and browser checks are listed on the Verification page.

09Benchmark protocol

There are two seeded sets of 300 random problems each, with 4 to 6 jobs, costs 1–9, values 0–20, and a budget of 30–70% of the total cost. The development set (seed 987654321) was used once to choose α and the γ range. The hold-out set (seed 20261009) was not used for any choice. The showcase example is in neither set. The figures quoted on this site come from the hold-out set; an automated test recomputes them, and the Benchmarks page recomputes them in your browser.

10The optional model

A small language model (LFM2.5-350M, 4-bit, pinned to one revision) can run on your GPU through Transformers.js and WebGPU. It does two jobs and nothing else.

Drafting a job table from a sentence. Decoding is constrained to a JSON schema, and the result is validated again with the same strict rules as typed input. You must confirm every cost and value before planning.
Rewording the result. Code states one fact per planner, and the model rewords one sentence at a time. Each sentence must keep every job name, every number and the comparison word, and must add no numbers or money or speed words. A sentence that fails is replaced by the code’s wording, and the page marks it as replaced.

In testing, the model sometimes swapped value and cost, invented money units, and once described an over-budget plan as acceptable. Those failures are why the checks exist.

11Limitations

Problems are small by design: 4 to 6 jobs. A classical simulation of the circuit cannot be faster than enumerating the plans.
The penalty is applied as an exact diagonal phase. Hardware would need a different encoding.
On the hold-out set the circuit’s candidate is optimal less often than the greedy planner. The figures are published on the Benchmarks page.
Different JavaScript engines may differ in the last bits of Math.sin and Math.cos, which could, rarely, change a sample at a boundary. Replays between Chrome and Node (the same engine) match exactly.
The optional model needs WebGPU. A CPU fallback does not work with this model, because ONNX Runtime’s WebAssembly build lacks one of its operators.

12References

E. Farhi, J. Goldstone and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv:1411.4028 (2014).
P. Kl. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli and S. Woerner, “Improving Variational Quantum Optimization using CVaR,” Quantum 4, 256 (2020).
L. Zhou, S.-T. Wang, S. Choi, H. Pichler and M. D. Lukin, “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices,” Physical Review X 10, 021067 (2020).
J. A. Nelder and R. Mead, “A Simplex Method for Function Minimization,” The Computer Journal 7(4), 308–313 (1965).
IBM Quantum, “Quantum approximate optimization algorithm” tutorial, quantum.cloud.ibm.com.
Hugging Face, Transformers.js documentation, huggingface.co/docs/transformers.js.