PaperlayerView exact revision on arXiv

Source-linked AI summary

Resource-Aware Scheduling for Distributed Quantum Computing

Connor Howe, Raghav Mundada, Jake O'Shaughnessy, Ibrahim Abdullahi, Ali Anwar

arXiv:2610.30482v1cs.NI

TL;DR

Practical DQC requires choosing at runtime whether to execute a circuit intact, cut it for one QPU, or distribute it, while accounting for system conditions beyond partitioning. The paper presents a resource-aware scheduler that models quantum and classical costs; its experiments find reconstruction dominates cutting overhead and distributed execution can improve tail latency.

  • Problem

    Runtime selection among intact, sequential-cut, and distributed plans remains comparatively underexplored, despite communication and reconstruction materially affecting latency and plan quality.

    Source: §I · p. 1

  • Method

    A resource-aware scheduler compares intact, sequential-cut, and distributed plans using explicit models of QPU execution, communication, and host-side reconstruction.

    Source: §I · p. 1

  • Results

    Distributed execution can improve tail latency by up to 39%, reconstruction dominates cut-execution overhead, and scheduler overhead remains negligible.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    The findings support runtime plan selection across quantum and classical resources rather than treating DQC only as circuit partitioning.

    Source: §I · p. 1

    The evaluation uses simulated rather than live hardware and synthetic rather than production workloads, and its plan break-even points may shift with scale, heterogeneity, or QPU count.

    Source: §X · pp. 12–13

Abstract

from arXiv · show

Distributed quantum computing (DQC) is a promising near-term approach for executing circuits that exceed the capacity of a single quantum processing unit (QPU). Prior work has made significant progress on circuit partitioning and reconstruction, but practical DQC requires more than cutting a circuit into smaller pieces. A runtime system must determine whether to execute the circuit intact, cut it for sequential execution on one QPU, or distribute it across multiple QPUs, while accounting for queueing, communication, reconstruction, and hardware constraints. We present a resource-aware scheduler for DQC that compares these execution alternatives at runtime using explicit models of QPU execution, communication, and host-side reconstruction, together with hardware-informed timing derived from simulated IBM QPUs. By treating communication and reconstruction as first-class scheduling costs, the scheduler selects execution plans using a more realistic view of end-to-end overhead than cutting-only approaches. Across our experiments, reconstruction accounts for over 83% of cutting overhead, distributed execution reduces P90 latency by up to 39% relative to uncut single-QPU execution, and scheduling overhead itself remains negligible, never exceeding 0.038% of end-to-end job latency. Together, these results show that DQC must be treated as a runtime scheduling problem over both quantum and classical resources, not just circuit partitioning.

I. INTRODUCTION

DQC needs runtime selection among intact, sequential-cut, and distributed execution because queueing, communication, reconstruction, and hardware conditions shape end-to-end cost. This work frames that choice as scheduling across quantum and classical resources, complementing prior work on cutting, partitioning, and orchestration.

I. INTRODUCTION

  • DQC execution must be chosen at runtime because queueing, QPU availability, communication, reconstruction, and hardware behavior affect whether each plan is worthwhile.The scheduler problem spans quantum and classical resources, beyond circuit structure alone.Source: §I · p. 1
  • The scheduler compares intact, sequential-cut, and distributed plans using explicit models of QPU execution, communication, and host-side reconstruction.Its timing estimates use simulated IBM QPUs and backend-specific AerSimulator noise models.Source: §I · p. 1
  • Distributed execution can improve tail latency by up to 39%, reconstruction dominates cutting overhead, and scheduler overhead remains negligible.The paper presents these results as evidence for runtime plan selection across quantum and classical resources.Source: §I · pp. 1–2

II. MOTIVATION: USE CASES

  • Large circuits, heterogeneous quantum-classical workflows, and latency-sensitive services motivate weighing feasibility against communication, reconstruction, queueing, and fidelity costs.These settings include workloads that may exceed one QPU, jobs under dynamic resource conditions, and services with latency objectives.Source: §II · p. 2

III. RELATED WORK

  • Prior work advances cutting, partitioning, and orchestration, while this work selects among intact, cut, and distributed execution using system state and end-to-end cost.The related-work discussion distinguishes runtime plan selection from improving partition quality or cutting methods.Source: §III · p. 2

IV. SYSTEM DESIGN

