Optimal Quantum State Testing Even with Limited Entanglement

arXiv:2604.07460 · quant-ph, cs.DS · Submitted 2026-04-08 · Read on arXiv

quant-ph, cs.DS

Submitted: 2026-04-08

Updated: 2026-09-24

Terminology

• Trace — 40× in this paper · explained in 2 episodes
• Entanglement — 18× in this paper · explained in 3 episodes
• Foundations of Computer Science — 4× in this paper
• Shadow Tomography — 4× in this paper · explained in 4 episodes
• Trace Distance — 4× in this paper · explained in 3 episodes
• Fidelity — 3× in this paper · explained in 2 episodes
• Accuracy — 2× in this paper · explained in 1 episode
• Annual ACM-SIAM Symposium on Discrete Algorithms — 2× in this paper
• Adaptive Algorithm — 1× in this paper · explained in 1 episode
• Adaptivity — 1× in this paper · explained in 1 episode
• Calibration — 1× in this paper · explained in 7 episodes
• Distillation — 1× in this paper · explained in 2 episodes
• Generalization — 1× in this paper · explained in 13 episodes
• Sample Complexity — 1× in this paper · explained in 15 episodes

Sources

• Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
• A Hierarchy for Replica Quantum Advantage
• Optimal high-precision shadow estimation
• The Power of Two Bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements
• Non-iid hypothesis testing: from classical to quantum
• Distributed Quantum Property Testing with Communication Constraints
• Nearly Time-Optimal Pure State Tomography with Pauli Measurements
• Few Single-Qubit Measurements Suffice to Certify Any Quantum State
• On the sample complexity of purity and inner product estimation
• Random purification channel made simple
• Random Stinespring superchannel: converting channel queries into dilation isometry queries
• The Church of the Symmetric Subspace
• Quantum state testing with restricted measurements
• Optimal learning of quantum channels in diamond distance
• Random purification channel for passive Gaussian bosons
• An infinite hierarchy of multi-copy quantum learning tasks
• Instance-Optimal Quantum State Certification with Entangled Measurements
• Mixed state tomography reduces to pure state tomography
• The debiased Keyl's algorithm: a new unbiased estimator for full state tomography
• Conjugate queries can help

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity