REVIEW 2 major objections 3 minor 3 cited by
Quantum Overlapping Tomography
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read All $k$-qubit reduced density matrices of an $n$-qubit state can be recovered from $e^{\mathcal{O}(k)} \log^2(n)$ rounds of parallel measurements.
desk verdict The overlapping tomography idea is sound and genuinely useful, but the reconstruction formulas as written miss the 1/2^k Pauli normalization; that is a one-line fix, not a fatal flaw. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is an $(n,k)$ family of perfect hash functions: a set of functions from the $n$ qubits to $k$ colors such that every $k$-qubit subset is assigned all distinct colors by at least one function in the set. The QOT protocol runs one full block of $3^k$ parallel Pauli-basis measurements for each function, repeated $M$ times, so the round for a separating function yields complete tomographic data for every $k$-qubit subsystem it separates. For $k=2$, the family is the binary-digit coloring of qubit indices: $f_i(j)$ is the $i$-th bit of $j-1$, giving $\lceil\log_2 n\rceil$ functions and an explicit total of $3M+6M\lceil\log_2 n\rceil$ measurement rounds.
What would settle it
A numerical simulation of the $k=2$ protocol for $n=256,512,1024$ with known true two-qubit marginals would settle the practical scaling claim: using the paper's repetition counts, all reconstructed expectation values should be within $\varepsilon=0.05$ with about 97% probability, and the total number of rounds should grow only like $\log^2 n$. If success rates fall substantially below that, or the round count must rise faster than $\log^2 n$, the central claim is refuted.
Extended reading notes
Core claim
The central discovery is that overlapping measurements are an advantage rather than an obstacle. Using an $(n,k)$ family of perfect hash functions—functions $f:[n]\to[k]$ in which every $k$-element subset is injectively colored by at least one function—the protocol colors all qubits by each hash function, performs all $3^k$ Pauli-basis assignments on the color classes, and repeats $M$ times. Whenever a particular $k$-qubit subsystem receives distinct colors under one hash function, the data from that function's round is a complete $k$-qubit tomography of that subsystem; because every $k$-subset is separated by some function in the family, all reduced density matrices are recovered. The paper proves the round count $e^{\mathcal{O}(k)} \log^2(n)$, gives the explicit $k=2$ construction based on binary digits of the qubit indices, and notes that the procedure adapts to qudits and to $(n,t,k)$ hash families.
Load-bearing premise
The load-bearing premise is that every measurement round can address all $n$ qubits at once, each in an independently chosen single-qubit basis, and that fresh identical copies of the same state can be prepared for every round.
Editorial extensions
If this is right
- For fixed $k$, the number of measurement rounds is polylogarithmic in $n$, so $k$-body correlations in systems of thousands of qubits become experimentally accessible.
- Complete pairwise entanglement characterization of a 1024-qubit state requires about 1,000,800 rounds; at 250 ms per round this is about three days of data taking.
- Only product measurements are needed—each qubit is measured in its own Pauli basis—so the protocol does not rely on entangled or non-demolition measurements.
- The reconstructed marginals supply the inputs needed for entanglement measures, $k$-local Hamiltonian expectation values, and the quantum marginal problem.
- The method adapts to qudits and to $(n,t,k)$ perfect hash families, giving flexibility to trade color count against round count.
Reading between the lines
- A practical cross-check follows from the overlap structure: when several hash functions separate the same $k$-qubit subsystem, the reconstructed marginals are independent estimates of the same object, so their agreement gives a noise diagnostic the paper does not develop.
- For lattice systems, the same idea can be specialized from all $k$-subsets to geometrically local subsets; the paper sketches a checkerboard example for nearest-neighbor pairs, and the general graph-coloring formulation with its round-count tradeoffs remains open.
- The constant in $e^{\mathcal{O}(k)}$ and the repetition factor $M$ could be improved in practice by using balanced hash families, which spread the separating functions evenly and allow the number of repetitions to be divided by the multiplicity $T$; the paper notes the construction but leaves implementation choices open.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces Quantum Overlapping Tomography (QOT), a protocol for determining all k-qubit reduced density matrices of an n-qubit state using only product measurements. The key idea is to use (n,k) perfect hash families to assign the n qubits to k 'colors' in multiple rounds, so that every k-qubit subset is separated by at least one coloring. Each coloring yields all k-site Pauli correlations for the subsystems whose qubits receive distinct colors, and the data from different colorings are combined to reconstruct every reduced density matrix. With N = e^{O(k)} log n hash functions and M repetitions per setting, the total number of parallel measurement rounds is claimed to be e^{O(k)} log^2(n). A concrete protocol is given for k=2, together with an experimental estimate for n=1024 qubits claiming that all pairwise reduced density matrices can be characterized in about three days.
Significance. If correct, QOT would improve the measurement complexity of determining all k-body reduced density matrices from the naive e^{O(k)} n^k to polylogarithmic in n for fixed k, using only parallel single-qubit measurements that are already available in cold-atom and ion-trap platforms. The core combinatorial insight is sound, the k=2 protocol is explicit and checkable, and the paper provides a concrete experimental scenario with quantitative estimates. The asymptotic scaling argument is essentially correct in spirit, and the claimed n-dependence is right. However, the reconstruction equations omit the Pauli normalization and the derivation of the hash-family size contains a reversed inequality; both are correctable but make the present text not literally correct.
major comments (2)
- [Section II, Eqs. (1) and (4); Section IV, Eq. (8)] The Pauli expansion as written omits the factor 1/2^k. Because tr(σ_a σ_b) = 2^k δ_{a,b}, the correct expansion is ρ = 2^{-k} Σ tr((⊗σ)ρ) ⊗σ. As written, Eq. (8) reconstructs 2^k ρ_rs; for the maximally mixed two-qubit state it returns I⊗I instead of I/4. Since Section VI feeds these matrices into entanglement-of-formation formulas, the protocol as stated would compute entanglement measures of an unnormalized operator. The fix is a one-line normalization and does not affect the round count, but it is required for the central claim that QOT determines the reduced density matrices.
- [Section III, Eqs. (5)-(6)] The inequality direction is reversed. The probability (n choose k)(1 - k!/k^k)^N decreases as N increases, so condition (5) requires N to be at least roughly e^{O(k)}(k log n + log(1/δ)), not at most that quantity. The sentence 'N needs to be at most' does not follow from (5). The intended conclusion—that there exists a perfect hash family of size O(e^{O(k)} log n)—is true and is supported by the cited literature, but it should be derived either by the standard probabilistic-method expectation argument (expected number of bad subsets less than 1) or by direct reference to [12-25]. The present derivation is therefore not logically sound as written.
minor comments (3)
- [Section IV, Step 2.j] The bullet list under Step 2.j says '9 measurements' but contains only six settings; the subsequent count uses 6M, so this is a typographical error.
- [Section VI, experimental estimate] For n=1024, q=10, and M=16,000, the formula 3M + 6Mq gives 1,008,000 rounds, not 1,000,800 as stated. The discrepancy does not change the 'a few days' conclusion, since both values correspond to roughly 70 hours at 250 ms per round.
- [Appendix, Eq. (11)] The event in the union bound should be 'there exists an i' (or 'for some i'), not 'for all i'. The union bound is applied correctly in spirit, but the displayed event is misstated.
Circularity Check
No significant circularity: the QOT sampling bound is derived from external perfect-hash-family bounds and a standard concentration inequality, not from the target result.
full rationale
The paper's central claim, that all k-qubit reduced density matrices can be determined in e^{O(k)} log^2(n) rounds, follows from two independent ingredients: (i) the size of an (n,k) perfect-hash family, bounded probabilistically in Eq. (6) and supplied by external references [12-25], and (ii) the repetition count M ~ k log(n)/epsilon^2 from the Chernoff-Hoeffding inequality and a union bound in the Appendix, Eq. (13). Neither ingredient is defined in terms of the log^2(n) round count, and neither is fitted to the final claim. The k=2 protocol in Section IV reconstructs each two-qubit reduced density matrix from directly measured Pauli expectation values via Eq. (8); any missing normalization in Eq. (8) is a correctness defect, not a circularity, because the reconstruction formula is not equivalent to the claimed round bound by construction. The paper does not rely on self-citation: the cited perfect-hash-family constructions and concentration results are external, and no load-bearing step reduces to a prior result by the same authors. Thus the derivation is self-contained rather than circular.
Assumptions & free parameters
assumptions (5)
- standard math Chernoff-Hoeffding inequality as stated in Eq. (9)
- standard math Existence and efficient construction of (n,k) families of perfect hash functions of size e^{O(k)} log n
- standard math Pauli expansion of a k-qubit density matrix, rho = (1/2^k) sum tr(P rho) P
- domain assumption Many identical copies of the unknown n-qubit state can be prepared, and all qubits can be measured in parallel in chosen single-qubit bases
- domain assumption Per-qubit measurement fault probability Delta satisfies k Delta = O(1)
Cite this review
Pith. "Pith review of Quantum Overlapping Tomography." pith.science (2026). https://pith.science/paper/XU6C3H7L
@misc{pith2026190802754,
author = {Pith},
title = {Pith review of: Quantum Overlapping Tomography},
year = {2026},
howpublished = {\url{https://pith.science/paper/XU6C3H7L}},
note = {Machine review of arXiv:1908.02754}
}
abstract
It is now experimentally possible to entangle thousands of qubits, and efficiently measure each qubit in parallel in a distinct basis. To fully characterize an unknown entangled state of $n$ qubits, one requires an exponential number of measurements in $n$, which is experimentally unfeasible even for modest system sizes. By leveraging (i) that single-qubit measurements can be made in parallel, and (ii) the theory of perfect hash families, we show that all $k$-qubit reduced density matrices of an $n$ qubit state can be determined with at most $e^{\mathcal{O}(k)} \log^2(n)$ rounds of parallel measurements. We provide concrete measurement protocols which realize this bound. As an example, we argue that with current experiments, the entanglement between every pair of qubits in a system of 1000 qubits could be measured and completely characterized in a few days. This corresponds to completely characterizing entanglement of nearly half a million pairs of qubits.
Figures
Forward citations
Cited by 3 Pith papers
-
Optimal estimation of high-dimensional quantum states using locally gentle measurements
α-gentle tomography of rank-r qudits has minimax Frobenius rate Θ(rd²/(nα²)), with gentleness penalty scaling as ambient dimension d rather than parameter count rd.
-
Locally Gentle State Certification for High Dimensional Quantum Systems
Locally α-gentle quantum state certification against the maximally mixed state has minimax sample complexity Θ(d^3/(ε^2 α^2)) for fixed unentangled measurements, a factor d/α^2 over the non-gentle rate.
-
Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
All elements of a qubit k-RDM can be measured with O(3^k log^{k-1} N) circuits, and all elements of a fermionic 2-RDM with O(N^2) circuits, matching a new Ω(N^2) lower bound for Clifford measurements.
Reference graph
Works this paper leans on
-
[1]
Ladd, Thaddeus D., et al. “Quantum computers.” Nature 464.7285 (2010): 45
work page 2010
-
[2]
Scaling the ion trap quantum processor
Monroe, Christopher, and Jungsang Kim. “Scaling the ion trap quantum processor.” Science 339.6124 (2013): 1164-1169
work page 2013
-
[3]
Super- conducting circuits for quantum information: an out- look
Devoret, Michel H., and Robert J. Schoelkopf. “Super- conducting circuits for quantum information: an out- look.” Science 339.6124 (2013): 1169-1174
work page 2013
-
[4]
Quantum spintronics: en- gineering and manipulating atom-like spins in semicon- ductors
Awschalom, David D., et al. “Quantum spintronics: en- gineering and manipulating atom-like spins in semicon- ductors.” Science 339.6124 (2013): 1174-1179
work page 2013
-
[5]
Probing many-body dynam- ics on a 51-atom quantum simulator
Bernien, Hannes, et al. “Probing many-body dynam- ics on a 51-atom quantum simulator.” Nature 551.7682 (2017): 579
work page 2017
-
[6]
10-qubit entanglement and parallel logic operations with a superconducting circuit
Song, Chao, et al. “10-qubit entanglement and parallel logic operations with a superconducting circuit.”Physical Review Letters 119.18 (2017): 180511
work page 2017
-
[7]
O’Donnell, Ryan, and John Wright. “Efficient quan- tum tomography.” Proceedings of the forty-eighth annual ACM symposium on Theory of Computing . ACM, 2016
work page 2016
-
[8]
Sample-optimal tomography of quantum states
Haah, Jeongwan, et al. “Sample-optimal tomography of quantum states.” IEEE Transactions on Information Theory 63.9 (2017): 5628-5641
work page 2017
Show all 52 references
-
[9]
Efficient quantum state tomog- raphy
Cramer, Marcus, et al. “Efficient quantum state tomog- raphy.” Nature Communications 1 (2010): 149
2010
-
[10]
Efficient tomography of a quantum many-body system
Lanyon, B. P., et al. “Efficient tomography of a quantum many-body system.” Nature Physics 13.12 (2017): 1158
2017
-
[11]
Shadow tomography of quantum states
Aaronson, Scott. “Shadow tomography of quantum states.” Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing . ACM, 2018
2018
-
[12]
Data Structures and Algorithms. 1. Sorting and Searching
Mehlhorn, Kurt. “Data Structures and Algorithms. 1. Sorting and Searching.” Springer-Verlag, Berlin (1984)
1984
-
[13]
Storing a sparse table with O(1) access time
Fredman, Michael L., J´ anos Koml´ os and Endre Sze- mer´ edi, “Storing a sparse table with O(1) access time.” Journal of the Association for Computing Machinery 31 (1984): 538-544. 7
1984
-
[14]
On the size of separating systems and families of perfect hash func- tions
Fredman, Michael L., and J´ anos Koml´ os. “On the size of separating systems and families of perfect hash func- tions.” SIAM Journal on Algebraic Discrete Methods 5.1 (1984): 61-68
1984
-
[15]
Explicit construction of exponential sized families of k-independent sets
Alon, Noga. “Explicit construction of exponential sized families of k-independent sets.” Discrete Mathematics 58.2 (1986): 191-193
1986
-
[16]
New bounds for per- fect hashing via information theory
Korner, J., and Katalin Marton. “New bounds for per- fect hashing via information theory.” European Journal of Combinatorics 9.6 (1988): 523-530
1988
-
[17]
The spatial com- plexity of oblivious k-probe hash functions
Schmidt, Jeanette P., and Alan Siegel. “The spatial com- plexity of oblivious k-probe hash functions.” SIAM Jour- nal on Computing 19.5 (1990): 775-786
1990
-
[18]
Color- coding
Alon, Noga, Raphael Yuster, and Uri Zwick. “Color- coding.” J. ACM 42.4 (1995): 844-856
1995
-
[19]
Splitters and near-optimal derandomization
Naor, Moni, Leonard J. Schulman, and Aravind Srini- vasan. “Splitters and near-optimal derandomization.” Proceedings of IEEE 36th Annual Foundations of Com- puter Science. IEEE, 1995
1995
-
[20]
Some recursive constructions for per- fect hash families
Atici, M., et al. “Some recursive constructions for per- fect hash families.” Journal of Combinatorial Designs 4.5 (1996): 353-363
1996
-
[21]
Perfect hashing
Czech, Zbigniew J., George Havas, and Bohdan S. Ma- jewski. “Perfect hashing.” Theoretical Computer Science 182.1-2 (1997): 1-143
1997
-
[22]
Optimal linear perfect hash families
Blackburn, Simon R., and Peter R. Wild. “Optimal linear perfect hash families.” Journal of Combinatorial Theory , Series A 83.2 (1998): 233-250
1998
-
[23]
Perfect hash families: probabilistic methods and explicit constructions
Blackburn, Simon R. “Perfect hash families: probabilistic methods and explicit constructions.” Journal of Combi- natorial Theory, Series A 92.1 (2000): 54-60
2000
-
[24]
New constructions for perfect hash families and related struc- tures using combinatorial designs and codes
Stinson, Douglas R., Ruizhong Wei, and L. Zhu. “New constructions for perfect hash families and related struc- tures using combinatorial designs and codes.” Journal of Combinatorial Designs 8.3 (2000): 189-200
2000
-
[25]
Balanced families of per- fect hash functions and their applications
Alon, Noga, and Shai Gutner. “Balanced families of per- fect hash functions and their applications.” ACM Trans- actions on Algorithms (TALG) 6.3 (2010): 54
2010
-
[26]
Perfect hashing and probability
Nilli, Alon. “Perfect hashing and probability.” Combina- torics, Probability and Computing 3.3 (1994): 407-409
1994
-
[27]
Beating Fredman-Koml´ o s for perfect k-hashing
Guruswami, Venkatesan, and Andrii Riazanov. “Beating Fredman-Koml´ o s for perfect k-hashing.” arXiv:1805.04151 (2018)
2018 arXiv
-
[28]
Quantum com- putation and quantum information
Nielsen, Michael A., and Isaac Chuang. “Quantum com- putation and quantum information.” (2002): 558-559
2002
-
[29]
Entanglement of formation of an arbitrary state of two qubits
Wootters, William K. “Entanglement of formation of an arbitrary state of two qubits.” Physical Review Letters 80.10 (1998): 2245
1998
-
[30]
Optimal local preparation of an arbitrary mixed state of two qubits: Closed expression for the single-copy case
Vidal, Guifr´ e. “Optimal local preparation of an arbitrary mixed state of two qubits: Closed expression for the single-copy case.” Physical Review A 62.6 (2000): 062315
2000
-
[31]
Harmony for 2-Qubit Entanglement
Osuga, Kento, and Don N. Page. “Harmony for 2-Qubit Entanglement.” arXiv:1906.09273 (2019)
2019 arXiv
-
[32]
http:/www.public.asu.edu/∼ redoughe/ phf pages/phf tables.html
Dougherty, Ryan. http:/www.public.asu.edu/∼ redoughe/ phf pages/phf tables.html
-
[33]
Quantum-gas microscopes: a new tool for cold-atom quantum simulators
Kuhr, Stefan. “Quantum-gas microscopes: a new tool for cold-atom quantum simulators.”National Science Re- view 3.2 (2016): 170-172
2016
-
[34]
An atom-by-atom assembler of defect-free arbitrary two-dimensional atomic arrays
Barredo, Daniel, et al. “An atom-by-atom assembler of defect-free arbitrary two-dimensional atomic arrays.” Science 354.6315 (2016): 1021-1023
2016
-
[35]
Observation of a many-body dy- namical phase transition with a 53-qubit quantum simu- lator
Zhang, Jiehang, et al. “Observation of a many-body dy- namical phase transition with a 53-qubit quantum simu- lator.” Nature 551.7682 (2017): 601
2017
-
[36]
String-net con- densation: A physical mechanism for topological phases
Levin, Michael A., and Xiao-Gang Wen. “String-net con- densation: A physical mechanism for topological phases.” Physical Review B 71.4 (2005): 045110
2005
-
[37]
Detecting topo- logical order in a ground state wave function
Levin, Michael, and Xiao-Gang Wen. “Detecting topo- logical order in a ground state wave function.” Physical Review Letters 96.11 (2006): 110405
2006
-
[38]
Topological order: From long-range entangled quantum matter to a unified origin of light and electrons
Wen, Xiao-Gang. “Topological order: From long-range entangled quantum matter to a unified origin of light and electrons.” ISRN Condensed Matter Physics 2013 (2013)
2013
-
[39]
The complexity of the local Hamiltonian problem
Kempe, Julia, Alexei Kitaev, and Oded Regev. “The complexity of the local Hamiltonian problem.” SIAM Journal on Computing 35.5 (2006): 1070-1097
2006
-
[40]
Classical and quantum compu- tation
Kitaev, Alexei Yu, et al. Classical and quantum compu- tation. No. 47. American Mathematical Soc., 2002
2002
-
[41]
Solving the quantum many-body problem with artificial neural net- works
Carleo, Giuseppe, and Matthias Troyer. “Solving the quantum many-body problem with artificial neural net- works.” Science 355.6325 (2017): 602-606
2017
-
[42]
Learning phase transitions by confusion
Van Nieuwenburg, Evert PL, Ye-Hua Liu, and Sebastian D. Huber. “Learning phase transitions by confusion.”Na- ture Physics 13.5 (2017): 435
2017
-
[43]
Machine learn- ing phases of matter
Carrasquilla, Juan, and Roger G. Melko. “Machine learn- ing phases of matter.” Nature Physics 13.5 (2017): 431
2017
-
[44]
Discovering phase transitions with unsuper- vised learning
Wang, Lei. “Discovering phase transitions with unsuper- vised learning.” Physical Review B 94.19 (2016): 195105
2016
-
[45]
Quantum entanglement in deep learning architectures
Levine, Yoav, et al. “Quantum entanglement in deep learning architectures.” Physical Review Letters 122.6 (2019): 065301
2019
-
[46]
Quantum loop topography for machine learning
Zhang, Yi, and Eun-Ah Kim. “Quantum loop topography for machine learning.” Physical Review Letters 118.21 (2017): 216401
2017
-
[47]
Neural-network quantum state tomography
Torlai, Giacomo, et al. “Neural-network quantum state tomography.” Nature Physics 14.5 (2018): 447
2018
-
[48]
Multipartite quantum states and their marginals
Walter, Michael. “Multipartite quantum states and their marginals.” arXiv:1410.6820 (2014)
2014 arXiv
-
[49]
Quantum marginal problem and its physical relevance
Schilling, Christian. “Quantum marginal problem and its physical relevance.” arXiv:1507.00299 (2015)
2015 arXiv
-
[50]
Quantum state tomography via reduced density matrices
Xin, Tao, et al. “Quantum state tomography via reduced density matrices.” Physical Review Letters 118.2 (2017): 020401
2017
-
[51]
Efficient learning of quantum noise
Harper, Robin, Steven T. Flammia, and Joel J. Wallman. “Efficient learning of quantum noise.” arXiv:1907.13022 (2019)
2019 arXiv
-
[52]
Efficient es- timation of Pauli channels
Flammia, Steven T., and Joel J. Wallman. “Efficient es- timation of Pauli channels.” arXiv:1907.12976 (2019). 8 Appendix: Application of the Chernoff-Hoeffding Inequality One version of the Chernoff-Hoeffding inequality is as follows. Given M i.i.d. random variables Xj, each valued ...
2019 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.