Quantum Algorithms for the Mean Estimation Problem
summary
Classical and quantum-sample models both require O(σ/√N) samples for one-dimensional mean estimation, but with quantum circuit (black-box) access model the dependence improves to linear in N rather than √N, an optimal quantum advantage. Algorithms combine phase estimation, quantum counting, amplitude amplification with statistical tools like trimmed estimators to handle outliers, though heavy-tailed variances remain delicate. Related concrete results: finding many hash-collision pairs needs more queries if quantum memory is small, and Raz’s parity-learning shows exponential sample blowup for limited classical memory; quantum-memory versions stay open.
AI-written summary · about
chapters (6)
related talks
01h 06mQuantum Algorithms for Approximating Partition Functions
01h 09mRecent Progress in Quantum Advantage
19mAvenues for Quantum Error Correction and Mitigation
44mQuantum machine learning: Prospects and challenges
20mThe Quantum Supremacy Tsirelson Inequality
22mSecurity of Quantum Machine Learning Systems
33mSpoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
48mStatistics In Quantum Computational Supremacy