Structure-aware quantum overlapping tomography: minimal measurement families for geometric, symmetry-constrained, and nonlocal-observable targets

Quantum overlapping tomography (QOT) determines all $k$ -qubit reduced density matrices of an $n$ -qubit state using at most $e^{\mathcal{O}(k)}\log^2(n)$ rounds of parallel single-qubit measurements, organized by $(n,k)$ perfect hash families, while treating the $n$ qubits as an unstructured set. The source paper (Cotler and Wilczek, 2020) explicitly poses its adaptation to structured physical settings as open: (i) geometry-aware measurement families that reconstruct all $k$ -qubit marginals on subsystems of bounded diameter $d$ on a lattice described by a weighted graph $G$ , of minimal size; (ii) systematic exploitation of symmetries and selection rules to streamline the protocol; (iii) prioritization of local correlations when long-range correlations are negligible; and (iv) modifications targeting special nonlocal observables, such as stringlike order parameters for topological order.

Background

Full quantum state tomography of an $n$ -qubit system is infeasible at scale: a generic density matrix contains $4^n-1$ real parameters, so reconstructing it requires resources exponential in $n$ . Many physical questions, however, need only local information — expectation values of few-body observables, pairwise entanglement, or correlation functions — all of which are encoded in the $k$ -qubit reduced density matrices (k-RDMs), obtained by tracing out all but $k$ qubits of the state.

Cotler and Wilczek's quantum overlapping tomography (QOT) addresses exactly this task. The experimental primitive is a parallel product measurement: in one round, every qubit is measured individually in one of the Pauli bases $X$ , $Y$ , or $Z$ ; a measurement setting is the global choice of one single-qubit basis per qubit. A $k$ -RDM is determined once all $3^k$ combinations of single-qubit Pauli bases have been sampled for the $k$ qubits involved. QOT organizes settings using an $(n,k)$ perfect hash family: a collection of functions $f:[n]\to[k]$ such that every $k$ -element subset of the $n$ qubits is mapped injectively by at least one function. Each hash function partitions the qubits into groups so that many $k$ -subsets are separated simultaneously; across $e^{\mathcal{O}(k)}\log(n)$ distinct settings every $k$ -subset is fully covered, and with repetitions for statistical accuracy all k-RDMs are obtained in at most $e^{\mathcal{O}(k)}\log^2(n)$ rounds — for example, all two-qubit entanglement of a 1000-qubit system within days.

QOT treats the $n$ qubits as unstructured, but the systems it targets — atoms in optical lattices, superconducting qubits on chips — are structured: they have geometry (a lattice with a metric), symmetries and selection rules (translation invariance, spin rotation, conserved quantities), predominantly local correlations, and physically relevant nonlocal observables. Prominent among the latter are string order parameters: products of single-site operators along a spatial path, which diagnose topological order (ordering beyond the Landau symmetry-breaking paradigm, arising e.g. in quantum spin liquids) and symmetry-protected phases. The adjacent classical shadows framework (random single-qubit measurements plus a median-of-means estimator, 'Predicting many properties of a quantum system from very few measurements', Nature Physics (2020)) predicts properties of a state from few samples, but it does not optimize the number of parallel product-measurement settings for a structured target class, which is the combinatorial core of QOT.

In its closing section, the source paper lists the structured extensions as open. The lattice question is concrete: given an $n$ -qubit state on a geometry described by a weighted graph $G$ and a distance cutoff $d$ , measure all k-RDMs on subsystems whose pairwise graph distance is at most $d$ ; this requires a geometry-aware generalization of $(n,k)$ perfect hash families carrying the data $(G,d)$ , of minimal size. Later work reformulated this in graph-theoretic terms: the target subsystems define a connectivity graph (or, for $k>2$ , a connectivity hypergraph $H$ whose hyperedges are the target subsets), and constructions are governed by its chromatic number $\chi$ (the minimum number of colors needed to color vertices so that adjacent vertices, or vertices sharing a hyperedge, differ) and by covering arrays from combinatorial design theory (arrays of symbols such that every small set of columns realizes all symbol combinations, which ensure informational coverage of all target marginals).

Problem Statement

Under the common objective of structure-aware, resource-minimal overlapping tomography, construct explicit parallel product-measurement schedules — each setting assigning one single-qubit measurement basis per qubit — that determine the relevant marginals or observables of an $n$ -qubit state, together with a size analysis (number of distinct settings, and repetitions for target accuracy $\epsilon$ ) and lower bounds or optimality where claimed, for the following structured target classes from the source question:

