PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Amana Liaqat, Ahmed Darwish, Stephen DiAdamo, Dan Holme, Kieran McDowall, Emre Sahin, Naeimeh Mohseni, Giorgio Cortiana, Corey O'Meara

arXiv:2610.10772v1quant-phcs.ETmath.OC

TL;DR

MBD seeks sparse matching decompositions, and the paper asks whether partitioning can scale quantum-assisted constrained optimization beyond an individual processor’s width. It combines QAOA sampling with E-FCFW, spectral partitioning, and feasibility repair. On PEGASE-1354, QAOA samples achieve lower residual decomposition error than simulated annealing and random sampling, while spatial packing reduces execution time by approximately a factor of three.

  • Problem

    The paper asks whether partitioning can make quantum-assisted constrained optimization practical beyond an individual processor’s width for the sparse matching-decomposition problem.

    Source: §I · p. 1

  • Method

    The approach combines single-layer QAOA candidate sampling with E-FCFW, spectral partitioning, reconstruction, and greedy feasibility repair.

    Source: §I · p. 1

  • Results

    At ps = 50, QAOA sampling achieves lower residual decomposition error than simulated annealing and random sampling, while spatial packing reduces execution time by approximately a factor of three.

    Source: D. Deployment on PEGASE-1354 · p. 5, §V · p. 6

  • Takeaways & Limitations

    The PEGASE-1354 results demonstrate an executable distributed workflow for gate-based quantum sampling on a problem whose classical difficulty makes it relevant to the search for quantum advantage.

    Source: §V · p. 6

    The results provide evidence of a useful sampling regime, not proof of classical intractability or quantum advantage.

    Source: §V · p. 6

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper motivates sparse matching decompositions for network applications and asks whether quantum-assisted constrained optimization can scale beyond one processor’s width. It formulates MBD as minimizing the number of matchings in a decomposition, a problem that is NP-hard even though finding an individual maximum-weight matching is polynomial-time solvable.

I. INTRODUCTION

  • Quantum-assisted constrained graph decomposition is the scaling target; single-layer QAOA supplies diverse matching candidates while classical E-FCFW optimizes their weights, without establishing an advantage on these instances.The pipeline combines spectral partitioning, reconstruction, and greedy repair to execute beyond an individual processor’s width.Source: §I · p. 1

II. PROBLEM FORMULATION

  • The formulation represents network demand as a sparse linear combination of valid matchings and reviews E-FCFW as a framework for producing sparse graph representations.The framework augments classical Frank-Wolfe steps with diverse candidate sampling.Source: §II · p. 2

A. Minimum Birkhoff Decomposition

  • MBD minimizes the number of matchings needed to reconstruct the demand matrix, and this cardinality-minimization problem is NP-hard.On non-bipartite graphs, double substochasticity alone is insufficient for an exact decomposition.Source: A. Minimum Birkhoff Decomposition · p. 2

B. The Extended Fully-Corrective Frank-Wolfe Framework

E-FCFW minimizes the distance between the target demand and its decomposition while expanding and correcting a pool of matching candidates. It combines a deterministic maximum-weight matching with additional diverse samples and imposes a cardinality restriction.

B. The Extended Fully-Corrective Frank-Wolfe Framework

  • The objective is the scaled squared Frobenius distance between the target demand matrix D* and approximation matrix D.The framework seeks sparse approximations using Frank-Wolfe optimization.Source: B. The Extended Fully-Corrective… · p. 2
  • At each iteration, standard Frank-Wolfe queries a linear minimization oracle that finds a maximum-weight matching on the residual graph.The residual graph is D* − D^k.Source: B. The Extended Fully-Corrective… · p. 3
  • E-FCFW re-optimizes weights over collected matchings and augments the active pool with both a maximum-weight matching and diverse sampled candidates.It retains at most k + 1 positive weights; weight optimization on a fixed support is a convex quadratic program, while support selection remains combinatorial.Source: B. The Extended Fully-Corrective… · p. 3

III. METHODOLOGY

Each E-FCFW iteration partitions the residual graph, samples local QAOA circuits, reconstructs global matchings, and updates decomposition weights.

III. METHODOLOGY

  • Each E-FCFW iteration partitions the residual graph, samples local QAOA circuits, reconstructs global matchings, and updates decomposition weights.Calibration, reconstruction settings, pseudocode, and scheduling details are collected in Appendix A.Source: §III · p. 3

A. QAOA Matching Sampler

The method samples edge-selection candidates with single-layer QAOA, partitions residual graphs, and reconstructs feasible global matchings. Classical updates add candidates to the active pool, while hardware scheduling packs independent circuits into available processor capacity.

A. QAOA Matching Sampler

  • Each residual edge is encoded as a qubit, and the QUBO rewards selection while penalizing collisions; the sampler returns a candidate pool with fixed offline-calibrated angles.The collision penalty is λ = 0.2, and greedy repair subsequently enforces feasibility.Source: A. QAOA Matching Sampler · p. 3

B. Partitioning and Reconstruction

  • Multi-way spectral partitioning groups strongly connected regions under an edge-count bound; stitching and greedy repair produce feasible matchings, though cut edges are not guaranteed to become internal within a finite iteration budget.Local samples are combined using batched Cartesian products, and repair accepts selected edges in descending residual-weight order when both endpoints are unoccupied.Source: B. Partitioning and Reconstruction · p. 3

C. Classical Update and Hardware Execution

  • The classical update adds distinct repaired candidates and a global maximum-weight matching, re-optimizes weights, and stops at a target error, plateau, or iteration limit; the scheduler packs circuits into disjoint processor regions.Packing uses otherwise idle capacity and buffer qubits to reduce dispatch rounds.Source: C. Classical Update and Hardware… · p. 4

IV. EXPERIMENTAL RESULTS

The experiments compare distributed QAOA sampling with classical samplers and MPS simulation, then examine how simulation fidelity, partition size, and circuit topology relate to convergence and execution demands.

A. Experimental Setup

  • The evaluation uses p = 1 QAOA with 25,000 shots per partition per round, and hardware runs omit pulse-level mitigation because tested mitigation degraded candidate quality.Simulated annealing uses 1,500 reads per partition, each with 1,000 sweeps; these are specified sampling budgets, not matched computational costs.Source: A. Experimental Setup · p. 4

B. Classical Simulation and Hardware Convergence

  • Higher MPS bond dimensions improve mirror fidelity and final decomposition cost, indicating that retaining correlations lost at low χ matters for this sampling task.Mirror fidelity is the probability of recovering the all-zero state after a state-preparation circuit and its inverse at finite χ.Source: B. Classical Simulation and Hardware… · p. 4, Figure 2 · p. 5
  • Hardware QAOA tracks simulated convergence and achieves lower costs than random sampling and simulated annealing; a 50-edge partition bound remains close to unpartitioned hardware convergence.The comparison is for the tested samplers and budgets; simulated annealing plateaus at round 18, while QAOA continues to improve.Source: B. Classical Simulation and Hardware… · p. 4

C. Partition Size and Circuit Density

  • Partition bounds of 50 and 80 converge better than 20, whose aggressive fragmentation cuts too many edges and stalls early.The bounds trade graph fragmentation against circuit complexity.Source: C. Partition Size and Circuit Density · p. 4
  • An 80-qubit circuit has transpiled two-qubit depth 67, while circuits with 42–52 qubits reach depths 110–169, showing that qubit count alone does not determine routing depth.Dense local interaction structures can require extensive SWAP routing; linear paths and open trees route with minimal SWAP overhead.Source: C. Partition Size and Circuit Density · pp. 4–5

D. Deployment on PEGASE-1354

On PEGASE-1354, partitioned QAOA sampling is compared with repaired classical baselines and deployed on IBM hardware. The reported results show lower residual error than simulated annealing and random sampling, while spatial packing reduces execution time with a modest convergence difference.

D. Deployment on PEGASE-1354

  • The 1,710-edge PEGASE graph is split into 41 subgraphs at a 50-edge partition bound for distributed execution.Spatial packing places two 38-qubit and two 34-qubit circuits on 144 of the processor’s 156 available qubits, separated by idle buffer qubits.Source: D. Deployment on PEGASE-1354 · p. 5
  • Under identical 50-edge partitioning, QAOA sampling achieves lower residual decomposition error than simulated annealing and repaired uniform random sampling.The PEGASE transmission graph requires 1,710 qubits unpartitioned; spectral partitioning at the same bound produces 41 subgraphs.Source: D. Deployment on PEGASE-1354 · p. 5, Figure 3 · p. 6
  • Spatially packed hardware execution reduces measured time by approximately 3×, reaching error 1.58 × 10^-6 at its round-17 plateau versus 1.11 × 10^-6 for unpacked execution at the 20-round limit.The final convergence difference is 4.7 × 10^-7; packing trades away some transpiler choice and may expose circuits to spectator crosstalk.Source: D. Deployment on PEGASE-1354 · pp. 5–6, Figure 3 · p. 6
  • Without repair, discarding invalid matchings stalls QAOA near 10^-5, while random sampling yields zero valid matchings; with repair, QAOA reaches 1.1 × 10^-6 versus above 2 × 10^-6 for random samples.The comparison indicates that repair enhances structured QAOA candidates rather than replacing them.Source: D. Deployment on PEGASE-1354 · p. 6, Figure 3 · p. 6

V. DISCUSSION AND CONCLUSION

The distributed QAOA pipeline extends E-FCFW decomposition to the 1,710-edge PEGASE grid, while the 50-qubit partition results and MPS tests indicate that partitions must retain a useful quantum sampling task. Preliminary QOBLIB results report sparse decompositions, and the authors identify broader benchmark evaluation and runtime accounting as future work.

V. DISCUSSION AND CONCLUSION

  • On PEGASE-1354, partitioned QAOA extends E-FCFW decomposition to the 1,710-edge grid using circuits that fit current hardware, and spatial packing cuts execution time by approximately threefold.The reported QAOA-with-repair result improves on random sampling with the same repair.Source: §V · p. 6
  • The ps = 50 results retain unpartitioned convergence behavior, while bond-dimension tests show that aggressively truncating quantum correlations degrades candidate quality; neither establishes quantum advantage.The authors present these results as evidence for a useful regime, not proof of classical intractability.Source: §V · p. 6
  • Intermediate-density modular networks such as power grids are the target regime: sparse graphs may admit efficient classical solutions, while dense graphs incur prohibitive SWAP-routing overhead.The paper attributes classical heuristic difficulty in modular networks to frustrated local minima across partition cuts.Source: §V · p. 6
  • The proposed next step is to test partitions of at least 100 qubits while varying density to balance useful quantum correlations against reliable transpiled circuit depth.The authors argue that width and density must be optimized together.Source: §V · p. 6
  • Preliminary Heron-hardware runs on three QOBLIB MBD instances up to 4,096 variables reached target tolerance within 15 outer iterations and retained 50–75 matchings, versus over 250 for Birkhoff+.Future work will evaluate the full benchmark suite with comprehensive runtime accounting and stronger classical-solver comparisons.Source: §V · pp. 6–7

DATA AND CODE AVAILABILITY

  • The pipeline implementation, example Divi workflows, demonstration notebooks, and benchmark datasets are slated for availability; code requests may be sent to the authors.Source: DATA AND CODE AVAILABILITY · p. 7

Appendix A: Extended Methods and Hardware Layouts

The appendix describes offline QAOA calibration, the partitioned E-FCFW iteration, and sampling-budget and hardware choices. PEGASE angles are transferred from a representative partition, while local samples are recombined, repaired, and used in the classical weight update.

1. Parameter Calibration and Sampling Budgets

  • Offline calibration transfers angles from small, topology- and degree-matched prototypes (N ≤ 16), requiring about 100 parallel circuits and ten minutes of MPS simulation in the reported setup.Transferred angles are used instead of optimizing them at every E-FCFW iteration.Source: §1 · p. 7
  • For PEGASE, a bond-dimension-128 simulation of a representative 49-qubit partition scans γ ∈ [−π, π] and β ∈ [0, π/4]; its minimum near (2.49, 0.16) supplies fixed execution angles.Finite bond dimension makes this an approximate MPS calibration, not an exact simulation guarantee.Source: §1 · p. 7
  • Simulated annealing uses 1,000 sweeps per read and 1,500 reads per partition per round; its 1.5 × 10^6 sweeps are compared by acquisition time, not matched algorithmic operations, with 25,000 quantum shots.The candidate-ranking and outer stopping criteria are shared across sampling methods.Source: §1 · p. 7
  • Hardware runs omit dynamical decoupling and 32-randomization gate twirling because tests found degraded candidate quality, using heuristic transpilation to minimize two-qubit depth instead.Source: §1 · p. 7
  • Each outer iteration initializes or updates the matching set and decomposition, forms the residual graph, and recursively spectrally partitions it into subgraphs of at most ps edges.The partition bound is the maximum circuit qubit count; each subgraph receives a shallow QAOA circuit at the preselected angles and yields a candidate sample set.Source: §1 · p. 7
  • Local samples are recombined by beam search or Cartesian stitching, greedily repaired, and retained alongside a global maximum-weight matching before the cardinality-constrained quadratic program updates weights.The iteration then prunes zero-weight matchings before continuing.Source: §1 · p. 7
  • Figure 4 depicts PEGASE-1354 split into 41 subgraphs at ps = 50, distinguishing internal edges from cut edges and shading individual partitions.Source: Figure 4 · p. 8

2. Stitching and Feasibility Repair

The method controls the combinatorial growth of stitched samples and repairs conflicts to produce feasible matchings. Repair only prunes selected edges, so candidate quality remains bounded by the quantum sampler's proposed edge set.

2. Stitching and Feasibility Repair

  • Cartesian stitching batches cross-products at 55 combinations per step; beam search retains at most 200 candidates per group and prunes pairwise combinations to that limit at each merge level.Both approaches limit the otherwise exponential number of combinations.Source: §2 · p. 8
  • Stitched candidates can violate matching feasibility through intra-partition collisions permitted by shallow circuits and finite penalties, or shared-vertex collisions across partition boundaries.Source: §2 · p. 8
  • Greedy repair sorts sampled edges by residual weight, accepts an edge only when both endpoints are unoccupied, and discards conflicts; it never introduces unselected edges.The procedure guarantees matching feasibility in O(|Ẽ| log |Ẽ|) time, but candidate quality is bounded by the sampler's proposed edges.Source: §2 · p. 8
  • Spatial packing places two 38-qubit and two 34-qubit circuits in disjoint regions of the 156-qubit Heron processor, with idle qubits and unused couplers separating them.Source: Figure 5 · p. 8

3. MPS Mirror Diagnostic

The MPS mirror diagnostic estimates approximation error by running a QAOA preparation circuit and its inverse, then measuring the frequency of the all-zero outcome. It characterizes the compute-uncompute trajectory rather than directly certifying the forward state.

3. MPS Mirror Diagnostic

  • For a 132-qubit QAOA circuit, Maestro appends the adjoint circuit and estimates the return probability from 15,000 computational-basis shots; the all-zero frequency is the mirror fidelity.Exact execution returns the initial all-zero state with unit probability, whereas MPS truncations can lower the measured return probability.Source: §3 · p. 8
  • A mirror-fidelity departure from unity diagnoses MPS entanglement truncation, but the return probability assesses the compute-uncompute trajectory rather than certifying the forward state directly.Source: §3 · pp. 8–9
  • The PEGASE calibration landscape marks a minimum near (γ0, β0) = (2.49, 0.16) for a representative 49-qubit partition simulated at bond dimension 128.Source: Figure 6 · p. 9

4. Orchestration and Circuit Scheduling

Divi coordinates partition dispatch, reconstruction, and repair, while the scheduler packs independent circuits into execution rounds. On PEGASE-1354, the layout used 41 subgraphs and ran four independent circuits simultaneously on one Heron processor.

4. Orchestration and Circuit Scheduling

  • Approximately 3× lower PEGASE execution time was observed with spatial circuit packing, which reduced dispatch rounds by up to 4× in reported configurations.The scheduler orders circuits by size, shares shot counts within rounds, and can replicate circuits or adjust shot allocation to reduce underfilled rounds.Source: §4 · p. 9

5. Partition and Packing Layouts

  • The PEGASE-1354 partition layout contains 41 subgraphs, and the quotient graph uses four colors to distinguish them.The layout emphasizes splitting the workload at the principal-problem level.Source: §5 · p. 9
  • Four independent subgraph circuits fit on one Heron processor for simultaneous execution because samples from one subgraph do not depend sequentially on another's.Disjoint register regions and idle buffer qubits separate packed circuits.Source: §5 · p. 9, §4 · p. 9

Related papers

Loading 2610.10772v1…