arXiv CSopen access

How Many Shots Are Enough for a Quantum Circuit?

How Many Shots Are Enough for a Quantum Circuit? GIUSEPPE BISICCHIA, University of Pisa, Italy ALESSANDRO BOCCI, University of Pisa, Italy ERNESTO PIMENTEL, University of Malaga, Spain ANTONIO BROGI, University of Pisa, Italy Quantum algorithms require repeated circuit executions – known as shots – to estimate output distributions accurately. Determining

arXiv:2606.16965v1 [quant-ph] 15 Jun 2026

the minimal number of shots needed to meet a target accuracy is crucial to reduce costs and resource usage, especially on today’s noisy and expensive quantum hardware. In this paper, we address the shot optimisation problem in a black-box setting, where no assumptions are made about the structure of the quantum circuit or the noise model of the backend. We introduce IncrementalExecution, a novel online framework that dynamically determines when to stop executing shots based on the principle of point of diminishing returns: the point at which additional shots no longer significantly alter the empirical distribution of a fixed circuit. The framework supports customisable policies for shot management, enabling flexible trade-offs between execution cost and result fidelity within static execution scenarios. We assess our proposal through an extensive experimental evaluation spanning 33,750 framework configurations across 180 unique static quantum circuit–backend combinations, for a total of 7.3M independent experiments. Unlike prior work that relies on problem-specific knowledge or algorithm-dependent assumptions (e.g., variational or adaptive workflows), our approach is applicable to a large set of static circuits and immediately deployable on current quantum cloud platforms. Additional Key Words and Phrases: Quantum Computing, Quantum Software Engineering, Hybrid Quantum Cloud, Incremental Execution, Point of Diminishing Returns ACM Reference Format: Giuseppe Bisicchia, Alessandro Bocci, Ernesto Pimentel, and Antonio Brogi. 2026. How Many Shots Are Enough for a Quantum Circuit?. 1, 1 (June 2026), 57 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

Introduction

Quantum computing is inherently probabilistic [21]. When executing a quantum circuit, the result is not deterministic but rather sampled from an unknown probability distribution defined by the quantum state measured [45]. Consequently, obtaining meaningful and accurate results from quantum computations requires executing the circuit multiple times – a process known as performing shots. Each shot corresponds to a single execution of the circuit, and the empirical distribution obtained from repeated shots approximates the true underlying quantum distribution, or ground truth [37]. When executing a quantum circuit, quantum software developers choose a fixed number of shots based on the size of the circuit or prior knowledge. The number of shots chosen to execute a quantum circuit significantly impacts both the accuracy of the resulting measurement statistics and the cost of computation, in terms of both execution time and Authors’ Contact Information: Giuseppe Bisicchia, [email protected], University of Pisa, Pisa, Italy; Alessandro Bocci, alessandro.bocci@ unipi.it, University of Pisa, Pisa, Italy; Ernesto Pimentel, [email protected], University of Malaga, Malaga, Spain; Antonio Brogi, [email protected], University of Pisa, Pisa, Italy. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. Manuscript submitted to ACM Manuscript submitted to ACM

1

2

Bisicchia et al.

resource consumption [3, 4]. This becomes especially significant in current Noisy Intermediate-Scale Quantum (NISQ) devices, which are resource-constrained and prone to fluctuations in noise characteristics [20, 36]. Thus, accurately determining the number of shots to execute is increasingly recognised as an essential practical challenge in quantum computing [15, 24, 48, 49]. Shot allocation has been extensively studied in the context of variational and other adaptive quantum algorithms [26, 29, 32, 50]. However, these workloads introduce intrinsic non-stationarity, as the circuit structure or parameters evolve across optimisation iterations, causing the underlying output distribution to change over time. Instead, we focus on static, non-variational quantum circuits1 , whose structure and parameters remain fixed across repeated executions. This setting captures a broad and practically relevant class of workloads, including benchmarking, calibration, device characterisation, and the execution of fixed quantum algorithms. In this work, therefore, we investigate the following main research question (MRQ): MRQ: Given a static, non-variational quantum circuit and a noisy quantum processing unit (QPU), is it possible to determine how many shots are sufficient to reach a required target accuracy? It is worth noting that the statistical structure of this problem is not intrinsically quantum. At its core, it is an online sample-optimisation problem for a stationary black-box stochastic process with finite outcomes: after each batch of samples, one must decide whether additional samples are still changing the empirical distribution sufficiently to justify their cost. Classical instances include Monte Carlo estimation of categorical distributions, repeated benchmarking of randomized algorithms, stochastic simulators with discrete outputs, probabilistic software testing, and workload or failure-mode characterisation in distributed systems. Quantum circuit execution provides a particularly compelling instantiation because samples correspond to hardware shots, which incur monetary cost, queueing latency, and noise-dependent variability. Specifically, we aim to design a methodology capable of approximating the optimal number of shots, defined as the point of diminishing returns where additional shots no longer meaningfully alter the empirical output distribution2 for a fixed circuit instance. We tackle this question under a general black-box setting, where no assumptions are made about the internal structure of the circuit or the noise model of the quantum hardware3 . Prior work on this problem typically assumes knowledge about the quantum system, such as known noise models or the use of specific algorithmic families (e.g., Variational Quantum Algorithms (VQAs) [17] or Quantum Machine Learning (QML) [5]). These assumptions restrict the scope of applicability and compromise robustness in realistic scenarios, where hardware noise is inherently stochastic, time-dependent, and hard to model accurately [2]. Moreover, approaches designed for variational settings do not directly transfer to static circuits, where the primary challenge lies in efficiently estimating a fixed but unknown output distribution. 1 A static quantum circuit execution refers to the repeated execution of a quantum circuit whose gate sequence, topology, and parameters remain fixed

across all shots. Under this assumption, the ground-truth output probability distribution is stationary throughout the execution. In contrast, variational, adaptive, or feedback-driven executions induce non-stationary output distributions due to circuit updates across iterations and require different statistical guarantees and stopping criteria. 2 While many quantum applications ultimately aim to estimate expectation values of specific observables, in this work we deliberately focus on stabilisation of the output distribution. This choice is motivated by generality: a sufficiently accurate empirical distribution enables the evaluation of a wide class of observables, whereas the converse does not hold [37]. 3 The same problem can also be formulated in a grey-box setting, where partial information is available – such as aggregated properties of the circuit structure, output distribution, or noise model – and in a white-box setting, where full access to the circuit and noise model is assumed. In this work, we focus on the black-box formulation as the most assumption-free scenario within the scope of static circuit execution. Extending the methodology to variational or other adaptive workloads requires handling non-stationary distributions induced by circuit updates, and we leave this to future work. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

3

Our approach fundamentally differs from prior work by reframing the problem into one of detecting the point of diminishing returns, a state where additional shots no longer result in statistically significant updates to the empirical output distribution of a static circuit. Once this point is reached, further execution becomes unnecessary, as it no longer improves the estimation of the underlying distribution or the accuracy of the results. This reframing is particularly well suited to static circuits, where the target distribution remains stationary across executions. Building on this principle, we introduce a general, iterative framework – named IncrementalExecution – which iteratively performs a limited number of shots until the point of diminishing returns is reached. The framework supports a variety of execution policies designed to detect and exploit the point of diminishing returns efficiently while enabling customisation and adaptation to different use cases and optimisation goals within static execution scenarios. These policies govern the shot allocation process in an online, dynamic fashion, enabling the framework to adaptively decide when to stop execution. In summary, the main contributions of our work are:

(1) We formally define the black-box shot optimisation problem for static, non-variational quantum circuits, where the goal is to determine the minimal number of quantum circuit executions (shots) required to meet a target accuracy, without making assumptions about the circuit structure or QPU noise model. (2) We introduce a notion of a posteriori optimality, which determines the optimal number of shots after execution by identifying the minimal number required to achieve the point of diminishing returns for a specific static execution, assuming full access to the output samples. (3) We design and implement the IncrementalExecution framework, an online, iterative approach that leverages the point of diminishing returns to stop execution as soon as sufficient statistical confidence is reached for static circuits. The framework directly addresses the black-box shot optimisation problem within this scope. (4) We define a suite of flexible execution policies that operationalise the framework and allow adaptation to various practical requirements and optimisation goals, enabling a controlled trade-off between cost and accuracy in static execution contexts. (5) We propose and release a new comprehensive benchmark dataset [6, 10] that includes the iterative, shot-by-shot execution of various static, non-variational quantum circuits on different quantum hardware backends, enabling reproducible evaluation of shot-optimisation techniques.

Our experimental evaluation indicates that the IncrementalExecution Framework effectively and efficiently approximates the optimal number of shots in black-box settings for static circuits. Furthermore, we show how suitable execution policies allow users to explicitly control and balance execution costs and statistical accuracy. To the best of our knowledge, this work is the first to address the problem of shot-count optimisation using an online strategy in a black-box setting for static, non-variational quantum circuits, without relying on assumptions about circuit structure or noise models. The remainder of this paper is organised as follows. Section 2 reviews related literature. Section 3 formally defines the shot optimisation problem. Section 4 introduces the IncrementalExecution Framework. Section 5 describes execution policies. Section 6 presents an empirical evaluation. Section 7 discusses applicability. Section 8 addresses threats to validity, and Section 9 concludes. Manuscript submitted to ACM

4

Bisicchia et al.

2

Related Work

Optimising the number of shots in quantum computations is a critical research challenge, particularly for NISQ devices, where execution cost, latency, and hardware noise significantly affect result quality. Existing approaches to shot optimisation can be broadly categorised into four main classes: (1) analytical noise- or concentration-based estimation methods, (2) adaptive shot allocation techniques for variational and other adaptive quantum algorithms, (3) learning-based strategies, and (4) online black-box execution control. In the following, we review these categories and position our work within this landscape. 2.1

Analytical Noise- and Concentration-Based Estimation

Analytical approaches estimate the required number of shots by deriving error bounds under explicit statistical or noise-related assumptions. Seksaria and Prabhakar [41] propose a systematic framework that incorporates detailed hardware noise models, including state preparation and measurement (SPAM) errors, amplitude damping (𝑇1 ), phase damping (𝑇2 ), and gate errors. Their approach leverages the Central Limit Theorem to derive closed-form expressions for measurement variance. While effective, its accuracy critically depends on precise noise characterisation and has primarily been validated on VQE workloads [43]. A complementary line of work relies on concentration inequalities to estimate the number of shots required to bound statistical error with high probability [25, 34, 44]. Hoeffding-style inequalities [27] are commonly used to derive worst-case bounds on the estimation error of expectation values or probabilities under the assumption of independent and identically distributed samples. Weissman-type inequalities [33, 46] further extend this analysis by providing finite-sample guarantees on the ℓ1 distance between the empirical and true output distributions. While these bounds offer strong theoretical guarantees, they typically lead to conservative shot estimates and require users to predefine confidence levels and error thresholds a priori, limiting their practical applicability in quantum execution settings [16, 35]. 2.2

Adaptive Shot Allocation in Variational and Adaptive Quantum Algorithms

The most extensively explored class of shot optimisation techniques targets variational and other adaptive quantum algorithms, where shot allocation is dynamically adjusted across optimisation iterations. In these settings, the circuit structure or parameters evolve over time, inducing non-stationary output distributions. Variance-Preserved Shot Reduction (VPSR). Zhu et al. [50] propose the VPSR approach, which dynamically reallocates measurement shots based on real-time variance estimates of Hamiltonian terms grouped into commuting cliques. Their method achieves substantial shot reductions in molecular ground-state simulations (e.g., 𝐻 2 and 𝐿𝑖𝐻 ), but relies on explicit Hamiltonian structure and is inherently tied to VQE-style workflows. Coupled Adaptive Shot Strategies. Gu et al. [26] introduce global Coupled Adaptive Number of Shots (gCANS), optimising shot allocation by maximising expected utility derived from gradient magnitudes at each iteration. Kübler et al. [31] refine this approach with individual CANS (iCANS), allocating shots at the level of individual gradient components. Both strategies assume access to gradient information and are designed for iterative parameter optimisation. Distribution-Adaptive Dynamic Shot Allocation (DDS). Kim et al. [30] propose DDS, which links the required number of shots to the entropy of the circuit output distribution and dynamically adapts shot counts across optimisation Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

5

iterations. While effective in reducing average shot counts, DDS assumes an adaptive execution model where circuit parameters change over time. Shot Optimisation in Quantum Machine Learning. Phalak and Ghosh [39] explore adaptive shot scheduling in quantum machine learning by varying shot counts across training epochs using linear and step-based schedules. Their approach achieves large shot reductions with minimal accuracy degradation, but relies on supervised learning signals and task-specific performance metrics. Estimator–Optimiser Framework. Kahani and Nobakhti [29] propose a modular estimator–optimiser framework for VQAs, explicitly separating observable estimation from parameter optimisation. Their approach dynamically controls estimation error through sensitivity analysis, but assumes iterative circuit updates and estimator-specific tuning. 2.3

Learning-Based Methods

Learning-based strategies use machine learning techniques, most notably reinforcement learning (RL), to infer shot allocation policies from execution data. Liang et al. [32] propose an RL-based framework that learns shot allocation decisions during VQE optimisation. While reducing reliance on handcrafted heuristics, this approach is tightly coupled to variational workflows and requires training over representative optimisation trajectories. 2.4

Positioning of This Work

Most existing shot optimisation strategies rely on explicit assumptions about circuit structure, noise characteristics, access to gradient information, or adaptive execution semantics. While effective within their intended domains, these approaches are not directly applicable to static, non-variational quantum circuit executions, where the primary challenge lies in efficiently estimating a fixed but unknown output distribution under hardware noise. In contrast, our proposed IncrementalExecution framework adopts an online, black-box execution control perspective specifically tailored to static circuits. Rather than estimating accuracy a priori or relying on algorithm-specific signals, the framework dynamically detects the point of diminishing returns—the point at which additional shots no longer induce statistically meaningful changes in the empirical output distribution—and halts execution accordingly. This enables principled and assumption-light shot optimisation for static workloads, complementing existing analytical, adaptive, and learning-based techniques, and addressing a distinct and practically relevant gap in the literature. Table 1 summarises the reviewed methods, highlighting their optimisation metrics, algorithmic contexts, and underlying assumptions. 3

The Black-box Sample Optimisation Problem

Quantum circuit execution is inherently stochastic: each execution produces a measurement outcome sampled from an unknown output distribution. Accurately estimating this distribution requires repeated sampling—or shots—yet each additional shot incurs cost and latency, especially on real quantum hardware. In this paper, we study the fundamental question of how to determine, as efficiently as possible, how many shots are sufficient for a given execution, i.e., when additional shots yield diminishing returns. Importantly, we restrict attention to static, non-variational circuits: the circuit structure and parameters remain fixed across all shots of the execution, so that the effective output distribution can be treated as stationary during that execution. Variational and other adaptive workloads, in which circuits change across optimisation iterations and induce Manuscript submitted to ACM

6

Bisicchia et al. Table 1. Comparison of existing shot optimisation strategies.

Work

Optimisation Metric

Algorithmic Context

Underlying tions

Assump-

Analytical and Concentration-Based Methods Seksaria & Prabhakar [41]

Variance

Static / VQA

Explicit noise model (SPAM, 𝑇1 , 𝑇2 , gate errors)

Hoeffding Inequality [27]

Error bound

Static, non-variational

i.i.d. samples, predefined confidence level

Weissman Inequality [46]

ℓ1 distance bound

Static, non-variational

Finite-sample concentration, conservative bounds

Adaptive Shot Allocation in Variational Algorithms Zhu et al. (VPSR) [50]

Variance

VQE

Hamiltonian structure, commuting observables

Gu et al. (gCANS) [26]

Utility per iteration

VQA

Access to cost gradients

Kübler et al. (iCANS) [31]

Gradient variance

VQA

Partial derivatives available

Kim et al. (DDS) [30]

Entropy

VQA

Iterative parameter updates

Phalak & Ghosh [39]

Accuracy

QML

Supervised learning signal

Kahani & Nobakhti [29]

Estimator sensitivity

VQA

Iterative loop

optimisation

Learning-Based Methods Liang et al. [32]

Convergence mance

perfor- VQE

Trained RL policy

Online, Black-Box Execution Control This Work

Point of Diminishing Returns

Static, Variational

Non-

Stationary distribution, black-box access only

non-stationary output distributions, require different stopping criteria and statistical guarantees and are outside our scope. This section formalises the problem of sample optimisation in a black-box setting and then instantiates it for static quantum circuit execution. Specifically: • We first define the general problem of estimating an unknown discrete distribution under a hard sampling budget, and we introduce an a posteriori procedure to compute the minimal sufficient number of samples from a complete execution trace. • We then define an online, observable proxy for convergence—the point of diminishing returns—that can be detected without access to the true distribution. • Finally, we instantiate these notions in the quantum setting for static circuits executed on noisy quantum backends. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit? 3.1

7

General Formulation

Consider a black-box stochastic process that produces outcomes in a finite discrete space X according to an unknown target distribution 𝑃. Each draw yields one sample 𝑥 ∈ X; repeating the process 𝑛 times yields the empirical distribution 𝑃ˆ𝑛 . Throughout this section we assume that, for the duration of an execution, samples are generated from a stationary distribution (i.e., 𝑃 does not change with 𝑛). This formulation is intentionally domain-independent. The only assumptions are that outcomes lie in a finite discrete space, repeated samples are drawn from a stationary distribution during the execution, and each sample has nonnegligible cost. Quantum circuit execution is introduced in Section 3.3 as one concrete instantiation, where the sampling oracle is a circuit–backend pair and samples are measurement shots. A distance or divergence metric D (·, ·) is used to quantify the difference between two probability distributions over X. Given a threshold 𝛿 > 0 representing the maximum acceptable estimation error and a hard budget B on the maximum number of available samples, we define the following problem. Definition 3.1 (The Black-box Sample Optimisation Problem). Given an unknown distribution 𝑃 over a discrete space X, a divergence metric D, a maximum estimation error threshold 𝛿, and a budget B ∈ N, find the smallest positive integer 𝑛 ∗ ≤ B such that 𝑛 ∗ = min

 𝑛 ≤ B | D (𝑃ˆ𝑚 , 𝑃) ≤ 𝛿, ∀𝑚 ≥ 𝑛 ∪ {B} ,

where 𝑃ˆ𝑚 denotes the empirical distribution based on the first 𝑚 samples. To justify the previous definition (and the subsequent ones), we observe that the divergence between the empirical distribution 𝑃ˆ𝑛 and the target distribution 𝑃 converges almost surely to 0. Let X be a finite discrete outcome space, 𝜌 a fixed quantum state on a finite-dimensional Hilbert space H , and E = {𝐸𝑥 }𝑥 ∈ X a POVM. By the Born rule, 𝑃 (𝑥) = Tr(𝜌𝐸𝑥 ) defines a probability distribution on X. Assume that repeated executions of the experiment produce i.i.d. outcomes (𝑋𝑡 )𝑡 ≥1 with distribution 𝑃, and then 𝑛 1 ∑︁ 𝑃ˆ𝑛 (𝑥) = 1{𝑋𝑡 = 𝑥 } 𝑛 𝑡 =1 a.s. as the empirical distribution after 𝑛 shots. By the Strong Law of Large Numbers, 𝑃ˆ𝑛 (𝑥) −−→ 𝑃 (𝑥) for each 𝑥 ∈ X as 𝑛 → ∞. Since X is finite, this implies almost-sure convergence of the full vector 𝑃ˆ𝑛 to 𝑃 in any equivalent norm on

R | X | , and consequently,

a.s.

D (𝑃ˆ𝑛 , 𝑃) −−→ 0

as 𝑛 → ∞.

The previous formulation captures the ideal objective: determine the smallest 𝑛 such that the empirical distribution is within 𝛿 of the (unknown) target distribution 𝑃. In many practical settings, including quantum circuit execution on real devices, 𝑃 cannot be accessed directly; consequently, this ideal definition cannot be evaluated online or even retrospectively without additional assumptions. To obtain a computable notion of optimality under a fixed sampling budget, we adopt a standard practical reference: the empirical distribution obtained using the full budget, 𝑃ˆB . While 𝑃ˆB remains an approximation of 𝑃, it is the best estimate available under the imposed budget and therefore provides a principled baseline for assessing whether earlier prefixes of the execution were already sufficient. We define the resulting a posteriori optimality criterion as follows. Definition 3.2 (The A Posteriori Black-box Sample Optimisation Problem). Given an execution history of subsequent B samples {𝑥 1, . . . , 𝑥 B } drawn from an unknown distribution 𝑃, a divergence metric D, and a target Manuscript submitted to ACM

8

Bisicchia et al.

threshold 𝛿 > 0, find the optimal number of samples 𝑛 ∗ ≤ B such that  𝑛 ∗ = min 𝑛 ≤ B | D (𝑃ˆ𝑚 , 𝑃ˆB ) ≤ 𝛿, ∀𝑚 ≥ 𝑛 , where 𝑃ˆ𝑚 is the empirical distribution over the first 𝑚 samples and 𝑃ˆB is the empirical distribution over all B samples.

This notion of optimality is a posteriori because it requires access to the complete execution trace in order to compute 𝑃ˆB . It yields a computable and execution-specific “grounded” convergence point: the earliest prefix whose empirical distribution is within 𝛿 of the best estimate obtainable under the budget. In this sense, 𝑛 ∗ captures the point of diminishing returns for that execution. Since D (𝑃ˆB , 𝑃ˆB ) = 0, the worst case is 𝑛 ∗ = B. It is important to emphasise that this a posteriori notion of optimality is not intended to be used during execution. Rather, it provides a principled retrospective baseline that can only be computed after observing the full execution history. Its purpose is to quantify how early convergence could have been achieved and to serve as a reference for evaluating online strategies that do not have access to the full budget distribution.

