Optimal tradeoffs for estimating Pauli observables

2024/04/29 by Sitan Chen, Chen, Sitan, Weiyuan Gong +3 · 17 citations
Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #Quantum chaos and dynamical systems

paper · pdf · doi:10.48550/arxiv.2404.19105

openalex publication_date 2024/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state ρ, estimate tr(Pρ) for some set of Pauli operators P to within additive error ε. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate |tr(Pρ)| for all P using O(n/ε⁴) copies, but with k≤ n qubits of memory, Ω(2^(n-k)/3) copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on ε? What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions. For any subset A of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to log |A| factors. We show any protocol that makes poly(n)-copy measurements must make Ω(1/ε⁴) measurements. For any protocol that makes poly(n)-copy measurements and only has k < n qubits of memory, we show that \widetildeΘ(min\2ⁿ/ε², 2^n-k/ε⁴\) copies are necessary and sufficient. The protocols we propose can also estimate the actual values tr(Pρ), rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.

Cited by

• Optimal Distributed Similarity Estimation of Quantum Channels
• Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs
• Product testing with single-copy measurements
• An infinite hierarchy of multi-copy quantum learning tasks
• Clifford testing: algorithms and lower bounds
• Learning stabilizer structure of quantum states
• Efficient learning of bosonic Gaussian unitaries
• On the Limitations of Pseudorandom Unitaries
• Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States
• Distributed Quantum Property Testing with Communication Constraints
• Universal Sample Complexity Bounds in Quantum Learning Theory via Fisher Information Matrix
• Duality of extremal quantum states in verification and data hiding
• Adversarially robust quantum state learning and testing
• One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency
• Instance-Optimal Quantum State Certification with Entangled Measurements
• Improved Classical Shadow Tomography Using Quantum Computation
• Quantum Advantage for Sensing Properties of Classical Fields

Related

• Pauli measurements are not optimal for single-copy tomography
• Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
• One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency
• Sample efficient tomography via Pauli Measurements
• Efficient sampling for Pauli-measurement-based shadow tomography in direct fidelity estimation