PaperlayerView exact revision on arXiv

Source-linked AI summary

Compiling Together: High-Throughput Distributed Quantum Computing via Multi-Compilation

Yipei Liu, Sen Zhang, Zebo Yang, Lei Yang

arXiv:2610.03260v1quant-phcs.ARcs.SYeess.SY

TL;DR

Distributed quantum computing is constrained by finite Bell-pair capacity, and a single compilation can leave some links idle. The paper jointly allocates shots across equivalent compilations that stress different links; across the evaluated settings, multi-compilation improves throughput and fidelity over single compilation.

  • Problem

    A single DQC compilation can concentrate communication demand on some links and leave other Bell-pair capacity unused, limiting shot throughput.

    Source: §1 · pp. 1–2

  • Method

    The paper runs equivalent compilations concurrently and pools their samples, formulating candidate selection and shot allocation under per-link capacities as CMA.

    Source: §1 · p. 2, §8 · p. 11

  • Results

    Across multiple workloads and topologies, multi-compilation improves throughput over single compilation and fidelity under equal Bell-pair budgets, with evaluation scaling to 36 QPUs and 144-qubit circuits.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Multi-compilation converts otherwise-idle per-link Bell-pair capacity into additional shots that can be pooled for higher output fidelity under equal Bell-pair budgets.

    Source: §8 · pp. 11–12

    CMA remains NP-hard, and exact MILP solution may require extensive combinatorial search.

    Source: §6.2 · p. 7

Abstract

from arXiv · show

Quantum computing is a promising paradigm for problems that are challenging for classical machines, but realizing that promise requires far more qubits than a single processor can offer. Distributed quantum computing (DQC) scales out by connecting multiple quantum processing units (QPUs), at the cost of making entanglement the scarce resource: every remote gate consumes a Bell pair, and inter-QPU links generate Bell pairs at finite rates orders of magnitude slower than local gates. Since quantum programs are executed repeatedly, this rate bounds how fast shots complete and thus how fast results are obtained. Existing DQC compilers emit a single implementation per circuit, so throughput is capped by its busiest link while other links stay idle. We observe that alternative compilations of the same circuit are logically equivalent yet stress different links; executing them concurrently and pooling their samples converts idle Bell pairs into additional shots. We formulate the joint selection of compilations and allocation of shots under per-link Bell-pair capacities as Candidate-Constrained Max-Shot Allocation (CMA), prove it NP-hard, and solve it with a dynamic program and its approximate variant AppDP, a compact MILP, and a greedy heuristic Effi. In simulation on six-QPU networks, multi-compilation raises throughput by 2-4.5* over the single compilation and correspondingly improves output fidelity under equal Bell-pair budgets. On hardware, it increases measured fidelity by up to 93% and reaches the single-compilation fidelity in up to 10* less time. Scaling to 36 QPUs and 144-qubit circuits, MILP improves throughput over the single compilation by 76.8% on average across 48 configurations while Effi allocates in milliseconds.

1 Introduction

Distributed quantum computing needs many repeated shots, but finite Bell-pair rates can bottleneck execution. The paper proposes concurrently running equivalent compilations that use different links, jointly allocating their shots to improve throughput and fidelity.

1 Introduction

  • A single compilation may concentrate demand on a subset of links, leaving parallel Bell-pair generation capacity unused and limiting completed shots.Programs require repeated shots to obtain reliable results, so throughput affects how quickly computational results are obtained.Source: §1 · pp. 1–2
  • Alternative compilations can stress different links, allowing concurrent execution to use capacity left idle by a single compilation and increase aggregate shot throughput.Equivalent compilations produce the same ideal output distribution, so their measurement samples can be pooled.Source: §1 · p. 2
  • Candidate selection and shot allocation must be joint because candidates may compete for the same link capacity, and more shots do not necessarily improve pooled accuracy under noise.Different compilations can have different communication costs and noise.Source: §1 · p. 2
  • The paper formulates Candidate-Constrained Max-Shot Allocation (CMA), proves it NP-hard, and develops allocation strategies balancing solution quality with optimization overhead.It validates multi-compilation in distributed simulation and on IBM quantum hardware.Source: §1 · p. 2
  • The evaluation scales to 36 QPUs and 144-qubit circuits; MILP has the highest evaluated throughput, AppDP retains most of it, and Effi allocates in milliseconds.Across multiple workloads and topologies, multi-compilation improves throughput over single compilation and fidelity under equal Bell-pair budgets.Source: §1 · p. 2