A Posteriori Optimal Sample Count Algorithm. We next provide a simple procedure for computing 𝑛 ∗ from a complete execution history. While it is not usable online, it serves as a rigorous retrospective baseline in our evaluation.

Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

9

Algorithm 1: A Posteriori Optimal Sample Count Computation (Suffix-Stable) Input: Measurement outcomes {𝑥 1, 𝑥 2, . . . , 𝑥 B }, threshold 𝛿, divergence metric D Output: Optimal number of samples 𝑛 ∗ ≤ B // Step 1: Build the reference distribution 𝑃ˆB initialize count_B[𝑘] ← 0 for all outcomes 𝑘; for 𝑖 ← 1 to B do count_B[𝑥𝑖 ] ← count_B[𝑥𝑖 ] +1; foreach key 𝑘 in count_B do 𝑃ˆB [𝑘] ← count_B[𝑘] /B; // Step 2: Compute divergences 𝑑 [𝑚] = D (𝑃ˆ𝑚 , 𝑃ˆB ) for all 𝑚 initialize count_m[𝑘] ← 0 for all outcomes 𝑘; total ← 0; for 𝑚 ← 1 to B do count_m[𝑥𝑚 ] ← count_m[𝑥𝑚 ] +1; total ← total +1; foreach key 𝑘 in count_B do 𝑓 ← count_m.get(𝑘, 0); 𝑃ˆ𝑚 [𝑘] ← 𝑓 /total; 𝑑 [𝑚] ← D (𝑃ˆ𝑚 , 𝑃ˆB ); // Step 3: Find the earliest 𝑛 such that max𝑚≥𝑛 𝑑 [𝑚] ≤ 𝛿 suffix_max ← 0; 𝑛 ∗ ← B; for 𝑚 ← B to 1 do suffix_max ← max(suffix_max, 𝑑 [𝑚]); if suffix_max ≤ 𝛿 then 𝑛 ∗ ← 𝑚; return 𝑛 ∗ ; Algorithm 1 returns the smallest prefix length 𝑛 ∗ such that 𝑃ˆ𝑚 is within 𝛿 of the full-budget empirical distribution 𝑃ˆB for all 𝑚 ≥ 𝑛 ∗ . This procedure is not usable online, since 𝑃ˆB is only available after consuming the full budget. Nevertheless, it provides (i) a concrete, computable baseline for evaluation and (ii) an operational interpretation of “diminishing returns” under a hard sampling budget. 3.2

The Point of Diminishing Returns as a Practical Approximation

To enable online decision making without access to 𝑃 (and without requiring the full trace needed for 𝑃ˆB ), we adopt an observable convergence proxy: the point of diminishing returns. The core idea is to monitor how much the empirical distribution changes as additional samples are collected. When these changes become sufficiently small, the empirical distribution can be treated as stable for practical purposes, and further sampling is unlikely to yield meaningful improvements. Definition 3.3 (Approximate Point of Diminishing Returns). Let 𝑃ˆ𝑛 be the cumulative empirical distribution after 𝑛 ≤ B samples, and let D (·, ·) be a divergence metric over distributions. Given a look-back window 𝜏, the approximate Manuscript submitted to ACM

10

Bisicchia et al.

point of diminishing returns is said to occur at step 𝑛 if 𝑛 is the smallest value such that:   D 𝑃ˆ𝑛 , 𝑃ˆ𝑛−𝜏 ≤ 𝜀 where 𝜀 > 0 is a tolerance parameter controlling sensitivity to change. Unlike 𝛿 in Definition 3.2, which is defined with respect to the full-budget reference 𝑃ˆB , 𝜀 is an online tolerance that controls sensitivity to distributional changes observed during execution. In our IncrementalExecution framework, 𝜀 is a configurable parameter. While this criterion does not guarantee closeness to the unknown true distribution 𝑃, it yields a practical, modelagnostic stopping signal. Moreover, the criterion is theoretically well-motivated in the sense that, under mild regularity assumptions, the divergence between two empirical distributions separated by a fixed lag 𝜏 must vanish asymptotically. In particular, if the samples are i.i.d. (independent and identically distributed) from 𝑃 and D is a divergence (or metric) that is continuous with respect to the convergence mode induced by 𝑃ˆ𝑛 (e.g., total variation, ℓ1 , ℓ2 , or standard 𝑓 -divergences on finite support), then

a.s.

D (𝑃ˆ𝑛 , 𝑃ˆ𝑛−𝜏 ) −−→ 0

as 𝑛 → ∞.

A direct way to see this is to note that by the Strong Law of Large Numbers (SLLN), as we already justified, for any fixed 𝑥 ∈ X,

a.s. 𝑃ˆ𝑛 (𝑥) −−→ 𝑃 (𝑥).

Hence, for each 𝑥, both sequences 𝑃ˆ𝑛 (𝑥) and 𝑃ˆ𝑛−𝜏 (𝑥) converge almost surely to the same limit 𝑃 (𝑥), implying 𝑃ˆ𝑛 (𝑥) − 𝑃ˆ𝑛−𝜏 (𝑥) → 0 a.s. Coordinate-wise convergence, together with continuity of D, yields D (𝑃ˆ𝑛 , 𝑃ˆ𝑛−𝜏 ) → 0 almost surely. Operationally, this means that for any fixed tolerance 𝜀 > 0, there exists (almost surely) a finite step 𝑛𝜀 after which the lag-𝜏 empirical divergence remains below 𝜀, providing a principled basis for using Definition 3.3 as an online proxy for stabilization. Importantly, the asymptotic guarantee above should be interpreted only as a consistency property of the proxy, not as a certificate of small error with respect to 𝑃 at finite 𝑛. In finite-budget regimes, the choice of 𝜏 and 𝜀 controls a bias–variance trade-off: larger 𝜏 tends to suppress spurious fluctuations but may delay detection, whereas smaller 𝜀 enforces stricter stabilization at the cost of longer sampling. In Section 6, we empirically show that this approximate point of diminishing returns provides an effective online proxy for the a posteriori optimality criterion in Definition 3.2. 3.3

The Quantum Black-box Shot Optimisation Problem

The Black-box Sample Optimisation Problem naturally instantiates in quantum computing [48]. For a fixed (static) quantum circuit 𝐶 executed on a noisy backend 𝑄, each shot yields a single measurement outcome and can be viewed as a sample from an unknown, effective output distribution 𝑃 (𝐶, 𝑄) induced by the circuit-backend pair. Repeating the execution 𝑛 times yields an empirical distribution 𝑃ˆ𝑛 (𝐶, 𝑄), and the shot budget B bounds the maximum number of executable shots. Within our scope, we assume static circuit execution: the circuit structure and parameters do not change across shots, and the effective output distribution is treated as stationary over the duration of the execution. Under these assumptions, the goal is to determine the smallest 𝑛 such that the resulting empirical distribution is sufficiently stable (or sufficiently close to the best available reference under the budget). Consequently, we define the quantum instance of the a posteriori black-box problem as follows. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

11

Definition 3.4 (The Quantum Black-box Shot Optimisation Problem Circuits). Given a static quantum circuit 𝐶 and a noisy quantum processing unit 𝑄, and a maximum shot budget B ∈ N, determine the smallest natural number 𝑛 ∗ ≤ B such that:  𝑛 ∗ = min 𝑛 ≤ B | D (𝑃ˆ𝑚 (𝐶, 𝑄), 𝑃ˆB (𝐶, 𝑄)) ≤ 𝛿, ∀𝑚 ≥ 𝑛 , where 𝑃ˆ𝑚 (𝐶, 𝑄) denotes the empirical distribution obtained by performing 𝑚 shots of 𝐶 on 𝑄; 𝑃ˆB (𝐶, 𝑄) denotes the empirical distribution obtained using the full budget B; and 𝛿 > 0 is the tolerance threshold below which 𝑃ˆ𝑛 (𝐶, 𝑄) is considered a sufficiently accurate approximation of 𝑃ˆB (𝐶, 𝑄). Since 𝑃ˆB (𝐶, 𝑄) is the best estimate attainable under the budget, identifying an optimal 𝑛 ∗ ≤ B can save B − 𝑛 ∗ shots while preserving essentially the same empirical distributional estimate achievable at full budget. From this point forward, we instantiate the divergence metric D using three standard distributional distances/divergences: Total Variation Distance (TVD), Hellinger distance, and Jensen–Shannon (JS) divergence. We primarily report results with TVD for its simplicity and direct interpretability, and we use Hellinger and JS to validate our conclusions. Total Variation Distance (TVD). Given two discrete probability distributions 𝑃 and 𝑃 ′ over the same outcome space X, the Total Variation Distance is defined as: TVD(𝑃, 𝑃 ′ ) =

1 ∑︁ |𝑃 (𝑥) − 𝑃 ′ (𝑥)| . 2 𝑥∈X

TVD measures the maximal discrepancy in assigned probability mass across events and ranges from 0 (identical distributions) to 1 (disjoint support). Hellinger distance. The (squared) Hellinger distance between 𝑃 and 𝑃 ′ is: 2 √︁ 1 ∑︁ √︁ 𝐻 2 (𝑃, 𝑃 ′ ) = 𝑃 (𝑥) − 𝑃 ′ (𝑥) , 2 𝑥∈X √︁ and 𝐻 (𝑃, 𝑃 ′ ) = 𝐻 2 (𝑃, 𝑃 ′ ). Hellinger distance is symmetric, bounded in [0, 1], and behaves smoothly for small probabilities, which is useful for sparse empirical distributions. Jensen–Shannon (JS) divergence. Let 𝑀 = 12 (𝑃 + 𝑃 ′ ). The Jensen–Shannon divergence is defined as: 1 1 JS(𝑃 ∥ 𝑃 ′ ) = KL(𝑃 ∥ 𝑀) + KL(𝑃 ′ ∥ 𝑀), 2 2 where KL(· ∥ ·) denotes the Kullback–Leibler divergence. JS is symmetric and always finite; when using log2 , it is bounded in [0, 1] [23]. While TVD, Hellinger distance, and JS divergence quantify distributional discrepancy in different ways, they are tightly connected and often interchangeable up to constants for the purpose of detecting stabilisation. First, Hellinger controls TVD (and vice versa up to constants): under standard normalisations, √ 𝐻 2 (𝑃, 𝑄) ≤ TVD(𝑃, 𝑄) ≤ 2 𝐻 (𝑃, 𝑄),

(1)

so convergence in Hellinger is equivalent to convergence in TVD (with rescaled thresholds). Second, JS is a symmetric, bounded information divergence, and its square root is a metric (often called the Jensen–Shannon distance). Moreover, JS can be bounded above and below by (squared) variation distance for categorical distributions; in particular, for the equal-weight case and common support, Corander et al. [18] show that JS admits two-sided bounds in terms of the Manuscript submitted to ACM

12

Bisicchia et al.

(a) TVD to ideal distribution as a function of shot count.

(b) Change in empirical distribution between successive windows (𝜏 = 50).

Fig. 1. Empirical behaviour of static quantum circuit output distributions as the shot count increases. Each line corresponds to a circuit–backend pair.

squared (total) variation distance, implying that for small discrepancies,
JS(𝑃 ∥ 𝑄) = Θ TVD(𝑃, 𝑄) 2 ,

(2)

and providing explicit constants (and a sharper logarithmic lower bound) under mild conditions. Practically, this means TVD reacts linearly to probability-mass shifts, while Hellinger and JS are typically smoother and often behave quadratically near convergence, which can reduce sensitivity to small residual fluctuations when used as online stopping signals. Preliminary Study To assess the feasibility of our approach in the static setting, we conducted a preliminary study to evaluate whether empirical output distributions exhibit stabilisation as the number of shots increases, and whether this behaviour can be captured by Definition 3.3. Figure 1 presents empirical evidence of these dynamics. Each line corresponds to a unique pair consisting of a quantum circuit and a noisy quantum backend. We considered 28 different circuits with qubit counts ranging from 4 to 16 and executed them on five IBM noisy simulators. For each circuit-backend pair, we ran the circuit in batches of 𝜏 = 50 shots, up to a total of B = 20,000 samples, recording the empirical distribution 𝑃ˆ𝑛 after each batch. In subfigure (a), we compute the TVD between each empirical distribution 𝑃ˆ𝑛 (𝐶, 𝑄) and the corresponding ideal distribution 𝑃𝑛 (𝐶, 𝑄), obtained by executing the same circuit 𝐶 on a noiseless simulator 𝑄. With few shots, the TVD is unstable due to high sampling variance. As 𝑛 increases, the empirical distribution concentrates and TVD decreases, reflecting improved estimation. Eventually, the curves plateau: additional shots provide only marginal gains, as residual discrepancies are increasingly dominated by systematic effects (e.g., device noise) rather than sampling noise. Subfigure (b) shows Delta-TVD, i.e., the divergence between empirical distributions separated by a fixed look-back window 𝜏 = 50. The rapid decay followed by a plateau indicates that the empirical distribution stabilises, consistent with the emergence of a point of diminishing returns as defined in Section 3.2. Advantages in Quantum Contexts. The approximate point of diminishing returns provides a practical and flexible convergence signal for static quantum circuit execution: Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

13

• It does not require access to circuit internals, an explicit noise model, or the ideal distribution 𝑃 (𝐶, 𝑄), making it applicable across hardware backends and circuit families within the static setting. • It can be computed online from observed outcomes, without requiring the full trace needed to compute 𝑃ˆB (𝐶, 𝑄). • It naturally adapts to circuit- and backend-specific behaviour, enabling shot allocation that reflects empirical statistical complexity. • It is metric-agnostic and, in our evaluation, we instantiate it with TVD, Hellinger distance, and Jensen-Shannon divergence to assess robustness to the choice of D. In summary, static quantum circuit execution provides a concrete and practically relevant instantiation of the Blackbox Sample Optimisation Problem. The point of diminishing returns yields an online stopping signal that underpins our IncrementalExecution framework, introduced next as a fully online procedure for black-box shot optimisation in static quantum experiments. 4

The Incremental Execution Framework

Building on the problem formulation and a posteriori analysis of Section 3, we now introduce the IncrementalExecution Framework: a practical and online method for dynamically approximating the optimal number of shots required to estimate the output distribution of a quantum circuit with sufficient accuracy 4 . 4.1

From A Posteriori Optimality to Online Execution

As established in Definition 3.2, the optimal number of shots 𝑛 ∗ is the smallest 𝑛 ≤ B such that the empirical distribution 𝑃ˆ𝑛 is within distance 𝛿 of the best possible approximation 𝑃ˆB obtained using the full budget. While informative, this a posteriori approach requires all B samples to be collected upfront, making it unsuitable for online or cost-sensitive execution. Nevertheless, despite its lack of operational applicability, a posteriori optimality serves as a crucial evaluation benchmark in this work. The objective of the IncrementalExecution framework is to approximate this ideal stopping point online, without ever executing the full shot budget. In this work, therefore, our goal is to approximate 𝑛 ∗ in an online setting, where samples are acquired incrementally, and the decision to continue or stop is made dynamically based only on observed data. We reframe the problem as one of approximating the point of diminishing returns – the point at which additional shots do not meaningfully change the cumulative output distribution. This leads to the following guiding principle: Continue performing shots only while they significantly improve the accuracy of estimated distribution. Stop as soon as further sampling yields negligible gain. This philosophy transforms shot execution into a feedback-driven process that adapts online to circuit behaviour and hardware variability. To operationalise this approach, our design goals are to: • Operate under a black-box assumption, requiring no prior knowledge of the circuit structure or the noise characteristics of the quantum backend. 4 Throughout this work, unless explicitly stated otherwise, we define accuracy in terms of closeness to the best empirically attainable distribution under a

fixed budget of quantum circuit executions. Specifically, unless stated otherwise, we evaluate accuracy with respect to the empirical distribution 𝑃ˆB obtained from all B available shots on a given noisy QPU, rather than the ideal (noiseless) distribution 𝑃𝐶 . This choice reflects the fact that 𝑃ˆB is the best estimate of the circuit’s true output distribution that can be practically obtained under budget constraints. In contrast, the ideal distribution 𝑃𝐶 , derived from a noiseless simulation of the circuit, is typically inaccessible on real quantum hardware due to stochastic noise and uncharacterised error sources. As such, 𝑃ˆB serves as a more realistic and actionable target for optimisation in real-world settings, where noise prevents convergence to the ideal output. Manuscript submitted to ACM

14

Bisicchia et al. • Avoid over-execution, reducing unnecessary cost while maintaining user-defined accuracy guarantees. • Dynamically determine how many additional shots are required, based solely on the measurement outcomes observed so far. To this end, we introduce a general-purpose, adaptive algorithm grounded in the notion of point of diminishing

returns, which serves as a robust and efficient proxy for accuracy in real-world quantum execution environments. 4.2

The Framework

The IncrementalExecution Framework (Algorithm 2) is structured as an adaptive, feedback-driven loop that incrementally refines the number of shots used to estimate a quantum circuit’s output distribution. Rather than deciding upfront how many shots are needed, the framework proceeds incrementally: it performs a small batch of shots, evaluates whether their outcomes meaningfully improve our knowledge of the circuit’s output distribution (i.e., if it reaches point of diminishing returns), and only continues performing shots if they do. Algorithm 2: IncrementalExecution Input: Quantum circuit 𝐶, backend Q, initial batch size 𝑏 0 Input: Distance metric D, convergence threshold 𝜀, max shots B Input: Stopping criterion StoppingCriterion, stability criterion StabilityCriterion, allocation policy AllocateShots ˆ total shots used 𝑁 Output: Estimated distribution 𝑃, 𝑃ˆ ← ∅; history ← [ ], stable ← 0; 𝑛 ← 0, 𝑏 ← 𝑏 0 ; while 𝑛 < B do 𝑅 ← Run(𝐶, B, 𝑏) ; // Execute next batch of 𝑏 shots append 𝑅 to history; update 𝑃ˆ with outcomes in 𝑅 ; // Incremental empirical distribution update 𝑛 ← 𝑛 + 𝑏; ˆ 𝑅); (converged, info) ← StoppingCriterion(history, 𝑃, if converged then stable ← stable + 1; else stable ← 0; ˆ 𝑅, info); 𝑘 ← StabilityCriterion(history, 𝑃, if stable ≥ 𝑘 then break ;

// Point of diminishing returns confirmed

