PaperlayerView exact revision on arXiv

Source-linked AI summary

Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation

Shin Nishio, Yulu Pan, Takahiko Satoh, Hideharu Amano, Rodney Van Meter

arXiv:1903.10963v1quant-phcs.CL

TL;DR

Because error rates vary across qubits and full error correction remains out of reach, compilation must account for hardware errors to improve execution success. The paper uses composable Estimated Success Probability (ESP) to guide circuit compilation and finds improved ESP and lower KL divergence for one-qubit adders, while the relationship weakens for more complex circuits.

  • Problem

    Qubit error rates vary, while full error correction remains out of reach, making error-aware compilation relevant to execution success.

    Source: §1 · p. 1

  • Method

    The compiler optimizes composable Estimated Success Probability (ESP), defined as the product of the success probabilities of a circuit’s component operations.

    Source: §4 · p. 7, §5 · p. 12

  • Results

    The compiler improved circuit ESP, and one-qubit adders showed lower KL divergence; for more complex circuits, the relationship vanished or KL divergence became worse than uniform distribution.

    Source: §5 · p. 12

  • Takeaways & Limitations

    ESP-focused compilation can mitigate errors for smaller NISQ circuits, but the benefit is limited as circuit complexity grows.

    Source: §5 · p. 12

    Full tomography is impractical even at 20 qubits and beyond reach for larger systems because the number of possible states grows exponentially.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

NISQ (Noisy, Intermediate-Scale Quantum) computing requires error mitigation to achieve meaningful computation. Our compilation tool development focuses on the fact that the error rates of individual qubits are not equal, with a goal of maximizing the success probability of real-world subroutines such as an adder circuit. We begin by establishing a metric for choosing among possible paths and circuit alternatives for executing gates between variables placed far apart within the processor, and test our approach on two IBM 20-qubit systems named Tokyo and Poughkeepsie. We find that a single-number metric describing the fidelity of individual gates is a useful but imperfect guide. Our compiler uses this subsystem and maps complete circuits onto the machine using a beam search-based heuristic that will scale as processor and program sizes grow. To evaluate the whole compilation process, we compiled and executed adder circuits, then calculated the KL-divergence (a measure of the distance between two probability distributions). For a circuit within the capabilities of the hardware, our compilation increases estimated success probability and reduces KL-divergence relative to an error-oblivious placement.

1. INTRODUCTION

Because qubit error rates vary, this paper focuses on error-aware mapping and gate execution on IBM’s 20-qubit Tokyo and Poughkeepsie systems. It evaluates whether estimated gate success can guide circuit choices and whether compilation improves complete-circuit execution.

1. INTRODUCTION

  • The paper focuses on mapping program variables to hardware locations and generating gates between distant qubits, testing its approach on Tokyo and Poughkeepsie.This is the second phase of machine-level compilation.Source: §1 · pp. 1–2
  • Qubit error rates vary substantially, and Tokyo’s reported two-qubit error rates range from 3% to 12%, motivating placement choices that prioritize execution success.The authors make success probability, rather than gate-count reduction, their primary goal.Source: §1 · p. 2
  • The product of individual gate success probabilities ranked two equivalent circuits correctly about two-thirds of the time, despite inaccurate absolute estimates.The compiler uses this metric to choose among alternative implementations of long-distance gates.Source: §1 · p. 2
  • A beam-search heuristic addresses the NP-complete circuit-mapping problem, and the authors report that simple ESP can improve success probability at reasonable classical compilation cost.They expect the approach to scale to larger processors, while proposing more nuanced metrics as a path to further improvement.Source: §1 · pp. 2–3
  • Smaller adder circuits produced less divergence from expected output distributions than random variable placement, while the largest circuits exceeded the hardware’s capabilities.The compiler was tested on adders with one-, two-, and four-qubit input registers.Source: §1 · pp. 2–3

2. BACKGROUND

The background describes hardware error categories, the limits of full tomography, randomized benchmarking, and prior architecture-aware compilation work. It motivates using accessible per-gate error estimates while accounting for connectivity and fidelity.

