Few Single-Qubit Measurements Suffice to Certify Any Quantum State
summary
Gives an algorithm that certifies any n‑qubit pure target state using linear number of copies and making quadratically many single-qubit measurements, distinguishing perfect fidelity from infidelity ≥ ε with 99% power. Core is a single‑copy subroutine that measures a random prefix in the computational basis, then uses a decision‑tree adaptive basis (built by induction so postselected subtrees become phase states) and an optimal single‑qubit test; repeating yields the linear sample complexity. Also proves an exponential lower bound for non‑adaptive product measurements and leaves constant‑tolerance and tighter copy bounds open.
AI-written summary · about
chapters (9)
- 0:00Introduction to certification
- 3:49Prior work and main results
- 9:29Algorithm structure and tree
- 14:25Decomposition lemma
- 22:17Designing the test
- 30:54Basis construction via induction
- 39:20Final algorithm and analysis
- 42:46Future work and adaptivity
- 46:10Q&A session
related talks
49mCertifying almost all quantum states with few single-qubit measurements
33mLightning Talks
42mTests for "Quantumness"
31mDemonstrating an Unconditional Separation Between Quantum and Classical Information Resources
01h 00mQuantum Physics for Software Developers
28mThe Problem with Qubits
45mClassical Verification of Quantum Computational Advantage
56mWhat is Your Logical Qubit?