{"id":"e3283295-0a6c-474c-b3b7-755180ffdbfc","arxiv_id":"1908.02754","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"All k-qubit reduced density matrices of an n-qubit state can be reconstructed from e^{O(k)} log^2(n) rounds of parallel product measurements using perfect hash families.","lead":"This paper shows how to measure all correlations among any k qubits of a large quantum system using only a polylogarithmic number of parallel measurement rounds. The method reuses measurement data across overlapping groups of qubits, and the authors estimate that every pair entanglement in a 1000-qubit system could be characterized in a few days.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eqs. (1), (4), and (8) omit the 1/2^k normalization in the Pauli expansion, so the protocol as written reconstructs 2^k times the reduced density matrix.","rationale":"The reader's weakest_assumption was operational (parallel measurement of all qubits, identical copies, and hash-family constructibility). My identified concern is different: the reconstruction formulas in Eqs. (1), (4), and (8) are missing the 1/2^k Pauli-expansion normalization. The reader's rationale does list this normalization as a required correction, but it was not the stated weakest_assumption, hence partial agreement. This concern is load-bearing for the literal claim that the protocol determines the reduced density matrices, because the output of Eq. (8) is 2^k times the true RDM. It is not load-bearing for the scaling claim; the number of rounds and the measurement strategy are unaffected once the normalization is inserted. The perfect-hash-family argument and the Hoeffding/union-bound sample count are internally consistent and, modulo the normalization fix, the central result stands. I therefore do not move the reader's CONDITIONAL verdict; acceptance should remain conditional on the normalization correction and the minor Section VI arithmetic fix already flagged by the reader.","tokens_in":11847,"tokens_out":52421,"duration_ms":585379,"concrete_test":"Set k=2 and take rho = I/4 (maximally mixed). The true expectation values are tr((sigma_alpha tensor sigma_beta)rho) = delta_{alpha,0} delta_{beta,0}. Evaluating the right-hand side of Eq. (8) gives sigma_0 tensor sigma_0 = I tensor I, which equals 4 rho. Repeat with rho = |00><00|: the RHS is 4 times the correct expansion, again 4 rho. Recompute with the corrected expansion rho = 2^{-k} sum ... and verify that both cases reproduce rho exactly. This settles the missing normalization without requiring simulation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central scaling argument in Section III is sound: perfect hash families of size e^{O(k)} log n, combined with M ~ k log(n)/eps^2 repetitions per setting, give e^{O(k)} log^2(n) parallel rounds. However, the reconstruction step is wrong as written. Eq. (1) expands rho = sum_{alpha,beta} tr((sigma_alpha tensor sigma_beta)rho) sigma_alpha tensor sigma_beta without the factor 1/2^k required by the orthogonality relation tr(sigma_a sigma_b) = 2^k delta_{a,b}. The same omission appears in Eq. (4) and in the k=2 reconstruction Eq. (8). Consequently, applying the stated formula to measured expectation values yields 2^k rho, not rho. For k=2 and the maximally mixed state, Eq. (8) returns I tensor I (trace 4) instead of I/4. Because Section VI uses the reconstructed matrices to compute entanglement of formation, the protocol as stated would feed unnormalized matrices into entanglement measures. The fix is a one-line normalization, dividing the right-hand sides of Eqs. (1), (4), and (8) by 2^k; it does not alter the round count or the asymptotic bound. But until that factor is inserted, the claim that QOT determines all k-qubit reduced density matrices is literally false.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12108,"tokens_out":10369,"duration_ms":106088,"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":[{"comment":"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":"Section II, Eqs. (1) and (4); Section IV, Eq. (8)"},{"comment":"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.","section":"Section III, Eqs. (5)-(6)"}],"minor_comments":[{"comment":"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":"Section IV, Step 2.j"},{"comment":"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.","section":"Section VI, experimental estimate"},{"comment":"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.","section":"Appendix, Eq. (11)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is well within the scope of the journal and the core idea is sound. The errors are localized and fixable; I would be comfortable with a major revision that corrects the normalization and the inequality direction, followed by a final accept once the authors verify the corrected equations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core QOT idea is sound and genuinely new as a measurement protocol. The paper's contribution is organizing overlapping tomographic data with perfect hash families: for any k-subset, some hash function separates it, so a single round of product measurements on the color classes yields data for all k-qubit reduced density matrices. The k=2 binary coloring is concrete, and the asymptotic round count e^{O(k)} log^2(n) is derived cleanly from union bounds and Chernoff-Hoeffding. That is a real improvement over the naive n^k scaling and over Aaronson's shadow tomography, which needs entangled measurements and poly(n) copies. I also appreciate the explicit discussion of balanced hash families and (n,t,k) generalizations, which shows the authors thought about practical variants.\n\nThe main defect is real: Eqs. (1), (4), and (8) omit the 1/2^k factor required by the Pauli basis expansion. The stress-test note is correct. As written, the protocol reconstructs 2^k times the density matrix, so feeding those matrices into an entanglement measure would be wrong. The fix is a one-line normalization on the right-hand sides, and it does not affect the scaling argument or the measurement bound. Still, it needs to be corrected before publication; the claim that QOT determines the reduced density matrices is literally false until that factor appears.\n\nMinor issues: the final number in Section VI, 1,000,800, is a typo for 1,008,000. The M estimate in the appendix is a bit loose but in the right ballpark. The comparison with shadow tomography is compressed; a direct sample-complexity comparison with classical shadows would be helpful, though that work appeared later, so the citation pattern is fine.\n\nThe central argument holds up. The paper is worth a serious referee, and with the normalization fixed and a few small edits, it should be accepted. I would take it seriously if I were in the quantum-information or many-body metrology area.","headline":"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.","tokens_in":12600,"tokens_out":2511,"would_cite":false,"duration_ms":29117,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","81P40","81P50"],"pacs":["03.65.Ud","03.67.Lx","06.20.Dk"],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum overlapping tomography","perfect hash families","parallel measurements","reduced density matrices","Pauli measurements","entanglement characterization","many-body entanglement","quantum state tomography"],"falsifier":"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.","tokens_in":11655,"feed_emoji":"⚛️","tokens_out":15904,"duration_ms":162545,"temperature":0.7,"pith_summary":"Quantum overlapping tomography aims to solve a measurement bottleneck: experiments can entangle thousands of qubits but cannot fully tomograph a state of that size. The paper claims that all $k$-qubit reduced density matrices of an $n$-qubit state can be determined, to fixed accuracy and with high probability, in $e^{\\mathcal{O}(k)} \\log^2(n)$ rounds of parallel single-qubit measurements. The trick is to treat the overlap between $k$-qubit subsystems as a resource: a round of measurements chosen from a perfect hash family provides complete tomographic data for every $k$-qubit subset that the hash function separates. If the claim is right, the entanglement of every pair in a 1000-qubit system—about 500,000 pairs—could be fully characterized in days rather than weeks.","feed_headline":"Researchers can map all pair entanglements in 1000 qubits in days","feed_subtitle":"Hash-function colorings let one parallel round of measurements serve thousands of overlapping qubit pairs.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines perfect hash families, the combinatorial objects that organize which qubit subsets are measured together.","marker":"[12]"},{"why":"Establishes size bounds for separating systems and perfect hash families, giving the $e^{\\mathcal{O}(k)} \\log n$ scaling for the required number of functions.","marker":"[14]"},{"why":"Provides an explicit, efficiently computable construction of $(n,k)$ perfect hash families of size $e^{\\mathcal{O}(k)} \\log n$, used for the general $k$ protocol.","marker":"[18]"},{"why":"Constructs balanced perfect hash families, which allow the repetition count to be reduced from $M$ to $M/T$ in favorable parameter regimes.","marker":"[25]"}],"fun_headline_variants":["All pair entanglements in 1000 qubits mapped in days","Hash families turn 1000-qubit entanglement tomography into days","Overlapping tomography: every qubit pair in 1000 qubits in days","Perfect hash functions slash tomography time for 1000 qubits","1000-qubit state: all pair correlations captured in days"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["All pair entanglements in 1000 qubits mapped in days","Hash families turn 1000-qubit entanglement tomography into days","Overlapping tomography: every qubit pair in 1000 qubits in days","Perfect hash functions slash tomography time for 1000 qubits","1000-qubit state: all pair correlations captured in days"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001197,"raw_usage":{"total_tokens":4918,"prompt_tokens":911,"completion_tokens":4007,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":3915}},"tokens_in":527,"tokens_out":4007,"duration_ms":31510,"temperature":1.0,"reasoning_tokens":3915,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:37:51.559122+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Data Structures and Algorithms. 1. Sorting and Searching","cited_arxiv_id":null,"evidence_quote":"Defines perfect hash families, the combinatorial objects that organize which qubit subsets are measured together."},{"cited_title":"On the size of separating systems and families of perfect hash func- tions","cited_arxiv_id":null,"evidence_quote":"Establishes size bounds for separating systems and perfect hash families, giving the $e^{\\mathcal{O}(k)} \\log n$ scaling for the required number of functions."},{"cited_title":"Color- coding","cited_arxiv_id":null,"evidence_quote":"Provides an explicit, efficiently computable construction of $(n,k)$ perfect hash families of size $e^{\\mathcal{O}(k)} \\log n$, used for the general $k$ protocol."},{"cited_title":"Balanced families of per- fect hash functions and their applications","cited_arxiv_id":null,"evidence_quote":"Constructs balanced perfect hash families, which allow the repetition count to be reduced from $M$ to $M/T$ in favorable parameter regimes."}],"review_version":1}