2.1 Error model

  • The error model groups errors into single-qubit gates, CNOTs, and SPAM; SPAM occurs only once per qubit and has less cumulative impact on success.Single-qubit and CNOT errors can include bit or phase flips, while CNOT errors can propagate between qubits.Source: §2.1 · p. 3

2.2 Tomography

  • Full tomography characterizes states or processes but requires exponentially growing resources, making it impractical even at 20 qubits and beyond reach for larger systems.It can characterize state-dependent crosstalk and other factors that simpler error estimates do not fully describe.Source: §2.2 · p. 3

2.3 Randomized Benchmarking

  • Randomized benchmarking samples Clifford-gate sequences, appends an operation that reverses them, measures the output, and varies sequence length to estimate average gate error.Attenuation can be fitted across sequence lengths, with SPAM effects compensated through that attenuation.Source: §2.3 · p. 3
  • Qiskit’s daily RB-derived error values are useful and reasonably inexpensive, but incomplete descriptions of system behavior.The authors ask whether these values suffice to extract high success probability without extensive machine testing before each compilation.Source: §2.3 · pp. 3–4

2.4 Architecture-Aware Compilation

  • Earlier architecture-aware studies emphasized execution time; later work considered fidelity, including approaches that account for per-qubit error variation.The cited work by Zulehner et al. did not consider qubit-to-qubit error variance, while Tannu et al. and Finigan et al. [49] [50] maximized ESP using per-qubit errors.Source: §2.4 · p. 4

3. LONG-DISTANCE CNOTS AND MAKING CHOICES

The section tests whether Estimated Success Probability (ESP) can guide choices among routes and equivalent circuits for remote CNOT gates. ESP often favors better-performing options, but its accuracy varies across route length, circuit choices, and processor settings.

3.1 Path selection for remote CNOT

  • ESP chose the better of two routes with 70% accuracy at 2 hops, 66.6% at 3 hops, and 62.5% at 4 hops.Experiments covered routes up to four hops, the maximum qubit eccentricity reported for the largest IBM processor then available.Source: §3.1 · pp. 4–5
  • The route experiments measured bit-flip errors, although ESP's reported error values include bit-flip and phase-flip errors; the authors identify this and crosstalk as possible explanations for mismatches.They say future tests will distinguish the relative importance of these two explanations and do not consider calibration drift important.Source: §3.1 · p. 5

3.2 Circuit Selection for Remote CNOT

  • The experiments compare theoretically equivalent remote-CNOT paths and circuits because their realized fidelities can differ on the hardware.The motivating problem is choosing a high-fidelity route or circuit when control and target qubits are not neighbors.Source: §3.1 · p. 4, §3.2 · p. 5
  • For three circuit candidates on Tokyo, ESP selected the optimum 40% of the time, compared with a 1/3 random-selection rate.ESP chose circuits B, C, and D 35%, 10%, and 55% of the time, while the respective experimental optima were B 50%, C 15%, and D 35%.Source: §3.2 · p. 5
  • Tokyo's unequal two-qubit edge errors led ESP to choose circuits B or D more often than circuit C, despite C using one fewer two-qubit gate.If the two edge errors are balanced, circuit C is the best choice.Source: §3.2 · p. 5
  • On Tokyo, ESP-selected circuits among seven candidates had average fidelity 0.8609 versus average ESP 0.8255, while ESP chose the optimum 25% of the time.With seven candidates, 25% exceeded random selection's 1/7 optimum rate.Source: §3.2 · p. 6
  • ESP selected the optimum circuit from among seven candidates 43% of the time; average fidelity was 0.8492 for the best-result circuit and 0.8405 for the ESP-selected circuit, a 0.87% difference.The authors call this gap extremely small compared with 3.5% in Tokyo and say reliability is improved.Source: §3.2 · p. 6
  • ESP selected the optimum circuit from seven candidates 36% of the time; selected-circuit execution fidelity averaged 0.7966 versus 0.8077 for the best-result circuit, a 1.10% difference.Accuracy improved significantly over result 2′, was slightly lower than result 3, and overall fidelity was low.Source: §3.2 · p. 7

