Optimal Tradeoffs for Estimating Pauli Observables
Sitan Chen, Weiyuan Gong, Qi Ye
Abstract
We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state, estimate Trfor some set of Pauli operatorsto 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 estimatefor allusingcopies, but withqubits of memory,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 onWhat is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subsetof Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up tofactors. •We show any protocol that makes poly-copy measure-ments must makemeasurements. •For any protocol that makes poly-copy measurements and only hasqubits of memory, we show thatcopies are necessary and sufficient. The protocols we propose can also estimate the actual values, 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
11 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Instance-Optimal Quantum State Certification with Entangled Measurements cites Exponential Separations Between Learning With and Without Quantum Memory
- Instance-Optimal Quantum State Certification with Entangled Measurements cites Entanglement is Necessary for Optimal Quantum Property Testing
- Instance-Optimal Quantum State Certification with Entangled Measurements cites Distributed Quantum inner product estimation
- Clifford Testing: Algorithms and Lower Bounds cites Exponential Separations Between Learning With and Without Quantum Memory
- Clifford Testing: Algorithms and Lower Bounds cites Entanglement is Necessary for Optimal Quantum Property Testing
- Clifford Testing: Algorithms and Lower Bounds cites Improved Stabilizer Estimation via Bell Difference Sampling
- Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation cites Exponential Separations Between Learning With and Without Quantum Memory
- Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation cites Improved Stabilizer Estimation via Bell Difference Sampling
- Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation cites Improved Quantum data analysis
- Exponential Separations Between Learning With and Without Quantum Memory cites Entanglement is Necessary for Optimal Quantum Property Testing
- Exponential Separations Between Learning With and Without Quantum Memory cites Improved Quantum data analysis
- Triply efficient shadow tomography cites Exponential Separations Between Learning With and Without Quantum Memory
- Triply efficient shadow tomography cites Improved Quantum data analysis
- Distributed Quantum inner product estimation cites Exponential Separations Between Learning With and Without Quantum Memory
- Distributed Quantum inner product estimation cites Entanglement is Necessary for Optimal Quantum Property Testing
- Distributed Quantum inner product estimation cites Improved Quantum data analysis
- Learning Stabilizer Structure of Quantum States cites Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation
- Learning Stabilizer Structure of Quantum States cites Triply efficient shadow tomography
- Learning Stabilizer Structure of Quantum States cites Improved Stabilizer Estimation via Bell Difference Sampling
- Improved Stabilizer Estimation via Bell Difference Sampling cites Improved Quantum data analysis
- Improved Quantum data analysis cites Entanglement is Necessary for Optimal Quantum Property Testing
Cited by top-tier papers11
- Instance-Optimal Quantum State Certification with Entangled MeasurementsRyan O'Donnell, Chirag WadhwaSTOC 2026 · 14 citations
- Triply efficient shadow tomographyRobbie King, David Gosset, Robin Kothari, Ryan BabbushSODA 2025 · 5 citations
- Learning Stabilizer Structure of Quantum StatesSrinivasan Arunachalam, Arkopal DuttSTOC 2026 · 5 citations
- Clifford Testing: Algorithms and Lower BoundsMarcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert et al.STOC 2026 · 4 citations
- Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic EstimationSitan Chen, Weiyuan Gong, Qi Ye, Zhihan ZhangSTOC 2025 · 4 citations
Builds on12
- Exponential Separations Between Learning With and Without Quantum MemorySitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry LiFOCS 2021 · 79 citations
- Improved Quantum data analysisCostin Badescu, Ryan O'DonnellSTOC 2021 · 40 citations
- Entanglement is Necessary for Optimal Quantum Property TestingSébastien Bubeck, Sitan Chen, Jerry LiFOCS 2020 · 33 citations
- Distributed Quantum inner product estimationAnurag Anshu, Zeph Landau, Yunchao LiuSTOC 2022 · 27 citations
- Improved Stabilizer Estimation via Bell Difference SamplingSabee Grewal, Vishnu Iyer, William Kretschmer, Daniel LiangSTOC 2024 · 20 citations
Related papers
- Pauli Measurements Are Not Optimal for Single-Copy TomographyJayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun YuSTOC 2025 · 1 citation
- Dimension Independent and Computationally Efficient Shadow TomographyPulkit SinhaSTOC 2025 · 1 citation
- An Optimal Tradeoff between Entanglement and Copy Complexity for State TomographySitan Chen, Jerry Li, Allen LiuSTOC 2024 · 9 citations
- Learning Distributions over Quantum Measurement OutcomesWeiyuan Gong, Scott AaronsonICML 2023 · 13 citations
- When Does Adaptivity Help for Quantum State Learning?Sitan Chen, Brice Huang, Jerry Li, Allen Liu et al.FOCS 2023 · 12 citations
