Graph-Aware Exact Branch-and-Bound with Device Profiles for Static Qubit Allocation

Static qubit allocation is a combinatorial optimization problem that maps logical qubits to physical qubits on a quantum device to minimize interaction costs. Because this is a form of the Quadratic Assignment Problem (QAP), it is computationally expensive to solve exactly. The author asks whether information inherent in the fixed physical device graph and partial search states can be used to prune the branch-and-bound search tree more efficiently than existing distributed methods.

The study proposes a two-part optimization strategy. First, it implements a combinatorial bundle that includes: (1) assigned-cost filtering to quickly discard sub-optimal branches; (2) dynamic symmetry pruning that uses automorphisms of the device graph to identify and skip equivalent placements; and (3) conditioned parent-LAP screening, which uses the parent node's assignment certificate to reject children before constructing their specific lower-bound matrices. Second, the author introduces an engineering bundle that precomputes circuit-independent device artifacts—such as distance histograms for all possible physical sets—allowing for constant-time lookups during the search process.

The proposed method demonstrates substantial performance improvements over the existing Gilmore-Lawler bound (GLB) baseline. In single-threaded configurations, the algorithm achieved geometric-mean speedups of 2.98x and 13.27x on standard test instances. When scaled to 60 threads on a single shared-memory server, the system successfully certified the optimality of all instances in the Boeblingen–Cairo experiment within 30 minutes, a task that previously required significantly more distributed compute resources.

Exact qubit allocation is critical for establishing a gold standard against which heuristic mappers can be measured. By reducing the resource requirements for exact solvers, this work makes it feasible to compute optimal mappings for larger or more complex quantum devices, providing deeper insights into which device properties contribute to the difficulty of specific allocation instances.