2 Background and Related Work

DQC partitions a logical circuit across QPUs, with remote operations relying on shared entanglement. Because Bell pairs are generated per link at finite rates, link-specific capacity constrains distributed execution.

2.1 Distributed Quantum Computing

  • DQC assigns logical qubits to QPUs; local gates stay on one QPU, while remote gates can use telegate or teledata, with telegate consuming a Bell pair and classical communication.Telegate leaves data qubits on their original QPUs; teledata instead teleports a data qubit to another QPU.Source: §2.1 · p. 2
  • Placement and routing determine which links carry remote operations, and equivalent circuit compilations can induce different link demands.Prior work explores circuit variants for device-error diversity and circuit scheduling across QPUs [3], but does not combine equivalent compilations to exploit per-link capacity.Source: §2.1 · p. 3

2.2 Bell-Pair Communication

  • Bell pairs provide shared entanglement for remote operations, and probabilistic generation means they arrive at finite rates rather than instantaneously.Reported experimental rates range from tens to hundreds of Bell pairs per second.Source: §2.2 · p. 3
  • Bell-pair capacity belongs to individual links: links can generate pairs concurrently, but unused capacity on one link cannot make up for insufficient capacity on another.Source: §2.2 · p. 3

3 Observation and Motivation

The section motivates multi-compilation by showing that a single compilation can leave Bell-pair capacity idle. Complementary compilations can use that capacity for more samples and higher fidelity, especially when entanglement is scarce.

3.1 Bell-Pair Generation Limits Throughput

  • Remote Bell-pair generation can be substantially slower than local two-qubit operations, making link rates a throughput constraint.The comparisons include 42 ns and 68 ns CZ gates versus reported Bell-pair generation intervals of about 103 ms and 5.5 ms.Source: §3.1 · p. 3, Figure 2 · p. 3

3.2 Wasted Bell-Pair Capacity Leads to Fidelity Loss

  • 30 shots/s from each of two compilations using different links combine into 60 shots/s, and pooled fidelity reaches 0.960 versus 0.892 for A and 0.907 for B.The example uses complementary Bell-pair demands, so the compilations do not compete under the independent-link model.Source: §3.2 · pp. 3–4, Figure 3 · p. 4

3.3 Multi-compilation Outperforms Single

  • As Bell-pair capacity increases, multi-compilation consistently yields higher output fidelity, with the largest gains under scarcity and diminishing gains when one compilation can complete the requested shots.The evaluation compiles an 8-qubit circuit into six compilations with different placements and varies total DQC capacity.Source: Figure 4 · p. 4, §3.3 · p. 4

4 DQC System Model

The model represents the DQC network as links with finite Bell-pair rates and takes a fixed set of compiled candidates as input. It allocates integer shot rates across candidates subject to per-link resource demand.

4.1 Network Resources and Compiled Candidates

  • The network has links with finite, potentially heterogeneous Bell-pair rates; the model assumes local computation and control are not binding and does not specify individual gate timing or a physical schedule.Source: §4.1 · pp. 4–5
  • Each candidate is a partition, QPU mapping, and routing for the same circuit, with a per-link Bell-pair demand per shot; candidate generation is outside the allocation problem.The model assumes every candidate uses at least one communication link.Source: §4.1 · p. 5

4.2 Allocation and Resource Complementarity

  • The allocation assigns each candidate an integer rate in shots/s, sums those rates for throughput, and constrains link demand by the candidates’ per-shot Bell-pair requirements.The one-shot/s integrality is an adopted allocation granularity, not a requirement on arbitrary long-run average rates.Source: §4.2 · p. 5

5 Problem Formulation

The section defines CMA as a joint candidate-selection and shot-allocation problem constrained by per-link Bell-pair capacities and a candidate limit. It establishes that optimizing this allocation is NP-hard.

5.2 Allocation Problem

  • Edge-resource feasibility requires each link’s aggregate Bell-pair demand to stay within its generation rate; spare capacity on one link cannot offset a shortage on another.The constraint is imposed separately on every communication edge.Source: §5.2 · p. 5
  • The candidate limit caps the number of compiled implementations with positive assigned shots, reflecting the overhead of maintaining and scheduling multiple implementations.Source: §5.2 · p. 5
  • CMA chooses integer execution rates for compiled candidates to maximize aggregate throughput while respecting edge capacities and the candidate limit.The formulation jointly determines which candidates execute and how many shots each receives.Source: §5.2 · p. 5, §5.1 · p. 5

5.1 Problem Statement

  • CMA’s inputs include a QPU network, edge Bell-pair generation rates, compiled candidates, and each candidate’s per-edge resource requirements.The objective is aggregate circuit-execution throughput.Source: §5.2 · p. 5, §5.1 · p. 5

5.3 Computational Hardness

  • Candidate selection and allocation are coupled because candidates can compete for the same links or complement one another across different links.Individual candidate throughput alone therefore does not determine the best joint allocation.Source: §5.3 · pp. 5–6
  • The decision version of CMA is NP-complete, making its optimization version NP-hard.The proof reduces maximum set packing to CMA using unit-capacity element and private edges.Source: §5.3 · p. 6

6 Optimization Methods

The section presents dynamic programming, a compact MILP, and Effi for allocating shots across compiled candidates. These methods trade optimization overhead, solution quality, and scalability differently.

6 Optimization Methods

  • The methods comprise a dynamic program for CMA, a compact MILP that avoids explicit resource-state enumeration, and Effi, a lightweight allocation heuristic.Source: §6 · p. 6

6.1 Dynamic Programming

  • The exact dynamic program tracks used-link resource budgets and candidate slots, choosing whether to skip each candidate or assign it positive shots.Its state space uses the effective links consumed by at least one candidate.Source: §6.1 · p. 6
  • The DP resource grid grows exponentially with the number of effective links; for fixed link count it is pseudo-polynomial, and its sparse frontier can still grow substantially.The stated rolling-space bound excludes storage for reconstructing the allocation.Source: §6.1 · p. 6
  • AppDP limits the sparse DP frontier by pruning states when its prescribed state limit is exceeded, preserving feasibility but not generally optimality.The passage specifies a frontier cap of 100 states.Source: §6.1 · pp. 6–7

6.2 Mixed-Integer Linear Programming

  • The MILP uses integer shot variables and binary candidate-selection variables in a compact formulation whose size does not grow with numerical link capacities.Its compactness does not remove CMA’s NP-hardness or the possibility of extensive combinatorial search.Source: §6.2 · p. 7

6.3 Lightweight Greedy Allocation

  • Effi progressively selects a candidate with the largest feasible shot count, assigns those shots, and subtracts their per-link costs from residual capacities.Each update remains feasible, and the first iteration matches the single-candidate baseline; however, a locally best early choice can block a better combination and Effi has no global-optimality certificate.Source: §6.3 · p. 7
  • Figure 5 depicts six-QPU network topologies, and Table 1 reports VQE shot-allocation optimization results across six-QPU topologies.Source: Figure 5 · p. 8, Table 1 · p. 8

7 Experiment

The experiments compare single-candidate and multi-candidate allocation across six-QPU simulations, IBM hardware emulation, and systems up to 36 QPUs, measuring throughput, fidelity, utilization, and runtime. Multi-candidate allocation improves throughput and fidelity, with results varying by method, workload, and topology.

7.1 Experimental Setup

  • The evaluation uses identical candidate sets per instance, a default candidate limit K=8, five six-QPU topologies, and workloads spanning 10- to 144-qubit circuits.The hardware study emulates DQC by partitioning a 156-qubit IBM device into nine logical QPUs.Source: §7 · p. 8, §7.1 · p. 8, §7.3 · p. 9

7.2.1 Throughput Optimization Results across Inter-

  • Across six-QPU topologies, MILP has the highest or tied-highest shot rate, AppDP is often close but slower to optimize, and Effi improves throughput with near-baseline runtime.Different per-link demands let multiple compilations use Bell-pair capacity left idle by a single compilation.Source: §7.2.1 · pp. 8–9
  • Across six-QPU simulations, multi-candidate allocation improves fidelity for sampling-limited workloads; QAOA rises from 0.25 to about 0.44 at T=1, while GHZ and BITCODE fidelity largely saturate.Figure 6 resolves the fidelity comparisons by topology; the multi-candidate methods remain above Baseline for VQE, QAOA, TFIM, and FULLADDER, with gaps narrowing as budgets increase.Source: §7.2.1 · p. 9, Table 2 · p. 9, Figure 6 · p. 10

7.3.1 Throughput OptimizationResults on Hardware.

  • On the nine-QPU hardware partition, MILP improves throughput over Baseline by 350% for VQE-20, 236% for QAOA-20, and 500% for TFIM-20.MILP has the highest or tied-highest shot rate in every case; AppDP stays close but takes longer to optimize, while Effi runs in time comparable to Baseline.Source: §7.3.1 · pp. 10–11, Table 3 · p. 10
  • At T=6000s, MILP raises measured fidelity from 0.657 to 0.803 for VQE-20, 0.357 to 0.621 for QAOA-20, and 0.302 to 0.584 for TFIM-20; multi-candidate methods reach baseline target fidelity up to 10× sooner.At sampled budgets, the target is reached at least 2× sooner for VQE-20 and QAOA-20 and 10× sooner for TFIM-20.Source: Figure 7 · p. 10, §7.3.2 · p. 11

7.4.1 Results for VQE.

  • For VQE scalability, MILP leads or ties in all 16 configurations, improving throughput 25.0%–180.0% over Baseline; AppDP averages 91.1% of MILP throughput and Effi 75.4%.At 12 QPUs, Star and Grid show larger gains than Line; at 36 QPUs, MILP still more than doubles throughput on Star and Grid.Source: §7.4.1 · p. 11

7.4 Scalability Results

  • At 36 QPUs, MILP more than doubles VQE throughput over Baseline on Star and Grid, while improvements persist for QAOA and TFIM at the largest scale.For QAOA and TFIM, MILP improves over Baseline by 49.3% and 69.2%, respectively; AppDP improves by 23.7% and 38.8%.Source: §7.4.1 · p. 11, §7.4.2 · p. 11
  • Effi allocates at millisecond scale across VQE scalability configurations, while MILP runtime reaches 179.5 seconds and AppDP reaches 18.0 seconds.For QAOA, Effi’s gains shrink and vanish at 30 and 36 QPUs, despite remaining millisecond-scale; MILP reaches 153.1 seconds at 36 QPUs.Source: §7.4.1 · p. 11, §7.4.2 · p. 11

8 Conclusion

The conclusion presents multi-compilation as a way to use otherwise idle per-link Bell-pair capacity by running equivalent circuit compilations and pooling their samples. It reports throughput and fidelity gains over the best single compilation across workloads, hardware, and systems up to 36 QPUs.

8 Conclusion

  • The work formulates candidate selection and shot allocation as CMA, proves it NP-hard, and addresses it with dynamic programming, AppDP, compact MILP, and millisecond-scale Effi.Source: §8 · pp. 11–12
  • Across six 10-qubit workloads, five topologies, hardware, and systems up to 36 QPUs and 144-qubit circuits, multi-compilation raises throughput over the best single compilation and improves fidelity under equal Bell-pair budgets.Source: §8 · p. 12
  • Multi-compilation is presented as a practical lever for managing entanglement in distributed quantum systems.Source: §8 · p. 12
Loading 2610.03260v1…