pith. machine review for the scientific record. sign in

arxiv: 2604.26043 · v1 · submitted 2026-04-28 · 🪐 quant-ph

Recognition: unknown

An Exponential Advantage for Adaptive Tomography of Structured States under Pauli Basis Measurements

Alireza Goldar , Zhen Qin , Zhihui Zhu , Zhe-Xuan Gong , Michael B. Wakin
Authors on Pith no claims yet

Pith reviewed 2026-05-07 16:22 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum state tomographyadaptive measurementsPauli basisstructured statescopy complexitytrace distancequantum informationminimax estimation
0
0 comments X

The pith

Adaptive local Pauli measurements recover a family of tree-structured quantum states with polynomially many copies while any non-adaptive choice of measurements requires exponentially many.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an explicit discrete family of quantum states organized by a prefix or tree structure. For states in this family, choosing the next local Pauli measurement adaptively, based on earlier outcomes, permits accurate reconstruction using only polynomially many copies in the number of qubits. Any strategy that must select all measurement settings in advance, without using outcome information, requires an exponential number of copies to guarantee success across the entire family. This isolates a concrete regime in which adaptivity changes the scaling of sample complexity for quantum state tomography when measurements are restricted to tensor-product Pauli operators and performance is measured by trace distance.

Core claim

There exists a discrete prefix/tree family of states such that adaptive selection of tensor-product Pauli measurements achieves polynomial copy complexity for high-probability trace-distance recovery in a minimax sense over the family, while every non-adaptive design requires exponentially many copies in the worst case. The adaptive upper bound is obtained by stagewise prefix recovery that uses hierarchical breadcrumb information revealed by partial prefix matches. The non-adaptive lower bound follows from a rare-prefix mechanism: every fixed design under-samples some deep prefix subset, and outside that subset the competing hypotheses induce identical one-shot measurement laws, so only anex

What carries the argument

The prefix/tree family of states, which permits hierarchical stagewise recovery from partial prefix matches under adaptive Pauli measurements but forces any fixed design to under-sample critical subsets.

If this is right

  • For quantum states known to lie in this structured family, adaptive protocols can reduce the required number of experimental runs from exponential to polynomial in system size.
  • Local Pauli measurements, which are experimentally common, can exhibit exponential sample-complexity gaps between adaptive and non-adaptive designs when the state has hierarchical structure.
  • The scaling of tomography depends on whether the measurement choice can depend on previous outcomes for states with prefix-like organization.
  • Practical quantum state estimation on devices should incorporate adaptive feedback when the target state is promised to have known tree or prefix structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Analogous exponential separations may appear for other families of structured states or under different error metrics such as fidelity.
  • The result motivates construction of adaptive algorithms that exploit hierarchical structure in quantum learning tasks beyond exact membership in the given family.
  • Approximate versions of the family or noisy measurement settings could be studied to test whether the polynomial-versus-exponential gap survives small perturbations.

Load-bearing premise

The unknown state is guaranteed to belong to the known structured prefix or tree family.

What would settle it

Finding even one fixed, non-adaptive collection of local Pauli measurement settings that achieves polynomial copy complexity for every state in the constructed family would falsify the exponential lower bound.

Figures

Figures reproduced from arXiv: 2604.26043 by Alireza Goldar, Michael B. Wakin, Zhen Qin, Zhe-Xuan Gong, Zhihui Zhu.

Figure 1
Figure 1. Figure 1: Required adaptive budget for the LLR-based view at source ↗
Figure 2
Figure 2. Figure 2: Required non-adaptive budget for the LLR view at source ↗
Figure 3
Figure 3. Figure 3: Direct comparison of adaptive and non-adaptive view at source ↗
read the original abstract

Broad claims about whether adaptivity helps in quantum state tomography can be misleading unless the state family, measurement architecture, and error metric are specified carefully. We study a restricted but physically important regime: single-copy quantum state tomography under local Pauli basis measurements, where the allowed measurement settings are tensor-product measurement operators built from local single-qubit Pauli operators, and performance is measured in trace distance with high probability in a minimax sense over a known structured family. We construct an explicit discrete prefix/tree family of states for which adaptive measurement selection achieves polynomial copy complexity, while every non-adaptive design requires exponentially many copies in the worst case. The adaptive upper bound comes from stagewise prefix recovery using hierarchical breadcrumb information revealed by partial prefix matches. The non-adaptive lower bound is based on a rare-prefix mechanism: every fixed design under-samples some deep prefix subset, and outside that subset the competing hypotheses induce identical one-shot laws, so only an exponentially small fraction of the measurement budget contributes to the KL divergence between the full data distributions. The result isolates a concrete regime in which adaptivity provably changes the sample-complexity scaling under the experimentally common local Pauli measurement architecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper constructs an explicit discrete prefix/tree family of quantum states and shows that, under tensor-product local Pauli basis measurements, an adaptive strategy achieves polynomial copy complexity for high-probability minimax trace-distance tomography over the family, while every non-adaptive design requires exponentially many copies in the worst case. The adaptive upper bound proceeds via stagewise hierarchical prefix recovery using partial-match breadcrumb information; the non-adaptive lower bound uses a rare-prefix argument in which any fixed design under-samples some deep branch, with competing hypotheses outside that branch inducing identical one-shot distributions and thus contributing only an exponentially small total KL divergence.

