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

AI summary

Overview

Research area: Quantum optimization, specifically distributed quantum-assisted constrained graph decomposition, combining QAOA sampling with classical Frank-Wolfe optimization on superconducting hardware. Technical level: Intermediate. Readers should be comfortable with QAOA circuits, QUBO formulations, graph matching, and the Frank-Wolfe framework. Scope: The paper evaluates whether spectral partitioning, single-layer QAOA sampling, classical feasibility repair, and spatial circuit packing can make a 1,710-edge constrained optimization problem executable across current IBM quantum processors while retaining a substantive quantum sampling task per partition.

What This Paper Is About

Minimum Birkhoff Decomposition (MBD) asks for the sparsest weighted sum of matchings that reconstructs a network demand graph, and it is NP-hard. The paper tests a pipeline that uses shallow QAOA circuits to generate diverse matching candidates, then lets a classical Extended Fully-Corrective Frank-Wolfe (E-FCFW) solver choose and weight them. Because the target PEGASE-1354 instance would need 1,710 qubits in an unpartitioned edge encoding, the work partitions the problem into smaller subgraphs and executes them concurrently on IBM Heron processors.

Key Contributions

1. A distributed quantum-assisted decomposition pipeline that combines single-layer (p = 1) QAOA sampling, E-FCFW, multi-way spectral partitioning, batched Cartesian stitching, and greedy feasibility repair.
2. A demonstration on the PEGASE-1354 bus test case (1,354 vertices, 1,710 edges), where partitioning at a 50-qubit bound produces 41 subgraphs for execution on IBM superconducting hardware.
3. Spatial circuit packing on the 156-qubit Heron lattice, placing two 38-qubit and two 34-qubit circuits across 144 qubits and reducing measured execution time by approximately a factor of three.
4. An empirical characterization of the design space: partition-size trade-offs, matrix product state (MPS) bond-dimension effects on candidate quality, the dependence of transpiled two-qubit depth on local interaction density rather than qubit count, and an ablation isolating the role of greedy repair.

Main Findings

• QAOA outperforms tested classical baselines: Under identical 50-qubit partitioning and the same repair procedure on PEGASE-1354, QAOA samples achieve lower residual decomposition error than simulated annealing and uniform random sampling.
• Partition size matters: The best reported hardware result uses a 50-qubit partition bound. Reducing partitions to 20 qubits degrades convergence because too many edges are cut; partition bounds of 50 and 80 significantly improve on 20.
• Spatial packing trades quality for speed: Unpacked hardware execution closely tracks 128-bond-dimension MPS simulation and reaches 1.11 × 10⁻⁶ at the 20-round limit. Packed execution stops at its round-17 plateau with error 1.58 × 10⁻⁶ while reducing measured execution time by approximately 3×. The final convergence difference is 4.7 × 10⁻⁷.
• Entanglement retention affects quality: Higher MPS bond dimension improves both mirror fidelity and final decomposition cost. Aggressive partitioning at 20 qubits yields shallow circuits approximable at bond dimension χ ≤ 16, but convergence deteriorates.
• Depth follows topology, not width: An 80-qubit circuit has transpiled two-qubit depth 67, whereas circuits with only 42–52 qubits reach depths 110–169. Dense loop structures and clustered degree-3 junctions create tightly coupled line graphs requiring extensive SWAP routing.
• Greedy repair is essential: Discarding invalid matchings without repair stalls QAOA convergence near 10⁻⁵, while uniform random sampling without repair yields zero valid matchings. Random sampling with repair retains residual error above 2 × 10⁻⁶, whereas QAOA with the same repair reaches 1.1 × 10⁻⁶.
• Simulated annealing plateaus early on the 120-node benchmark: SA triggers the plateau criterion at round 18 with decomposition length 15, while QAOA continues to improve.
• Preliminary QOBLIB results: On three MBD benchmark instances up to 4,096 variables, partitioned QAOA on IBM Heron hardware reached the target tolerance within 15 outer iterations and retained 50 to 75 matchings, compared with over 250 for the Birkhoff+ greedy baseline.
• Error mitigation was counterproductive here: Dynamical decoupling with the XpXm pulse sequence and gate twirling with 32 randomizations degraded candidate quality on these partitioned workloads, so hardware runs used depth-minimized compilation instead.

Methodology in Plain English

Each edge of the graph becomes a qubit, with a 1 meaning the edge is selected. A QUBO cost function rewards edges with large residual weight and penalizes pairs of edges that share an endpoint, using a penalty strength λ = 0.2. A single-layer QAOA circuit prepares a superposition over candidate matchings, using angles calibrated offline: (0.5, −0.5) for the 120-node benchmark and approximately (2.49, 0.16) for PEGASE. The residual graph is repartitioned at every outer iteration using multi-way spectral partitioning, with a cap of p_s edges—and therefore p_s qubits—per subgraph. Local samples are recombined by batched Cartesian products, then a greedy repair pass sorts selected edges by descending residual weight and accepts an edge only if both endpoints are unoccupied. The top five distinct valid candidates, plus a global maximum-weight matching, enter the E-FCFW active set, where a cardinality-constrained quadratic program updates the matching weights. The loop stops at normalized error 10⁻⁶, relative improvement of at most 10⁻³, or 20 iterations.

Why This Matters

The work shows an executable route for running gate-based quantum sampling on constrained optimization problems larger than a single processor, without claiming quantum advantage. It argues that partitions must retain a genuinely quantum sampling task—small, easily simulated fragments would remove the reason to use a quantum processor. The bond-dimension study provides evidence that truncating quantum correlations degrades candidate quality, marking a useful regime rather than proof of classical intractability.

Real-world applications:

• Network scheduling, where fewer matchings reduce switching and reconfiguration overhead.
• Optical switching in communication networks.
• Peer-to-peer energy trading, the focus of the acknowledged SparQ grant.
• Operational planning on large transmission grids, represented by the 1,354-bus, 1,710-line PEGASE model of a European high-voltage network.

Industry relevance: The collaboration spans Qoro Quantum, the National Quantum Computing Centre, the Hartree Centre, and E.ON Digital Technology, and runs on IBM's ibm_kingston and ibm_marrakesh processors. It connects quantum software orchestration, HPC simulation, and energy-sector optimization in one pipeline.

Future Directions

• Target partitions of at least 100 qubits and vary their density systematically, since Table 1 shows width and density must be optimized together.
• Extend the preliminary QOBLIB MBD evaluation across the full benchmark suite with comprehensive runtime accounting and comparisons against strong classical solvers.
• Control partition density alongside size, retaining enough interactions to challenge classical sampling while keeping routed two-qubit depth manageable.
• Establish whether intermediate-density modular networks, such as power transmission grids, are a regime where quantum sampling offers distinct utility rather than just comparable behavior.

Target Audience

Quantum optimization researchers studying QAOA sampling and hybrid quantum-classical algorithms; power systems and energy trading engineers interested in combinatorial scheduling and decomposition; practitioners building distributed quantum workflows on superconducting hardware; and HPC or quantum software engineers working on circuit packing, transpilation, and orchestration.

Authors’ abstract

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.