(1) Geometry-aware families. For a weighted graph $G$ describing the qubit layout and a distance cutoff $d$ — equivalently, a connectivity graph or hypergraph $H$ of target subsystems — construct measurement families covering all $k$ -subsets of diameter at most $d$ , of minimal size, or within a stated constant factor of minimal. Settled cases that an answer need not redo: nearest-neighbor two-body tomography of planar systems (nine Pauli settings, optimal); $k$ -body tomography with $3^k$ Pauli settings when the chromatic number of $H$ is at most $k+1$ ; $3^k$ general projective settings for all $k$ -body marginals. Still open: minimal families for arbitrary geometries — general weighted graphs $G$ with arbitrary distance cutoff $d$ , non-lattice connectivities, and $k>2$ beyond the chromatic-number cases above — and whether chromatic-number-based (colouring) constructions are ever non-minimal for connectivity graphs.

(2) Symmetry-exploiting QOT. Given that the state obeys known symmetries or selection rules (e.g., permutation, translation, or conserved quantities), systematically incorporate these constraints into the QOT construction so as to provably reduce the number of measurement settings or simplify postprocessing, without assuming structure beyond the stated symmetry class.

(3) Nonlocal-observable QOT. Modify the QOT construction to efficiently measure structured classes of nonlocal observables — in particular stringlike products (order parameters for topological order) — with a quantified number of settings and accuracy guarantees.

The three target classes are independent, each posed as a separate target: for each, a construction and its setting count are sought with the coverage property that every target marginal or observable is reconstructible from the recorded settings under the parallel single-qubit product-measurement model.

References

Jordan Cotler and Frank Wilczek, 'Quantum Overlapping Tomography', Physical Review Letters 124, 100401 (2020), DOI: 10.1103/PhysRevLett.124.100401, arXiv:1908.02754, https://arxiv.org/abs/1908.02754
Bruna G. M. Araújo, Márcio M. Taddei, Daniel Cavalcanti, Antonio Acín, 'Local quantum overlapping tomography', Physical Review A 106, 062441 (2022), DOI: 10.1103/PhysRevA.106.062441, arXiv:2112.03924, https://arxiv.org/abs/2112.03924
Kiara Hansenne, Rui Qu, Lisa T. Weinbrenner, Carlos de Gois, Haifei Wang, Yang Ming, Zhengning Yang, Paweł Horodecki, Weibo Gao, Otfried Gühne, 'Optimal Overlapping Tomography', Physical Review Letters 135, 060801 (2025), DOI: 10.1103/t6qb-kdcp, arXiv:2408.05730, https://arxiv.org/abs/2408.05730
Chao Wei, Kada Yang, Liangyu Che, Feng Xu, Junda Song, Tao Xin, 'Optimal quantum overlapping tomography: Theory and experiment', Physical Review Applied 24, 044091 (2025), DOI: 10.1103/z2d4-3r8z, arXiv:2410.13473, https://arxiv.org/abs/2410.13473
Shuowei Ma, Qianfan Wang, Lvzhou Li, Fei Shi, 'Optimal qudit overlapping tomography and optimal measurement order', arXiv:2601.10059 (2026), https://arxiv.org/abs/2601.10059
Zhengning Yang, Shihao Ru, Lianzhen Cao, Nikolay Zheludev, Weibo Gao, 'Experimental demonstration of Quantum Overlapping Tomography', Physical Review Letters 130, 050804 (2023), DOI: 10.1103/PhysRevLett.130.050804, arXiv:2207.14488, https://arxiv.org/abs/2207.14488
Zherui Jerry Wang, David Dechant, Yash J. Patel, Jordi Tura, 'Mitigating shot noise in local overlapping quantum tomography with semidefinite programming', Physical Review A 111, 052444 (2025), DOI: 10.1103/PhysRevA.111.052444, arXiv:2501.18546, https://arxiv.org/abs/2501.18546
Nengkun Yu, 'Sample efficient tomography via Pauli Measurements', arXiv:2009.04610 (2020), https://arxiv.org/abs/2009.04610
Andrew Zhao, Akimasa Miyake, 'Group-theoretic error mitigation enabled by classical shadows and symmetries', npj Quantum Information 10, 57 (2024), DOI: 10.1038/s41534-024-00854-5, arXiv:2310.03071, https://arxiv.org/abs/2310.03071
Hsin-Yuan Huang, Richard Kueng, John Preskill, 'Predicting many properties of a quantum system from very few measurements', Nature Physics 16, 1050-1057 (2020), DOI: 10.1038/s41567-020-0932-7, arXiv:2002.08953, https://arxiv.org/abs/2002.08953
Haifei Wang, Rui Qu, Zhengning Yang, Xiaodan Lyu, Haotao Zhu, Zitong Xu, Lianzhen Cao, Joel Yang, Otfried Gühne, Weibo Gao, 'Experimental High-Dimensional Quantum Overlapping Tomography', arXiv:2608.15795 (2026), https://arxiv.org/abs/2608.15795