Combinatorial optimisation is the search for the best arrangement among exponentially many discrete options, and it has become the main testing ground for non-conventional compute (quantum annealers, gate-based QAOA variants, probabilistic bit hardware, tensor-network engines), where the current published record shows working demonstrations at tens to a few hundred variables but no settled advantage over classical solvers.
Summary
Combinatorial optimisation covers problems where the answer is a discrete configuration: which items to put in a knapsack, what order to visit cities in, how to cut a graph, which assets to hold, how to schedule cars through a paint shop. The number of candidate configurations grows exponentially with problem size, so exact solution is hopeless beyond modest sizes and practice relies on heuristics, relaxations and problem-specific preprocessing. In the non-conventional compute world these problems matter because almost all of them can be rewritten as the ground state of an Ising-type energy function, which is exactly what several unconventional hardware substrates natively minimise.
The rewriting step is where much of the engineering sits. The standard target is QUBO (quadratic unconstrained binary optimisation), with generalisations to higher-order binary forms (HOBO/PUBO) and to d-valued variables on qudits (QUDO, tensor QUDO), each with different variable counts and constraint-handling costs. Encoding choice dominates resource cost: the naive one-hot formulation of the travelling salesman problem needs O(n^2) qubits, while a compact binary register brings it to O(n log n). Constraints are handled either by penalty terms, which enlarge the problem and distort the energy landscape, or by constraint-preserving mixers such as XY-mixers that confine the evolution to the feasible subspace but incur Trotterisation error on gate-based hardware. Classical preprocessing that prunes candidate arcs before encoding cuts decision-variable counts for both classical and quantum solvers.
The solver side is a crowded field rather than a single technology. Gate-based variational methods (QAOA and its parameterisation variants, Grover-mixer QAOA for higher-order problems, feedback-based schemes), analog quantum annealing, quantum Markov chain Monte Carlo built on many-body-localised dynamics, probabilistic-bit hardware, and classical or GPU-based Ising and tensor-network engines all attack the same Ising target. Scalability is generally bought with decomposition: partition the problem into qubit-sized subproblems, solve locally, stitch classically.
The parameters that decide the outcome are: qubits or spins per problem variable after encoding; how constraints are enforced and what that does to the landscape; trainability of the variational parameters, which is governed by barren-plateau structure now being characterised analytically through dynamical Lie algebras; and, decisively, what a well-tuned classical baseline achieves on the same instance.
Evidence base
- 4 May 2026: compact binary-register encoding cuts TSP data-qubit requirements from O(n^2) to O(n log n), with 100%, 100% and 95.5% best average success rates on 4, 5 and 6 city instances, and a two-qubit divide-and-conquer run of a 5-city instance on SpinQ NMR hardware.
- 5 May 2026: a chance-constrained knapsack scheme ran on IBM Heron processors at circuit depths up to 177 and 3,443 gates on up to 150 qubits, with results the authors say indicate improvement over classical optimisation schemes.
- 5 May 2026: for problems with a single global equality constraint spanning all variables, Trotter errors significantly impair XY-mixer performance and penalty-based methods are preferable.
- 14 May 2026: benchmarking feedback-based quantum optimisation against classical counterparts found quantum advantageous in solution quality but slower to converge, with one classical algorithm showing significant scalability on higher-order unconstrained binary problems.
- 14 May 2026: formulating qubit allocation as a combinatorial optimisation problem and solving it with a reinforcement learning policy cut SWAP overhead by 65 to 85% versus existing quantum compilers on MQTBench and Queko circuits.
- 2 June 2026: distributed multi-GPU tensor-network contraction gave 7 to 173 times extra speedup beyond slicing on an 8-GPU DGX H100 node and 42 to 67,869 times at 1,024 H100 GPUs.
- 5 June 2026: the Probabilistic Approximate Optimization Algorithm was demonstrated on a 64x64 perimeter-gated SPAD array in 0.35 micron CMOS, reaching high approximation ratios on 26-spin Sherrington-Kirkpatrick instances with 2p parameters up to p = 17 layers.
Open questions
- Does the reported improvement over classical optimisation schemes on the 150-qubit Heron chance-constrained knapsack runs survive comparison against a state-of-the-art stochastic-programming solver on the same instances?
- Can any quantum optimisation heuristic avoid the dequantisation pattern where a classical counterpart matches its solution quality and converges faster?
- Is there a constraint-handling method that works for global equality constraints spanning all variables without either penalty-induced landscape distortion or crippling Trotter error?
- Do decomposition frameworks that split problems into qubit-sized subproblems retain solution quality as instance size grows, or does the classical stitching stage become the binding constraint?
Assessment drafted 2026-08-31 from up to 18 KB sources using the technology-scorecard framework; scores are a draft read pending review.