Significance. If the bounds hold, the result isolates a concrete, physically relevant regime (local Pauli measurements on a known structured family) in which adaptivity provably changes the sample-complexity scaling from exponential to polynomial. The explicit state construction and reliance on standard information-theoretic tools (KL divergence, minimax high-probability analysis) make the separation rigorous and falsifiable. This contributes to the literature on adaptive quantum tomography by providing a clear, non-asymptotic example rather than a generic claim.

major comments (2)
  1. [Adaptive upper bound (hierarchical recovery)] The stagewise prefix-recovery argument claims polynomial copy complexity with high-probability trace-distance guarantee, but the error-probability calculations for partial prefix matches and the accumulation of breadcrumb information across stages are not fully detailed in the provided text; these calculations are load-bearing for the polynomial upper bound.
  2. [Non-adaptive lower bound (rare-prefix mechanism)] The rare-prefix lower-bound mechanism asserts that only an exponentially small fraction of any fixed measurement budget contributes to the KL divergence because competing hypotheses induce identical one-shot laws outside the under-sampled subset. An explicit calculation verifying this identical-distribution property for the tree-family states (and the resulting exponential smallness of the total KL) is required to confirm the exponential separation.
minor comments (2)
  1. [State family definition] Define the discrete prefix/tree family with a small concrete example (e.g., depth-3 tree) at the beginning of the construction section to aid readability.
  2. [Main theorems] Clarify the precise minimax high-probability statement (including the failure probability scaling with the family size) in the theorem statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments, which help strengthen the presentation of our explicit separation between adaptive and non-adaptive local Pauli tomography. We address each major comment below and will incorporate the requested details into the revised manuscript.

read point-by-point responses

  1. Referee: The stagewise prefix-recovery argument claims polynomial copy complexity with high-probability trace-distance guarantee, but the error-probability calculations for partial prefix matches and the accumulation of breadcrumb information across stages are not fully detailed in the provided text; these calculations are load-bearing for the polynomial upper bound.

    Authors: We agree that the error-probability analysis for partial matches and breadcrumb accumulation requires fuller expansion to make the polynomial upper bound fully rigorous. In the revision we will add explicit bounds in the adaptive strategy section: at each stage k the probability of an incorrect partial-prefix decision is at most exp(-Ω(m_k)) where m_k is the number of copies allocated to that stage, and we will show via a union bound over the O(log n) stages together with the reduction in hypothesis space provided by prior breadcrumbs that the total failure probability remains exponentially small while the total copy count stays polynomial in n. The revised text will include the precise constants and the inductive argument on how breadcrumb information propagates. revision: yes

  2. Referee: The rare-prefix lower-bound mechanism asserts that only an exponentially small fraction of any fixed measurement budget contributes to the KL divergence because competing hypotheses induce identical one-shot laws outside the under-sampled subset. An explicit calculation verifying this identical-distribution property for the tree-family states (and the resulting exponential smallness of the total KL) is required to confirm the exponential separation.

    Authors: We acknowledge that the manuscript currently sketches rather than fully expands the identical-distribution claim. In the revision we will add a dedicated lemma (with proof) showing that any two states in the family whose differing branches lie outside the support of a fixed non-adaptive measurement design have identical one-shot Pauli measurement distributions on all qubits not in the rare prefix; this follows directly from the tensor-product structure of both the states and the measurements. Consequently the total KL divergence between the full data distributions is bounded by the KL contribution from the exponentially small fraction of measurements that hit the under-sampled prefix, yielding the exponential lower bound via standard change-of-measure arguments. The explicit fraction and the resulting KL bound will be stated with all constants. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses explicit construction and standard information theory

full rationale

The paper defines an explicit discrete prefix/tree family of states and derives the adaptive polynomial upper bound via stagewise hierarchical recovery from partial prefix matches, while the non-adaptive exponential lower bound follows from showing that any fixed measurement design under-samples deep prefixes and yields identical one-shot distributions (hence exponentially small total KL divergence) for competing hypotheses outside the rare subset. Both directions are direct consequences of the problem definition, the local Pauli measurement model, and the minimax high-probability trace-distance guarantee; no step reduces by construction to a fitted parameter, self-referential definition, or load-bearing self-citation. The argument is internally consistent and self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the mathematical construction of the prefix/tree state family and standard assumptions from quantum information theory; no free parameters are introduced and the invented family is a proof artifact rather than a physical postulate.

