L7-06 · Sample complexity and resource accounting
Separate copies, queries, gates, and total experimental cost.
Level 7 · Doctoral & postdoctoral
Objective. Separate copies, queries, gates, and total experimental cost.
Before this lesson. L7-04, L7-05
Hands-on lab. Chance and repeated trials
Learn¶
Sample complexity counts the observations needed for a stated accuracy and failure probability. Query complexity counts accesses to an oracle or process. Gate complexity counts circuit operations. Wall-clock cost also includes state preparation, reset, compilation, communication, and analysis. These quantities cannot be substituted without an access model.
For a bounded measurement mean, independent samples give a simple concentration bound. The bound can be conservative but it states a reproducible requirement. Correlated drift or adaptive stopping can invalidate an independence-based analysis. Declare those conditions before interpreting the calculated count.
A quantum advantage can concern one resource while increasing another. State whether the comparison counts classical samples, coherent queries, quantum memory, or compute time. A theoretical oracle model can be useful, but its assumptions must be visible beside any practical claim.
Practice¶
Solution
The bound gives N >= 50 ln(20), approximately 149.79. Use 150 independent shots. This does not count gate operations, state-preparation time, or the extra cost of estimating several observables.
Check your understanding¶
Which statement is correct about resource counts?
A. Queries, copies, and wall-clock time are interchangeable
B. A small shot count guarantees low total cost
C. Each count needs its own stated access and cost model
Show the answer
C. Each count needs its own stated access and cost model
Different resource measures describe different operations. An algorithm can save queries while spending more preparation or computation time, so the comparison must state its model.
Sources¶
This lesson draws on Liu et al., 2025Watrous, 2018Huang et al., 2021.
Next: L7-07 · Classical shadows and observable structure
- Liu, X., Qiu, Y., Dahlsten, O., & Vedral, V. (2025). Quantum Causal Inference with Extremely Light Touch. Npj Quantum Information, 11(1). 10.1038/s41534-024-00956-0
- Watrous, J. (2018). The Theory of Quantum Information. https://cs.uwaterloo.ca/~watrous/TQI/
- Huang, H.-Y., Broughton, M., Mohseni, M., Babbush, R., Boixo, S., Neven, H., & McClean, J. R. (2021). Power of data in quantum machine learning. Nature Communications, 12(1). 10.1038/s41467-021-22539-9