Source-linked AI summary
Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era
Siyuan Niu, Aida Todri-Sanial
TL;DR
NISQ limitations restrict reliable circuits and leave quantum hardware under-utilized, while simultaneous execution can trade throughput against fidelity. QuMC selects concurrency, allocates reliable crosstalk-aware partitions, and reduces mapping overhead; experiments on IBM hardware include varied-size circuits and VQE. The paper reports that QuMC can outperform independent state-of-the-art mapped executions and improve VQE overhead.
Problem
NISQ devices support only small reliable circuits, creating hardware under-utilization while simultaneous execution can compromise circuit fidelity.
Method
QuMC combines a parallelism manager, greedy and heuristic reliable-partition algorithms, crosstalk characterization, and improved mapping transition.
Results
QuMC outperformed independent executions using a state-of-the-art qubit mapping approach in varied-size circuit experiments and added value when applied to VQE.
Takeaways & Limitations
The framework enables simultaneous quantum-circuit execution while targeting preserved fidelity and can be applied to reduce VQE overhead.
Takeaways & Limitations
The main concern is the trade-off between output fidelity and hardware throughput when selecting which and how many programs to execute simultaneously.
Abstract
from arXiv · showhide
NISQ devices have several physical limitations and unavoidable noisy quantum operations, and only small circuits can be executed on a quantum machine to get reliable results. This leads to the quantum hardware under-utilization issue. Here, we address this problem and improve the quantum hardware throughput by proposing a Quantum Multi-programming Compiler (QuMC) to execute multiple quantum circuits on quantum hardware simultaneously. This approach can also reduce the total runtime of circuits. We first introduce a parallelism manager to select an appropriate number of circuits to be executed at the same time. Second, we present two different qubit partitioning algorithms to allocate reliable partitions to multiple circuits - a greedy and a heuristic. Third, we use the Simultaneous Randomized Benchmarking protocol to characterize the crosstalk properties and consider them in the qubit partition process to avoid the crosstalk effect during simultaneous executions. Finally, we enhance the mapping transition algorithm to make circuits executable on hardware using a decreased number of inserted gates. We demonstrate the performance of our QuMC approach by executing circuits of different sizes on IBM quantum hardware simultaneously. We also investigate this method on VQE algorithm to reduce its overhead.
1 Introduction
NISQ hardware is under-utilized because physical constraints and noisy operations limit reliable execution to small circuits, while cloud access adds latency and queueing. QuMC addresses this by selecting, partitioning, and scheduling simultaneous circuits with fidelity awareness.
- NISQ constraints and noisy gates limit reliable execution to small, shallow circuits without quantum error correction.
- Cloud quantum systems add submission latency and long queueing delays, creating pressure to use hardware more efficiently.
- QuMC introduces a parallelism manager that selects the number of circuits to execute simultaneously without losing fidelity.
- Two qubit-partition algorithms allocate reliable regions: a greedy method provides optimal choices, while a heuristic reduces time complexity with nearly optimal results.
- The approach incorporates crosstalk-aware partitioning, improved mapping transition, and VQE evaluation on real quantum hardware.
- Two four-qubit circuits on a 10-qubit device raise the illustrative hardware throughput from 40% to 80%.
2 Background
Multi-programming executes several quantum circuits concurrently to improve hardware usage, but careless allocation can reduce fidelity. QuMC addresses shortcomings in prior approaches through hardware-aware, crosstalk-aware partitioning and improved mapping.
- Parallel execution presents a fidelity-throughput trade-off and requires choosing both suitable circuits and an appropriate concurrency level.
- Prior methods incompletely analyze topology and calibration, use many additional SWAP gates, and omit crosstalk during partition allocation.
- QuMC considers hardware topology, calibration data, and crosstalk through dedicated partition methods and a mapping transition algorithm.
3 Our multi-programming framework
QuMC combines workload selection, hardware-aware reliable partitioning, fidelity evaluation, and scheduling to execute quantum circuits either simultaneously or independently on real hardware.
- Input layer: The workflow accepts multiple quantum circuits together with hardware topology, calibration data, and crosstalk information.
- Parallelism manager: The parallelism manager decides whether circuits run concurrently or separately and selects a simultaneous workload count based on fidelity.
- Hardware-aware multi-programming compiler: The compiler partitions qubits into reliable regions, allocates them to circuits, and evaluates partition fidelity to validate the chosen concurrency.
- Scheduler: The scheduler applies mapping transition so circuits become executable on real quantum hardware.
- Output layer: QuMC produces outputs from circuits executed simultaneously or independently according to the preceding decisions.
- The method focuses on IBM architecture but can adapt to nearest-neighbor hardware and parallel operations on different qubits.
4 Parallelism manager
The parallelism manager selects candidate circuits using density and works with a fidelity metric to determine whether simultaneous execution should proceed or be reduced.
- Crosstalk can be absent between partitions P1 and P3 but present between P2 and P3, motivating crosstalk-aware partition choices.
- The manager introduces circuit density as #CNOTs/ni and treats higher-density circuits as more subject to errors.
- It orders circuits by density and selects K circuits as the maximum simultaneous workload subject to the hardware qubit limit.
- When K equals one, circuits execute independently; otherwise, the selected workloads enter the hardware-aware compiler for further optimization.
5 Hardware-aware multi-programming compiler
The hardware-aware compiler combines partitioning, crosstalk characterization, and fidelity-based concurrency control to execute multiple circuits simultaneously on reliable, non-overlapping qubit partitions.
- QuMC allocates reliable, non-overlapping partitions and restricts routing swaps to each circuit’s own partition.Partition quality accounts for topology, calibration data, and crosstalk effects.
- Crosstalk effect characterization: Simultaneous Randomized Benchmarking characterizes strong crosstalk between one-hop CNOT pairs using a threshold of E(gi|gj) > 3 × E(gi).Pairs beyond one hop are ignored because their crosstalk effects are described as very weak.
- Greedy sub-graph partition algorithm: GSP searches hardware subgraphs and selects the lowest-score non-overlapping partition while checking for strong crosstalk with previously allocated partitions.The algorithm provides optimal partition choices but has high runtime overhead.
- Qubit fidelity degree-based heuristic sub-graph partition algorithm: QHSP reduces GSP’s overhead by building partitions from high-fidelity-degree qubits that combine connectivity with CNOT and readout reliability.Its fidelity degree weights CNOT and readout errors through a user-defined λ parameter.
- Qubit fidelity degree-based heuristic sub-graph partition algorithm: QHSP’s partition procedure includes sorting physical and logical qubits, then iteratively merging favorable neighboring qubits until each partition reaches the circuit size.The stated sorting costs include O(nlog(n)) for physical qubits and O(g+klog(k)) for circuit gates and logical qubits.
- The parallelism manager compares independent and concurrent fidelity scores, allowing simultaneous execution only when the fidelity difference remains below threshold δ.If fidelity loss is significant, the system reduces concurrency or executes circuits independently.
6 Scheduler
The scheduler transforms circuits into hardware-compliant schedules by combining topology- and calibration-aware mapping with an improved simultaneous mapping transition algorithm.
- Initial mapping: Initial mappings account for swap error rate and distance, then merge circuit mappings according to their assigned partitions.This makes the simultaneous mapping transition start from partition-specific mappings rather than a single unrestricted hardware mapping.
- Circuit scheduling: Circuits are converted into DAGs, whose dependency layers are traversed to execute compliant gates directly and identify gates requiring added operations.The scheduler removes executed gates from the current first layer and processes remaining gates through candidate insertion steps.
- Mapping transition: The transition algorithm evaluates SWAP and Bridge candidates using a heuristic cost function that includes distance, error, self-impact, and future-layer effects.SWAP uses three CNOTs and changes the mapping, whereas Bridge uses four CNOTs without changing it.
- Complexity: The simultaneous mapping transition algorithm retains the baseline asymptotic complexity while improving performance over HA.For nearest-neighbor connectivity and an extended layer with at most O(n) CNOT gates, its complexity is O(gn^2.5).
- Mapping transition: The algorithm selects tentative gates according to the heuristic cost and updates the extended layer as scheduling proceeds.Candidate lists are generated for unresolved gates, and the best gate is selected before the extended layer is updated.
7 Evaluation
The evaluation compares QuMC with state-of-the-art methods and examines multiple applications of the framework.
- The study compares QuMC with the state of the art and showcases its applications.
7.1 Methodology
The methodology evaluates fidelity, added-gate overhead, and throughput across independent and simultaneous executions on IBM quantum devices using selected benchmark circuits.
- Metrics: Circuit output fidelity is measured with Probability of a Successful Trial, computed from expected-result shots over 8192 hardware trials.
- Metrics: Additional CNOT gates quantify the SWAP or Bridge insertion overhead and the algorithms’ ability to reduce added gates.
- Metrics: Trial Reduction Factor is the ratio of shots required independently to shots required simultaneously, measuring throughput improvement.
- Compared methods: HA is the independent-execution baseline, while PHA, GSP, and QHSP support comparisons involving partitioning and simultaneous execution.PHA selects a best partition, whereas GSP and QHSP combine partitioning with the improved mapping transition.
- Experimental setup: Experiments use IBM Q 27 Toronto and IBM Q 65 Manhattan with QUEKO, application-specific, and RevLib benchmarks.Only shallow small circuits are executed on hardware; medium and large circuits are compiled without hardware execution because noise prevents meaningful results.
- Experimental setup: The study reports independent and simultaneous executions, selecting the best initial mapping from ten attempts and setting α1, α2, and W to 0.5.QHSP uses λ=2 for different-size circuits and λ=1 for the deuteron experiment; the post-partition threshold δ is 0.1.
7.2 Application: simultaneous executions of multiple circuits of different sizes
QuMC’s QHSP configuration supports simultaneous execution of circuits with fidelity losses relative to partitioned independent execution while increasing throughput and reducing added-gate overhead in the reported experiments.
- Two circuits: 31.8% higher fidelity and 9.2% fewer additional gates are obtained by QHSP versus HA, while QHSP versus PHA loses 5.4% fidelity and adds 0.3% gates.
- Three and four circuits: For three and four simultaneous circuits on IBM Q 65 Manhattan, QHSP improves fidelity over HA by 5.3% and 13.3%, respectively, while reducing inserted gates.
- Three and four circuits: The corresponding fidelity losses versus PHA are 1.5% and 6.4%, while TRF reaches three and four for the two configurations.
- Different-size circuits: With δ=0.2, all five small benchmarks run simultaneously on IBM Q 65 Manhattan, with QHSP fidelity 0.493 versus PHA fidelity 0.54 and 9.5% loss.
- Medium and large circuits: For medium and large benchmarks, QHSP reduces additional gates versus HA by 23.2%, 15.6%, and 13.2% across the reported compilation settings.
- Overall analysis: QHSP uses nearly the same number of gates as PHA, with fidelity decreasing less than 10% at threshold 0.1 and throughput increasing two- and fourfold on the two devices.
7.3 Application: estimate the ground state energy of deuteron
The authors apply QuMC with Pauli grouping to estimate deuteron’s ground-state energy, using simultaneous measurement circuits to reduce VQE overhead. The parallelism manager selects eight circuits corresponding to four parameterized circuits and four optimization repetitions.
- Experimental setup: Pauli grouping partitions the four Pauli strings into two commuting families, reducing each ansatz’s naive four measurements to two measurement circuits.The families are {ZI, IZ} and {XX, Y Y}.
- QuMC configuration: Eight circuits are selected for simultaneous execution, representing four parameterized circuits with four different parameters under Pauli grouping.Because one parameterized circuit requires two measurement circuits, this is equivalent to four optimization repetitions.
- Results: Figure 13 contrasts PG’s independent process using eight measurements with QuMCPG’s simultaneous process using one measurement, with TRF=8.The figure reports the comparison for deuteron ground-state energy estimation under four optimisations.
8 Discussion
The discussion examines how simultaneous execution affects fidelity across hardware sizes and circuit depths. QuMC can improve utilization and reduce runtime, while fidelity depends on partition quality, crosstalk, and relative circuit depth.
- Multi-programming mechanism and fidelity loss: Multi-programming improves hardware utilization and reduces total circuit runtime, but may slightly reduce circuit fidelity.The authors frame this as a throughput–output-fidelity trade-off.
- Multi-programming mechanism and fidelity loss: On IBM Q 127 Washington, two high-scoring, nonadjacent partitions are selected to execute identical circuits simultaneously without additional crosstalk.Their partition-score difference is around 0.01, and results are repeated five times.
- Multi-programming on circuits with varying depths: For the benchmark set in Section 7.2, the longest circuit is 2.5 times deeper than the shortest, yet the slightly shorter circuit’s fidelity is not influenced by parallel execution.This observation is based on program-wise results from Tables 5, 7, and 9.
- Multi-programming on circuits with varying depths: On IBM Q 7 Nairobi, P1 and P2 are separated by more than one hop to avoid additional crosstalk while testing circuits with varying depths.The original circuit has fixed depth 22, while the modified circuit ranges from depth 22 to 88.
9 Conclusion
The conclusion presents QuMC as a hardware-aware compiler for simultaneous quantum-circuit execution, combining parallelism selection, reliable partitioning, crosstalk consideration, and reduced-gate mapping. Experiments report improved utilization and runtime, while VQE results indicate reduced algorithmic overhead.
- Contributions: QuMC selects the number of simultaneous circuits using a parallelism manager and fidelity metric, then allocates reliable partitions with greedy and heuristic algorithms.The partitioning algorithms incorporate hardware topology, calibration data, and crosstalk.
- Contributions: A crosstalk-aware partition algorithm considers crosstalk during partitioning to mitigate its effect during simultaneous execution.The authors identify this as the first crosstalk-aware partition algorithm.
- Contributions: An improved simultaneous mapping transition algorithm transpiles circuits with fewer inserted gates.The stated goal is executable hardware mappings with reduced mapping overhead.
- Experimental results: Experiments on IBM hardware show that QuMC can outperform independent executions using a state-of-the-art qubit-mapping approach, while VQE experiments show added value for existing quantum algorithms.The VQE experiment estimates the deuteron ground-state energy.
- Scope: The evaluation uses IBM quantum hardware, although the authors state that QuMC is general enough to adapt to other quantum hardware.A preparation-time access constraint prevented use of IBM private chips.
- Guidelines: The main practical concern is the trade-off between output fidelity and hardware throughput, so the number of simultaneous programs and fidelity threshold require careful selection.The recommended threshold for the small experimental benchmarks is 0.1.
A Supplementary experimental results
Supplementary experiments compare fidelity and inserted-gate counts for simultaneous execution of small, medium, and large circuits on IBM Q 27 Toronto and IBM Q 65 Manhattan. The reported tables organize results by circuit count and benchmark size.
- Experimental coverage: The supplementary results include two small circuits on IBM Q 27 Toronto, three and four small circuits on IBM Q 65 Manhattan, and medium and large circuits on both devices.The experiments are reported in Tables 5–13.
- Fidelity comparisons: Tables 7 and 9 compare fidelity for simultaneous execution of three and four small circuits on IBM Q 65 Manhattan.Table 7 covers three circuits, while Table 9 covers four.
- Reported metrics: The supplementary metrics include average PST, partition-process runtime, and changes in average PST or total additional gates.The notation defines t as partition-process runtime, ∆PST as a comparison of average PST, and ∆g as a comparison of summed additional gates.
- Inserted-gate comparisons: Tables 10–13 compare the number of additional gates for four small, two medium, three medium, and two large simultaneous benchmarks.The hardware is IBM Q 65 Manhattan except for the two-medium-benchmark experiment on IBM Q 27 Toronto.