How Many Shots Are Enough for a Quantum Circuit?

This paper introduces IncrementalExecution, a black-box online framework that dynamically optimizes the number of quantum circuit shots by identifying the point of diminishing returns to balance execution costs and result fidelity without relying on specific circuit structures or noise models.

The Gist

The Big Problem: The "Blind Taste Test"

Imagine you are a chef trying to perfect a new soup recipe. You can't taste the whole pot at once; you have to take small spoonfuls (samples) to guess the flavor.

• The Soup: A quantum computer circuit.
• The Spoonfuls: "Shots." In quantum computing, you can't just run a program once and get a perfect answer. Because of the weird nature of quantum physics, you have to run the same program many times to get a reliable picture of the result.
• The Dilemma: If you take too few spoonfuls, your guess about the flavor might be wrong. If you take too many, you waste time and money (since quantum computers are expensive to rent).

The big question the authors ask is: How many spoonfuls do you actually need before you can stop tasting and be confident you know the flavor?

The Old Way vs. The New Way

The Old Way (The Guesswork):
Previously, developers had to guess a fixed number of shots (e.g., "Let's run this 10,000 times") based on rules of thumb or complex math formulas that assumed they knew exactly how the quantum computer would behave.

• The Flaw: Quantum computers are noisy and unpredictable. Sometimes 10,000 shots are overkill (wasting money); other times, they aren't enough (giving a bad result). It's like guessing you need exactly 50 spoonfuls of soup without ever tasting the first one.

The New Way (The "Diminishing Returns" Approach):
The authors introduce a new framework called IncrementalExecution. Instead of guessing a number, they suggest a smart, step-by-step approach.

Think of it like filling a bucket with a leaky hose:

1. You start pouring water (running shots).
2. You check the water level (the data) after every few seconds.
3. You keep pouring as long as the water level is rising significantly.
4. The Stop Signal: The moment you notice that adding more water barely changes the level anymore, you stop. You've reached the "point of diminishing returns."

How It Works (The "Black Box" Magic)

The authors call their method a "black box" approach. This means they don't need to know:

• How the soup recipe is written (the circuit structure).
• How the stove is broken (the noise model of the hardware).

They just look at the results coming out.

1. Run a small batch: Execute the circuit 50 times.
2. Check the pattern: Look at the results.
3. Run another batch: Execute it 50 more times.
4. Compare: Did the new 50 shots change the overall picture much?
   • Yes? Keep going.
   • No? The pattern has stabilized. Stop now. You saved money!

The "Diminishing Returns" Concept

The paper relies on a simple economic idea: Diminishing Returns.
Imagine you are studying for a test.

• First hour: You learn 50% of the material. Huge gain!
• Second hour: You learn another 30%. Good gain.
• Third hour: You learn 10%.
• Fourth hour: You learn 1%.
• Fifth hour: You learn 0.1%.

At some point, the effort (time/money) isn't worth the tiny gain in knowledge. The paper's software automatically finds that exact moment for quantum circuits and tells you to stop.

What They Found (The Results)

The authors tested this idea on 33,750 different settings across 180 different quantum circuits and simulated noisy computers. They ran 7.3 million experiments in total.

Here is what they discovered:

1. It Works: They can reliably stop early without losing accuracy.
2. It Saves Resources: Their smart method often uses far fewer shots than the "safe" fixed numbers or the strict math formulas used before.
3. It's Flexible: They found that different "rules" work better for different types of problems.
   • Analogy: Sometimes you need a very sensitive spoon to taste a delicate soup (strict settings). Other times, a rougher spoon is fine for a hearty stew (loose settings). Their system lets you choose the right "spoon" for the job.
4. It Handles Noise: Even though quantum computers are messy and noisy, this method is robust enough to handle the chaos without needing to know the specific cause of the noise.

Why This Matters

In the world of quantum computing, time is money. Every extra second a quantum computer runs costs the user real cash. By figuring out exactly when to stop, this framework helps users:

• Save money.
• Get results faster.
• Avoid wasting resources on unnecessary calculations.

Summary

The paper presents a smart, automatic "stop-watch" for quantum computers. Instead of blindly running a program a million times just to be safe, this new tool watches the results in real-time. As soon as the results stop changing significantly, it says, "Okay, we have enough data. Let's stop." It's a practical, cost-saving tool that works without needing to understand the complex physics behind the machine.

Technical Summary

Technical Summary: How Many Shots Are Enough for a Quantum Circuit?

1. Problem Statement

Quantum algorithms inherently produce probabilistic outputs, requiring repeated circuit executions (shots) to approximate the underlying probability distribution. Determining the minimal number of shots necessary to achieve a target accuracy is a critical resource optimization challenge, particularly for Noisy Intermediate-Scale Quantum (NISQ) devices where execution costs, queueing latency, and hardware noise are significant constraints.

Existing approaches to shot optimization typically rely on specific assumptions that limit their applicability:

• Analytical methods often require explicit knowledge of noise models (e.g., SPAM errors, $T_1/T_2$ times) or specific circuit structures.
• Adaptive strategies are designed for variational algorithms (VQAs) where circuit parameters evolve, inducing non-stationary output distributions.
• Learning-based methods often require training on specific optimization trajectories.

This paper addresses the black-box shot optimization problem for static, non-variational quantum circuits. In this setting, the circuit structure and parameters remain fixed across all shots, resulting in a stationary but unknown output distribution. The goal is to determine the minimal number of shots required to reach a target accuracy without prior knowledge of the circuit topology, noise model, or the true distribution.

2. Methodology: IncrementalExecution Framework

