Scaling Quantum Optimization to the Thousand-Qubit Scale with Distributed Quantum Sampling
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.
Related
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Iterative map with power-law scaling of Gamma-distributed fluctuations related to prime numbers
- Scaling Spatially Varying Distributed Lag Nonlinear Models for Nationwide Small-Area Data: A Divide-and-Conquer Approach
- Linear convergence rate analysis of Proximal-Tracking for nonsmooth distributed optimization
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
BibTeX
@misc{liaqat2026scaling,
title = {{Scaling Quantum Optimization to the Thousand-Qubit Scale with Distributed Quantum Sampling}},
author = {Amana Liaqat and Ahmed Darwish and Stephen DiAdamo and Dan Holme and Kieran McDowall and Emre Sahin and Naeimeh Mohseni and Giorgio Cortiana and Corey O'Meara},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10772},
eprint = {2610.10772},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10772},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Scaling Quantum Optimization to the Thousand-Qubit Scale with Distributed Quantum Sampling
AU - Amana Liaqat
AU - Ahmed Darwish
AU - Stephen DiAdamo
AU - Dan Holme
AU - Kieran McDowall
AU - Emre Sahin
AU - Naeimeh Mohseni
AU - Giorgio Cortiana
AU - Corey O'Meara
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10772
UR - https://arxiv.org/abs/2610.10772
AB - 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.
ER -