Lune

FOCS2024Top-tier venue

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ρ\rho, estimate Tr(Pρ)(P\rho)for some set of Pauli operatorsFFto within additive errorϵ\epsilon. 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ρ)\vert \text{Tr}(P\rho)for allPPusingO(n/ϵ4)O(n/\epsilon^{4})copies, but withk≤nk\leq nqubits of memory,Ω(2(n−k)/3)\Omega(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ϵ?\epsilon ?What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subsetAAof Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up tolog⁡∣A∣\log\vert A\vertfactors. •We show any protocol that makes poly(n)(n)-copy measure-ments must makeΩ(1/ϵ4)\Omega(1/\epsilon^{4})measurements. •For any protocol that makes poly(n)(n)-copy measurements and only hask<nk < nqubits of memory, we show thatΘ~(min⁡{2n/ϵ2,2n−k/ϵ4})\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})copies are necessary and sufficient. The protocols we propose can also estimate the actual valuesTr(Pρ)\text{Tr}(P\rho), 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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers11

  1. Instance-Optimal Quantum State Certification with Entangled MeasurementsRyan O'Donnell, Chirag WadhwaSTOC 2026 · 14 citations
  2. Triply efficient shadow tomographyRobbie King, David Gosset, Robin Kothari, Ryan BabbushSODA 2025 · 5 citations
  3. Learning Stabilizer Structure of Quantum StatesSrinivasan Arunachalam, Arkopal DuttSTOC 2026 · 5 citations
  4. Clifford Testing: Algorithms and Lower BoundsMarcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert et al.STOC 2026 · 4 citations
  5. Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic EstimationSitan Chen, Weiyuan Gong, Qi Ye, Zhihan ZhangSTOC 2025 · 4 citations

Builds on12

  1. Exponential Separations Between Learning With and Without Quantum MemorySitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry LiFOCS 2021 · 79 citations
  2. Improved Quantum data analysisCostin Badescu, Ryan O'DonnellSTOC 2021 · 40 citations
  3. Entanglement is Necessary for Optimal Quantum Property TestingSébastien Bubeck, Sitan Chen, Jerry LiFOCS 2020 · 33 citations
  4. Distributed Quantum inner product estimationAnurag Anshu, Zeph Landau, Yunchao LiuSTOC 2022 · 27 citations
  5. Improved Stabilizer Estimation via Bell Difference SamplingSabee Grewal, Vishnu Iyer, William Kretschmer, Daniel LiangSTOC 2024 · 20 citations

Related papers

  1. Pauli Measurements Are Not Optimal for Single-Copy TomographyJayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun YuSTOC 2025 · 1 citation
  2. Dimension Independent and Computationally Efficient Shadow TomographyPulkit SinhaSTOC 2025 · 1 citation
  3. An Optimal Tradeoff between Entanglement and Copy Complexity for State TomographySitan Chen, Jerry Li, Allen LiuSTOC 2024 · 9 citations
  4. Learning Distributions over Quantum Measurement OutcomesWeiyuan Gong, Scott AaronsonICML 2023 · 13 citations
  5. When Does Adaptivity Help for Quantum State Learning?Sitan Chen, Brice Huang, Jerry Li, Allen Liu et al.FOCS 2023 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines