Run-length certificates in quantum learning: sample complexity and noise thresholds

Abstract

Quantum learning from state samples is often benchmarked in a fixed-budget paradigm, relating error to a prescribed number of copies. We instead adopt a stopping-time viewpoint: in minimal-feedback learning, the learning completion can be defined by an online run-length certificate extracted from a one-bit-per-copy record. As an instantiation, we analyze single-shot measurement learning (SSML), introduced in [Phys. Rev. A 98, 052302 (2018)] and [Phys. Rev. Lett. 126, 170504 (2021)], which tunes a unitary and halts after $M_H$ consecutive successes. Viewing the halting as a sequential certification linking the observed counter to infidelity, we derive sample-complexity bounds that separate search (driving success probability toward unity) from certification (run statistics of consecutive successes). The resulting trade-off among $M_H$, dimension $d$, and one-bit reliability clarifies when performance is control-limited versus certificate-limited. With label-flip noise probability $q$, we find a sharp feasibility threshold: once $q{M}_H\gtrsim 1$, the expected halting time grows exponentially, making the learning completion impractical even under ideal control. More broadly, this shows that under severely constrained feedback, the certification can dominate sample complexity and small label noise becomes the information bottleneck. Finally, the near-optimal accuracy enabled by run-length certification aligns with the quantum-state-estimation (and equivalently, no-cloning) limits, expressed in the stopping-time terms.

19 pages, 3 figures

References in corpus (12)

• On the Measurement of Qubits
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Adaptive Bayesian Quantum Tomography
• Practical Bayesian Tomography
• Separable Measurement Estimation of Density Matrices and its Fidelity Gap with Collective Protocols
• Learning quantum states and unitaries of bounded gate complexity
• Learning unknown pure quantum states
• Experimental Learning of Pure Quantum States using Sequential Single-Shot Measurement Outcomes
• Reinforcement learning to learn quantum states for Heisenberg scaling accuracy
• Ensuring superior learning outcomes and data security for authorized learner