4. COMPILING COMPLETE PROGRAMS

The compiler ranks complete circuit realizations using Estimated Success Probability (ESP), extending the component-level metric to a circuit. Because ESP is not suitable for evaluating real-device output distributions, the paper uses KL divergence for that evaluation.

4. COMPILING COMPLETE PROGRAMS

  • ESP for a circuit is the product of the ESPs of its components, which gives the compiler a metric for distinguishing more reliable circuit realizations.The compiler's stated optimization task is to maximize ESP(C).Source: §4 · pp. 7–8
  • The ESP formulation assumes each gate or measurement either succeeds completely or halts execution on failure, and that failures are independent and depend only on the physical qubits involved.Source: §4 · p. 7
  • Because real circuit outputs are probability distributions, the paper evaluates compiled circuits by comparing sampled and ideal distributions with KL divergence rather than ESP.The paper studies the relationship between ESP and KL divergence on IBM Q20 Tokyo.Source: §4 · p. 8

4.1 Search Space

The compiler's search space combines gate-execution progress with mappings of logical variables to physical qubits. Connectivity and gate-order constraints restrict valid transitions, while the full search is intractable to explore exhaustively.

4.1 Search Space

  • A search state pairs a gate-execution state with a qubit mapping, yielding 2^N execution states and QPV = Q×(Q−1)×···×(Q−V+1) mappings per state.Source: §4.1 · p. 8
  • Executing a gate moves upward within a mapping's hypercube, while inserting SWAPs changes the mapping and moves laterally; each bottom-to-top path represents a compiled circuit.Source: §4.1 · p. 8
  • Adjacency and gate dependencies forbid transitions, and exhaustive search is infeasible because it may traverse 2^N × QPV states and the optimal path problem is NP-hard.Source: §4.1 · p. 8

4.2 The Optimization Algorithm

The optimization algorithm uses beam search to prune the circuit-mapping search, balancing solution quality against computational cost. It combines heuristic and random initial mappings to pair informed starts with exploration.

4.2 The Optimization Algorithm

  • Beam search retains a fixed number of promising states at each depth, with larger beam width increasing search effort and the prospect of better solutions.Beam width 1 is greedy search, while an unbounded width approaches breadth-first search.Source: §4.2 · p. 8
  • The search starts from a heuristic initial qubit mapping plus random mappings, combining heuristic starting configurations with exploration of other configurations.M denotes the number of random initial mappings.Source: §4.2 · p. 8
  • With N gates, M random initial mappings, and beam width B, the algorithm's total complexity is O(N^2M + N^3B).The first term accounts for the initial iteration; the second covers the remaining iterations.Source: §4.2 · p. 8

4.3 Subroutines for Compilation Algorithm

The compiler scores partial mappings using current and estimated future gate success, initializes mappings to favor heavily used low-noise connections, and selects SWAP sequences by estimated success probability.

4.3.1 Scoring States

  • The compilation algorithm initializes mappings, executes dependency-ready gates with selected SWAPs, updates state scores, and retains the top B states at each step.The final output is the best state remaining after all gates have been processed.Source: §4.3.1 · p. 9
  • Future-gate imaginary ESPs are multiplied by executed-gate ESP to score states, and pruning removes lower-scoring states.Imaginary ESP estimates the SWAPs needed under the current mapping plus the gate success probability; it may differ from actual ESP after earlier SWAP insertions change mappings.Source: §4.3.1 · p. 9

4.3.2 Heuristic Initial Mapping: Greatest Connecting Edge Mapping

  • Greatest Connecting Edge Mapping builds a guest graph from CNOT counts, then maps its strongest connections onto low-noise adjacent physical qubits when available.It starts with the guest graph's greatest edge on the least noisy physical edge; unmapped variables without available adjacent qubits are assigned randomly at the end.Source: §4.3.2 · p. 9

