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 · 2026
Read An Exponential Advantage for Adaptive Tomography of Structured States under Pauli Basis Measurements by Alireza Goldar, Zhen Qin, Zhihui Zhu, Zhe-Xuan Gong, Michael B. Wakin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26043.txt.
Introduction
Goldar and four colleagues pin down a setting where adaptive measurement genuinely beats fixed measurement in quantum state tomography. The setting is single-copy tomography of a structured state family under local Pauli measurements. They build a prefix-tree family for which adaptive choices need only polynomially many copies. Any fixed design needs exponentially many in the worst case. The adaptive gain comes from stagewise recovery guided by partial prefix matches. Fixed designs undersample some deep prefix and waste most of their budget telling apart hypotheses that look identical elsewhere.
Catalog record
| CREATOR | Alireza Goldar, Zhen Qin, Zhihui Zhu, Zhe-Xuan Gong, Michael B. Wakin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66598 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26043
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
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 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. 1 Introduction 1.1 Overview The efficiency of quantum state tomography (QST) generally scales poorly with system size, motivating several broad lines of work to reduce its complexity, including structured quantum state tomography, protocols with stronger measurement resources, adaptive measurement protocols, and broader approaches to quantum-state learning and prediction [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ] . However, a central lesson from this literature is that the usefulness of adaptivity depends strongly on the exact measurement setting and learning objective, meaning that broad claims of “adaptivity helps” or “adaptivity does not help” can often be misleading. In this paper, we identify a concrete measurement setting and quantum state state family in which adaptive measurement protocols provably changes the worst-case sample complexity scaling. Specifically, we demonstrate a rigorous exponential separation: for a structured family of multi-qubit states, an adaptive strategy achieves polynomial sample complexity, whereas every non-adaptive design requires exponentially many state copies. Crucially, this separation comes purely from sequential basis selection, without changing the underlying physical measurement architecture. To be precise, we study individual-copy quantum state tomography under local Pauli basis measurements. The allowed measurement settings are tensor-product Pauli bases built from the three single-qubit observables X , Y , and Z , yielding a set \mathcal{B}=\{X,Y,Z\}^{n} of 3^{n} possible settings. One experimental shot consists of choosing a basis b\in\mathcal{B} , measuring an unknown density matrix \rho on (\mathbb{C}^{2})^{\otimes n} , and observing an outcome o\in\{0,1\}^{n} . The resulting data are distributed according to Born’s rule as p(o\mid b,\rho)=\mathrm{Tr}\!\big(\Pi_{o}^{(b)}\rho\big) , where \Pi_{o}^{(b)} denotes the projector associated with outcome o under measurement setting b . Our success criterion is trace-distance accuracy with high probability in a minimax sense over a known, fixed family \mathcal{F} of density matrices. The separation is established over an explicit, structured “prefix/tree” family of states indexed by a hidden Pauli basis string. The key feature of this family is that information is distributed hierarchically across prefixes of the hidden string, rather than being concentrated entirely at the full length- n level. As a result, partial agreement between a measurement basis and the hidden string is already informative: matching a correct prefix reveals a corresponding prefix-level signal, even if the remaining suffix does not match. This creates a breadcrumb structure that can be exploited sequentially by an adaptive procedure, in contrast to a non-hierarchical single-spike setting where mismatched measurements reveal nothing. For this prefix/tree family, we prove two complementary results. First, we provide a constructive adaptive strategy that performs stagewise prefix recovery. At stage k , the procedure tests the three possible next Pauli symbols using a prefix statistic, yielding a polynomial copy complexity. Under our concrete parameterization, the adaptive procedure recovers the state up to trace distance \varepsilon using \widetilde{O}(n^{3}\varepsilon^{-2}) copies. Second, we prove that every non-adaptive design is exponentially costly. Any fixed non-adaptive allocation necessarily under-samples some long-prefix subset; by analyzing a hard two-point subproblem inside that subset, we show that non-adaptive strategies require an exponential \Omega\big(3^{n}\varepsilon^{-2}\log(1/\eta)\big) number of copies in the worst case to succeed with probability 1-\eta . Placing this result in context, our theorem isolates a regime where adaptivity fundamentally changes the worst-case sample complexity within a specific structured family. The prefix/tree family is primarily a proof-oriented construction designed to isolate a genuine limitation of non-adaptive local Pauli tomography. However, it connects naturally to broader themes in structured tomography [ 13 , 14 , 15 ] and to commuting-Pauli and stabilizer-type constructions, which play important roles in quantum error correction, measurement-based quantum computation, and many-body physics [ 16 , 17 , 18 , 19 ] . 1.2 Related Work One important line of work studies whether quantum states can be learned efficiently, both in broad quantum-learning formulations and in worst-case tomography under single-copy measurements [ 1 , 2 ] . In this direction, Chen et al. [ 5 ] showed that for general states, adaptivity does not improve the minimax sample complexity for trace-distance learning, though it can help for infidelity. By contrast, our work focuses on a structured family where adaptivity fundamentally changes the minimax trace-distance scaling, highlighting how strongly the utility of adaptivity depends on the underlying state family and measurement restrictions. A parallel line of research investigates the sometimes exponential improvements possible when the learner is granted stronger physical resources, such as quantum memory or entangled measurements among two or more state copies [ 6 , 7 , 8 , 9 ] . While these works show substantial gains under richer sensing models, our separation arises purely from sequential basis selection, with single-copy measurement in a local Pauli basis that is practical for current quantum hardware [ 4 , 20 ] . Within the Pauli-basis measurement framework, prior work has extensively explored observable estimation and identity testing, where the difficulty often stems from only a small subset of settings revealing the informative signal [ 10 , 9 ] . While philosophically similar, our objective is different: we aim for a minimax adaptive-versus-non-adaptive separation for state identification over a carefully designed structured family rather than observable estimation. From an algorithmic perspective, substantial work highlights the practical benefits of active learning and sequential design for empirical efficiency in tomography [ 21 , 22 , 23 , 15 ] . Our paper complements this literature by providing a rigorous theorem-level separation under a specific measurement restriction, rather than proposing an empirical heuristic. Our approach also connects to structured low-complexity tomography under local measurements, including tensor network-inspired and compressed sensing-based settings [ 24 , 25 , 26 , 13 , 14 ] , which show that exploiting structure fundamentally changes the learning problem. Although our structured family is introduced primarily as a discrete, proof-oriented construction, it can be represented in matrix product operator (MPO) form, providing a natural bridge to this literature and to the broader tensor-network