Measurement-Budget Allocation in Quantum Learning with Finite-Shot Generalization Guarantees
Organizations: Department of Electrical Engineering and Computer Science, University of Stavanger, Norway
Abstract
On near-term quantum hardware, estimating a Born probability requires repeated circuit executions. A quantum learning experiment with a fixed measurement budget must therefore decide how many distinct training states to use and how many shots to spend on each. We study this trade-off for binary quantum classifiers whose measurement operator is learned from the training data and evaluated with fresh measurement outcomes. We prove a distribution-free generalization bound for bounded, -Lipschitz losses with a sample term of order and a shot term of order ; under the two terms move in opposite directions. Minimizing a closed-form surrogate of the bound gives the allocation rule , , whose bound value is within 0.1% of the exact numerical minimum on all budgets we evaluate, and a worst-case rate of . PennyLane simulations with 2- and 4-qubit variational circuits on nine synthetic benchmarks show that the empirical gap stays below the bound in all configurations, although the bound is vacuous at the simulated budgets and becomes non-vacuous only for larger budgets (e.g., for ). For a loss that is concave in the score, the empirical gap is U-shaped under a fixed budget and the measured shot contribution matches its analytical value; for the absolute loss, shot noise is unbiased and no shot-limited regime appears. The rule can be used to plan finite-shot evaluations before an experiment is run.
Figures & tables
| Work | Method | Q1 | Q2 | Q3 |
|---|---|---|---|---|
| Caro et al. [ 10 ] | Covering numbers | |||
| Haug & Kim [ 11 ] | Quantum Fisher information | |||
| Huang et al. [ 13 ] | Information-theoretic | |||
| Gil-Fuster et al. [ 14 ] | Randomization tests | |||
| Bshouty & Jackson [ 15 ] | Quantum PAC | |||
| Berberich et al. [ 16 ] | Lipschitz bounds |
| Quantity | Symbol | Definition | Observable? |
|---|---|---|---|
| Population risk | No (requires the full distribution) | ||
| Ideal empirical risk | No (requires infinite shots) | ||
| Shot-estimated empirical risk | Yes |
| Property | Classical | Quantum (this work) |
|---|---|---|
| Score observation | Direct | binary shots (Born rule) |
| Sample error term | ||
| Shot error term | None | |
| Resources to plan | only | and |
| Surrogate budget-rate scaling |
| Excess (%) | ||||||
|---|---|---|---|---|---|---|
| 500 | 4 | 38.9 | 39.6 | 1.2007 | 1.2006 | 0.01 |
| 500 | 16 | 77.7 | 76.8 | 1.7314 | 1.7314 | 0.00 |
| 1000 | 4 | 53.2 | 55.2 | 1.0199 | 1.0197 | 0.02 |
| 1000 | 16 | 106.5 | 107.1 | 1.4694 | 1.4694 | 0.00 |
| 2000 | 4 | 73.1 | 76.8 | 0.8660 | 0.8657 | 0.03 |
| 2000 | 16 | 146.2 | 149.2 | 1.2468 | 1.2467 | 0.01 |
| Regime | Condition | Dominant term | Recommended action |
|---|---|---|---|
| Sample-limited | Increase , reduce | ||
| Balanced | Both comparable | Near-optimal; increase if further reduction needed | |
| Shot-limited | Decrease , increase |
| Dominant | Full | ||||||
|---|---|---|---|---|---|---|---|
| 500 | 4 | 39 | 12 | 0.641 | 0.579 | 1.220 | 1.437 ∗ |
| 500 | 16 | 78 | 6 | 0.906 | 0.853 | 1.759 | 1.913 ∗ |
| 1000 | 4 | 53 | 18 | 0.549 | 0.482 | 1.031 | 1.218 ∗ |
| 1000 | 16 | 106 | 9 | 0.777 | 0.709 | 1.486 | 1.618 ∗ |
| 2000 | 4 | 73 | 27 | 0.468 | 0.401 | 0.869 | 1.028 ∗ |
| 2000 | 16 | 146 | 13 | 0.662 | 0.600 | 1.262 | 1.375 ∗ |
| Datasets | Mean slope | Std. (across datasets) | |
| Theoretical reference slope: . | |||
| Bound | Gap | Slack | Ratio / reported | ||||
|---|---|---|---|---|---|---|---|
| 500 | 4 | 40 | 12 | 1.427 ∗ | 0.0203 | 1.4068 | / |
| 500 | 16 | 80 | 6 | 1.901 ∗ | 0.0102 | 1.8907 | / |
| 1000 | 4 | 55 | 18 | 1.205 ∗ | 0.0162 | 1.1890 | / |
| 1000 | 16 | 110 | 9 | 1.603 ∗ | 0.0061 | 1.5966 | / |
| 2000 | 4 | 75 | 26 | 1.028 ∗ | 0.0096 | 1.0181 | / |
| 2000 | 16 | 151 | 13 | 1.363 ∗ | 0.0047 | 1.3581 | / |
| Concave loss | Absolute loss | ||||
|---|---|---|---|---|---|
| gap at | shape | ||||
| 500 | 4 | 39 | 20 | 0.027 | decreasing |
| 1000 | 4 | 53 | 20 | 0.023 | decreasing |
| 2000 | 4 | 73 | 80 | 0.018 | decreasing |
| 500 | 16 | 78 | 10 | 0.017 | decreasing, then flat |
| 1000 | 16 | 106 | 20 | 0.012 | decreasing, then flat |
Quantum Machine Learning
Quantum machine learning uses quantum circuits and quantum data to build learning algorithms and study their computational and statistical limits.
See all 271 papers