Verifiable blind observable estimation

Abstract

Cryptographic verification is essential for establishing trust in quantum-computing-as-a-service. However, a fundamental gap exists in the current verification landscape: existing efficient protocols are largely restricted to decision problems where correctness is boosted by classical majority voting. This excludes observable estimation, the statistical task underpinning nearly all near-term quantum advantage applications. For such tasks, current verification techniques face a prohibitive trade-off: either weak security guarantees or massive space overhead that exceeds the capacity of near-term hardware. To resolve this, we introduce the Secure Delegated Observable Estimation (SDOE) ideal resource, the first formal cryptographic framework for trustworthy expectation-value estimation within Abstract Cryptography. We then present the Verifiable Blind Observable Estimation (VBOE) protocol, which efficiently constructs this resource. VBOE circumvents the limitations inherent in prior methodologies by enabling the sequential collection of samples with negligible security error, requiring zero extra qubit overhead. By directly averaging computation rounds in classical post-processing, our protocol provides the only known path to rigorous, composable verification for the most common class of near-term quantum-classical hybrid algorithms. This work bridges foundational cryptographic theory with practical quantum tasks, enabling the certification of quantum utility on current and near-future devices.