Scaling Quantum Optimization to the Thousand-Qubit Scale with Distributed Quantum Sampling

The gist: Scaling quantum optimization to thousand-qubit scale with distributed quantum sampling demonstrates an executable path for deploying gate-based quantum sampling on thousand-variable constrained optimization problems on current hardware.

Problem Formulation

The Minimum Birkhoff Decomposition (MBD) seeks a sparse weighted sum of matchings and is a challenging optimization problem with applications in network scheduling and energy trading<ref:2610.10772#pg2>. The MBD problem is formulated as an l0-norm minimization over symmetric doubly substochastic matrices to minimize the number of constituent matchings needed to reconstruct the demand matrix D∗<ref:2610.10772#pg4>. The objective function for the Extended Fully-Corrective Frank–Wolfe (E-FCFW) framework is the scaled squared Frobenius norm distance between the target demand D∗ and the approximation matrix D<ref:2610.10772#pg5>.

Methodology

The pipeline combines several techniques to scale quantum-assisted decomposition:

1. Single-layer (p = 1) QAOA is used to supply di-∗ stephen@qoroquantum.de verse matching candidates and optimize their weights classically<ref:2610.10772#pg4>. The QUBO Hamiltonian C(x) is defined using the ordered-pair convention, where the penalty λ = 0.2 discourages collisions<ref:2610.10772#pg4>.

2. Spectral partitioning is employed to reduce circuit width and routing overhead by clustering affinity-matrix eigenvectors<ref:2610.10772#pg5>.

3. Local samples are combined by batched Cartesian products or pruned beam search, followed by a greedy repair pass to enforce matching feasibility<ref:2610.10772#pg6>.

4. Spatial circuit packing executes independent subproblems concurrently on multiple QPUs using disjoint regions of the 156-qubit Heron lattice<ref:2610.10772#pg10>.

Experimental Results

The study evaluated the pipeline on the 1,354-node PEGASE bus test case, which requires 1,710 qubits in an unpartitioned encoding<ref:2610.10772#pg4>. The best reported hardware result uses a 50-qubit partition bound<ref:2610.10772#pg4>. Impressive results showed that repaired QAOA samples achieve lower residual decomposition error than both simulated annealing and uniform random sampling baselines<ref:2610.10772#pg7>.

The spatial circuit packing reduces hardware execution time by approximately a factor of three<ref:2610.10772#pg4>. Partitioning at ps = 50 retains convergence close to the unpartitioned hardware run, supporting its use to reduce circuit size without losing the useful sampling behavior in this instance<ref:2610.10772#pg7>.

Conclusion and Future Work

The results establish an executable distributed workflow for a problem class whose classical difficulty makes it relevant to the search for quantum advantage<ref:2610.10772#pg4>. The ps = 50 results provide evidence for this requirement, as aggressive truncation of quantum correlations degrades candidate quality<ref:2610.10772#pg6>. Future work will extend this evaluation across the full benchmark suite with comprehensive runtime accounting and comparisons against strong classical solvers<ref:2610.10772#pg4>. The next step is to target partitions of at least 100 qubits and vary their density systematically<ref:2610.10772#pg4>. The initial results show that the method consistently reaches the target tolerance within 15 outer iterations and achieves substantially sparser decompositions than classical greedy baselines<ref:2610.10772#pg9>.

How it works

The E-FCFW algorithm augments the candidate pool at each iteration by combining the deterministic maximum-weight matching MMW with a sampling subroutine that generates d diverse candidate matchings Msample<ref:2610.10772#pg4>. To restore feasibility without introducing unselected edges, greedy repair sorts the candidate edge set E˜ by descending residual weight and accepts an edge if and only if both endpoints are currently unoccupied<ref:2610.10772#pg6>. This procedure runs in O(E˜ log E˜) time and guarantees matching feasibility<ref:2610.10772#pg6>.

Partitioning and Packing Layouts

The PEGASE-1354 layout shows 41 subgraphs with an edge bound ps = 50, where colors distinguish neighboring partitions<ref:2610.10772#pg9>. Spatial circuit packing places four independent circuits on one Heron processor to be run simultaneously within the same QPU run for a higher ratio of QPU utilization<ref:2610.10772#pg10>. This reduces dispatch rounds by up to 4× in the reported configurations, and the observed PEGASE execution-time reduction is approximately 3×<ref:2610.10772#pg10>.

MPS Mirror Diagnostic

The MPS mirror diagnostic assesses truncation error using Maestro’s native mirror fidelity check, which implements a deterministic compute-uncompute diagnostic related to the mirror-circuit principle<ref:2610.10772#pg10>. Higher bond dimensions improve both mirror fidelity and final cost in Fig. 2(b)<ref:2610.10772#pg6>. Subgraphs that contain dense loop structures or clustered degree-3 junctions produce tightly coupled line graphs that require extensive SWAP routing when mapped back onto Heron’s physical qubits<ref:2610.10772#pg6>. The next scaling step should control partition density alongside size, retaining enough connectivity to preserve useful quantum correlations while keeping routed depth manageable<ref:2610.10772#pg4>.