axioms (2)
  • standard math Quantum states are represented by density operators and measurements yield probability distributions according to the Born rule
    Invoked implicitly when discussing one-shot laws and KL divergence between measurement distributions.
  • domain assumption Performance is quantified by trace distance with high-probability minimax guarantees over the state family
    Explicitly stated as the error metric and success criterion in the abstract.
invented entities (1)
  • Discrete prefix/tree family of states no independent evidence
    purpose: To exhibit the exponential adaptive advantage
    Constructed specifically for the proof; no independent physical evidence is provided outside the mathematical construction.

pith-pipeline@v0.9.0 · 5514 in / 1503 out tokens · 111603 ms · 2026-05-07T16:22:45.900272+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Measuring the largest coefficients of a quantum state

    quant-ph 2026-05 unverdicted novelty 7.0

    A hierarchical prefix-tree algorithm identifies the dominant Pauli coefficients of sparse quantum states using Bell sampling on two copies, with sample-complexity bounds tied to the number of coefficients and state purity.

Reference graph

Works this paper leans on

30 extracted references · 19 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    The learnability of quan- tum states

    Scott Aaronson. “The learnability of quan- tum states”. Proceedings of the Royal So- ciety A: Mathematical, Physical and En- gineering Sciences 463, 3089–3114 (2007). arXiv:quant-ph/0608142

    work page arXiv 2007

  2. [2]

    Anshu and S

    Anurag Anshu and Srinivasan Arunachalam. “Asurveyonthecomplexityoflearningquan- tum states”. Nature Reviews Physics6, 59– 69 (2024). arXiv:2305.20069

    work page arXiv 2024

  3. [3]

    Quantum certification and bench- marking

    Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. “Quantum certification and bench- marking”. Nature Reviews Physics2, 382– 390 (2020). arXiv:1910.06343

    work page arXiv 2020

  4. [4]

    Huang, R

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. “Predicting many proper- ties of a quantum system from very few measurements”. Nature Physics16, 1050– 1057 (2020). arXiv:2002.08953

    work page arXiv 2020

  5. [5]

    When does adap- tivity help for quantum state learning?

    Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. “When does adap- tivity help for quantum state learning?”. In Proceedings of the 64th IEEE Annual Sym- posium on Foundations of Computer Sci- ence (FOCS). Pages 391–404. (2023). arXiv:2206.05265

    work page arXiv 2023

  6. [6]

    Quantum advantage in learn- ing from experiments

    Hsin-Yuan Huang, Michael Broughton, Jor- dan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. “Quantum advantage in learn- ing from experiments”. Science376, 1182– 1186 (2022)

    2022

  7. [7]

    Exponential sepa- rations between learning with and without quantum memory

    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. “Exponential sepa- rations between learning with and without quantum memory”. In Proceedings of the 62nd IEEE Annual Symposium on Founda- tions of Computer Science (FOCS). (2021). arXiv:2111.05881

    work page arXiv 2021

  8. [8]

    Efficient pauli channel estimation with logarithmic quantum memory

    Sitan Chen and Wenjun Gong. “Efficient pauli channel estimation with logarithmic quantum memory”. PRX Quantum 6, 020323 (2025)

    2025

  9. [9]

    Optimal tradeoffs for estimating pauli ob- servables

    Sitan Chen, Wenjun Gong, and Qisheng Ye. “Optimal tradeoffs for estimating pauli ob- servables”. In Proceedings of the 65th IEEE Annual Symposium on Foundations of Com- puter Science (FOCS). Pages 1086–1105. (2024). arXiv:2404.19105

    work page arXiv 2024

  10. [10]

    Almost tight sample complex- ity analysis of quantum identity testing by pauli measurements

    Nengkun Yu. “Almost tight sample complex- ity analysis of quantum identity testing by pauli measurements”. IEEE Transactions on Information Theory69, 5060–5068 (2023)

    2023

  11. [11]

    Pauli error estimation via population recov- ery

    Steven T. Flammia and Ryan O’Donnell. “Pauli error estimation via population recov- ery”. Quantum5, 549 (2021)

    2021

  12. [12]

    Online learning of quantum states

    Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. “Online learning of quantum states”. Journal of Sta- tistical Mechanics: Theory and Experiment 2019, 124019 (2019). arXiv:1802.09025

    work page arXiv 2019

  13. [13]

    Optimal quantum state tomog- raphy with local informationally complete measurements

    Casey Jameson, Zhen Qin, Alireza Goldar, Michael B. Wakin, Zhihui Zhu, and Zhe- Xuan Gong. “Optimal quantum state tomog- raphy with local informationally complete measurements” (2024). arXiv:2408.07115

    work page arXiv 2024

  14. [14]

    Nearly tight bounds for testing tree tensor network states

    Benjamin Lovitz and Angus Lowe. “Nearly tight bounds for testing tree tensor network states” (2024). arXiv:2410.21417

    work page arXiv 2024

  15. [15]

    Adaptive quan- tum state tomography with active learning

    Hannah Lange, Matjaž Kebrič, Maximilian Buser, Ulrich Schollwöck, Fabian Grusdt, and Annabelle Bohrdt. “Adaptive quan- tum state tomography with active learning”. Quantum7, 1129 (2023)

    2023

  16. [16]

    Doped stabilizer states in many-body physics and where to find them

    Andi Gu, Salvatore F. E. Oliviero, and Lorenzo Leone. “Doped stabilizer states in many-body physics and where to find them”. Physical Review A110, 062427 (2024)

    2024

  17. [17]

    Stabilizer Codes and Quantum Error Correction

    Daniel Gottesman. “Stabilizer codes and quantum error correction”. PhD thesis. Cal- ifornia Institute of Technology. (1997). arXiv:quant-ph/9705052

    work page internal anchor Pith review arXiv 1997

  18. [18]

    A one-way quantum computer

    Robert Raussendorf and Hans J. Briegel. “A one-way quantum computer”. Physical Re- view Letters86, 5188–5191 (2001)

    2001

  19. [19]

    Fault-tolerant quantum computation by anyons

    A. Yu. Kitaev. “Fault-tolerant quantum com- putation by anyons”. Annals of Physics303, 2–30 (2003). arXiv:quant-ph/9707021

    work page Pith review arXiv 2003

  20. [20]

    Quantum Computing in the NISQ era and beyond.Quantum, 2:79, August 2018

    John Preskill. “Quantum computing in the NISQ era and beyond”. Quantum 2, 79 (2018). arXiv:1801.00862

    work page internal anchor Pith review arXiv 2018

  21. [21]

    Adaptive bayesian quantum tomography

    Ferenc Huszár and Neil M. T. Houlsby. “Adaptive bayesian quantum tomography”. Physical Review A85, 052120 (2012)

    2012

  22. [22]

    Adap- tive quantum state tomography improves ac- 17 curacy quadratically

    Dylan H. Mahler, Lee A. Rozema, Ardavan Darabi, Christopher Ferrie, Robin Blume- Kohout, and Aephraim M. Steinberg. “Adap- tive quantum state tomography improves ac- 17 curacy quadratically”. Physical Review Let- ters111, 183601 (2013)

    2013

  23. [23]

    Practical adaptive quantum tomography

    Christopher Granade, Christopher Ferrie, and Steven T. Flammia. “Practical adaptive quantum tomography”. New Journal of Physics 19, 113017 (2017). arXiv:1605.05039

    work page arXiv 2017

  24. [24]

    Efficient quantum state tomography

    Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon- Cardinal, David Poulin, and Yi-Kai Liu. “Efficient quantum state tomography”. Nature Communications 1, 149 (2010). arXiv:1101.4366

    work page arXiv 2010

  25. [25]

    Quantum state tomography via compressed sensing

    David Gross, Yi-Kai Liu, Steven T. Flam- mia, Stephen Becker, and Jens Eisert. “Quantum state tomography via compressed sensing”. Physical Review Letters 105, 150401 (2010). arXiv:0909.3304

    work page arXiv 2010

  26. [26]

    Quantum tomogra- phy via compressed sensing: Error bounds, sample complexity, and efficient estimators

    Steven T. Flammia, David Gross, Yi-Kai Liu, and Jens Eisert. “Quantum tomogra- phy via compressed sensing: Error bounds, sample complexity, and efficient estimators”. New Journal of Physics14, 095022 (2012). arXiv:1205.2300

    work page arXiv 2012

  27. [27]

    Matrix product density operators: Simulation of finite-temperature and dissipative systems

    Frank Verstraete, Juan J. Garcia-Ripoll, and J. Ignacio Cirac. “Matrix product density operators: Simulation of finite-temperature and dissipative systems”. Physical Review Letters93, 207204 (2004)

    2004

  28. [28]

    Sample-optimal tomography of quantum states

    Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. “Sample-optimal tomography of quantum states”. IEEE Transactions on Information Theory 63, 5628–5641 (2017). arXiv:1508.01797

    work page arXiv 2017

  29. [29]

    O’Donnell and J

    Ryan O’Donnell and John Wright. “Efficient quantum tomography”. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Pages 899–912. STOC ’16. Association for Computing Ma- chinery (2016). arXiv:1508.01907

    work page arXiv 2016

  30. [30]

    Probability inequalities forsumsofboundedrandomvariables

    Wassily Hoeffding. “Probability inequalities forsumsofboundedrandomvariables”. Jour- nal of the American Statistical Association 58, 13–30 (1963). 18

    1963