The system evaluates jobs across QPU execution, communication, and host-side reconstruction resources. Its planner chooses among execution plans or deferral, while the execution and sampling models keep quantum occupancy distinct from downstream classical costs.

A. Architecture Overview

  • The system can run a circuit intact on one QPU, cut it for sequential execution on one QPU, distribute cut subcircuits across QPUs, or defer the job.The profiler and planner use circuit characteristics and current QPU state to identify and rank feasible options.Source: A. Architecture Overview · p. 2, Figure 1 · p. 3, B. Execution Plans · p. 3
  • The planner enumerates feasible plans, predicts queueing, execution, communication, and reconstruction costs, filters plans that miss service-level objectives, and selects the minimum-score feasible plan.The architecture sends the selected plan to an executor that stages quantum, communication, and reconstruction tasks across separate worker pools.Source: A. Architecture Overview · p. 3

C. Sampling Overhead

  • Wire cuts increase the number of subexperiments, expanding execution workload and raising communication and host-side reconstruction costs.The scoring model uses per-shot QPU blocking time rather than scaling QPU occupancy by the sampling-expanded workload.Source: C. Sampling Overhead · p. 3

D. Scoring Objective

The scheduler scores feasible plans using predicted quantum-resource occupancy, fragmentation, coordination, and output quality. For distributed plans, it separately estimates end-to-end makespan and filters plans that exceed latency targets.

D. Scoring Objective

  • The plan score balances predicted execution delay, partitioning overhead, coordination cost, and estimated output quality.Queue wait and per-shot QPU blocking time represent quantum-resource occupancy; the scoring model uses per-shot blocking time rather than the full sampling-expanded workload.Source: D. Scoring Objective · p. 3
  • The fragmentation penalty discourages unnecessarily complex cut plans, while the coordination penalty applies only to distributed execution.The fragmentation term uses the number of labels and wire cuts; coordination cost increases with additional QPUs.Source: D. Scoring Objective · p. 3
  • The quality term favors plans expected to use more reliable devices or incur lower effective gate overhead.The fidelity proxy uses hardware-derived one- and two-qubit error rates.Source: D. Scoring Objective · p. 4
  • Reconstruction is included in total job makespan and resource contention, but excluded from the QPU-blocking term because it does not occupy QPU resources after quantum execution.This keeps quantum-resource occupancy separate from downstream classical processing.Source: D. Scoring Objective · p. 4

E. Plan C Makespan and SLO Filtering

  • For distributed plans, makespan combines the slowest QPU's parallel quantum path with communication and reconstruction, then filters out plans that exceed latency targets.The score ranks the plans that remain feasible by occupancy, coordination, and quality.Source: E. Plan C Makespan and SLO Filtering · p. 4

F. Resource Models

The scheduler models QPU execution, communication, and host-side reconstruction as separate resource classes to represent contention and delay. Its QPU timing uses hardware-informed estimates, with an analytic model available for comparison and fallback.

F. Resource Models

  • Separate QPU, communication, and reconstruction resource models let the scheduler represent contention and delay more realistically than a single folded execution-time estimate.Predicted QPU queue wait depends on when a connected free component of sufficient size becomes available, not merely on the total number of free qubits.Source: F. Resource Models · p. 4
  • Communication cost includes fixed overhead, a component scaling with subexperiment count, and added coordination cost as more QPUs are involved.The model captures workload-dependent communication and cross-device coordination.Source: F. Resource Models · p. 4
  • Reconstruction cost includes fixed overhead and per-subexperiment cost, and can dominate latency because subexperiment count grows exponentially with wire cuts.Source: F. Resource Models · p. 4

G. Hardware-Informed QPU Timing

  • Hardware-informed QPU timing derives per-shot blocking time from each circuit's scheduled duration on a transpiled target device, scaled by that QPU's time resolution.This reflects hardware connectivity, gate decomposition, and scheduling effects rather than relying only on circuit-level gate counts.Source: G. Hardware-Informed QPU Timing · p. 4
  • The scheduler also supports an analytic timing model, but the hardware-informed model is used in the main experiments because it captures transpilation, topology constraints, and hardware-level scheduling.The analytic approximation uses circuit depth, per-layer time, measurement cost, and per-shot overhead.Source: G. Hardware-Informed QPU Timing · p. 4

H. Assignment Policy and Scheduling Loop

The scheduler assigns distributed partitions with a makespan-oriented greedy policy, then repeatedly updates pending jobs and resources before selecting a feasible plan or waiting.

H. Assignment Policy and Scheduling Loop

  • For Plan C, labels are ordered by decreasing cost and assigned to the QPU with the lowest projected load, using quality-aware tie-breaking.The policy aims to reduce the quantum critical path while accounting for device reliability.Source: H. Assignment Policy and Scheduling Loop · p. 4
  • At each runtime step, the scheduler releases completed reservations, updates pending jobs, re-ranks devices, and invokes the planner; deferred jobs are reconsidered after backoff.Accepted plans are passed to the executor for staged execution.Source: H. Assignment Policy and Scheduling Loop · p. 4
  • Plan selection enumerates feasible candidates, filters them by predicted makespan against service-level targets, scores the survivors, and dispatches the minimum-score option.Separating feasibility, deadline filtering, and plan comparison is intended to improve interpretability and extensibility.Source: H. Assignment Policy and Scheduling Loop · p. 4

V. IMPLEMENTATION

The implementation evaluates the scheduler with simulated IBM QPUs and AerSimulator, using circuit-cutting tools and a backend abstraction. Experiments vary circuit workloads, submission patterns, and system conditions, and measure latency, quality, plan selection, and scheduler overhead.

V. IMPLEMENTATION

  • The Python and Qiskit implementation evaluates Plans A, B, C, and WAIT under simulated multi-QPU conditions, using simulated IBM device properties and AerSimulator noise models.Circuit cutting and quasi-probability reconstruction use Qiskit's Circuit Cutting Addon, and a common backend abstraction allows partitioning strategies to vary without changing scheduling logic.Source: §V · p. 5

VI. EXPERIMENTAL SETUP

  • The default pool contains three heterogeneous simulated IBM QPUs with 7, 9, and 11 qubits, and workloads include GHZ, random CX, QFT, QAOA-like, and VQE-like circuits.Source: §VI · p. 5
  • Circuits range from 3 to 14 qubits, jobs use 2,000 shots unless noted, and submissions are tested as streaming Poisson arrivals or batches arriving at time zero.Narrow jobs fit intact on at least one available QPU; heavy jobs require cutting or distributed execution due to capacity constraints.Source: §VI · p. 5
  • Evaluation metrics include median and P90 end-to-end latency, a fidelity proxy, plan-selection frequency, component overheads, and scheduler decision time.The simulator-based evaluation reports variability from workload, queueing, and backend choice rather than hardware noise, with controls held consistent across comparisons unless swept.Source: §VI · pp. 5–6
  • The experiment plan examines execution-mode tradeoffs, sensitivity to workload and system parameters, adaptation, runtime overhead, and the effects of submission strategy and latency constraints.The default setup uses a three-QPU pool, an arrival rate of 1.0 jobs/s, and 40 jobs per run unless otherwise noted.Source: §VI · p. 6, Table I · p. 6

VII. EVALUATION

The evaluation examines tradeoffs among intact, sequentially cut, and distributed execution, how runtime conditions shape plan choice, and whether scheduler overhead remains negligible. It finds that reconstruction and communication materially shape cut-execution costs, while execution-plan choice changes latency and fidelity trends.

VII. EVALUATION

  • Cut execution is shaped as much by host-side reconstruction and communication as by QPU execution.Execution-plan choice also changes observed latency and fidelity trends, especially under congestion or coordination pressure.Source: §VII · p. 6
  • Cut-multi achieves the best P90 latency despite communication and reconstruction overhead, while no-cut has the widest latency spread and worst tail behavior.Figure 2a groups median component latency by selected plan kind; Figure 2b groups end-to-end latency by scheduling condition.Source: Figure 2 · p. 6
  • Scheduler overhead remains negligible relative to end-to-end job latency.Source: §VII · p. 6

A. Core Tradeoffs Among Plans A, B, and C

Distributed cut execution reduces tail latency relative to no-cut under favorable conditions, although cut plans carry reconstruction overhead. The evaluation also shows that the plan comparisons depend on how jobs are grouped and that coordination cost shifts the choice between sequential and distributed execution.

A. Core Tradeoffs Among Plans A, B, and C

  • Figure 2a groups jobs by selected plan kind, whereas Figure 2b groups them by scheduling condition, so their views are complementary but not directly comparable.Cut-enabled conditions can still select Plan A for sufficiently small circuits.Source: A. Core Tradeoffs Among Plans A, B,… · p. 6
  • Plan A jobs had a 0.99 s median end-to-end latency, compared with 1.98 s for Plan B and 1.73 s for Plan C, with cut-plan medians driven largely by modeled reconstruction.The Plan A median covers n = 88 jobs.Source: A. Core Tradeoffs Among Plans A, B,… · p. 6
  • Cut-multi achieved a P90 of approximately 1.13 s versus approximately 1.85 s for no-cut, a 39% reduction relative to no-cut.Source: A. Core Tradeoffs Among Plans A, B,… · p. 6
  • Across 20 matched seeds, cut-multi reduced P90 end-to-end latency relative to no-cut by 0.514 s on average, a 28.6% average reduction.The 95% confidence interval for the average reduction was [20.0%, 37.0%], and the paired Wilcoxon signed-rank test gave p = 0.00195.Source: A. Core Tradeoffs Among Plans A, B,… · pp. 6–7
  • As coordination penalty increases, the scheduler shifts from distributed Plan C toward sequential Plan B, with median end-to-end latency increasing.Source: Figure 4 · p. 7

B. Reconstruction Dominates Cutting Overhead

Reconstruction is the dominant cutting overhead, while coordination cost and congestion alter the balance between sequential and distributed plans. Quality-aware routing benefits from heterogeneous device pools, and scheduler decision time remains small across the studied circuit-width and pool-size sweeps.

B. Reconstruction Dominates Cutting Overhead

  • Reconstruction accounts for 83.1% of cutting overhead on average across 20 matched seeds, making host-side reconstruction a first-class scheduling resource.The 95% confidence interval was [82.8%, 83.4%]; a representative breakdown attributed 87% (805 ms of 925 ms) to reconstruction.Source: B. Reconstruction Dominates Cutting… · p. 7

C. Coordination Cost Governs the Plan B–C Boundary

  • Plan C accounts for 85% of jobs at low coordination cost, but disappears entirely at δC = 0.50 s/QPU as the scheduler shifts toward Plan B.Forcing Plan B raises median end-to-end latency from 0.956 s to 1.041 s under these conditions.Source: C. Coordination Cost Governs the Plan… · p. 7

D. Adaptive Plan Selection Yields Non-Monotonic Congestion

  • Fidelity degrades smoothly with congestion, but median latency peaks at 75% congestion and recovers at 100% as the scheduler shifts more aggressively toward Plan C.Under partial congestion, jobs continue to queue for preferred single-device execution; full congestion shifts more work across available QPUs.Source: D. Adaptive Plan Selection Yields… · p. 7, Table II · p. 7

E. Quality-Aware Routing Benefits from Heterogeneous Pools

F. Scheduler Overhead Remains Negligible

  • Scheduler overhead never exceeds 0.038% of median end-to-end latency in the shown configurations, and its mean across 20 matched seeds is 0.0203%.Scheduler time rises when workloads move from intact to cut-enabled execution, but remains small as pool size increases across the studied range.Source: F. Scheduler Overhead Remains Negligible · p. 8

G. Submission Strategy Strongly Impacts Performance

Submission strategy and workload composition substantially affect latency, while tighter SLOs remove cut-enabled plans from consideration. The results show that these runtime and workload conditions change plan adoption, latency, and, under tight deadlines, the number of jobs that complete.

G. Submission Strategy Strongly Impacts Performance

  • Large batch submission raises P90 latency to 4.299 s, about 4.3× the 0.991 s lowest-latency streaming case, while fidelity remains stable across strategies.Streaming keeps P90 latency below 1.4 s in all streaming conditions; batch submission increases queueing and cut-plan pressure.Source: G. Submission Strategy Strongly… · p. 9, Table IV · p. 9

H. Stream Composition Sweep

  • Moving from a 0% to a 100% heavy-circuit stream increases P90 end-to-end latency by 1.270 s on average, or 139.7%, as Plan C adoption rises to 90%.Mean fidelity decreases by 0.0519 over the same sweep; at 100% heavy circuits, fidelity is 0.908 and P90 latency is 2.490 s.Source: H. Stream Composition Sweep · p. 9, Figure 9 · p. 9

I. Latency Constraints Change Which Plans Remain Viable

  • At SLO = 0.5 s, only 12 of 40 jobs complete, all under Plan A; tighter targets filter out cut-enabled plans because their predicted latency includes communication and reconstruction.The 1.0 s and looser settings approach full compliance near 1.5 s, while the 0.5 s curve lags.Source: §I · p. 9, Figure 10 · p. 9

J. Scaling to Large-Scale Systems

At larger scales, plan choice and latency depend on fleet capacity and congestion; batch submission suppresses distributed execution more than streaming. Real-hardware tests also reveal where simulated fidelity predictions diverge and how a correction performs on held-out circuits.

J. Scaling to Large-Scale Systems

  • Plan C adoption is 60.0% at N = 2 and stabilizes around 31–43% from N = 16 through N = 128; scheduling overhead stays at 0.36–0.46 ms.The reported overhead remains flat across fleet sizes 2–128.Source: J. Scaling to Large-Scale Systems · p. 10, Figure 11 · p. 11
  • Under batch submission, Plan C share falls to 20.6% at 2688 qubits, while streaming raises it to 37.2%; batch-induced congestion is the main suppressor across most widths.Plan C needs multiple QPUs free simultaneously; a softer capacity effect remains at the largest widths even under streaming.Source: J. Scaling to Large-Scale Systems · p. 10
  • P50 latency falls from 9.0 s at N = 2 to 1.5 s at N = 64–128, while P90 falls from 10.3 s to 2.0 s.Across circuit widths, P50 stays at 5.1–7.4 s through 1344 qubits, then reaches 10.6 s at 2688 qubits; P90 is 23.6 s at 2688 qubits.Source: J. Scaling to Large-Scale Systems · p. 10
  • For wire cuts, generated subexperiment counts track the theoretical 9^kw bound at low kw, then plateau at the Monte Carlo sampling cap; QAOA MaxCut results match the synthetic sweep through kw = 3.Above kw = 3, automated cut search on the real graph often converged on a more expensive partition.Source: J. Scaling to Large-Scale Systems · p. 10, Figure 14 · p. 11

VIII. REAL-HARDWARE VALIDATION

  • On ibm_kingston and ibm_fez, raw AerSimulator predictions underestimate real fidelity at low fragment weight and overestimate it at high weight.The reported explanation is dynamical-decoupling benefits for idle spectators at low weight and unmodeled crosstalk and routing at high weight.Source: §VIII · p. 10
  • A two-component error-space correction closely tracks held-out real-hardware fidelity on both chips: 0.45 corrected versus 0.48 real on kingston, and 0.49 versus 0.40 on fez.A third chip, ibm_marrakesh, showed an opposite spectator-error pattern and a sharp fragment-fidelity collapse outside the correction’s validated scope.Source: §VIII · pp. 10–11

IX. ABLATION STUDY

The ablations show that scheduler terms respond to relevant workload conditions, while the two cutting backends yield identical outcomes under the evaluated setup. Fidelity-aware routing improves results in heterogeneous pools; the paper also bounds the generality of its evaluation and models.

A. Weight Sensitivity

  • On the all-wide workload, coord-heavy shifts Plan C from 98% to 58% and Plan B from 2% to 42%; on the mixed workload, Plan A covers over 72% regardless of weight setting.Penalty terms are inactive for narrow circuits; removing penalties produces no significant change on either workload.Source: A. Weight Sensitivity · p. 11, Figure 16 · p. 12

B. Cutting Backend Comparison

  • Across 40 jobs, FitCut and the Qiskit-addon backend produce identical results: median e2e = 0.956 s, fidelity = 0.786, and plan mix 85% C / 15% B.Both call the same approximate mincut partitioner, which returns 2-label minimum cuts regardless of search parameters.Source: B. Cutting Backend Comparison · p. 11

C. Fidelity-Proxy Validation and Quality-Term Behavior

X. LIMITATIONS AND DISCUSSION

  • The evaluation uses simulated rather than live quantum hardware and synthetic benchmarks, so different circuit families, production mixes, or real-system effects may shift the observed trade-offs.The authors identify calibration drift, queue variability, additional noise, and network latency as effects not fully represented.Source: §X · p. 12
  • Communication and reconstruction are represented by simplified cost models, so their absolute costs may differ across systems, host implementations, or assumptions.The fidelity proxy is validated for trend behavior, not as a replacement for full application-level accuracy analysis.Source: §X · pp. 12–13

XI. CONCLUSION

  • The paper concludes that runtime scheduling over quantum and classical resources is necessary, while exact plan boundaries depend on workload scale and deployment architecture.The experiments focus on the hardware, workloads, and system sizes evaluated in Section VI.Source: §X · p. 13, §XI · p. 13
Loading 2610.30482v1…