The authors propose IncrementalExecution, an online, iterative framework that dynamically determines when to stop executing shots based on the point of diminishing returns. This is defined as the state where additional shots no longer induce statistically significant changes in the empirical output distribution.

Core Concepts

• A Posteriori Optimality: The paper first defines a theoretical baseline: the minimal number of shots $n^*$ such that the empirical distribution $\hat{P}_{n^*}$ is within a threshold $\delta$ of the best possible estimate obtainable under a full budget $B$ (denoted $\hat{P}_B$). This serves as a retrospective ground truth for evaluation but is not computable online.
• Point of Diminishing Returns (Online Proxy): To enable online decision-making without access to the full budget distribution, the framework uses an observable proxy. It monitors the divergence between the current cumulative empirical distribution and a past distribution (separated by a look-back window $\tau$). Execution stops when this divergence falls below a tolerance $\epsilon$ for a required number of consecutive iterations ($k$).

Framework Architecture

The framework is modular, consisting of three pluggable policy components:

1. Stopping Criterion: Determines if the recent batch of shots introduced a statistically significant change (e.g., Delta Distance or Delta Moving Average).
2. Stability Criterion: Enforces a minimum number of consecutive stable iterations ($k$) to prevent premature stopping due to transient fluctuations.
3. Shot Allocation Policy: Dynamically determines the size of the next batch of shots (e.g., constant or adaptive based on convergence trends).

The framework operates under strict black-box assumptions: it requires no access to circuit internals, noise models, or ideal distributions. It relies solely on observed measurement outcomes.

3. Experimental Evaluation

The authors conducted an extensive evaluation involving 33,750 unique framework configurations across 180 unique static circuit–backend combinations, totaling 7.3 million independent experiments.

Experimental Setup

• Circuits: 28 static circuits (including QFT, QAOA, VQE, Random, QNN) with qubit counts ranging from 4 to 14.
• Backends: Five IBM noisy simulator backends (fake_fez, fake_kyiv, fake_marrakesh, fake_sherbrooke, fake_torino).
• Budget: A maximum shot budget of 20,000 was used to generate reference distributions.
• Metrics: Total Variation Distance (TVD), Hellinger distance, and Jensen–Shannon (JS) divergence were used to measure distributional stability.

Key Findings

• Validity and Parameters: Finding valid configurations (where the stopping condition is met within the budget) is highly sensitive to the stopping threshold $\epsilon$ and the target tolerance $\delta$. Validity is generally attainable only when $\epsilon < \delta$. The Delta Moving Average (DMA) stopping policy showed greater robustness in stricter regimes compared to the simple Delta policy.
• Circuit Size Impact: Small circuits (4–8 qubits) generally allow for high validity rates (often 100%) with the best configurations. Large circuits (10–14 qubits) present a harder challenge, with validity rates dropping and configurations requiring more shots, often approaching the full 20,000-shot budget under strict tolerances.
• Metric Sensitivity:
  • TVD is the most demanding metric, often requiring more shots to satisfy validity constraints.
  • Hellinger and JS are more permissive and often yield higher validity rates, particularly for larger circuits and looser tolerances.
• Comparison with State-of-the-Art:
  • vs. Analytical Bounds: IncrementalExecution is orders of magnitude more sample-efficient than worst-case concentration inequalities (Hoeffding and Weissman), which provide distribution-agnostic upper bounds that are overly conservative for practical NISQ scenarios.
  • vs. Fixed Budgets: The framework successfully stops execution once the target accuracy is reached, avoiding the waste of fixed-shot baselines that continue executing even after convergence.
• Algorithmic Behavior: Different algorithm families exhibit distinct stabilization profiles. Simple circuits (e.g., dj) stabilize quickly, while complex circuits (e.g., qft, random) require significantly more shots, sometimes reaching the budget cap, indicating that the fixed budget itself may be insufficient for high-variance regimes.

4. Key Contributions

1. Problem Formulation: A formal definition of the black-box shot optimization problem for static, non-variational circuits, explicitly avoiding assumptions about circuit structure or noise models.
2. A Posteriori Optimality: The introduction of a retrospective optimality criterion to serve as a rigorous baseline for evaluating online strategies.
3. IncrementalExecution Framework: A general, online, iterative framework that leverages the point of diminishing returns to stop execution adaptively.
4. Policy Suite: A comprehensive set of execution policies (stopping, stability, and allocation) that allow users to trade off between cost and accuracy.
5. Benchmark Dataset: The release of a new dataset containing iterative, shot-by-shot execution traces of static circuits on noisy backends, enabling reproducible evaluation of shot-optimization techniques.

5. Significance and Claims

The paper claims to be the first work to address shot-count optimization using an online strategy in a black-box setting for static circuits without relying on assumptions about circuit structure or noise models.

• Practical Viability: The authors argue that the framework is immediately deployable on current quantum cloud platforms. They highlight that emerging infrastructure, such as quantum sessions (IBM) and reservation-based models (IonQ, Rigetti), mitigates the latency overheads typically associated with adaptive, iterative execution, making the "stop-and-check" paradigm feasible.
• Cost Reduction: By detecting the point of diminishing returns, the framework prevents the execution of unnecessary shots, directly reducing monetary costs and queueing time on expensive hardware.
• Generality: Unlike prior work restricted to variational algorithms or specific noise models, this approach applies to a broad class of static workloads, including benchmarking, calibration, and fixed-algorithm execution.

The authors maintain a modest stance, acknowledging that their evaluation is based on noisy simulators and that real-hardware validation (including queueing delays and calibration drift) is a necessary future step. They also note that while the framework is qubit-agnostic, the optimal configuration parameters depend on circuit size and complexity, suggesting that automated tuning mechanisms are required for broad deployment.