Deployment on PEGASE-1354

The PEGASE-1354 transmission graph would require 1,710 qubits under an unpartitioned edge encoding<ref:2610.10772#pg4>. Spectral partitioning at ps = 50 instead produces 41 subgraphs for distributed execution<ref:2610.10772#pg9>. The partition bound ps counts edges (qubits)<ref:2610.10772#pg9>. Logical two-qubit depth reflects the maximum degree of interacting edge pairs, which governs transpiled depth on heavy-hex hardware<ref:2610.10772#pg6>. The partition bound ps counts edges (qubits)<ref:2610.10772#pg9>.

Stitching and Feasibility Repair

Raw stitched candidates frequently violate matching feasibility due to two distinct sources of collisions: intra-partition collisions and boundary collisions<ref:2610.10772#pg6>. Feasibility repair resolves these conflicts via a greedy pruning pass over the candidate edge set E˜, which sorts edges by current residual weights and accepts an edge if both endpoints are currently unoccupied<ref:2610.10772#pg6>. Unselected edges (xj = 0) are never introduced, ensuring repair acts strictly as a conflict-resolution filter on the quantum candidate rather than an augmenting heuristic<ref:2610.10772#pg6>.

Classical Update and Hardware Execution

E-FCFW updates the nonnegative weights subject to its cardinality bound and removes zero-weight matchings<ref:2610.10772#pg4>. The loop stops at the target error, a relative improvement plateau, or the iteration limit<ref:2610.10772#pg9>. Algorithm 1 gives the full workflow<ref:2610.10772#pg9>. Qoro’s scheduler orders circuits by size and packs them into execution rounds with a shared shot count<ref:2610.10772#pg10>. The observed PEGASE execution-time reduction is approximately 3×<ref:2610.10772#pg10>.

Parameter Calibration and Sampling Budgets

Offline training uses small prototypes with similar topology, degree distribution, and edge-weight encoding to the target family<ref:2610.10772#pg9>. Angles are calibrated offline and transferred across related subgraphs instead of being optimized at each E-FCFW iteration<ref:2610.10772#pg4>. For the PEGASE bus test case, the calibration landscape is evaluated on a representative 49-qubit partition with Maestro at bond dimension 128<ref:2610.10772#pg10>. The marked minimum near (γ0, β0) = (2.49, 0.16) supplies fixed execution angles for the PEGASE-1354 transmission graph experiments<ref:2610.

1. The improved system can perform large-scale network scheduling and energy trading by solving Minimum Birkhoff Decomposition (MBD) problems with sparse approximations, as demonstrated by retaining 50 to 75 matchings in preliminary work on MBD track up to 4,096 variables.

2. The system will achieve significant throughput speedups in hardware execution because spatial circuit packing reduces hardware execution time by approximately a factor of three, allowing independent subproblems to be executed concurrently on quantum processors.

3. The AI can maintain high candidate quality during distributed optimization by utilizing repaired QAOA samples which achieve lower residual decomposition error than both simulated annealing and uniform random sampling baselines.

4. The system will scale beyond the width of a single processor by employing a workflow that combines spectral partitioning, spatial circuit packing, and classical feasibility repair, providing an executable path for deploying gate-based quantum sampling on thousand-variable constrained optimization problems on current hardware.

The Minimum Birkhoff Decomposition (MBD) seeks a sparse weighted sum of matchings and is a challenging optimization problem with applications in network scheduling and energy trading. We scale a quantum-assisted decomposition method by combining single-layer QAOA sampling with Extended Fully-Corrective Frank-Wolfe (E-FCFW) optimization, spectral graph partitioning, and greedy feasibility repair. We demonstrate the pipeline on the 1,354-node PEGASE bus test case (representing a 1,354-bus transmission grid with 1,710 transmission lines), whose 1,710 edges define a native 1,710-variable matching optimization problem requiring 1,710 qubits in the unpartitioned encoding. Partitioning enables distributed execution on IBM superconducting quantum processors. The best reported hardware result uses a 50-qubit partition bound, while reducing partitions to 20 qubits degrades convergence in the partition-size comparison. Larger partitions are more demanding for matrix product state (MPS) simulation, and bond-dimension tests show that truncating quantum correlations reduces candidate quality. The results therefore motivate retaining a substantive quantum sampling task within each partition as the overall problem scales. On the PEGASE-1354 benchmark, repaired QAOA samples achieve lower residual decomposition error than both simulated annealing and uniform random sampling baselines, while spatial circuit packing reduces hardware execution time by approximately a factor of three. These results demonstrate that combining spectral partitioning, spatial circuit packing, and classical feasibility repair provides an executable path for deploying gate-based quantum sampling on thousand-variable constrained optimization problems on current hardware.