4.3.3 Finding Best Swap Sequence

  • BEST_SWAP selects a meeting edge and SWAP paths that maximize the product of their ESPs and the CNOT's ESP.The implementation precomputes optimal paths for all qubit pairs with Warshall-Floyd and caches BEST_SWAP results.Source: §4.3.3 · pp. 9–10

4.4 Experimental Evaluation of Compilation

The evaluation compares ideal and sampled output distributions because circuit runs do not have a single-shot success label. On Tokyo, beam search often raised ESP substantially, but the ESP–KL relationship and output quality weakened as adders grew more complex.

4.4.1 Probability Distribution Based Evaluation

  • The evaluation compares the ideal output distribution with the machine-sampled empirical distribution using KL divergence; lower DKL indicates a closer match.Runs sampled 5,000 shots per estimate, and lower DKL means the compiled circuit's output is closer to ideal.Source: §4.4.1 · p. 10

4.4.2 Experiment and Result

  • Cucarro ripple-carry adders with 1-, 2-, and 4-qubit inputs were tested on IBM Q20 Tokyo against beam-search (B=10,000, M=1,000) and random-selection compilers, using 5,000-shot repeated sampling.Source: §4.4.2 · pp. 10–11
  • For the 2-qubit adder example, random selection had ESP = 0.169 and DKL = 0.297, while beam search had ESP = 0.091 and DKL = 0.216.Figure 18 compares both observed distributions with the ideal distribution.Source: Figure 18 · p. 11
  • Beam-search circuits often achieved about one magnitude higher ESP than alternatives across the plotted experiments.The plots use a logarithmic ESP axis.Source: §4.4.2 · p. 12
  • Most 1-qubit adder runs beat a uniform distribution, but only half of 2-qubit runs and none of 4-qubit runs did, regardless of compiler.KL divergence worsened as the number of qubits and circuit complexity increased.Source: §4.4.2 · p. 12
  • ESP and KL correlated at −0.475 for 1-qubit adders, at −0.0279 for 2-qubit adders, and negatively for 4-qubit adders whose KL remained worse than uniform.For 4-qubit adders, the reported KL improvement was too small to make computation reliable.Source: §4.4.2 · p. 12

5. FUTURE WORK AND CONCLUSION

The beam search compiler improves circuit ESP, and for 1-qubit adders that improvement accompanies lower KL divergence; the relationship weakens or disappears for more complex circuits. The conclusion also identifies limits in ESP’s predictive accuracy, memory-error modeling, and KL-based evaluation.

5. FUTURE WORK AND CONCLUSION

  • The compiler optimizes full-circuit ESP, defined as the product of component ESPs, while KL divergence assesses experimental output distributions.The authors use KL divergence because circuit ESP cannot be experimentally observed for circuits ending in a superposition state; they describe KL as an intermediate tool in lieu of full tomography.Source: §5 · p. 12
  • ESP-based path and circuit selection produced lower KL divergence than random choice among shortest-path candidates, but the best success rate for a two-hop path was 70%.Source: §5 · p. 12
  • For 1-qubit adders, improved ESP accompanied lower KL divergence, but for more complex circuits the relationship vanished or KL divergence became worse than the uniform distribution.The authors describe the latter behavior as demonstrating the limits of current NISQ computation.Source: §5 · p. 12
  • In some cases, ESP selected the optimal choice from seven candidates only 43% of the time because ESP and physical reality diverge.Source: §5 · p. 12
  • The current approach does not account for memory errors, and incorporating gate-by-gate wait times with T1 and T2 decoherence is difficult in Qiskit.The authors are considering execution-time modeling with a blanket decoherence term.Source: §5 · p. 12
  • The KL-based evaluation does not work for quantum-supremacy circuits because it requires deriving the ideal distribution with a classical computer beforehand.The authors say further methods are needed to estimate KL divergence and assess sign errors as well as bit-flip errors.Source: §5 · p. 12
  • The authors hope error-aware compilation will inform Qiskit and other compilers, and that improved success prediction could help evaluate couplers and qubit layouts.Source: §5 · p. 12
Loading 1903.10963v1…