ˆ 𝑅, info); 𝑏 ← AllocateShots(history, 𝑃, ˆ 𝑁 return 𝑃,

Initialisation. The algorithm begins by setting up key variables: • 𝑃ˆ ← ∅: the cumulative empirical distribution, updated incrementally. • history: a sequence storing all observed outcomes. • stable: a counter for the number of consecutive stable iterations. • 𝑛 ← 0: the total number of shots executed so far. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

15

• 𝑏 ← 𝑏 0 : the initial size of the shot batch. These initial values prepare the algorithm to start incremental execution and monitoring. Main Execution Loop. The algorithm proceeds iteratively until either the point of diminishing returns is detected or the maximum allowed shot budget B is reached. Each iteration includes the following steps: • Batch Execution:A batch of 𝑏 shots is executed on the quantum backend 𝑄, producing a new set of measurement outcomes 𝑅. • Empirical Update: The outcomes in 𝑅 are appended to the history and used to update the cumulative distribution ˆ 𝑃. • Convergence Check: The function StoppingCriterion is invoked to determine whether the empirical distribution has changed significantly relative to the recent past (i.e., if it has reached the point of diminishing returns). It returns a boolean flag indicating local convergence and auxiliary information such as the computed divergence. If convergence is detected, the stability counter stable is incremented; otherwise, it is reset to zero. • Stability Enforcement: To guard against transient fluctuations, the function StabilityCriterion computes how many consecutive stable iterations are required to declare global convergence. If the threshold 𝑘 is met or exceeded, execution terminates early. • Shot Allocation: If convergence is not yet established, the function AllocateShots determines the size of the next shot batch based on the current history and convergence metadata. Termination and Output. The loop terminates either upon achieving stably the point of diminishing returns or reaching the maximum budget B. The algorithm then returns: ˆ the final cumulative empirical distribution; • 𝑃: • 𝑛: the total number of shots executed. The output reflects the estimated best possible estimation of the circuit’s output distribution within the budget and convergence constraints. Discussion. This adaptive procedure approximates the a posteriori optimal shot count 𝑛 ∗ (Definition 3.2) in an online fashion. As access to the full budget reference distribution 𝑃ˆB is unavailable during execution, the algorithm instead tracks changes in the empirical distribution over time. Convergence is inferred from distributional stability, under the assumption that small incremental changes imply diminishing returns. A key strength of the framework lies in its modularity. The behaviour of the algorithm is governed by three pluggable policy components: ˆ R) → (bool, info): Determines whether the most recent batch 𝑅 introStoppingCriterion (history, 𝑃, duces a statistically significant change in the empirical distribution. It acts as an estimator of the point of diminishing returns. Typically compares the current empirical distribution 𝑃ˆ𝑖 with that of the previous iteration 𝑃ˆ𝑖 −1 using a divergence metric D, and returns a boolean flag indicating convergence along with auxiliary diagnostic information. ˆ R, info) → int: Specifies how many consecutive stable iterations are StabilityCriterion (history, 𝑃, required to confirm convergence. Its purpose is to reduce the possibility of false positives when signalling the Manuscript submitted to ACM

16

Bisicchia et al. point of diminishing returns. It can be constant or adaptively computed based on recent divergence values or system variability. ˆ R, info) → int: Determines the number of shots in the next batch. Can be AllocateShots (history, 𝑃, fixed, randomised, or dynamically adjusted based on convergence trends or statistical uncertainty. Each component can be configured independently, enabling diverse optimisation strategies: • Dynamic thresholds for 𝜀 (the stopping criterion threshold 5 ) based on real-time calibration data considered application; • Multi-metric convergence, where stability is defined over multiple divergence metrics; • Task-aware objectives, combining convergence with downstream utility metrics (e.g., optimisation loss or classification accuracy).

4.3

Implementation Overview

The IncrementalExecution Framework is implemented as an open-source6 , modular, extensible Python class that supports dynamic shot allocation in quantum circuit execution under black-box conditions. It is written in Python 3.12 and designed to be easily integrable with both simulation environments and real quantum backends. Class Interface. The core class is defined as follows: class IncrementalExecution : def __init__ ( self , stopping_criterion : Callable , stability_criterion : Callable , allocate_shots : Callable , default_shots : int , max_shots : Optional [ int ] = None , runner : Optional [ Callable ] = None , verbose : bool = True ) def run ( self , runner : Optional [ Callable ] = None , initial_guess : Optional [ Dict [ str , int ]] = None , * args , ** kwargs ) -> Dict [ str , int ] def __call__ ( self , func : Callable ) -> Callable

This interface exposes the three key user-defined policy functions (i.e., StoppingCriterion, StabilityCriterion, and AllocateShots), while users may also provide: • runner: a callable that executes a quantum circuit (or synthetic simulation) and returns measurement outcome counts. Its only requirement is to feature a shots parameter. • default_shots: the number of shots to perform during the first iteration. • max_shots: maximum shots budget. 5 See Definition 3.3.

6 The full, open-source codebase is freely available at: https://github.com/GBisi/quantum-incremental-execution

Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

17

• initial_guess: an optional empirical distribution to bootstrap early convergence; useful when are available some information on the "shape" of the target distribution. Usage. The framework supports both functional and decorator-based usage. For example: # Functional interface incremental_exec = IncrementalExecution ( stopping_criterion = stop_crit , stability_criterion = stability_crit , allocate_shots = shot_policy , default_shots =50 , max_shots =20000 ) result = incremental_exec . run ( runner = my_runner ) # Decorator interface @incremental_exec def my_runner (* , shots ) : ... result = my_runner ()

4.4

Summary

In summary, the IncrementalExecution framework provides a principled and flexible solution to the shot optimisation problem in quantum computing. It turns the fixed-budget question “How many shots should I run?” into a dynamic decision problem that adapts to empirical data. Grounded in the concept of the point of diminishing returns, the framework provides a lightweight, accurate, and backend-agnostic solution for shot count optimisation. (1) It avoids the need to access the true distribution or simulate noise models. (2) It is robust to backend fluctuations and circuit-specific behaviours. (3) It supports integration on quantum cloud platforms, such as IBM Quantum Sessions (see Section 7). In the following section, we instantiate this framework with concrete implementations of the three decision policies, each with its own way of interpreting the concept of the point of diminishing returns. 5

Policy Space and Experimental Configurations

The flexibility of the IncrementalExecution Framework lies in its policy modularity. This section presents the suite of execution policies implemented and tested in our experiments, encompassing stopping criteria, stability enforcement, and shot allocation strategies. Each policy is parameterised, allowing fine-grained control over the trade-off between convergence speed and estimation accuracy. We also describe the configuration grid used to generate thousands of framework instantiations. Such policies and parameters should be seen as hyperparameters of the framework and may need a fine-tuning phase to reach the framework’s best performance on a specific application. 5.1

Stopping Criterion Policies

Stopping criteria determine whether the empirical distribution has reached the point of diminishing returns — i.e., whether additional measurements yield negligible information gain. We implemented three families of stopping Manuscript submitted to ACM

18

Bisicchia et al.

conditions, each relying on the comparison of the cumulative empirical distribution to past estimates using the divergence metric D (viz., TVD, Hellinger or J-S): • Delta Distance Criterion (Delta): Execution halts when the distance between the empirical distributions at the current and previous iterations 𝑖 − 𝜏, 𝑃ˆ𝑖 and 𝑃ˆ𝑖 −𝜏 , falls below a fixed threshold 𝜀: D (𝑃ˆ𝑖 , 𝑃ˆ𝑖 −𝜏 ) < 𝜀 Parameters tested in the experiments: – Thresholds 𝜀: {0.01, 0.025, 0.5, 0.1, 0.25} – Look-back window 𝜏: {1, 2, 3} • Delta Moving Average Criterion (DMA): Instead of requiring individual divergence values to be below the threshold, this criterion compares the moving average of divergence values over the last 𝑤 iterations to the threshold. Let 𝑑 𝑗 = D (𝑃ˆ𝑖 −𝑤+𝑗 , 𝑃ˆ𝑖 −𝑤+𝑗 −𝜏 ) for 𝑗 = 1, . . . , 𝑤. Then: Avg𝑤 (𝑑 1, . . . , 𝑑 𝑤 ) < 𝜀 where the average can be computed uniformly or as an exponentially weighted moving average (EWMA). Exponentially Weighted Moving Average (EWMA). Given a sequence 𝑑 1, . . . , 𝑑 𝑤 , the EWMA with smoothing factor 𝛼 ∈ (0, 1] is computed recursively as:   𝑠 1 = 𝑑 1   𝑠𝑡 = 𝛼𝑑𝑡 + (1 − 𝛼)𝑠𝑡 −1, 

for 𝑡 = 2, . . . , 𝑤

⇒

EWMA𝛼 = 𝑠 𝑤

Parameters tested in the experiments: – Thresholds 𝜀: {0.01, 0.025, 0.5, 0.1, 0.25} – Look-back window 𝜏: {1, 2, 3} – Window sizes 𝑤: {3, 5} – Smoothing factors 𝛼: {None, 0.5} 5.2

Stability Criterion Policy

To prevent early stopping due to transient fluctuations, we define a single stability criterion that requires a certain number of consecutive iterations to independently satisfy the stopping condition before termination is allowed. In this work, we implemented and tested a constant stability threshold: • Constant Stability Criterion: Convergence is accepted only if the stopping condition has held for 𝑘 consecutive iterations. Parameters tested in the experiments: – 𝑘 ∈ {1, 3, 5} 5.3

Shot Allocation Policies

The shot allocation policy determines how many additional measurements are taken in each iteration. In this work, we implemented and tested both static and adaptive strategies for shot allocation. • Constant Shot Allocation: A fixed number of shots is collected in each iteration, regardless of convergence state: Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

19

Parameters tested in the experiments: – Shots: {50, 100} • Dynamic Shot Allocation: The number of shots to be allocated at each iteration is adaptively estimated based on the evolution of the empirical distribution. Let 𝜀𝑖 = D (𝑃ˆ𝑖 , 𝑃ˆ𝑖 −1 ) denote the observed divergence between the current empirical distribution 𝑃ˆ𝑖 and the one from the previous iteration 𝑃ˆ𝑖 −1 . This sequence {𝜀𝑖 }𝑖 represents the per-iteration change in the empirical distribution. Assuming smooth convergence (i.e., the distances 𝜀𝑖 decrease over time), we can estimate the next divergence value by extrapolating the trend. Specifically, we compute the 𝜀2

𝑖 𝑖 . To reach a fixed ratio: 𝛿𝑖 = 𝜀𝑖𝜀−1 , and use it to estimate the distance in the next iteration: 𝜀𝑖+1 ≈ 𝛿𝑖 · 𝜀𝑖 = 𝜀𝑛−𝑖

divergence threshold 𝜀, the number of shots 𝑆𝑖+1 to allocate in the next iteration is scaled accordingly: 𝑆𝑖+1 =

𝜀𝑖2

· 𝑆𝑖 ,

𝜀𝑖 −1 where 𝑆𝑖 is the number of shots used in the current iteration. The intuition is to project the diminishing returns of sampling, allocating more shots if convergence is slowing, or fewer if the distribution stabilises rapidly. To ensure stability in early iterations, where 𝜀𝑖 and 𝛿𝑖 may fluctuate unpredictably, a fixed number of initial batches can be used before enabling dynamic scaling. Parameters tested in the experiments: – Minimum initial fixed iterations: {0, 1, 3}

5.4

Common Execution Parameters

In all configurations, the maximum shot budget B was fixed to 20,000 shots. The default_shots parameter (i.e., the number of shots in the first iteration) was selected independently and tested with the same two values: {50, 100}. This ensured fair and consistent initialisation across all policies. We evaluated our framework considering five different 𝛿 thresholds: {0.01, 0.025, 0.5, 0.1, 0.25}. Finally, all configurations were tested in combinations with three different divergence metrics: TVD, Hellinger and JS.

5.5

Parameter Grid and Configurations

By combining all policies and their parameter values, we explored a total of 33, 750 unique configurations. These were computed as follows: • Stopping criteria (75 configurations): – Delta: 5 thresholds × 3 look-back window sizes = 15 – DMA: 5 thresholds × 3 look-back window sizes × 2 windows × 2 alphas = 60 • Stability enforcement: 3 values of 𝑘 • Shot allocation: (5 configurations): – Constant: 2 values of constant batch size – Dynamic: 3 minimum initial fixed iterations • Default shot count for first batch: 2 values • 𝛿 threshold: 5 values • Divergence metrics: 3 values Manuscript submitted to ACM

20

Bisicchia et al. Thus, the total configuration space is: 75 × 3 × 5 × 2 × 5 × 3 = 33, 750 total configurations This thorough evaluation allows us to characterise the empirical behaviour of the IncrementalExecution Framework

under a wide variety of convergence dynamics and cost-accuracy trade-offs. In Section 6, we analyse these configurations and compare them against the optimal a posteriori policy defined in Alg. 1. 6

Experimental Evaluation

This experimental evaluation7 section has a twofold objective: (i) to assess whether there exist configurations capable of achieving the target accuracy while reducing the total number of shots with respect to a fixed budget, and (ii) to provide practical insights and preliminary guidelines for policy fine-tuning as a function of quantum circuit characteristics. More in detail, we tackle the following research questions about our framework: • RQ1: How the parameters of IncrementalExecution impact on finding the target accuracy? • RQ2: How the configuration of IncrementalExecution is affected by noise models and circuits? • RQ3: Which are the best configurations of IncrementalExecution? • RQ4: How the best configurations of IncrementalExecution behave in comparison with the state of the art? 6.1

Experimental Setup

To evaluate the several configurations of our framework, we collected 180 unique execution traces, each corresponding to a distinct quantum circuit and backend pair, in order to investigate how changing the quantum algorithm, circuit size, or noise model affects IncrementalExecution. In particular, we employed: • 5 IBM noisy backend simulators: fake_faze, fake_kyiv, fake_marrakesh, fake_sherbrooke, and fake_torino. • 6 quantum algorithms for static circuits: dj, static qaoa, qnn, qft, random, and static vqe. • 6 qubit sizes (4, 6, 8, 10, 12, and 14) for each circuit. We collected the output distribution for each trace by executing the circuits on the backends in batches of 50 shots, until reaching a total of 20,000 shots per trace. From these samples, we compute the a posteriori optimal value for each trace using the three divergence metrics introduced in Section 3.3: TVD, Hellinger, and JS. This data collection8 also supported a preliminary study that shaped our experimental design in two ways: (i) it informed the choice of shot budgets used in the experiments, and (ii) it motivated a partition of circuits into small and large instances. We define these as size < 10 and size ≥ 10, respectively. Table 2 (Table 2) reports, for each circuit size, an estimate of the a posteriori optimal number of shots and the fraction of traces whose a posteriori optimum exceeds 10,000 shots, a budget that is half of that used to compute the a posterior optimal value for each trace. This percentage increases sharply with circuit size, from 8.15% at 4 qubits to 78.33% at 14 qubits, and it crosses 50% at 10 qubits. Based on this evidence, we observed that using a shot budget below 20,000 increases the number of traces that consume the entire budget before reaching the point of diminishing returns; therefore, we adopt 20,000 shots as the budget B for all runs of IncrementalExecution. Moreover, since the fraction of traces with an optimal shot count above 10,000 exceeds 50% from 10 qubits onward, we use the same threshold to group circuits in the remainder of the analysis: small circuits have 4, 6, or 8 qubits, while large circuits have 10, 12, or 14 qubits. 7 Experimental scripts, raw data and analysis are freely available at: https://github.com/GBisi/quantum-incremental-execution. 8 The dataset is fully available on: https://github.com/GBisi/qsimbench [10]

Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

21

Table 2. Shot-budget statistics from the preliminary study, grouped by circuit size.

Size 4 6 8 10 12 14

% optimal > 10,000 8.15% 18.52% 33.89% 51.30% 64.44% 78.33%

We evaluated all IncrementalExecution configurations by exhaustively exploring the policy space described in Section 5, for a total of 33,750 unique configurations. Each configuration specifies (i) the divergence metric, (ii) the stopping criterion, (iii) the stability-enforcement policy, and (iv) the shot-allocation strategy. We consider a configuration valid if, for each of the 180 traces, it returns a number of shots 𝑛 such that the resulting distribution diverges from the full budget distribution for less than the user-defined tolerance 𝛿, more formally D (𝑃ˆ𝑛 , 𝑃ˆ20000 ) ≤ 𝛿, which is based on Definition 3.4. In our experiments, we use values of 𝛿 ∈ {0.01, 0.025, 0.05, 0.1, 0.25}. In all the following evaluations, we always compare the results by comparing the perspective of the three divergence metrics and the five values of 𝛿 6.2

Analysis of the Configuration Parameters

We analyse the configuration space of IncrementalExecution to understand how its parameters affect the identification of valid configurations for the deltas and divergence metrics we consider. Specifically, we examine: (i) the threshold 𝜖, used by the stopping criterion to decide when to halt incremental iterations; (ii) the stopping-criterion policy, which specifies how to use the output distributions produced at each iteration to halt the incremental iterations; and (iii) the stability criterion, defined by a sliding window of size 𝑘, which requires the observed behavior to persist before a configuration is deemed stable. By systematically varying 𝜖, the stopping policy, and 𝑘, we quantify how sensitive the search is to these parameters, and how this sensitivity changes with the delta values and the adopted divergence metric. This analysis allows us to characterise which parameter regimes facilitate the discovery of valid configurations, providing practical guidance for selecting robust settings across heterogeneous deltas and metrics.

0

0

11.1

0

0

0

6.4

71.1

0

0

0

6.4

67.6

0

0

0

0

0

0

0

0

25.8

0

0

0

0

23.6

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0.1

1

25

5

0.1

1

25

5

0.1

0.2

0.2

0.2

0.0

% valid

0

0

95 85 75 65 55 45 35 25 15 5 0

5

0

0.0

0.22 62.2 73.3

0.0

0

0.0

0

5

73.3

0.0

58.9

0.0

0.89

0.0

0

5

0

0.0

56.7

0.0

42.2

5

Divergence metric = JS

5.3

25

Divergence metric = Hellinger

0

1

Divergence metric = TVD 0

0.01 0.025 0.05 0.1 0.25

Fig. 2. Heatmaps for 𝜖 0.01, 0.025, 0.05, 0.1, and 0.25, for all the divergence metrics and 𝛿 values considered. Manuscript submitted to ACM

22

Bisicchia et al.

6.2.1 Stopping Threshold 𝜖 analysis. Figure 2 reports, for each divergence metric, a heatmap in which each cell indicates the percentage of valid configurations obtained for a given pair of values (𝜖, 𝛿). The plots show that choosing 𝛿 ∈ 0.01, 0.025 impedes for IncrementalExecution to find valid configurations: the divergence between the distribution estimated from the shots selected by IncrementalExecution and the reference distribution computed using the full budget rarely falls below these stringent 𝛿 thresholds, so the validity condition is rarely satisfied. A clear pattern emerges when comparing divergence metrics and parameter regimes. First, validity is observed almost exclusively for the smallest threshold 𝜖 (0.01), and only when 𝛿 is sufficiently relaxed (typically 𝛿 ≥ 0.1). In this regime, IncrementalExecution achieves substantially higher validity rates under Hellinger and Jensen–Shannon (JS) than under TVD: at 𝛿 = 0.1, Hellinger and JS yield about 58.9% and 62.2% valid configurations, respectively, while TVD reaches 42.2%; at 𝛿 = 0.25, Hellinger and JS both reach 73.3%, compared to 56.7% for TVD. This suggests that, for the same (𝜖, 𝛿), TVD behaves as the most demanding metric in terms of meeting the validity constraint, whereas Hellinger and JS are more permissive and provide very similar outcomes. Second, increasing 𝜖 rapidly reduces the fraction of valid configurations across all metrics, indicating high sensitivity to this parameter. For 𝜖 = 0.025, TVD essentially collapses to near-zero validity (only 11.1% at 𝛿 = 0.25), while Hellinger and JS remain comparatively robust at the loosest delta, still yielding 71.1% and 67.6% valid configurations at 𝛿 = 0.25, but dropping to 6.4% at 𝛿 = 0.1. For larger thresholds (𝜖 ≥ 0.05), validity is recovered only at 𝛿 = 0.25 and only for Hellinger/JS (about 25.8% and 23.6%, respectively), whereas TVD yields no valid configurations. Overall, the figure highlights a strong interaction between 𝜖, 𝛿 and the divergence metric: stringent deltas almost never allow validity, 𝜖 is always strictly lower than 𝛿 to find valid configurations, highlighting and when validity is attainable, Hellinger and JS consistently support a wider and more stable set of valid configurations than TVD.

0

12.2

38.9

DMA

0

0

1.3

8.9

14.4

0

0

0.22

13.3

32.2

0

0

0.06

14.1

31.4

0.2

0.0

0.0

0.2

0.0

0.0

0.2

0.0

5

0

0.1

0

5

41.3

1 0.0 25

12.2

5

0

0.1

0

5

0

0.0 25

10

1

6.7

5

0

0.0

0

0.0 25

0

1

Delta

95 85 75 65 55 45 35 25 15 5 0

% valid

Divergence metric = JS

0.1

Divergence metric = Hellinger

5

Divergence metric = TVD

Fig. 3. Heatmaps for Delta and DMA stopping criterion policies, for all the divergence metrics and 𝛿 values considered.

6.2.2 Stopping Criterion analysis. Figure 3 compares the two stopping-criterion policies, Delta and DMA, across the considered divergence metrics. Each heatmap cell reports the percentage of valid configurations for a given 𝛿, with rows corresponding to the stopping policy. Across all metrics, validity is zero for the most stringent settings (𝛿 ∈ 0.01, 0.025), and it starts to appear only from 𝛿 = 0.05 onward. However, the two policies behave differently once validity becomes attainable. Under TVD, Delta yields no valid configurations at 𝛿 = 0.05 and only modest rates at larger deltas (6.7% at 𝛿 = 0.1 and 10% at 𝛿 = 0.25). In contrast, DMA is consistently more effective for TVD, having valid configurations already at 𝛿 = 0.05 (1.3%) and improving to 8.9% at 𝛿 = 0.1 and 14.4% at 𝛿 = 0.25. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

23

The gap between the policies is even clearer for Hellinger and JS. For Hellinger, Delta reaches 12.2% valid configurations at 𝛿 = 0.1 and 41.3% at 𝛿 = 0.25, whereas DMA provides similar performance at 𝛿 = 0.1 (13.3%) but is lower at 𝛿 = 0.25 (32.2%), while still enabling a small fraction of valid configurations at 𝛿 = 0.05 (0.22%) where Delta yields none. A comparable pattern holds for JS: Delta obtains 12.2% at 𝛿 = 0.1 and 38.9% at 𝛿 = 0.25, while DMA slightly improves at 𝛿 = 0.1 (14.1%) but is lower at 𝛿 = 0.25 (31.4%), again with a small advantage at 𝛿 = 0.05 (0.06%) where Delta is zero. Overall, DMA appears more conservative in the sense that it can occasionally obtain valid configurations under tighter deltas (notably at 𝛿 = 0.05) and it improves results for the most demanding metric (TVD). Conversely, when 𝛿 is sufficiently loose (especially 𝛿 = 0.25), and the divergence is measured with Hellinger or JS, Delta tends to achieve the highest validity rates. This highlights a trade-off between the two stopping policies: DMA offers slightly better robustness in stricter regimes, while Delta can be more effective in permissive regimes where many configurations can satisfy the validity condition.

0

1.3

7.2

k3

0

0

0.67

12

19.3

0

0

0

17.3

46.7

0

0

0

17.3

45.3

5

0

0

2.5

12

19.3

0

0

0.53

20.5

47.5

0

0

0.13

22.5

46.1

0.0

95 85 75 65 55 45 35 25 15 5 0

% valid

0

0.2 5

0

0.1

8

0.0 5

1.3

0.0 1 0.0 25

0

0.2 5

0

0.1

0

0.0 5

2

25

1.3

0.0 1

0

0.2 5

0

0.0

0

0.0 1

1

0.1

Divergence metric = JS

0.0 5

Divergence metric = Hellinger

25

Divergence metric = TVD

Fig. 4. Heatmaps for stability window 𝑘 1, 3 and 5, for all the divergence metrics and 𝛿 values considered.

6.2.3 Stability Windows 𝑘 analysis. Figure 4 analyses the effect of the stability window parameter (here shown as 𝑘 ∈ 1, 3, 5) on the percentage of valid configurations, across divergence metrics and 𝛿 values. As in the previous analyses, the strictest deltas (𝛿 ∈ 0.01, 0.025) lead to no valid configurations for any metric and any window size, confirming that these settings are too demanding for the observed divergences to consistently fall below the target threshold. When validity becomes attainable (𝛿 ≥ 0.05), increasing the window size generally improves the success rate, especially for Hellinger and JS. Under TVD, the effect is present but more limited: with 𝑘 = 1 no valid configurations are found at 𝛿 = 0.05, while 𝑘 = 3 and 𝑘 = 5 recover small but non-zero rates (0.67% and 2.5%, respectively). At 𝛿 = 0.1, TVD rises sharply from 1.3% (𝑘 = 1) to 12% (𝑘 = 3 and 𝑘 = 5), and at 𝛿 = 0.25 it increases from 2% to 19.3% for both 𝑘 = 3 and 𝑘 = 5. This suggests that, for TVD, a larger window is necessary to filter out transient fluctuations, but gains saturate quickly beyond 𝑘 = 3. The benefit of larger windows is more pronounced for Hellinger and JS. For Hellinger, validity is zero at 𝛿 = 0.05 for 𝑘 ∈ 1, 3 and becomes non-zero only with 𝑘 = 5 (0.53%), while at 𝛿 = 0.1 it improves from 1.3% (𝑘 = 1) to 17.3% (𝑘 = 3) and 20.5% (𝑘 = 5). At 𝛿 = 0.25, the increase is substantial: from 8% (𝑘 = 1) to 46.7% (𝑘 = 3) and 47.5% (𝑘 = 5). JS shows the same trend: at 𝛿 = 0.1, validity rises from 1.3% (𝑘 = 1) to 17.3% (𝑘 = 3) and 22.5% (𝑘 = 5); at 𝛿 = 0.25, it increases from 7.2% to 45.3% and 46.1%, respectively, with a small non-zero value at 𝛿 = 0.05 only for 𝑘 = 5 (0.13%). Overall, these results indicate that requiring stability over a longer window markedly improves the likelihood of identifying valid configurations, particularly when using Hellinger or JS. Moreover, performance tends to saturate Manuscript submitted to ACM

24

Bisicchia et al.

between 𝑘 = 3 and 𝑘 = 5, suggesting that moderate window sizes already provide most of the benefit, while TVD remains the most restrictive metric even under larger windows. 6.3

Impact of Circuit Size and Noise Models

We now analyse the experimental results from the perspective of (i) circuit size, by contrasting the small and large circuit groups introduced earlier, and (ii) the adopted noise model, instantiated through the five simulated backends used in our data collection. The goal of this section is to understand whether valid configurations of IncrementalExecution depend on the intrinsic complexity of the circuit and on the characteristics of the underlying noise profile. Following the same methodology as in the previous section, we characterise validity by varying 𝛿 and the considered divergence metrics, and we measure how the percentage of valid configurations changes across circuit-size regimes and backends. This comparison highlights which settings remain robust when moving from smaller to larger circuits, and how different noise models alter the feasibility of satisfying the validity constraints under the same (𝛿, metric) combinations.

Divergence metric = JS

0

0

5.4

23.1

60.1

0

0

0.58

21.3

60.3

0

0

0.76

19.4

58.8

large

0

0

1.1

8.4

13.6

0

0

0.18

13.1

34

0

0

0.04

13.7

32.9

95 85 75 65 55 45 35 25 15 5 0

5 0.2

0.1

5 0.0

1 0.0 25

0.0

5 0.2

0.1

5 0.0

0.0 25

1 0.0

5 0.2

0.0

0.0 25

0.0

1

% valid

small

0.1

Divergence metric = Hellinger

5

Divergence metric = TVD

Fig. 5. Heatmaps for small and large circuits, for all the divergence metrics and 𝛿 values considered.

6.3.1 Circuit size analysis. Figure 5 compares the percentage of valid configurations obtained for smaller and larger circuits as 𝛿 varies, across the three divergence metrics. As expected, the strictest settings (𝛿 ∈ 0.01, 0.025) yield no valid configurations in any case, confirming that these targets are too stringent irrespective of circuit size and metric. When 𝛿 is relaxed, circuit size becomes a key discriminant. For small circuits, validity increases sharply as 𝛿 grows: under TVD it rises from 5.4% at 𝛿 = 0.05 to 23.1% at 𝛿 = 0.1 and reaches 60.1% at 𝛿 = 0.25. A very similar trend is observed for Hellinger and JS, which are slightly more favourable at the loosest setting: Hellinger goes from 0.58% (𝛿 = 0.05) to 21.3% (𝛿 = 0.1) and 60.3% (𝛿 = 0.25), while JS goes from 0.76% to 19.4% and 58.8%. Overall, for small circuits, 𝛿 = 0.25 enables around 60% valid configurations across all metrics, indicating that IncrementalExecution can reliably meet the validity constraint when the delta tolerance is sufficiently permissive. In contrast, large circuits exhibit systematically lower validity rates, even at relaxed deltas. Under TVD, validity peaks at only 13.6% for 𝛿 = 0.25 (with 11% at 𝛿 = 0.05 and 8.4% at 𝛿 = 0.1). Hellinger and JS show the same qualitative behaviour, but yield higher rates than TVD at the loosest delta: for 𝛿 = 0.25, Hellinger reaches 34% and JS 32.9%, while remaining low at 𝛿 = 0.05 (0.18% and 0.04%) and moderate at 𝛿 = 0.1 (13.1% and 13.7%). Taken together, the figure highlights that increasing circuit size makes the validity condition harder to satisfy under all divergence metrics, consistent with larger circuits producing output distributions that are more strongly affected by Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

25

noise and sampling variability. Moreover, while the three metrics are broadly consistent for small circuits, Hellinger and JS appear more inclined to have valid configurations than TVD for large circuits, especially at 𝛿 = 0.25, suggesting

0

0

0

1.1

8.4

13.6

0

0

2.5

14.7 35.5

0

0

3.1 14.8 32.9

0

0

2.4

8.4

13.6

0

0

3.1

15.5 35.9

0

0

0.93 15.2 36.6

0

0

2.2

8.4

13.6

0

0

2.9

14.4 34.7

0

0

1

14.5 34.5

0

0

2.2

8.4

13.6

0

0

0.18 14.1 34.4

0

0

1

14.1 34.4

25

5

0.1

1

25

1

25

5

95 85 75 65 55 45 35 25 15 5 0

5 0.2

0.1

0.0

0.2

0.0

0.2

0.0

0.04 14.3 36.6

% valid

0

0.0

36

0.0

15

5

0.53

0.1

0

5

0

0.0

13.6

0.0

8.4

5

Divergence metric = JS

2.6

0.0

Divergence metric = Hellinger

0

fake_fez fake_kyiv fake_marrakesh fake_sherbrooke fake_torino

0.0

Divergence metric = TVD 0

1

that metric choice becomes more impactful as circuit complexity grows.

Fig. 6. Heatmaps for the five considered backends, for all the divergence metrics and 𝛿 values considered.

6.3.2 Noise models analysis. Figure 6 breaks down the percentage of valid configurations by noise model, comparing the five simulated backends (fake_fez, fake_kyiv, fake_marrakesh, fake_sherbrooke, and fake_torino) across 𝛿 values and divergence metrics. As in the previous plots, the strictest deltas (𝛿 ∈ 0.01, 0.025) produce no valid configurations for any backend and any metric, indicating that these targets are unattainable regardless of the noise profile. For 𝛿 ≥ 0.05, the overall behaviour is remarkably consistent across backends, with only modest variations. Under TVD, validity remains low and largely backend-independent: for most backends it is around 2–3% at 𝛿 = 0.05, 8.4% at 𝛿 = 0.1, and 13.6% at 𝛿 = 0.25. The only noticeable deviation occurs at 𝛿 = 0.05 for fake_kyiv, which achieves a higher rate (11%) than the other backends (roughly 2.2–2.6%), while still aligning with them at 𝛿 ≥ 0.1. The picture changes when moving to Hellinger and JS: validity increases substantially at the loosest delta and remains broadly stable across noise models. With Hellinger, the percentage of valid configurations at 𝛿 = 0.25 lies in a narrow range around the mid-30s (from 34.4% for fake_torino up to 36% for fake_faze), and around 14–15.5% at 𝛿 = 0.1. At 𝛿 = 0.05 the rates are low but non-zero and slightly more backend-dependent (e.g., from 0.18% for fake_torino up to 3.1% for fake_marrakesh, with fake_kyiv at 2.5%). JS shows an almost identical trend: at 𝛿 = 0.25 all backends fall between 32.9% and 36.6%, and at 𝛿 = 0.1 they cluster tightly around 14.1–15.2%. Differences are again most visible at 𝛿 = 0.05, ranging from near-zero for fake_faze (0.04%) to about 3.1% for fake_kyiv. Overall, these results suggest that, within the considered parameter ranges, the choice of divergence metric and 𝛿 has a much stronger impact on validity than the specific backend noise model. Backend-specific effects are limited and mainly appear in the stricter regime (𝛿 = 0.05), while for 𝛿 ∈ 0.1, 0.25 all noise models exhibit very similar validity rates, especially under Hellinger and JS, indicating that the observed trends are robust across the considered noise profiles. 6.4

Selecting the Best Configurations

So far, we have analysed how parameters, noise-model backends, and circuit size individually affect the validity of configurations. We now turn to identifying the best configurations jointly across these factors, and to evaluating how well they generalise to unseen data. Specifically, we search for the best configuration for each triple (size, 𝛿, divergence metric), Manuscript submitted to ACM

26

Bisicchia et al.

where size denotes the circuit family (small vs. large), 𝛿 is the target tolerance used to define validity, and the divergence metric is the distance adopted to compare output distributions. Since our previous results show that no valid configurations are found for 𝛿 = 0.01 and 𝛿 = 0.025, we exclude these values from the following selection analysis. 6.4.1 Scoring metrics. To rank configurations, we define two complementary metrics that quantify how close a configuration comes to the optimal shot budget. Let 𝑠𝑐,𝑡 be the number of shots selected by configuration 𝑐 on trace 𝑡, and let 𝑜𝑡 be the corresponding optimal number of shots (i.e., the minimum number of shots that satisfies the validity constraint for that trace). First, the average difference measures the typical absolute deviation from the optimum: 1 ∑︁ 𝑠𝑐,𝑡 − 𝑜𝑡 . AvgDiff (𝑐) = |T | 𝑡 ∈ T This metric is expressed in shots and captures the absolute inefficiency of a configuration: lower values indicate that, on average, the configuration selects a number of shots close to the optimum. Second, the median ratio captures the typical multiplicative overhead:   𝑠𝑐,𝑡 MedRatio(𝑐) = median𝑡 ∈ T . 𝑜𝑡 A value close to 1 indicates that the configuration usually matches the optimal budget; values larger than 1 indicate overshooting (using more shots than necessary). Values below 1 indicate undershooting, which should never happen for valid configurations, as the optimal value is defined as the lowest number of shots to satisfy the target 𝛿. 6.4.2 Train/test protocol. Our dataset comprises 180 traces, each corresponding to a specific combination of algorithm, circuit instance, and backend noise model. We first partition the traces by circuit size into small and large groups. Within each size group, we select the best configuration using an 80/20 split: configurations are ranked on the validation set (80% of the traces) and then evaluated on the held-out test set (20%). On the training split, we compute AvgDiff and MedRatio for every candidate configuration, normalise the two metrics to make them comparable, and combine them with equal weight into a single score. The configuration with the lowest combined score is selected as the best one for the corresponding (size, 𝛿, divergence metric) setting. In the following, we report the performance of the selected configuration on the test split, providing an unbiased estimate of how well the chosen configuration generalises to unseen traces within the same size regime. 6.4.3 Best configurations and validity on the test set. Table 3 summarises, for each combination of circuit size (small vs. large), 𝛿, and divergence metric, the identifier of the configuration selected as best on the validation split (80% of the traces) and its corresponding validity percentage when evaluated on the held-out test split (20%). Recall that the validity percentage represents the fraction of test traces for which the selected configuration satisfies the validity constraint under the given (𝛿, distance) setting. Overall, the selected configurations generalise well, but circuit size clearly influences robustness. For small circuits, the best configurations achieve 100% validity in almost all settings, with the only exception being TVD at 𝛿 = 0.10 (94.44%). For large circuits, instead, the validity of the selected configurations is more variable: while several settings still reach 100%, a few cases show noticeable drops (e.g., Hellinger at 𝛿 = 0.05 reaches 83.33%, and both Hellinger and JS show 94.44% in some of the 𝛿 ∈ {0.10, 0.25} settings). This confirms the trend observed in the previous analyses: larger circuits make the validity condition harder to satisfy consistently, and configuration choices that appear optimal on the validation set may generalise slightly less reliably when circuit complexity increases. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

27

Table 3. Best configuration (selected on the validation split) for each (size, 𝛿, distance) setting, and its validity percentage on the test split.

6.4.4

Size

Distance

𝜹

Best conf. (val)

small small small small small small small small small

tvd hellinger js tvd hellinger js tvd hellinger js

0.05 0.05 0.05 0.10 0.10 0.10 0.25 0.25 0.25

conf_7 conf_3567 conf_3650 conf_358 conf_465 conf_3682 conf_525 conf_561 conf_1320

100.00 100.00 100.00 94.44 100.00 100.00 100.00 100.00 100.00

large large large large large large large large large

tvd hellinger js tvd hellinger js tvd hellinger js

0.05 0.05 0.05 0.10 0.10 0.10 0.25 0.25 0.25

conf_105 conf_3559 conf_275 conf_84 conf_303 conf_3921 conf_3740 conf_3945 conf_327

94.44 83.33 100.00 100.00 94.44 100.00 100.00 94.44 94.44

Validity on test (%)

Incremental vs. optimal shots on the test set. We conclude this section by inspecting, on the held-out test traces,

how closely the best configuration selected for each (size, 𝛿, distance) setting matches the optimal number of shots. Figures 7–12 are formatted in the same way. For a fixed size and 𝛿, each plot contains three panels (TVD, Hellinger, and JS). In each panel, the blue bars represent the number of shots produced by IncrementalExecution using the selected best configuration, while the orange bars represent the optimal number of shots for the same trace. For each panel, we also report the two evaluation metrics on the test set: the average absolute deviation from the optimal shots (AvgDiff, in shots) and the median ratio between incremental and optimal shots (MedRatio). For readability, we abbreviate the backend names in the trace identifiers as follows: fake_fez→FEZ, fake_kyiv→KYI, fake_marrakesh→MAR, fake_sherbrooke→SHE, fake_torino→TOR. Small circuits, 𝛿 = 0.05. Figure 7 shows that, for the strictest 𝛿 considered, the selected best configurations remain valid but tend to use a shot amount distant from the optimal value. TVD (conf_7) is the closest in absolute terms (AvgDiff = 1138.9) with MedRatio = 1.67, while Hellinger (conf_3567) and JS (conf_3650) exhibit larger deviations (AvgDiff = 3258.3 and 3627.8) with MedRatio around 1.75 and 1.71. In this regime, the configuration using the TVD is the one approximating best the optimal value. Small circuits, 𝛿 = 0.10. In Figure 8, the three metrics still overshoot, with median ratios close to 2. TVD (conf_358) achieves the smallest absolute deviation (AvgDiff = 450.0, MedRatio = 1.99), followed by Hellinger (conf_465; AvgDiff = 847.2, MedRatio = 2.06) and JS (conf_3682; AvgDiff = 1075.0, MedRatio = 2.12). This suggests that, for small circuits, relaxing 𝛿 improves absolute accuracy but does not necessarily reduce the typical multiplicative overhead, which remains close to a factor of two. Manuscript submitted to ACM

28

Bisicchia et al. Circuit Size=small | ẟ=0.05 Incremental

Optimal

Divergence Metric: TVD | Best Configuration: conf_7 AvgDiff=1138.9, MedRatio=1.67

2450

1000

8250

7600

9550

8200

8150

7250

9850

8450

9650 6350

5350

5850

6550 1250

350

1550

250

1350

150

4350

2250

5350

4000

4850

3450

1150

300

550

50

550

0

100

5000

1800

3850

10000

8700

15000

Divergence Metric: Hellinger | Best Configuration: conf_3567

0

8400

5700

11500 8100

7550

11500

12100 7450

7800

7850

11700

12500

12000 7850

8100

6500 3050

5100

3200

4800 1500

6100 2700

3500

6400 3000

6200 3000

3700

1150

2300

300

5000

2000

10000

6600

11200

15000

150

Number of Shots

AvgDiff=3258.3, MedRatio=1.75

0

8400

6700

14700 9500

14100 9200

13600 9250

9450

9450

9400

13700

13900

14700 9350 6500 3600

6200

3850

5300 1550

7400 3600

4250

7300 3600

3350

3800

1600

3000 550

2000

150

5000

7300

10000

7900

15000

13900

Divergence Metric: JS | Best Configuration: conf_3650 AvgDiff=3627.8, MedRatio=1.71

dj dj qaoa qaoa qft qft random vqe dj dj qaoa qaoa qft qft qnn qnn random vqe 4 | FEZ 4 | TOR 4 | SHE 6 | MAR 6 | FEZ 6 | TOR 6 | FEZ 6 | KYI 8 | FEZ 8 | MAR 8 | KYI 8 | SHE 8 | FEZ 8 | TOR 8 | FEZ 8 | KYI 8 | FEZ 8 | KYI

Fig. 7. Small circuits and 𝛿 = 0.05: incremental shots (best configuration) vs. optimal shots on the test set.

Small circuits, 𝛿 = 0.25. Figure 9 corresponds to the most permissive delta and shows that the selected configurations are closer to the optimal in absolute terms. TVD (conf_525) attains AvgDiff = 166.7 with MedRatio = 2.00, while Hellinger (conf_561) has a slightly larger AvgDiff = 216.7 but the best MedRatio among the three (1.90). JS (conf_1320) has AvgDiff = 208.3 but a notably higher MedRatio (2.80), indicating that it more frequently overshoots the optimal budget even when the absolute deviation remains limited. Large circuits, 𝛿 = 0.05. Moving to large circuits, Figure 10 shows a different behaviour: the selected configurations track the optimal values more closely in relative terms. TVD (conf_105) achieves MedRatio = 1.09 (AvgDiff = 1508.3), Hellinger (conf_3559) is the closest multiplicatively with MedRatio = 1.03 (AvgDiff = 1338.9), and JS (conf_275) has MedRatio = 1.06 (AvgDiff = 2008.3). While the absolute deviations are larger than in the small-circuit case (as expected from the larger budgets), the ratios indicate that the incremental budgets are generally near-optimal under all three metrics. Large circuits, 𝛿 = 0.10. Figure 11 confirms this trend: all three metrics yield very similar median ratios (around 1.13–1.14), suggesting stable near-optimal behaviour in relative terms. TVD (conf_84) shows the smallest absolute Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

29

Circuit Size=small | ẟ=0.1 Incremental

Optimal

Divergence Metric: TVD | Best Configuration: conf_358 6000

AvgDiff=450.0, MedRatio=1.99

200

1100

3100

2750

3550

3150

2550

3600

3100

3500

3650 2300

1700

2000

2350 150

50

550

100

50

150

1700 600

850

1750

1450 650

150

150

150

50

0

150

1000

50

2000

1000

3000

2050

4000

3300

5000

Divergence Metric: Hellinger | Best Configuration: conf_465

2700 750

3600

3350

3100

3500

2950

3700

3350

3000

3300

2800

4150

3350

4150 1400

700

2300 600

1450 300

700

800

1800

1950

1800 850

1300 50

0

350

550

700

2000 1000

1950

3000

1350

4000

3350

5000

50

Number of Shots

6000

AvgDiff=847.2, MedRatio=2.06

5300

950

2700

4150

3900

4500

3750

5000

4800

3950

4900

2000 700

950

300

1500

1900

2600 850

2500

2600 1100

900

400

500

50

0

700

1000

100

2000

1050

3000

1500

2400

4000

3850

3950

5000

4600

5400

AvgDiff=1075.0, MedRatio=2.12

3950

Divergence Metric: JS | Best Configuration: conf_3682 6000

dj dj qaoa qaoa qft qft random vqe dj dj qaoa qaoa qft qft qnn qnn random vqe 4 | FEZ 4 | TOR 4 | SHE 6 | MAR 6 | FEZ 6 | TOR 6 | FEZ 6 | KYI 8 | FEZ 8 | MAR 8 | KYI 8 | SHE 8 | FEZ 8 | TOR 8 | FEZ 8 | KYI 8 | FEZ 8 | KYI

Fig. 8. Small circuits and 𝛿 = 0.10: incremental shots (best configuration) vs. optimal shots on the test set.

deviation (AvgDiff = 1280.6, MedRatio = 1.13), while Hellinger (conf_303) and JS (conf_3921) are slightly more higher in absolute terms (AvgDiff = 1630.6 and 1819.4) with MedRatio = 1.14 for both. Large circuits, 𝛿 = 0.25. At 𝛿 = 0.25 (Figure 12) the metrics separate more clearly. TVD (conf_3740) deviates the most from the optimal values, with MedRatio = 1.98 (AvgDiff = 3238.9). In contrast, Hellinger (conf_3945) and JS (conf_327) remain closer to the optimum, achieving MedRatio = 1.19 (AvgDiff = 1483.3) and MedRatio = 1.27 (AvgDiff = 1983.3), respectively. Thus, for large circuits under permissive 𝛿, Hellinger and JS better exploit the relaxed constraint to reduce shots, while TVD maintains a larger safety margin. Overall discussion. Two high-level takeaways emerge. First, circuit size strongly impacts the results: for small circuits, the best configurations frequently overshoot the optimal values (MedRatio often close to 2 or larger), even when AvgDiff becomes small at relaxed 𝛿; for large circuits, instead, the best configurations track the optimal much more closely in relative terms for 𝛿 ∈ {0.05, 0.10} (MedRatio ≈ 1.03–1.14). Second, the divergence metric matters most with higher values of 𝛿. For 𝛿 = 0.25 on large circuits, Hellinger and JS yield clearly better (lower) median ratios than TVD, indicating that they allow IncrementalExecution to save shots more aggressively while remaining valid. Conversely, under Manuscript submitted to ACM

30

Bisicchia et al. Circuit Size=small | ẟ=0.25 Incremental

Optimal

Divergence Metric: TVD | Best Configuration: conf_525 AvgDiff=166.7, MedRatio=2.00

50

200

700

550

800

650

700 500

650

500

350

550 300 100

50

150

50

150

50

400 150

200

250

100

250 50

100

50

100

200

50

400

300

600

500

500

800

650

850

1000

850

1200

0

1000 800 500

750

750

1050

1100 750

850

800

850 600

750

150

300 50

250 50

250 50

400

250

250

450 250

150

50

200 50

200

150

400

350

400

600

500

800

700

1000

50

Number of Shots

1200

1050

Divergence Metric: Hellinger | Best Configuration: conf_561 AvgDiff=216.7, MedRatio=1.90

0

Divergence Metric: JS | Best Configuration: conf_1320

0

150

250 50

250 50

50

250

450

950

950

1050

900

950

900

1050

900

1050 850

750

850

850

750

650 250

150

250 50

250

250 50

200

50

400

450

600

250

800

300

750

1000

900

AvgDiff=208.3, MedRatio=2.80 1200

dj dj qaoa qaoa qft qft random vqe dj dj qaoa qaoa qft qft qnn qnn random vqe 4 | FEZ 4 | TOR 4 | SHE 6 | MAR 6 | FEZ 6 | TOR 6 | FEZ 6 | KYI 8 | FEZ 8 | MAR 8 | KYI 8 | SHE 8 | FEZ 8 | TOR 8 | FEZ 8 | KYI 8 | FEZ 8 | KYI

Fig. 9. Small circuits and 𝛿 = 0.25: incremental shots (best configuration) vs. optimal shots on the test set.

stricter deltas, the three metrics behave more similarly, and the main differences are expressed in absolute deviations rather than in typical multiplicative overhead. Recap of Best Configuration Parameters. Table 4 summarises the parameter settings of the best configurations for each circuit size, 𝛿, and convergence distance shown in this Section. Scalability of the framework. The IncrementalExecution framework is not tied to a specific number of qubits. Its stopping, stability, and allocation policies operate solely on empirical distributions collected during execution and therefore remain well defined for larger circuits. What changes with qubit count, depth, and circuit structure is not the applicability of the framework, but the configuration that yields the best reliability–cost trade-off. Larger circuits may induce broader or more complex output distributions, which can require stricter stopping thresholds, larger stability windows, larger shot budgets, or different divergence metrics. For this reason, the configurations reported here should be interpreted as best fixed configurations for the evaluated regimes, whereas the parameter-selection methodology introduced in this paper can be reused to tune IncrementalExecution for larger and deeper circuits. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

31

Circuit Size=large | ẟ=0.05 Incremental

Optimal

0

8500

7750

20000

18950

20000

18950

20000

18950

20000

18950

20000

18950

20000

17900

17550

20000 3550

2350

3950

2200

20000

18550

20000

20000

18650

15650

5350

3950

1550

500

5000

2550

10000

3150

15000

14200

16650

20000

13800

AvgDiff=1508.3, MedRatio=1.09

18600

Divergence Metric: TVD | Best Configuration: conf_105 25000

20000 20000

17050

20000

19750

20000

19800

20000

19750

20000

19800

20000

19750

20000

19800

20000

19800 19800

20000

19750

20000

19500

19350

20000 13200

10050

12450

12400

20000 13400

20000

18650

20000

20000

18550

20000

17550

15400

20000

9000

10000

6750

15000

10050

20000

5600

Number of Shots

AvgDiff=1338.9, MedRatio=1.03

18550

Divergence Metric: Hellinger | Best Configuration: conf_3559 25000

5000 0

17300

20000

20000

19800

20000

19500

19400

20000 14350

10650

12850

19550

20000 14300

20000

18950

20000

20000

18900

20000

17850

20000

15250 9350

10000

7750

15000

10650

20000

16350

AvgDiff=2008.3, MedRatio=1.06

18900

Divergence Metric: JS | Best Configuration: conf_275 25000

5000 0

dj dj qaoa qaoa qft qft random vqe dj dj qaoa qaoa qft qft qnn qnn random vqe 10 | FEZ10 | TOR10 | SHE12 | MAR12 | FEZ12 | TOR12 | FEZ 12 | KYI 14 | FEZ14 | MAR 14 | KYI 14 | SHE14 | FEZ14 | TOR14 | FEZ 14 | KYI 14 | FEZ 14 | KYI

Fig. 10. Large circuits and 𝛿 = 0.05: incremental shots (best configuration) vs. optimal shots on the test set.

6.5

Best Configurations Compared to Hoeffding and Weissman Inequalities

We finally compare the best configurations identified for IncrementalExecution against two concentration-inequality baselines that provide a priori sample-complexity requirements: the Hoeffding inequality [27] and the Weissman inequality [46]. In our setting, these bounds can be interpreted as worst-case upper bounds on the number of shots needed to guarantee that an empirical distribution is within a target tolerance 𝛿 under a fixed confidence level. We set this confidence level to 95%, aligning it with the empirical reliability observed for our selected configurations: as shown in Table 3, the best configurations achieve validity rates that are typically close to (and often equal to) 100% on the test set, with the lowest observed values still around 95% (e.g., 94.44% in several settings). Let 𝑝 denote the (unknown) true outcome distribution over an alphabet of size 𝐾 (in our experiments, we take 𝐾 = 2𝑛 for an 𝑛-qubit circuit), and let 𝑝ˆ𝑛 be the empirical distribution obtained from 𝑛 i.i.d. shots. We write 𝛿 ∈ (0, 1) for the target tolerance and set the failure probability to Δ := 1 − confidence_level (thus Δ = 0.05 for 95% confidence). Manuscript submitted to ACM

32

Bisicchia et al. Circuit Size=large | ẟ=0.1 Incremental

Optimal

Divergence Metric: TVD | Best Configuration: conf_84

4500

2600

17800

17700

17750

17700

17600

17750

17700

17750

17800

17750

14600

14350

13350

13400 2300

600

2450

17100

15200

500

9000

17200

3400

2200

550

0

500

1600

5000

100

10000

7200

9950

15000

6550

20000

15200

17150

AvgDiff=1280.6, MedRatio=1.13 15400

25000

11400

11150

20000

18950

19000

20000

19000

20000

20000

19000

20000

19050

20000

17750

17400

20000 5150

3100

4850

4150

6150

5250

19250

15700

19350

18150

15600

14950 9750 4450

2400

5000

3450

10000

9150

15000

13250

20000

1600

Number of Shots

AvgDiff=1630.6, MedRatio=1.14

15550

Divergence Metric: Hellinger | Best Configuration: conf_303 25000

0

0

14000

12050

20000

19050

19100

20000

19050

20000

20000

19100

20000

19150

20000

17950

17650

20000 6200

3750

5200

4700

20000

16600

20000

20000

16450

7500

4700

2800

4200

5000

1750

10000

6200

11000

15000

10300

20000

13750

15900

AvgDiff=1819.4, MedRatio=1.14

16550

Divergence Metric: JS | Best Configuration: conf_3921 25000

dj dj qaoa qaoa qft qft random vqe dj dj qaoa qaoa qft qft qnn qnn random vqe 10 | FEZ10 | TOR10 | SHE12 | MAR12 | FEZ12 | TOR12 | FEZ 12 | KYI 14 | FEZ14 | MAR 14 | KYI 14 | SHE14 | FEZ14 | TOR14 | FEZ 14 | KYI 14 | FEZ 14 | KYI

Fig. 11. Large circuits and 𝛿 = 0.10: incremental shots (best configuration) vs. optimal shots on the test set.

Hoeffding baseline (union bound). Using Hoeffding’s inequality for each outcome and a union bound over the 𝐾 outcomes, we obtain the standard ℓ∞ control 2
Pr(∥𝑝ˆ𝑛 − 𝑝 ∥ ∞ ≥ 𝜀 ∞ ) ≤ 2𝐾 exp −2𝑛𝜀 ∞ ,

so that requiring the r.h.s. to be at most Δ yields the shot budget   1 2𝐾 𝑛 ≥ log . 2 Δ 2𝜀 ∞

(3)

(4)

Since our comparisons are stated in terms of total variation distance (TVD), we relate ℓ∞ to TVD via TVD(𝑝ˆ𝑛 , 𝑝) = 1 ˆ 𝐾 2𝛿 2𝛿 ∥ 𝑝 𝑛 − 𝑝 ∥ 1 ≤ 2 ∥ 𝑝ˆ𝑛 − 𝑝 ∥ ∞ . Therefore, a sufficient condition for TVD(𝑝ˆ𝑛 , 𝑝) ≤ 𝛿 is ∥ 𝑝ˆ𝑛 − 𝑝 ∥ ∞ ≤ 𝐾 . Plugging 𝜀 ∞ = 𝐾 2

into (4) gives the TVD-calibrated Hoeffding baseline

  𝐾2 2𝐾 𝑛 ≥ log . 8𝛿 2 Δ Manuscript submitted to ACM

(5)

How Many Shots Are Enough for a Quantum Circuit?

33

Circuit Size=large | ẟ=0.25 Incremental

Divergence Metric: TVD | Best Configuration: conf_3740

14300

12500

14200

12550

14100

12100

14200

3500 17700

14850

17700

14900

17000

14600

17800

1800

3400 19100

15150

19350

15200

18400

18850

15250

14950

3550

2100

10450

10250

9350

9200 2450

300

2250

250

3100

500

9900

9100

9450

8950

5900

4100

2650

1650

1550

300

0

100

10000

4250

10100

15000

9050

20000

5000

14950

17900 9750

8200

8700

8800 1800

200

1800

200

2400

400

9200

8450

9500

8250

5000

3400

2400

1700

Divergence Metric: JS | Best Configuration: conf_327 AvgDiff=1983.3, MedRatio=1.27

19350

25000

3800

9200

0

250

1200

10000

8400

15000

15000

20000

5000

12650

14200

450

4700

1900

100

1900

50

2600 50

5950

9100

10100

13100 6650

6650

6800 1500

1300

1800

Divergence Metric: Hellinger | Best Configuration: conf_3945 AvgDiff=1483.3, MedRatio=1.19

100

Number of Shots

25000

300

0

50

5000

50

10000

6300

6900

15000

13300

13300

20000

12700

AvgDiff=3238.9, MedRatio=1.98

15300

25000

Optimal

dj dj qaoa qaoa qft qft random vqe dj dj qaoa qaoa qft qft qnn qnn random vqe 10 | FEZ10 | TOR10 | SHE12 | MAR12 | FEZ12 | TOR12 | FEZ 12 | KYI 14 | FEZ14 | MAR 14 | KYI 14 | SHE14 | FEZ14 | TOR14 | FEZ 14 | KYI 14 | FEZ 14 | KYI

Fig. 12. Large circuits and 𝛿 = 0.25: incremental shots (best configuration) vs. optimal shots on the test set.

Weissman baseline (TVD / ℓ1 bound). As an alternative that directly controls ℓ1 , we use the inequality of Weissman et al. [46], which (in an appendix-friendly form) states that   𝑛𝜀 12 𝐾 ˆ Pr(∥𝑝𝑛 − 𝑝 ∥ 1 ≥ 𝜀 1 ) ≤ (2 − 2) exp − . 2

(6)

Since TVD(𝑝ˆ𝑛 , 𝑝) = 12 ∥ 𝑝ˆ𝑛 − 𝑝 ∥ 1 , setting 𝜀 1 = 2𝛿 yields
Pr(TVD(𝑝ˆ𝑛 , 𝑝) ≥ 𝛿) ≤ (2𝐾 − 2) exp −2𝑛𝛿 2 , and enforcing this probability to be at most Δ gives the corresponding shot requirement  𝐾  1 2 −2 𝑛 ≥ log . 2𝛿 2 Δ

(7)

(8)

In the experimental tables that follow (Tables 5–7), we instantiate these expressions with confidence level 0.95 (i.e., Δ = 0.05) and 𝐾 = 2𝑛 unless otherwise noted, and compare the resulting worst-case shot budgets against the empirical shot usage of the best IncrementalExecution configurations. Manuscript submitted to ACM

34

Bisicchia et al. Table 4. Best configuration parameters across circuit sizes and 𝛿 thresholds.

Config ID

Size

𝛿

Metric

Stop. crit.

Main parameters

𝑘

Next Shots

Default

conf_7 conf_3567 conf_3650

Small Small Small

0.05 0.05 0.05

TVD Hellinger JS

Delta DMA DMA

𝜏 = 2, 𝜀 = 0.01 𝑤 = 5, 𝜏 = 2, 𝜀 = 0.01 𝑤 = 5, 𝜏 = 2, 𝜀 = 0.01

3 5 5

100 100 100

50 100 100

conf_358 conf_465 conf_3682

Small Small Small

0.10 0.10 0.10

TVD Hellinger JS

DMA DMA Delta

𝑤 = 3, 𝜏 = 3, 𝛼 = 0.5, 𝜀 = 0.025 𝑤 = 3, 𝜏 = 3, 𝛼 = 0.5, 𝜀 = 0.025 𝜏 = 3, 𝜀 = 0.025

3 5 1

50 50 100

50 50 100

conf_525 conf_561 conf_1320

Small Small Small

0.25 0.25 0.25

TVD Hellinger JS

Delta Delta DMA

𝜏 = 1, 𝜀 = 0.05 𝜏 = 1, 𝜀 = 0.05 𝑤 = 5, 𝜏 = 1, 𝜀 = 0.25

1 1 3

50 50 100

50 50 50

conf_105 conf_3559 conf_275

Large Large Large

0.05 0.05 0.05

TVD Hellinger JS

DMA DMA DMA

𝑤 = 3, 𝜏 = 3, 𝛼 = 0.5, 𝜀 = 0.01 𝑤 = 3, 𝜏 = 3, 𝛼 = 0.5, 𝜀 = 0.01 𝑤 = 3, 𝜏 = 3, 𝜀 = 0.01

3 5 5

100 100 100

50 100 50

conf_84 conf_303 conf_3921

Large Large Large

0.10 0.10 0.10

TVD Hellinger JS

DMA Delta DMA

𝑤 = 3, 𝜏 = 3, 𝛼 = 0.5, 𝜀 = 0.01 𝜏 = 3, 𝜀 = 0.025 𝑤 = 3, 𝜏 = 3, 𝛼 = 0.5, 𝜀 = 0.025

3 5 5

50 100 100

50 50 100

conf_3740 conf_3945 conf_327

Large Large Large

0.25 0.25 0.25

TVD Hellinger JS

DMA Delta Delta

𝑤 = 3, 𝜏 = 3, 𝛼 = 0.5, 𝜀 = 0.025 𝜏 = 2, 𝜀 = 0.05 𝜏 = 1, 𝜀 = 0.025

3 3 5

100 100 50

100 100 50

We report these baselines alongside (i) the optimal shot budget and (ii) the number of shots selected by IncrementalExecution when using the best configuration for each divergence metric (columns Inc-TVD, Inc-Hell, and Inc-JS) on the held-out test traces. Tables 5–7 present the comparison for 𝛿 ∈ {0.05, 0.10, 0.25}. Each row corresponds to a test trace and reports the optimal and incremental number of shots. The Weissman and Hoeffding baselines, instead, are determined solely by the target tolerance 𝛿, the circuit size, and the chosen confidence level; hence, within each size group they take a single value, and we display them once using multirow entries.9 Incremental approach (TVD, Hellinger and JS). Consider the conditions assumed in our context: the outcome space X is finite and 𝑃ˆ𝑛 denotes the empirical distribution constructed from measurement outcomes that are i.i.d. draws from a target distribution 𝑃. Classical second-order limit results for empirical distributions, in particular consequences of the Central Limit Theorem (CLT), imply that the typical fluctuations of 𝑃ˆ𝑛 around 𝑃 scale as 𝑛 −1/2 . As a consequence, for any tolerance 𝛿 > 0 and confidence level 1 − 𝜁 ∈ (0, 1), there exists 𝑛 0 = 𝑛 0 (𝛿, 𝜁 , 𝑃) such that   Pr ∥ 𝑃ˆ𝑛 − 𝑃 ∥ 1 ≤ 𝛿 ≥ 1 − 𝜁 , ∀𝑛 ≥ 𝑛 0, with 𝑛 0 typically scaling on the order of 𝛿 −2 . As we are considering D which is continuous and locally Lipschitz around 𝑃 with respect to the ℓ1 norm. Then there exists a constant 𝐿 > 0 such that, for 𝑛 sufficiently large, D (𝑃ˆ𝑛 , 𝑃) ≤ 𝐿 ∥ 𝑃ˆ𝑛 − 𝑃 ∥ 1 . 9 For readability, we show an excerpt with two representative test traces per circuit size. Within each row, we bold the smallest shot count among the

three IncrementalExecution variants (Inc-TVD, Inc-Hell, Inc-JS). Full tables are in Appendix A. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

35

Table 5. Sample complexity comparison for 𝛿 = 0.05 (excerpt; two test traces per circuit size).

Trace

Size Optimal Inc-TVD Inc-Hell Inc-JS Weissman Hoeffding

dj_4_FEZ qaoa_4_SHE

4 4

100 300

550 1150

2000 3700

2000 3800

2818 8.27𝑒 + 04

qaoa_6_MAR vqe_6_KYI

6 6

1800 150

3850 1350

6200 4800

7300 5300

9472 1.61𝑒 + 06

dj_8_FEZ qaoa_8_KYI

8 8

250 5850

1550 6550

5100 6200 3.61𝑒 + 04 3.03𝑒 + 07 11200 14700

dj_10_FEZ qaoa_10_SHE

10 10

500 13800

2550 16650

5600 9350 1.43𝑒 + 05 5.57𝑒 + 08 20000 20000

qaoa_12_MAR vqe_12_KYI

12 12

14200 3150

15650 5350

20000 20000 5.68𝑒 + 05 1.01𝑒 + 10 20000 20000

dj_14_FEZ vqe_14_KYI

14 14

2200 8500

3950 7750

12400 19550 2.27𝑒 + 06 1.80𝑒 + 11 20000 20000

Consequently, for any 𝛿 > 0 and 𝜁 ∈ (0, 1), there exists 𝑛 0′ = 𝑛 0′ (𝛿, 𝜁 , 𝑃) such that   Pr D (𝑃ˆ𝑛 , 𝑃) ≤ 𝛿 ≥ 1 − 𝜁 , ∀𝑛 ≥ 𝑛 0′ . This explains why, in practice, the number of shots needed in our incremental approach can be substantially smaller than distribution-free worst-case bounds (like those expressed in Eq. 5 and 8, which ignore the 𝑛 −1/2 second-order fluctuation behavior of 𝑃ˆ𝑛 around 𝑃 and instead control uniform deviations over the entire probability simplex.. The above reasoning applies, in particular, to total variation distance (TVD(𝑃, 𝑄) = 21 ∥𝑃 − 𝑄 ∥ 1 ), Hellinger distance (𝐻 2 (𝑃, 𝑄) ≤ TVD(𝑃, 𝑄)), and Jensen–Shannon divergence, which is continuous and satisfies JS(𝑃, 𝑄) = Θ(TVD(𝑃, 𝑄) 2 ). in the local regime.

Reading the tables. Across all values of 𝛿, both inequality-based baselines are orders of magnitude larger than the optimal value and the number of shots selected by IncrementalExecution. This is expected: Hoeffding and Weissman provide worst-case, distribution-agnostic guarantees, whereas the optimal and IncrementalExecution exploit distributions obtained by executing observed traces. Results for 𝛿 = 0.05. Table 5 reports the strictest tolerance. Here, the two analytic baselines are extremely conservative: Hoeffding already reaches 8.27 × 104 shots for 4-qubit circuits and grows to 1.80 × 1011 for 14 qubits, while Weissman ranges from 2.82 × 103 (4 qubits) to 2.27 × 106 (14 qubits). In contrast, IncrementalExecution typically remains in the 103 –104 range and is often within a small factor of the optimal value. The gap becomes especially evident on large instances: for size 12 and 14, Inc-Hell and Inc-JS frequently saturate the 20,000-shot budget in our runs (e.g., qaoa_12_MAR and vqe_14_KYI), whereas Inc-TVD still provides finite, often substantially smaller values (e.g., 15,650 shots on qaoa_12_MAR and 7,750 on vqe_14_KYI). Overall, at 𝛿 = 0.05, the TVD-based configuration has the lowest number of shots consistently among the three variants of IncrementalExecution in the shown traces. Results for 𝛿 = 0.10. Moving to a looser tolerance (Table 6) reduces the needed number of shots for all methods, but the qualitative picture remains unchanged. The analytic baselines are still far above our online approaches: Hoeffding ranges from 2.07 × 104 shots (4 qubits) to 4.49 × 1010 (14 qubits), and Weissman from 705 to 5.68 × 105 . The incremental policies, Manuscript submitted to ACM

36

Bisicchia et al. Table 6. Sample complexity comparison for 𝛿 = 0.10 (excerpt; two test traces per circuit size).

Trace

Size Optimal Inc-TVD Inc-Hell Inc-JS Weissman Hoeffding

dj_4_FEZ qaoa_4_SHE

4 4

50 150

150 150

700 1300

700 900

705 2.07𝑒 + 04

qaoa_6_MAR qft_6_TOR

6 6

650 850

1450 2050

1950 1950

2400 2600

2368 4.02𝑒 + 05

dj_8_FEZ qft_8_FEZ

8 8

100 3300

550 3650

2300 3300

1900 4900

9023 7.56𝑒 + 06

dj_10_FEZ qaoa_10_SHE

10 10

100 6550

1600 9950

3450 4200 3.56𝑒 + 04 1.39𝑒 + 08 9750 11000

qaoa_12_MAR vqe_12_KYI

12 12

7200 550

9000 3400

14950 15900 1.42𝑒 + 05 2.52𝑒 + 09 6150 7500

dj_14_FEZ vqe_14_KYI

14 14

500 2600

2450 4500

4850 5200 5.68𝑒 + 05 4.49𝑒 + 10 11150 14000

instead, typically require a few thousand shots even at 12–14 qubits. At this tolerance, we also start observing more “metric-dependent” crossovers: Inc-Hell can match or slightly improve over Inc-TVD on some traces (e.g., qft_6_TOR and qft_8_FEZ), suggesting that for moderate tolerances the tighter stopping behaviour induced by Hellinger can be advantageous for certain distributions. Inc-JS remains generally less sample-efficient in the excerpt, and it is often the highest among the three incremental variants. Results for 𝛿 = 0.25. Table 7 shows the loosest tolerance, where all methods stop much earlier. Here, the number of shots for IncrementalExecution are often in the hundreds of shots for small circuits and in the few thousands for 12–14 qubits. While the analytic baselines also decrease substantially (e.g., Weissman is 113 shots at size 4 and 9.09 × 104 at size 14), Hoeffding remains extremely large, reaching 7.19 × 109 at 14 qubits even under this relaxed tolerance. This regime also makes the differences between divergence metrics more pronounced. In particular, Inc-Hell becomes the lowest variant on multiple traces (e.g., qft_6_FEZ, qaoa_12_MAR, and vqe_14_KYI), and Inc-JS can occasionally be competitive on specific traces (e.g., dj_10_TOR). These crossovers suggest that, once the target tolerance is sufficiently loose, the choice of the divergence metrics affects the stopping behaviour more than the global “difficulty” of meeting the constraint. Overall discussion. Taken together, Tables 5–7 show that the two concentration-inequality baselines are systematically overconservative in our setting, by several orders of magnitude compared to both the optimal and the incremental shot values selected by IncrementalExecution. This overconservatism is not an artefact of tuning: it is inherent to worst-case, distribution-agnostic guarantees. Empirically, IncrementalExecution achieves shot values that are close to the optimal while maintaining high validity rates (Table 3) and scales far more gracefully with circuit size. Across the three incremental variants, the best divergence depends on the tolerance. TVD is the most reliable choice under strict accuracy requirements (here, 𝛿 = 0.05), whereas Hellinger becomes increasingly competitive and can outperform TVD at looser thresholds (especially at 𝛿 = 0.25). JS is generally most costly in terms of shots, although it can occasionally be best on specific traces. Overall, these results motivate using TVD for stringent regimes and considering Hellinger as a strong alternative when the target tolerance is moderate to loose. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

37

Table 7. Sample complexity comparison for 𝛿 = 0.25 (excerpt; two test traces per circuit size).

6.6

Trace

Size Optimal Inc-TVD Inc-Hell Inc-JS Weissman Hoeffding

dj_4_FEZ qaoa_4_SHE

4 4

50 50

100 250

150 400

250 250

113

qaoa_6_MAR qft_6_FEZ

6 6

100 250

300 500

350 450

450 750

379 6.43𝑒 + 04

dj_8_MAR qft_8_FEZ

8 8

50 650

100 850

300 850

250 1050

1444 1.21𝑒 + 06

dj_10_FEZ dj_10_TOR

10 10

50 50

300 1800

1200 1700

1550 1650

5703 2.23𝑒 + 07

qaoa_12_MAR vqe_12_KYI

12 12

1500 50

6300 2600

5000 2400

5900 2.27𝑒 + 04 4.03𝑒 + 08 3100

dj_14_FEZ vqe_14_KYI

14 14

50 450

1900 3500

1800 3400

2250 9.09𝑒 + 04 7.19𝑒 + 09 3550

3309

Comparison with fixed shot allocation strategies

The previous comparison focuses on the number of shots selected by the best configurations and on their relation to concentration-inequality baselines. We enhance our analysis by comparing the residual distance between the distribution obtained by each strategy and the reference distribution obtained using the full budget of 20,000 shots. For each target tolerance 𝛿 and circuit-size group, we aggregate this distance over all matching executions using the median, and report the result separately for TVD, Hellinger distance, and JS divergence. The dashed horizontal line marks the target tolerance 𝛿; bars below this line therefore satisfy the target distance threshold after aggregation. The annotation box in each panel reports the median number of shots used by the optimal and incremental strategies. Importantly, these figures should not be interpreted as a simple ranking in which the lowest bar is always preferable. Fixed-shot baselines with larger budgets can naturally achieve smaller distances to the 20,000-shot reference distribution because they use substantially more shots. Our objective is to reach the required target distance while reducing the number of shots needed. Therefore, once a strategy falls below the 𝛿 line, the relevant question is how many shots were required to get there, rather than whether a substantially more expensive fixed-shot baseline achieves an even smaller distance. Figures 13–15 report the median distance profile across circuit-size groups and target tolerances. Median aggregation is used to focus on the typical behaviour of each strategy and to reduce the impact of extreme traces. For small circuits, IncrementalExecution remains below the target threshold across the considered values of 𝛿. At the strictest threshold, 𝛿 = 0.05, smaller fixed-shot baselines may remain above the target for at least one divergence metric, while larger fixed budgets approach or satisfy the required distance threshold. As 𝛿 becomes more permissive, especially for 𝛿 = 0.10 and 𝛿 = 0.25, more baselines fall below the threshold. However, smaller distances for high fixed-shot baselines should be interpreted together with their larger shot budgets: they are closer to the 20,000-shot reference because they continue executing even after the target distance may already have been reached. For large circuits, the same pattern becomes more pronounced. At 𝛿 = 0.05, the target is harder to satisfy, and several fixed-shot baselines remain above the threshold for one or more divergence metrics. In contrast, the optimal and Manuscript submitted to ACM

38

Bisicchia et al.

Median distance to 20k reference, δ = 0.05

Median distance to 20k reference

δ = 0.05

TVD

Hellinger

JS

Small circuits 0.12

median shots Opt. T/H/J=2.9k/3.4k/4k Inc. T/H/J=4.6k/6.5k/7.7k

0.10

Large circuits 0.7 0.6

median shots Opt. T/H/J=17.7k/18.6k/18.9k Inc. T/H/J=20k/20k/20k

0.5 0.08

0.4

0.06

0.3

0.04

0.2

0.02

0.1

0.00

Opt.

Inc.

F1k F2.5k F5k F10k F15k

Strategy / baseline

0.0

Opt.

Inc.

F1k F2.5k F5k F10k F15k

Strategy / baseline

Fig. 13. Median distance to the 20,000-shot reference distribution for 𝛿 = 0.05. The left panel reports small circuits, while the right panel reports large circuits. The dashed line marks the target tolerance. Strategy labels are abbreviated as follows: Opt. denotes the a posteriori optimal values, Inc. denotes IncrementalExecution, and F𝑥k denotes a fixed-shot baseline using 𝑥,000 shots. The Inc. bars have zero height because IncrementalExecution reaches the full 20,000-shot budget in the median case; its distribution therefore coincides with the 20,000-shot reference distribution.

incremental strategies lie close to the target boundary, which is the desired behaviour for a shot-optimisation method: stopping near the point where the required tolerance is met, rather than spending additional shots to further reduce the distance beyond what is required. At 𝛿 = 0.10 and 𝛿 = 0.25, IncrementalExecution remains below the target line, while high-budget fixed baselines can sometimes show smaller median distances. This does not contradict the benefit of IncrementalExecution, because those baselines use a larger, fixed number of shots independently of whether the target distance has already been achieved. Overall, the median profiles reinforce the main message of the evaluation: IncrementalExecution is not designed to dominate every fixed-shot baseline in absolute distance to the 20,000-shot reference distribution, since additional samples can always move the empirical distribution closer to that reference. Rather, it is designed to stop once the empirical distribution is close enough for the target tolerance. The relevant success condition is therefore whether the bars fall below the 𝛿 line. When that condition is met, the advantage of the incremental strategy lies in reaching the required distance threshold without committing in advance to a conservative fixed-shot budget. 6.7

Algorithm-wise Interpretation of the Results

The previous analyses considered the behaviour of IncrementalExecution mainly with respect to its policy parameters, circuit size, backend noise model, and divergence metric. We now complement this discussion by interpreting the behaviour of the IncrementalExecution framework and its configurations from the perspective of the quantum Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

39

Median distance to 20k reference, δ = 0.1

Median distance to 20k reference

δ = 0.1

TVD

Hellinger

JS

Small circuits 0.12

median shots Opt. T/H/J=750/825/1.1k Inc. T/H/J=1.7k/2.1k/2.6k

0.10

Large circuits 0.7 0.6

median shots Opt. T/H/J=13.8k/15.6k/16.5k Inc. T/H/J=14k/18.7k/20k

0.5 0.08

0.4

0.06

0.3

0.04

0.2

0.02

0.1

0.00

Opt.

Inc.

F1k F2.5k F5k F10k F15k

0.0

Opt.

Strategy / baseline

Inc.

F1k F2.5k F5k F10k F15k

Strategy / baseline

Fig. 14. Median distance to the 20,000-shot reference distribution for 𝛿 = 0.10. The left panel reports small circuits, while the right panel reports large circuits. The dashed line marks the target tolerance. Strategy labels are abbreviated as follows: Opt. denotes the a posteriori optimal values, Inc. denotes IncrementalExecution, and F𝑥k denotes a fixed-shot baseline using 𝑥,000 shots.

algorithms included in the benchmark. Importantly, the algorithm label is not used by IncrementalExecution: the framework remains fully black-box and bases its decisions only on the observed measurement outcomes. Nevertheless, grouping the results of the best configurations by algorithm provides useful insight into the empirical difficulty of stabilising different classes of output distributions. Figure 16 summarises this perspective by reporting, for each algorithm family and target tolerance, the median oracle shot count and the median shot counts selected by the best IncrementalExecution configurations under the three divergence metrics. A first observation is that the benchmark algorithms exhibit markedly different stabilisation profiles. The dj instances are among the easiest cases for the framework. They often reach the a posteriori optimum with relatively few shots, especially for relaxed tolerances, and the best IncrementalExecution configurations rarely approach the full budget even at larger sizes. This behaviour is consistent with the intuition that these circuits tend to induce comparatively structured output distributions, for which the empirical distribution stabilises quickly. The static VQE instances show a similar, although more variable, behaviour: for loose tolerances they often require only a small fraction of the 20,000-shot budget, while under stricter tolerances the Hellinger- and JS-based configurations can become conservative. In these cases, TVD tends to provide the most economical stopping behaviour, as also visible in Figure 16. The qaoa instances occupy an intermediate position. For small circuits, IncrementalExecution is generally able to stop well before the maximum budget, while for larger circuits and stricter tolerances the optimal and incremental shot counts grow substantially. This indicates that the difficulty of these instances is not solely algorithmic, but emerges from the interaction between algorithm family, circuit size, and target tolerance. In particular, when 𝛿 is relaxed, Manuscript submitted to ACM

40

Bisicchia et al.

Median distance to 20k reference, δ = 0.25

Median distance to 20k reference

δ = 0.25

TVD

Hellinger

JS

Small circuits 0.30

Large circuits 0.7

median shots Opt. T/H/J=175/250/250 Inc. T/H/J=450/475/700

0.6

0.25

0.5

0.20

0.4

0.15

0.3

0.10

0.2

0.05 0.00

median shots Opt. T/H/J=5.3k/8.3k/9k Inc. T/H/J=9.6k/8.5k/9.3k

0.1 Opt.

Inc.

0.0

F1k F2.5k F5k F10k F15k

Opt.

Inc.

Strategy / baseline

F1k F2.5k F5k F10k F15k

Strategy / baseline

Fig. 15. Median distance to the 20,000-shot reference distribution for 𝛿 = 0.25. The left panel reports small circuits, while the right panel reports large circuits. The dashed line marks the target tolerance. Strategy labels are abbreviated as follows: Opt. denotes the a posteriori optimal values, Inc. denotes IncrementalExecution, and F𝑥k denotes a fixed-shot baseline using 𝑥,000 shots.

Optimal

Inc-TVD

δ = 0.05

Inc-Hell

Inc-JS

δ = 0.10

δ = 0.25

20,000

Median shots

10,000

1,000

100 dj

e

vq

oa

qa

qft dom ran

n qn

dj

e

vq

oa

qa

qft dom ran

n

qn

dj

e

vq

oa

qa

qft dom ran

n

qn

Algorithm family

Fig. 16. Algorithm-wise median sample-complexity profiles for the oracle and for the best IncrementalExecution configurations under TVD, Hellinger, and JS. Values are grouped by target tolerance 𝛿 and algorithm family. The dashed line marks the maximum budget 𝐵 = 20,000.

Hellinger-based configurations become competitive and sometimes require fewer shots than TVD-based configurations, suggesting that smoother divergences can better exploit approximate stabilisation in these cases. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

41

The hardest cases are represented by qft, qnn, and random circuits. For these algorithms, especially at 12 and 14 qubits, many traces have the a posteriori optimal shot count already close to the full budget under 𝛿 ∈ {0.05, 0.10}. Correspondingly, several IncrementalExecution configurations also stop near, or at, the 20,000-shot cap. This behaviour suggests that these circuits induce output distributions with larger effective support or slower empirical stabilisation, so that the point of diminishing returns is reached later. Even when 𝛿 = 0.25, these algorithm families typically require more shots than dj and static VQE, confirming that circuit size alone does not fully explain the observed difficulty. The algorithm-wise view also clarifies the role of the divergence metric. TVD is the most reliable choice in stringent regimes. This explains why TVD-based configurations are often preferable for dj, static VQE, and strict-𝛿 settings. Conversely, Hellinger becomes increasingly attractive at moderate and loose tolerances, particularly for larger qaoa, qft, and static VQE instances, where its smoother response to small-probability fluctuations can reduce unnecessary sampling. JS generally behaves more conservatively in terms of shot usage, although it can still be competitive on specific traces. Overall, these results indicate that IncrementalExecution adapts not only to circuit size and backend noise, but also to the empirical distributional structure induced by the algorithm being executed. From a practical standpoint, this suggests that algorithm-aware policy selection can be beneficial when such information is available: TVD-based configurations are a robust default for strict accuracy requirements and more concentrated output distributions, while Hellinger-based configurations are a strong alternative for moderate-to-loose tolerances and algorithms whose output distributions stabilise more gradually. At the same time, these observations should be interpreted as tuning guidelines rather than assumptions of the framework: IncrementalExecution does not require algorithm-specific knowledge, and the algorithm-wise trends simply explain why different circuit families may benefit from different policy choices. A more detailed view of the per-trace sample-complexity results is reported in Appendix A. 6.8

Concluding Discussion

We now summarise the main findings of our experimental evaluation by explicitly linking them to the research questions introduced at the beginning of Section 6. RQ1: How the parameters of IncrementalExecution impact on finding the target accuracy? Our results show that reaching the target tolerance is highly sensitive to the stopping and stability parameters. In particular, validity concentrates in regimes where the stopping threshold is conservative (most notably 𝜀 = 0.01), while larger thresholds quickly collapse the space of valid configurations. Stability enforcement plays a complementary role: increasing the stability window 𝑘 substantially raises the likelihood of finding valid configurations (especially under Hellinger and JS), with gains that largely saturate around 𝑘 ∈ {3, 5}. Finally, the stopping policy introduces a clear trade-off: DMA is generally more robust in stricter regimes (and is especially beneficial for the most demanding metric, TVD), whereas Delta tends to yield higher validity rates when 𝛿 is sufficiently permissive. Overall, these findings indicate that (i) 𝜀 must typically be smaller than 𝛿 to obtain validity, and (ii) explicit stability enforcement is essential to avoid premature stopping driven by sampling noise. RQ2: How the configuration of IncrementalExecution is affected by noise models and circuits? Circuit characteristics have a strong impact on feasibility, while the specific noise model plays a comparatively minor role within the considered backends. The partition into small and large circuits is reflected in consistently different validity regimes: small circuits admit many more valid configurations and exhibit near-perfect robustness for the selected best policies, whereas large Manuscript submitted to ACM

42

Bisicchia et al.

circuits systematically reduce validity rates and make generalisation slightly less stable (e.g., 83.33%–94.44% in the worst cases). Conversely, the backend-level analysis shows that, for 𝛿 ∈ {0.1, 0.25}, validity percentages cluster tightly across the five simulated devices, suggesting that the main determinants of configuration feasibility are the target tolerance and circuit size rather than backend-specific noise idiosyncrasies. The algorithm-wise analysis further refines this observation: dj and static VQE instances are generally easier to stabilise, qaoa exhibits intermediate behaviour, whereas qft, qnn, and random circuits tend to require more shots, especially at larger sizes and under stricter tolerances. This suggests that algorithm family can provide a useful tip for policy tuning, even though IncrementalExecution itself remains fully black-box and does not rely on algorithm-specific information. Backend-specific differences become visible mainly in stricter regimes (e.g., 𝛿 = 0.05), where validity is rare and small variations can be amplified. RQ3: Which are the best configurations of IncrementalExecution? The best configurations selected with the train/test protocol confirm two consistent design patterns. First, robust best configurations typically combine conservative stopping (small 𝜀 and moderate 𝜏) with stability enforcement (𝑘 ≥ 3 for most settings). Second, the preferred stopping policy depends on the regime: DMA is frequently selected in stricter settings and for TVD-heavy regimes, while Delta appears more often among the best choices at looser tolerances and under Hellinger/JS, where it can exploit permissive constraints to stop earlier. Importantly, the selected configurations generalise well: for small circuits they achieve 100% validity in all but one case (TVD at 𝛿 = 0.10), while for large circuits they still remain close to full validity, albeit with a few noticeable drops in the tightest settings. Hence, “best” configurations are not universal: they are conditional on circuit size and target tolerance, which motivates reporting best policies per (size, 𝛿, metric) setting. RQ4: How the best configurations of IncrementalExecution behave in comparison with the state of the art? Compared to concentration-inequality baselines (Hoeffding [27] and Weissman [46]), the best configurations of IncrementalExecution are orders of magnitude more sample-efficient in our setting. This gap is inherent: analytic inequalities provide worst-case, distribution-agnostic guarantees, whereas IncrementalExecution leverages online evidence from the observed output distributions to stop early. Empirically, the incremental budgets are consistently close to the a posteriori optimal budgets, while maintaining high validity rates on the held-out test set, and they scale far more gracefully with circuit size than the inequality-based prescriptions. At the same time, our results also highlight an important boundary case: in several traces (especially for larger circuits under stricter tolerances and for some metric/policy combinations), IncrementalExecution reaches the maximum budget of 20,000 shots. This behaviour should not be interpreted only as “policy inefficiency”: it can also signal that the fixed budget is itself too low to obtain a statistically meaningful estimate for those circuit/noise regimes, i.e., the experiment is still in a high-variance region where convergence has not yet occurred. In such cases, the number of shots required to reach a given tolerance may move closer to the (otherwise overconservative) analytic prescriptions, because the task effectively becomes harder and more “worst-case-like”. Crucially, this is not a limitation of the incremental methodology per se. If the user is willing (or able) to allocate more shots than the initial budget, IncrementalExecution can simply continue beyond 20,000 and still provide value: it will keep tracking convergence online and can identify the point of diminishing returns, i.e., the regime where additional shots yield negligible improvements in the selected divergence. In other words, increasing the budget does not invalidate the approach; rather, it extends the observable convergence trajectory and allows the same policies to determine whether (and when) further execution becomes unproductive. Finally, the metric comparison clarifies when each divergence is preferable: TVD is the most reliable choice under strict accuracy requirements (here, 𝛿 = 0.05), while Hellinger becomes increasingly competitive as 𝛿 loosens and can Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

43

yield lower incremental budgets on large circuits at 𝛿 = 0.25. JS typically requires the most shots overall, but on isolated traces it can be the lowest. Overall implications and limitations. Taken together, RQ1–RQ4 indicate that IncrementalExecution is a practical mechanism to reduce shot budgets while preserving a target distributional accuracy, provided that the given tolerance (𝛿) is not excessively stringent and that stability is enforced to mitigate sampling fluctuations. Circuit size, together with the algorithm-induced structure of the output distribution, is the primary factor shaping both feasibility and achievable savings, whereas backend noise variations are secondary in the regimes where validity is attainable. Finally, while our evaluation provides strong evidence that incremental policies outperform worst-case analytic baselines in realistic NISQ-like conditions, these conclusions are conditioned on simulator-based noise models and a finite reference budget (20,000 shots). Future work should validate these trends on real hardware and investigate adaptive batch sizing and policy selection objectives that explicitly optimise the reliability–savings frontier rather than a single combined score. 7

Practical Applicability

A natural question arises regarding the feasibility of the proposed IncrementalExecution approach on real quantum hardware: can repeated, adaptive submissions be performed efficiently in practice, or do overheads such as queue times hinder their benefits? While this concern is well-justified, recent advances in quantum cloud infrastructure mitigate these limitations and render incremental execution a viable strategy on current quantum platforms. 7.1

Quantum Session Support

Several quantum service providers, most notably IBM Quantum, have introduced session-based execution models [40]. Within a session, users are allocated a continuous quantum processing window during which multiple circuit submissions can be issued with minimal latency. This capability enables rapid, successive dispatches of small shot batches, perfectly aligning with the needs of our incremental framework. By preserving contextual and hardware state across iterations, sessions reduce the per-batch overhead to negligible levels and significantly improve the responsiveness of adaptive execution schemes. 7.2

Reservation-Based Execution Models

Other providers, such as IonQ [28], Rigetti [22], and AWS Braket [1], offer alternative mechanisms that similarly support low-latency, iterative quantum-classical workloads. In particular, reservation-based models allow users to pre-book dedicated time slots on quantum hardware, during which they can dispatch multiple jobs without re-entering the global job queue. This model provides users with predictable access and substantially reduced wait times, enabling the tight quantum-classical feedback loops required by IncrementalExecution. Some platforms further support job batching, in which a sequence of parameterised circuits can be submitted and evaluated efficiently within a single reservation window. These capabilities make it feasible to execute adaptive algorithms with controlled latency and sufficient throughput to maintain convergence guarantees, even in the presence of constrained hardware availability. 7.3

Hybrid Execution Models in NISQ Workloads

It is worth noting that the IncrementalExecution model proposed in this work closely parallels the hybrid quantumclassical loop that underpins many of the most prominent NISQ-era algorithms, including VQA, such as VQE, and QML approaches. These hybrid approaches involve parameterised quantum circuits that are iteratively updated by a classical Manuscript submitted to ACM

44

Bisicchia et al.

optimiser based on quantum measurement results. Critically, each optimisation step requires fresh samples from the circuit with updated parameters — a process that is inherently iterative, non-deterministic, and highly sensitive to sampling noise. The infrastructure, scheduling mechanisms, and interface layers developed for VQA-like applications are directly applicable to the IncrementalExecution paradigm we propose. Just as hybrid algorithms require timely feedback to guide optimisation, our framework requires rapid evaluation of intermediate measurement distributions to detect convergence and determine whether further execution is warranted. This alignment is particularly significant given the central role that VQA and QML workloads play in current quantum computing research and application development. By leveraging the same architectural patterns and infrastructure already validated for these use cases, our framework not only becomes immediately implementable but also benefits from ongoing improvements in hybrid execution support. 7.4

Using IncrementalExecution in VQA and QML Workloads

This section discusses a possible integration scenario rather than an extension of our theoretical guarantees to fully non-stationary adaptive workloads. In a VQA or QML optimisation loop, the circuit parameters are updated between iterations; however, within a single iteration, the parameter values are fixed while the circuit is repeatedly sampled to estimate an objective, gradient, or output distribution. IncrementalExecution can be applied to this per-iteration static circuit evaluation. The optimisation trajectory as a whole remains non-stationary and requires additional mechanisms beyond the scope of this paper. A natural integration point for IncrementalExecution is the repeated sampling of a fixed parameterised circuit within one iteration of a hybrid workflow. Instead of relying on fixed shot budgets for each circuit evaluation, it is possible to invoke IncrementalExecution at each step of the hybrid loop, dynamically determining the number of shots required to obtain a stable and accurate estimate of the circuit’s output distribution for the current parameter setting. This not only reduces shot waste in over-sampled evaluations but also prevents under-sampling in high-variance regions of the optimisation landscape. Moreover, the framework’s support for the initial_guess option allows it to exploit prior knowledge from the previous step’s output distribution. This is especially useful in hybrid algorithms, where subsequent parameter updates typically induce smooth, incremental changes in the quantum circuit’s output distribution. By bootstrapping, at the beginning of every iteration, the initial empirical distribution 𝑃ˆ0 with the empirical output of the previous iteration, convergence checks can begin from an already-informed prior, accelerating convergence and further reducing execution cost. Recent work [30] supports this idea by empirically demonstrating that the output distributions of parametrised quantum circuits often evolve smoothly in parameter space. The authors propose using a form of distributional warm start, where knowledge of previously observed distributions informs the sample allocation strategy of subsequent iterations. Our framework can readily incorporate such strategies: for instance, the divergence between the current empirical distribution and the warm-start prior can guide the batch size allocation or convergence threshold, adapting more rapidly when parameter shifts are small. 7.5

Summary

In summary, while traditional execution paradigms on cloud-based quantum hardware may introduce latency barriers, emerging infrastructure developments, such as quantum sessions, reservation-based access, batched execution, and Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

45

priority queues, actively support the kinds of adaptive, interactive workloads required by our framework. Moreover, the structural similarities between our incremental approach and widely adopted hybrid quantum-classical algorithms further reinforce its practical viability. Importantly, VQA and QML circuits are particularly well-suited for integration with IncrementalExecution: not only does the framework align with their feedback-driven nature, but it can also exploit inter-step distributional smoothness to accelerate convergence and reduce shot usage. By leveraging distributional priors, either directly from prior steps or via more sophisticated mechanisms such as those proposed in [30], the framework supports intelligent shot allocation across optimisation steps, paving the way for more efficient, noise-resilient hybrid quantum workflows. The proposed execution strategy is thus well-aligned with the current operational realities and architectural trajectories of NISQ-era quantum computing. 8

Threats to Validity

We discuss potential threats to the validity of our findings, organised according to commonly accepted categories: internal, external, construct, and conclusion validity [47]. 8.1

Internal Validity

Internal validity concerns whether the experimental results are attributable to the variables being manipulated rather than to confounding factors. Our experiments rely on synthetic execution traces generated by IBM’s noisy FakeBackend simulators. While these simulators emulate real device noise based on recent calibration data, they may not fully capture temporal noise drift, scheduling effects, or transient failures encountered in real hardware. Nevertheless, by standardising the simulation environment across all tested configurations, we ensure that relative comparisons between policy variants remain valid. Additionally, care was taken to avoid implementation bias: all stopping criteria, distance functions, and framework internals were independently tested and validated. Outlier removal and convergence filtering were performed systematically and without favouring specific configurations. 8.2

External Validity

External validity refers to the generalisability of results beyond the specific circuits, backends, and parameter settings used in the study. Although our benchmark includes a diverse set of 180 circuit-backend combinations spanning multiple quantum algorithms (QPE, Grover, QFT, random circuits) and realistic noise models, it is still limited in scope. Results may not generalise to quantum algorithms with fundamentally different output characteristics or to future quantum processors with radically different noise behaviours. In particular, results may not generalise to variational or other adaptive workloads, where the output distribution changes across optimisation iterations and the stationarity assumption underlying our stopping criterion no longer holds without additional mechanisms. Our evaluation is also limited to circuits up to 14 qubits. This limitation concerns the empirical validation of specific configurations, not the applicability of IncrementalExecution itself. The framework and policies are qubit-agnostic: they require only online access to batches of measurement outcomes and do not assume a fixed circuit size, topology, or noise model. However, evaluating larger and deeper circuits requires substantially more resources because the a posteriori reference distribution used for validation becomes more expensive to estimate reliably as the effective output support grows. Consequently, we leave a systematic evaluation beyond 14 qubits and for wider/deeper circuit families to future work. Manuscript submitted to ACM

46

Bisicchia et al. Furthermore, we did not evaluate execution on real quantum hardware. While Section 7 argues that the framework

is compatible with modern hybrid and session-based runtimes, empirical confirmation on actual devices remains future work. 8.3

Construct Validity

Construct validity addresses whether the evaluation measures faithfully capture the intended properties—in our case, convergence and accuracy. The use of Total Variation Distance as the sole divergence metric, while standard and interpretable, may not capture all relevant aspects of output quality, especially for structured or task-specific distributions. However, our convergence criteria are generic and metric-agnostic; alternative divergence measures (e.g., Jensen–Shannon, Hellinger) could easily be substituted. 8.4

Conclusion Validity

Conclusion validity concerns the statistical soundness and reproducibility of the results. Our findings are based on over 7.3𝑀 experiments across a carefully designed parameter grid. Outlier filtering, validation/test splitting, and relative performance metrics were used to ensure robustness. However, we did not apply formal statistical hypothesis testing or confidence interval estimation, which could be considered in future work to further strengthen conclusions. Additionally, while we focused on relative performance comparisons, absolute performance could vary depending on backend availability, calibration profiles, and real-time load conditions. These factors should be taken into account when interpreting results in operational settings. 8.5

Summary

In summary, although our results are subject to the standard limitations of simulation-based evaluation and to the deliberate scope restriction to static, non-variational circuit executions, we have taken multiple steps to ensure fairness, reproducibility, and relevance of our conclusions. Future work will include validation on real quantum hardware, extensions to adaptive/variational workloads via mechanisms to handle non-stationary output distributions, and broader evaluation across additional circuit families and divergence measures. We also plan to study system-level considerations for integrating online stopping into cloud-based quantum runtimes, including the impact of batching, session semantics, and backend scheduling variability. 9

Conclusions and Future Work

In this paper, we investigated the following main research question: MRQ: Given a static, non-variational quantum circuit and a noisy quantum processing unit (QPU), is it possible to determine how many shots are sufficient to reach a required target accuracy? Our results provide a positive answer within the static execution scope considered here. Specifically, we showed that it is possible to determine a sufficient shot count online—without assumptions on circuit structure or backend noise models—by monitoring distributional stabilisation and stopping at the point of diminishing returns, i.e., when additional shots no longer produce statistically meaningful changes in the empirical output distribution. Central to our approach is the concept of the point of diminishing returns, which provides an observable stabilisation signal without requiring access to the unknown target distribution. To ground evaluation in a principled baseline, we further introduced the notion of a posteriori optimality, which retrospectively identifies the minimal prefix of an execution trace whose empirical distribution matches the best available estimate under the given budget. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

47

The primary objective of this paper was to establish and validate IncrementalExecution as a general-purpose solution within the scope of static circuit executions. Through an extensive empirical evaluation comprising over 7.3M experiments across 33,750 policy configurations and 180 circuit–backend pairs, our results indicate that: • Answer to the main research question: for static circuits, one can determine online a shot count that is sufficient to meet a user-defined stability/accuracy target by detecting distributional stabilisation and stopping at the observed point of diminishing returns, without requiring circuit- or noise-model assumptions. • Policy-driven flexibility for static circuits: IncrementalExecution can be configured to reach user-specified stability/accuracy targets across the evaluated execution traces, without relying on circuit-specific or backendspecific prior knowledge. This demonstrates that effective shot optimisation can be achieved in a black-box manner when the circuit remains fixed during execution. • Near-optimal online stopping: Compared to the a posteriori optimal baseline (which assumes access to the full execution history), the overhead incurred by online decision making is typically small, while achieving comparable distributional fidelity under the adopted divergence criterion. Our evaluation also highlights that there is no universally best configuration: optimal performance depends on properties of the executed circuit and backend (e.g., circuit size and output complexity). This suggests that systematic configuration and meta-optimisation can yield additional gains. As an initial step, we showed that circuit size provides a meaningful signal for guiding such tuning, and we anticipate that richer circuit descriptors could further improve configuration selection. Finally, we emphasise that the framework is not only conceptually principled but also practically deployable. Emerging support for session-based execution, reservation models, and hybrid runtimes across quantum cloud platforms makes online stopping strategies increasingly viable in operational settings, where reducing unnecessary shots can translate into tangible savings in time and cost. While the IncrementalExecution framework is, in principle, applicable to a broad class of stochastic sampling processes, quantum computing constitutes a domain in which its advantages are particularly pronounced. In this setting, shot budgets translate directly into monetary cost, wall-clock latency, and hardware contention, while oversampling cannot overcome accuracy plateaus induced by noise. As a result, the ability to detect the point of diminishing returns online is uniquely valuable for quantum workloads. In summary, although our methodology is formulated in general statistical terms, it is motivated by, and specifically tailored to, the practical constraints of quantum computing. By abstracting away circuit- and noise-specific assumptions, we offer a broadly applicable solution to a problem widely recognised as timely and important in the quantum computing literature: determining how many shots are sufficient. Looking ahead, several directions could further extend the scope and impact of IncrementalExecution: Beyond fixed-budget baselines. In this work, optimality is defined relative to a fixed budget B via the reference distribution 𝑃ˆB . A natural extension is to study a budget-less formulation, where the goal is to determine a stopping point without assuming an a priori maximum number of shots. Addressing this setting requires principled criteria for termination under uncertainty (e.g., confidence guarantees or asymptotic stabilisation tests), and we plan to investigate both theoretical and empirical solutions. Integration with complementary execution techniques. We currently consider executing a circuit on a single backend. Future work will embed IncrementalExecution into broader quantum workflow optimisations [15], including shot-wise distribution [11–14], circuit composition [7, 19, 38], and circuit cutting [8, 9, 42]. These integrations raise interesting questions about how stabilisation signals compose across distributed and decomposed Manuscript submitted to ACM

48

Bisicchia et al. executions. A particularly promising direction is the integration of IncrementalExecution with circuit cutting. Large circuits could be decomposed into smaller fragments whose output distributions are sampled independently. Since our current experiments already identify effective configurations for smaller static circuits, these configurations could serve as initial policies for fragment-level execution. IncrementalExecution would then determine, for each fragment, when additional shots no longer significantly improve the fragment distribution. The main open question is how fragment-level stabilisation errors compose during the reconstruction of the full-circuit observable or distribution. Studying the interaction between circuit cutting, fragment-wise shot optimisation, and reconstruction error therefore constitutes an interesting direction for scaling the approach to larger circuits. Learning-based policy design. We plan to develop learning-based strategies (e.g., reinforcement learning) to synthesise shot-allocation and stopping policies from data. Such approaches could move beyond static heuristics by conditioning decisions on circuit descriptors, observed stabilisation dynamics, and backend characteristics, learning policies that generalise across circuit families and execution environments. Validation on real quantum hardware. While our experiments use realistic noisy simulators, validating the framework on real devices is essential. Real hardware introduces additional factors, including queueing delays, calibration drift, transient failures, and runtime scheduling variability, that may affect both the stopping signal and the realised savings. Empirical evaluation under these conditions is a key next step. Automated hyperparameter tuning and configuration selection. Our results show that no single policy configuration is uniformly optimal across all circuit–backend pairs. Future work will therefore explore automated tuning and selection mechanisms, including Bayesian optimisation, evolutionary strategies, and AutoML techniques. By linking circuit properties (e.g., qubit count, depth, output sparsity) to effective hyperparameter settings, we aim to provide practical guidelines and tooling for deploying IncrementalExecution in real-world quantum software workflows. Extension to variational and adaptive workloads. A particularly important direction is extending IncrementalExecution to variational and other adaptive algorithms. Unlike the static setting studied here, these workloads induce non-stationary output distributions because the circuit changes across optimisation iterations. Supporting such settings will require additional mechanisms (e.g., phase-aware stopping rules, change-point detection, or iteration-coupled policies) to disentangle stabilisation from distributional shifts.

References [1] Amazon Braket Developer Guide. 2025. Working with reservations. https://docs.aws.amazon.com/braket/latest/developerguide/braket-reservations. html. [2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. 2019. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 (2019), 505–510. [3] AWS. 2025. Amazon Braket Pricing. https://aws.amazon.com/braket/pricing/. [4] Azure Quantum. 2025. Pricing Plans for Azure Quantum Providers. https://learn.microsoft.com/en-us/azure/quantum/pricing. [5] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. 2017. Quantum machine learning. Nature 549, 7671 (2017), 195–202. [6] Giuseppe Bisicchia. 2025. Quantum Incremental Execution Dataset. doi:10.5281/zenodo.15586358 [7] Giuseppe Bisicchia, Jaime Alvarado-Valiente, Javier Romero-Álvarez, Jose Garcia-Alonso, Juan M Murillo, and Antonio Brogi. 2025. Maximizing quantum hardware utilization via multiprogramming circuits and shot-wise distribution. Information and Software Technology (2025), 108005. [8] Giuseppe Bisicchia, Alessandro Bocci, José García-Alonso, Juan M Murillo, and Antonio Brogi. 2024. Cut&Shoot: Cutting & Distributing Quantum Circuits Across Multiple NISQ Computers. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 2. IEEE, 187–192. Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit?

49

[9] Giuseppe Bisicchia, Alessandro Bocci, Jose Garcia-Alonso, Juan M Murillo, and Antonio Brogi. 2026. Cut&Shoot: Distributed Execution of Quantum Circuit Fragments. IEEE Transactions on Quantum Engineering 7 (2026), 1–14. [10] Giuseppe Bisicchia, Alessandro Bocci, José García-Alonso, Juan M. Murillo, and Antonio Brogi. 2025. QSimBench: An Execution-Level Benchmark Suite for Quantum Software Engineering. In 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 02. 175–180. doi:10.1109/QCE65121.2025.10315 [11] Giuseppe Bisicchia, Giuseppe Clemente, José García-Alonso, Juan M Murillo, Massimo D’Elia, and Antonio Brogi. 2024. Distributing Quantum Computation Across Multiple NISQ Computers. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 2. IEEE, 442–443. [12] Giuseppe Bisicchia, Giuseppe Clemente, Jose Garcia-Alonso, Juan Manuel Murillo, Massimo D’Elia, and Antonio Brogi. 2025. Distributing quantum computations, shot-wise. Future Internet 17, 11 (2025), 507. [13] Giuseppe Bisicchia, José García-Alonso, Juan M Murillo, and Antonio Brogi. 2023. Dispatching shots among multiple quantum computers: An architectural proposal. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 2. IEEE, 195–198. [14] Giuseppe Bisicchia, Jose García-Alonso, Juan M Murillo, and Antonio Brogi. 2023. Distributing quantum computations, by shots. In International Conference on Service-Oriented Computing. Springer, 363–377. [15] Giuseppe Bisicchia, Jose García-Alonso, Juan M Murillo, and Antonio Brogi. 2024. From Quantum Software Handcrafting to Quantum Software Engineering. In 2024 IEEE International Conference on Software Analysis, Evolution and Reengineering-Companion (SANER-C). IEEE, 149–150. [16] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. 2013. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press. doi:10.1093/acprof:oso/9780199535255.001.0001 [17] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. 2021. Variational quantum algorithms. Nature Reviews Physics 3, 9 (2021), 625–644. [18] Jukka Corander, Ulpu Remes, and Timo Koski. 2021. On the Jensen–Shannon Divergence and the Variation Distance for Categorical Probability Distributions. Kybernetika 57, 6 (2021), 879–907. doi:10.14736/kyb-2021-6-0879 [19] Poulami Das et al. 2019. A case for multi-programming quantum computers. In IEEE/ACM MICRO. 291–303. [20] Ivan H Deutsch. 2020. Harnessing the power of the second quantum revolution. PRX Quantum 1, 2 (2020), 020101. [21] Paul Adrien Maurice Dirac. 1981. The principles of quantum mechanics. Number 27. Oxford university press. [22] QCS Documentation. 2025. QPU Reservations. https://docs.rigetti.com/qcs/guides/access-a-qpu/reserving-time-on-a-qpu. [23] Dominik M. Endres and Johannes E. Schindelin. 2003. A New Metric for Probability Distributions. IEEE Transactions on Information Theory 49, 7 (2003), 1858–1860. [24] Jose Garcia-Alonso, Enrique Moguel, Jaime Alvarado-Valiente, Javier Romero-Alvarez, Álvaro M. Aparicio-Morales, Juan M. Murillo, Francisco Javier Cavero, Adrián Romero-Flores, Alfonso E. Marquez-Chamorro, José Antonio Parejo, Antonio Ruiz-Cortés, Giuseppe Bisicchia, Alessandro Bocci, and Antonio Brogi. 2026. Rethinking Services in the Quantum Age: The SOQ Paradigm. ACM Trans. Softw. Eng. Methodol. (April 2026). doi:10.1145/3805807 [25] Alexander Gresch, Ugur Tepe, and Martin Kliesch. 2025. Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information. Journal of chemical theory and computation 21, 15 (2025), 7352–7359. [26] Andi Gu, Angus Lowe, Pavel A Dub, Patrick J Coles, and Andrew Arrasmith. 2021. Adaptive shot allocation for fast convergence in variational quantum algorithms. arXiv preprint arXiv:2108.10434 (2021). [27] Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American statistical association 58, 301 (1963), 13–30. [28] IonQ Quantum Cloud Documentation. 2025. Platform Systems. https://docs.ionq.com/user-manual/platform-systems. [29] Seyed Sajad Kahani and Amin Nobakhti. 2023. A novel framework for Shot number minimization in Quantum Variational Algorithms. arXiv preprint arXiv:2307.04035 (2023). [30] Youngmin Kim, Enhyeok Jang, Hyungseok Kim, Seungwoo Choi, Changhun Lee, Donghwi Kim, Woomin Kyoung, Kyujin Shin, and Won Woo Ro. 2024. Distribution-Adaptive Dynamic Shot Optimization for Variational Quantum Algorithms. arXiv preprint arXiv:2412.17485 (2024). [31] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio, and Patrick J Coles. 2020. An adaptive optimizer for measurement-frugal variational algorithms. Quantum 4 (2020), 263. [32] Senwei Liang, Linghua Zhu, Xiaolin Liu, Chao Yang, and Xiaosong Li. 2024. Artificial-intelligence-driven shot reduction in quantum measurement. Chemical Physics Reviews 5, 4 (2024). [33] Jay Mardia, Jiantao Jiao, Ervin TĂĄnczos, Robert D Nowak, and Tsachy Weissman. 2018. Concentration inequalities for the empirical distribution. arXiv preprint arXiv:1809.06522 (2018). [34] Karl Mayer and Charlie Baldwin. 2023. Estimating fidelity lower bounds of quantum subroutines. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 2. IEEE, 371–372. [35] Andriy Miranskyy. 2025. The Cost of Certainty: Shot Budgets in Quantum Program Testing. arXiv preprint arXiv:2510.22418 (2025). [36] Andriy Miranskyy, José Campos, Anila Mjeda, Lei Zhang, and Ignacio García Rodríguez de Guzmán. 2025. On the feasibility of quantum unit testing. arXiv preprint arXiv:2507.17235 (2025). [37] Michael A Nielsen and Isaac L Chuang. 2010. Quantum computation and quantum information. Cambridge university press. [38] Yasuhiro Ohkura et al. 2022. Simultaneous execution of quantum circuits on current and near-future NISQ systems. IEEE TQE 3 (2022), 1–10. Manuscript submitted to ACM

50

Bisicchia et al.

[39] Koustubh Phalak and Swaroop Ghosh. 2023. Shot optimization in quantum machine learning architectures to accelerate training. IEEE Access 11 (2023), 41514–41523. [40] IBM Quantum Documentation. 2025. Run jobs in a session. https://quantum.cloud.ibm.com/docs/en/guides/run-jobs-session. [41] Manav Seksaria and Anil Prabhakar. 2025. Shots and variance on noisy quantum circuits. arXiv preprint arXiv:2501.03194 (2025). [42] Wei Tang, Teague Tomesh, Martin Suchara, Jeffrey Larson, and Margaret Martonosi. 2021. Cutqc: using small quantum computers for large quantum circuit evaluations. In Proceedings of the 26th ACM International conference on architectural support for programming languages and operating systems. 473–486. [43] Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H Booth, et al. 2022. The variational quantum eigensolver: a review of methods and best practices. Physics Reports 986 (2022), 1–128. [44] Otto Veltheim and Esko Keski-Vakkuri. 2025. Optimizing quantum measurements by partitioning multisets of observables. Physical Review Letters 134, 3 (2025), 030801. [45] John Von Neumann. 2018. Mathematical foundations of quantum mechanics: New edition. Princeton university press. [46] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. 2003. Inequalities for the l1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep (2003), 125. [47] Claes Wohlin, Per Runeson, Martin Höst, Magnus C Ohlsson, Björn Regnell, Anders Wesslén, et al. 2012. Experimentation in software engineering. Vol. 236. Springer. [48] Man Zhang, Yuechen Li, Tao Yue, and Kai-Yuan Cai. 2025. Empirical Studies on Quantum Optimization for Software Engineering: A Systematic Analysis. arXiv preprint arXiv:2510.27113 (2025). [49] Jianjun Zhao. 2020. Quantum software engineering: Landscapes and horizons. arXiv preprint arXiv:2007.07047 (2020). [50] Linghua Zhu, Senwei Liang, Chao Yang, and Xiaosong Li. 2024. Optimizing shot assignment in variational quantum eigensolver measurement. Journal of Chemical Theory and Computation 20, 6 (2024), 2390–2403.

Manuscript submitted to ACM

How Many Shots Are Enough for a Quantum Circuit? A

51

Complete data comparison of incremental shots with Weissman and Hoeffding

This appendix section reports the complete per-trace tables underlying the best-configuration comparison discussed in Section 6.5. For each tolerance 𝛿 ∈ {0.05, 0.10, 0.25}, we list (i) the oracle shot budget, (ii) the shot budgets selected by IncrementalExecution using the best configuration for each divergence metric (Inc-TVD, Inc-Hell, Inc-JS), and (iii) the two a priori inequality baselines (Weissman and Hoeffding) at 95% confidence. As in the main text, the Weissman and Hoeffding values depend only on 𝛿 and the circuit size, and therefore remain constant within each (𝛿, size) group. For the sake of presentation, Tables 8–13 divide the test set traces by circuit sizes, small and large.

Manuscript submitted to ACM

52

Bisicchia et al. Table 8. Full sample comparison for 𝛿 = 0.05, all small circuits test traces.

Manuscript submitted to ACM

Trace

Size Oracle Inc-TVD Inc-Hell Inc-JS

Weissman

Hoeffding

dj_4_FEZ dj_4_FEZ dj_4_TOR dj_4_TOR dj_4_TOR qaoa_4_SHE qaoa_4_SHE qaoa_4_SHE qaoa_6_MAR qaoa_6_MAR qaoa_6_MAR qft_6_FEZ qft_6_FEZ qft_6_FEZ qft_6_TOR qft_6_TOR qft_6_TOR random_6_FEZ random_6_FEZ random_6_FEZ vqe_6_KYI vqe_6_KYI vqe_6_KYI dj_8_FEZ dj_8_FEZ dj_8_FEZ dj_8_MAR dj_8_MAR dj_8_MAR qaoa_8_KYI qaoa_8_KYI qaoa_8_KYI qaoa_8_SHE qaoa_8_SHE qaoa_8_SHE qft_8_FEZ qft_8_FEZ qft_8_FEZ qft_8_TOR qft_8_TOR qft_8_TOR qnn_8_FEZ qnn_8_FEZ qnn_8_FEZ qnn_8_KYI qnn_8_KYI qnn_8_KYI random_8_FEZ random_8_FEZ random_8_FEZ vqe_8_KYI vqe_8_KYI vqe_8_KYI

4 4 4 4 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

2818 2818 2818 2818 2818 2818 2818 2818 9472 9472 9472 9472 9472 9472 9472 9472 9472 9472 9472 9472 9472 9472 9472 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04 3.61𝑒 + 04

8.27𝑒 + 04 8.27𝑒 + 04 8.27𝑒 + 04 8.27𝑒 + 04 8.27𝑒 + 04 8.27𝑒 + 04 8.27𝑒 + 04 8.27𝑒 + 04 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 1.61𝑒 + 06 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07 3.03𝑒 + 07

100 150 50 300 550 300 1150 1600 1800 3000 3350 3450 3000 3600 4000 3500 4250 2250 2700 3600 150 1500 1550 250 3200 3850 350 3050 3600 5850 8100 9350 5350 7850 9400 8700 7800 9450 8450 7850 9450 7250 7450 9250 8200 7550 9200 7600 8100 9500 1000 5700 6700

550 550 550 550 550 1150 1150 1150 3850 3850 3850 4850 4850 4850 5350 5350 5350 4350 4350 4350 1350 1350 1350 1550 1550 1550 1250 1250 1250 6550 6550 6550 6350 6350 6350 9650 9650 9650 9850 9850 9850 8150 8150 8150 9550 9550 9550 8250 8250 8250 2450 2450 2450

2000 2000 2300 2300 2300 3700 3700 3700 6200 6200 6200 6400 6400 6400 6600 6600 6600 6100 6100 6100 4800 4800 4800 5100 5100 5100 6500 6500 6500 11200 11200 11200 12000 12000 12000 12500 12500 12500 11700 11700 11700 12100 12100 12100 11500 11500 11500 11500 11500 11500 8400 8400 8400

2000 2000 3000 3000 3000 3800 3800 3800 7300 7300 7300 7300 7300 7300 7900 7900 7900 7400 7400 7400 5300 5300 5300 6200 6200 6200 6500 6500 6500 14700 14700 14700 13900 13900 13900 13700 13700 13700 13900 13900 13900 13600 13600 13600 14100 14100 14100 14700 14700 14700 8400 8400 8400

How Many Shots Are Enough for a Quantum Circuit?

53

Table 9. Full sample comparison for 𝛿 = 0.05, all large circuits test traces. Trace

Size Oracle Inc-TVD Inc-Hell Inc-JS

Weissman

Hoeffding

dj_10_FEZ dj_10_FEZ dj_10_FEZ dj_10_TOR dj_10_TOR dj_10_TOR qaoa_10_SHE qaoa_10_SHE qaoa_10_SHE qaoa_12_MAR qaoa_12_MAR qaoa_12_MAR qft_12_FEZ qft_12_FEZ qft_12_FEZ qft_12_TOR qft_12_TOR qft_12_TOR random_12_FEZ random_12_FEZ random_12_FEZ vqe_12_KYI vqe_12_KYI vqe_12_KYI dj_14_FEZ dj_14_FEZ dj_14_FEZ dj_14_MAR dj_14_MAR dj_14_MAR qaoa_14_KYI qaoa_14_KYI qaoa_14_KYI qaoa_14_SHE qaoa_14_SHE qft_14_FEZ qft_14_FEZ qft_14_FEZ qft_14_TOR qft_14_TOR qnn_14_FEZ qnn_14_FEZ qnn_14_FEZ qnn_14_KYI qnn_14_KYI qnn_14_KYI random_14_FEZ random_14_FEZ random_14_FEZ vqe_14_KYI vqe_14_KYI vqe_14_KYI

10 10 10 10 10 10 10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14

1.43𝑒 + 05 1.43𝑒 + 05 1.43𝑒 + 05 1.43𝑒 + 05 1.43𝑒 + 05 1.43𝑒 + 05 1.43𝑒 + 05 1.43𝑒 + 05 1.43𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06 2.27𝑒 + 06

5.57𝑒 + 08 5.57𝑒 + 08 5.57𝑒 + 08 5.57𝑒 + 08 5.57𝑒 + 08 5.57𝑒 + 08 5.57𝑒 + 08 5.57𝑒 + 08 5.57𝑒 + 08 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.01𝑒 + 10 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11 1.80𝑒 + 11

500 6750 7750 1550 10050 10650 13800 15400 16350 14200 17550 17850 18650 18550 18900 18600 18550 18900 18550 18650 18950 3150 13400 14300 2200 12450 12850 2350 10050 10650 17550 19350 19400 17900 19500 18950 19750 19800 18950 19800 18950 19750 19800 18950 19750 19800 18950 19750 19800 8500 17050 17300

2550 2550 2550 3950 3950 3950 16650 16650 16650 15650 15650 15650 20000 20000 20000 20000 20000 20000 20000 20000 20000 5350 5350 5350 3950 3950 3950 3550 3550 3550 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 7750 7750 7750

5600 5600 5600 9000 9000 9000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 12400 12400 12400 13200 13200 13200 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000

9350 9350 9350 15250 15250 15250 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 19550 19550 19550 14350 14350 14350 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000

Manuscript submitted to ACM

54

Bisicchia et al. Table 10. Full sample comparison for 𝛿 = 0.10, all small circuits test traces.

Manuscript submitted to ACM

Trace

Size Oracle Inc-TVD Inc-Hell Inc-JS Weissman

Hoeffding

dj_4_FEZ dj_4_FEZ dj_4_TOR qaoa_4_SHE qaoa_4_SHE qaoa_4_SHE qaoa_6_MAR qaoa_6_MAR qaoa_6_MAR qft_6_FEZ qft_6_FEZ qft_6_FEZ qft_6_TOR qft_6_TOR qft_6_TOR random_6_FEZ random_6_FEZ random_6_FEZ vqe_6_KYI vqe_6_KYI dj_8_FEZ dj_8_FEZ dj_8_FEZ dj_8_MAR dj_8_MAR qaoa_8_KYI qaoa_8_KYI qaoa_8_KYI qaoa_8_SHE qaoa_8_SHE qaoa_8_SHE qft_8_FEZ qft_8_FEZ qft_8_FEZ qft_8_TOR qft_8_TOR qft_8_TOR qnn_8_FEZ qnn_8_FEZ qnn_8_FEZ qnn_8_KYI qnn_8_KYI qnn_8_KYI random_8_FEZ random_8_FEZ random_8_FEZ vqe_8_KYI vqe_8_KYI vqe_8_KYI

4 4 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

2.07𝑒 + 04 2.07𝑒 + 04 2.07𝑒 + 04 2.07𝑒 + 04 2.07𝑒 + 04 2.07𝑒 + 04 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 4.02𝑒 + 05 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06 7.56𝑒 + 06

50 100 50 150 350 400 650 1350 1500 1000 850 1050 850 800 1100 600 700 850 50 300 100 600 950 50 700 2000 3350 3950 1700 3350 3950 3300 2800 3850 3600 3000 3950 2550 2950 3750 3150 3100 3900 2750 3350 4150 200 750 950

150 150 150 150 150 150 1450 1450 1450 1750 1750 1750 2050 2050 2050 1700 1700 1700 150 150 550 550 550 150 150 2350 2350 2350 2300 2300 2300 3650 3650 3650 3500 3500 3500 3100 3100 3100 3550 3550 3550 3100 3100 3100 1100 1100 1100

700 700 550 1300 1300 1300 1950 1950 1950 1800 1800 1800 1950 1950 1950 1800 1800 1800 1450 1450 2300 2300 2300 1400 1400 4150 4150 4150 4150 4150 4150 3300 3300 3300 3350 3350 3350 3700 3700 3700 3500 3500 3500 3600 3600 3600 2700 2700 2700

700 700 500 900 900 900 2400 2400 2400 2500 2500 2500 2600 2600 2600 2600 2600 2600 1500 1500 1900 1900 1900 2000 2000 5400 5400 5400 4600 4600 4600 4900 4900 4900 4800 4800 4800 5000 5000 5000 4500 4500 4500 5300 5300 5300 2700 2700 2700

705 705 705 705 705 705 2368 2368 2368 2368 2368 2368 2368 2368 2368 2368 2368 2368 2368 2368 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023 9023

How Many Shots Are Enough for a Quantum Circuit?

55

Table 11. Full sample comparison for 𝛿 = 0.10, all large circuits test traces. Trace

Size Oracle Inc-TVD Inc-Hell Inc-JS

Weissman

Hoeffding

dj_10_FEZ dj_10_FEZ dj_10_FEZ dj_10_TOR dj_10_TOR dj_10_TOR qaoa_10_SHE qaoa_10_SHE qaoa_10_SHE qaoa_12_MAR qaoa_12_MAR qaoa_12_MAR qft_12_FEZ qft_12_FEZ qft_12_FEZ qft_12_TOR qft_12_TOR qft_12_TOR random_12_FEZ random_12_FEZ random_12_FEZ vqe_12_KYI vqe_12_KYI vqe_12_KYI dj_14_FEZ dj_14_FEZ dj_14_FEZ dj_14_MAR dj_14_MAR dj_14_MAR qaoa_14_KYI qaoa_14_KYI qaoa_14_KYI qaoa_14_SHE qaoa_14_SHE qaoa_14_SHE qft_14_FEZ qft_14_FEZ qft_14_FEZ qft_14_TOR qft_14_TOR qft_14_TOR qnn_14_FEZ qnn_14_FEZ qnn_14_FEZ qnn_14_KYI qnn_14_KYI qnn_14_KYI random_14_FEZ random_14_FEZ random_14_FEZ vqe_14_KYI vqe_14_KYI vqe_14_KYI

10 10 10 10 10 10 10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14

3.56𝑒 + 04 3.56𝑒 + 04 3.56𝑒 + 04 3.56𝑒 + 04 3.56𝑒 + 04 3.56𝑒 + 04 3.56𝑒 + 04 3.56𝑒 + 04 3.56𝑒 + 04 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 1.42𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05 5.68𝑒 + 05

1.39𝑒 + 08 1.39𝑒 + 08 1.39𝑒 + 08 1.39𝑒 + 08 1.39𝑒 + 08 1.39𝑒 + 08 1.39𝑒 + 08 1.39𝑒 + 08 1.39𝑒 + 08 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 2.52𝑒 + 09 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10 4.49𝑒 + 10

100 1600 1750 500 2400 2800 6550 9150 10300 7200 13250 13750 15400 15600 16450 15200 15550 16550 15200 15700 16600 550 5250 6200 500 4150 4700 600 3100 3750 13350 17400 17650 14350 17750 17950 17750 19050 19150 17750 19000 19100 17600 19000 19050 17700 19000 19100 17700 18950 19050 2600 11400 12050

1600 1600 1600 2200 2200 2200 9950 9950 9950 9000 9000 9000 17150 17150 17150 17200 17200 17200 17100 17100 17100 3400 3400 3400 2450 2450 2450 2300 2300 2300 13400 13400 13400 14600 14600 14600 17800 17800 17800 17750 17750 17750 17700 17700 17700 17750 17750 17750 17800 17800 17800 4500 4500 4500

3450 3450 3450 4450 4450 4450 9750 9750 9750 14950 14950 14950 18150 18150 18150 19350 19350 19350 19250 19250 19250 6150 6150 6150 4850 4850 4850 5150 5150 5150 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 11150 11150 11150

4200 4200 4200 4700 4700 4700 11000 11000 11000 15900 15900 15900 20000 20000 20000 20000 20000 20000 20000 20000 20000 7500 7500 7500 5200 5200 5200 6200 6200 6200 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 14000 14000 14000

Manuscript submitted to ACM

56

Bisicchia et al. Table 12. Full sample comparison for 𝛿 = 0.25, all small circuits test traces.

Manuscript submitted to ACM

Trace

Size Oracle Inc-TVD Inc-Hell Inc-JS Weissman

Hoeffding

dj_4_FEZ dj_4_TOR qaoa_4_SHE qaoa_6_MAR qaoa_6_MAR qft_6_FEZ qft_6_FEZ qft_6_TOR qft_6_TOR random_6_FEZ random_6_FEZ vqe_6_KYI dj_8_FEZ dj_8_MAR qaoa_8_KYI qaoa_8_KYI qaoa_8_KYI qaoa_8_SHE qaoa_8_SHE qaoa_8_SHE qft_8_FEZ qft_8_FEZ qft_8_FEZ qft_8_TOR qft_8_TOR qft_8_TOR qnn_8_FEZ qnn_8_FEZ qnn_8_FEZ qnn_8_KYI qnn_8_KYI qnn_8_KYI random_8_FEZ random_8_FEZ random_8_FEZ vqe_8_KYI vqe_8_KYI

4 4 4 6 6 6 6 6 6 6 6 6 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

3309 3309 3309 6.43𝑒 + 04 6.43𝑒 + 04 6.43𝑒 + 04 6.43𝑒 + 04 6.43𝑒 + 04 6.43𝑒 + 04 6.43𝑒 + 04 6.43𝑒 + 04 6.43𝑒 + 04 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06 1.21𝑒 + 06

50 50 50 100 150 250 300 200 250 150 250 50 50 50 300 700 850 350 600 750 650 800 900 650 750 900 500 750 900 650 750 900 550 800 950 50 150

100 100 250 300 300 500 500 500 500 400 400 150 150 100 550 550 550 500 500 500 850 850 850 850 850 850 700 700 700 800 800 800 700 700 700 200 200

150 200 400 350 350 450 450 500 500 400 400 250 250 300 750 750 750 850 850 850 850 850 850 1100 1100 1100 1050 1050 1050 1050 1050 1050 1000 1000 1000 500 500

250 250 250 450 450 750 750 750 750 650 650 250 250 250 850 850 850 850 850 850 1050 1050 1050 1050 1050 1050 950 950 950 1050 1050 1050 950 950 950 450 450

113 113 113 379 379 379 379 379 379 379 379 379 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444 1444

How Many Shots Are Enough for a Quantum Circuit?

57

Table 13. Full sample comparison for 𝛿 = 0.25, all large circuits test traces. Trace

Size Oracle Inc-TVD Inc-Hell Inc-JS

Weissman

Hoeffding

dj_10_FEZ dj_10_FEZ dj_10_TOR dj_10_TOR dj_10_TOR qaoa_10_SHE qaoa_10_SHE qaoa_10_SHE qaoa_12_MAR qaoa_12_MAR qaoa_12_MAR qft_12_FEZ qft_12_FEZ qft_12_FEZ qft_12_TOR qft_12_TOR qft_12_TOR random_12_FEZ random_12_FEZ random_12_FEZ vqe_12_KYI vqe_12_KYI vqe_12_KYI dj_14_FEZ dj_14_FEZ dj_14_FEZ dj_14_MAR dj_14_MAR dj_14_MAR qaoa_14_KYI qaoa_14_KYI qaoa_14_KYI qaoa_14_SHE qaoa_14_SHE qaoa_14_SHE qft_14_FEZ qft_14_FEZ qft_14_FEZ qft_14_TOR qft_14_TOR qft_14_TOR qnn_14_FEZ qnn_14_FEZ qnn_14_FEZ qnn_14_KYI qnn_14_KYI qnn_14_KYI random_14_FEZ random_14_FEZ random_14_FEZ vqe_14_KYI vqe_14_KYI vqe_14_KYI

10 10 10 10 10 10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14

5703 5703 5703 5703 5703 5703 5703 5703 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 2.27𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04 9.09𝑒 + 04

2.23𝑒 + 07 2.23𝑒 + 07 2.23𝑒 + 07 2.23𝑒 + 07 2.23𝑒 + 07 2.23𝑒 + 07 2.23𝑒 + 07 2.23𝑒 + 07 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 4.03𝑒 + 08 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09 7.19𝑒 + 09

50 100 50 250 300 1300 2400 2650 1500 3800 4250 6800 8400 9050 6650 8250 8950 6650 8450 9100 50 400 500 50 200 250 100 200 300 4700 8700 9350 5950 9750 10250 12700 15000 15300 12650 14950 15250 12100 14600 14950 12550 14900 15200 12500 14850 15150 450 1800 2100

300 300 1800 1800 1800 6900 6900 6900 6300 6300 6300 13300 13300 13300 13300 13300 13300 13100 13100 13100 2600 2600 2600 1900 1900 1900 1900 1900 1900 9100 9100 9100 10100 10100 10100 14200 14200 14200 14200 14200 14200 14100 14100 14100 14200 14200 14200 14300 14300 14300 3500 3500 3500

1200 1200 1700 1700 1700 3400 3400 3400 5000 5000 5000 9200 9200 9200 9500 9500 9500 9200 9200 9200 2400 2400 2400 1800 1800 1800 1800 1800 1800 8800 8800 8800 8200 8200 8200 17900 17900 17900 17800 17800 17800 17000 17000 17000 17700 17700 17700 17700 17700 17700 3400 3400 3400

1550 1550 1650 1650 1650 4100 4100 4100 5900 5900 5900 10100 10100 10100 9450 9450 9450 9900 9900 9900 3100 3100 3100 2250 2250 2250 2450 2450 2450 9200 9200 9200 10450 10450 10450 19350 19350 19350 18850 18850 18850 18400 18400 18400 19350 19350 19350 19100 19100 19100 3550 3550 3550

Received 20 February 2007; revised 12 March 2009; accepted 5 June 2009

Manuscript submitted to ACM

Related documents

• Experimental Settings in LLM-Based Program Repair: A Study of Inputs, Tool Access, Feedback, and Validation#965480
• A11yLTLNav: Automatic Detection of Accessibility Navigation Failures#965481
• Detecting Argument-Swap Bugs Using Context-Enhanced Code Representations#965482
• A Large-Scale Empirical Study of Quality Assurance Practices and Gaps in AI Agents#965483
• CARE: A Responsibility-Oriented Architecture for Domain-Scoped Resolution in Modular and Upgradeable Smart Contracts#965484