The size dependence of QUBO penalty parameters: calibrating the Quadratic Knapsack Problem on physical hardware

Details

Supervisors

Creemers, Stefan

Faculty

Louvain School of Management

Degree label

Master [120] : ingénieur de gestion, à finalité spécialisée

Abstract

Solving a constrained combinatorial problem on a quantum annealer requires absorbing the constraint into the objective as a penalty term, and the coefficient of that term decides whether the hardware returns anything usable. For the Quadratic Knapsack Problem the rules for choosing it have been characterized almost entirely in simulation, where minor embedding, chain integrity and finite coupler precision do not exist. This thesis measures what those rules are worth on a physical D-Wave processor. Three protocols divide the question. A log-linear regression fitted on 1 437 calibrations against a classical exact oracle returns a size exponent of 0.972 (s.e.±0.034, clustered by design cell) where the leading published rule reports 0.09, a disagreement of an order of magnitude established with no hardware involved and consistent with QPU campaigns at three instance sizes. That rule is fitted on a coefficient optimal under classical repair post-processing, where the quantity a processor needs is the penalty that enforces the constraint unaided. The slack encoding of the capacity constraint returns no viable run across 311 attempts on two topologies, failing on Zephyr because its auxiliary variables exceed the largest embeddable clique and on Pegasus, where the embedding succeeds, because no penalty value brings the solution weight down to capacity before the chains break. Transfer between instances works by region rather than by point, a single calibrated pair overrunning capacity on two instances of six and filling the knapsack to eight per cent of its capacity on a third, while the fitted rule stops working altogether above 25% density. Every one of the ten Billionnet & Soutif instances at 𝑛 = 100 and density 25% nonetheless admits a penalty setting under which the processor returns a feasible solution with reliable chains, and eight reach the proven optimum exactly. One methodological result cuts across the three protocols: the same grid supports opposite conclusions about the quadratic penalty coefficient depending on whether a chain-break reliability criterion is applied, which bears on how benchmark results on annealing hardware should be reported.