{"id":"606a43c9-3254-4b42-a70d-97b010cd82b0","arxiv_id":"2501.06705","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors design dimension-independent classical sketches that approximately preserve the trace distance between quantum states, supporting approximate database operations without full state tomography.","lead":"This paper proposes classical sketches that summarize quantum states in small vectors, enabling approximate search, selection, sorting, and join on quantum data using classical machines. It aims to make storing and querying quantum data from experiments practical, but building the sketches still requires exponentially many copies of each state.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The concentration proof for Theorem 13 assumes the block variables Z_j are i.i.d. and that two moments determine the Chernoff MGF; both assumptions are false, so the dimension-independent claim is unsupported as written.","rationale":"The reader's weakest assumption identified the 2-design gap, and that is a real problem: a unitary 2-design does not determine the moment generating function needed for the Chernoff tail. However, my stress test found a more basic issue that occurs even for Haar-random measurements: the Z_j variables are not i.i.d., as directly contradicted by the identity ∑_j Z_j = 0. This invalidates the product-of-MGF step in Eq. (17) regardless of whether the measurement is Haar or Clifford. The two issues are related but distinct: the i.i.d. failure undermines the Chernoff factorization, while the 2-design failure undermines the replacement of Haar by Clifford. Both attack the same load-bearing step, so the reader's REJECT verdict is unchanged. The concrete test I propose is minimal and decisive: for k=2 the dependence is exact and easy to verify, so no subtle asymptotics are needed to show the proof as written is not self-consistent. I am not claiming the theorem is false; the concentration may be provable by other means such as negative-association or Lipschitz concentration on the Haar unitary group. But those arguments are absent, and the manuscript's stated derivation cannot be accepted as a proof.","tokens_in":30939,"tokens_out":9967,"duration_ms":111374,"concrete_test":"Compute Cov(Z_1, Z_2) for the construction in B.1 with k=2 and any d≥2, either analytically from the Haar measure or by Monte Carlo sampling of random orthonormal bases. Since Z_1 + Z_2 = 0 exactly, the covariance is −Var(Z_1), which is nonzero; this directly contradicts the i.i.d. assertion used in Eq. (17). If instead the claim is that dependence is negligible for large d, the test should be repeated at d=2^8, 2^12, 2^16 with k=4 and check whether the joint distribution of (Z_1,...,Z_k) approaches independence fast enough for the product Chernoff bound, with explicit rates.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The core concentration argument in Appendix B.1 is invalid as written. After defining Z_j as the normalized sum of W_jℓ over a block, the proof states 'Since Z_j’s are i.i.d.' and then factorizes the moment generating function as a product over j (Eq. (17)). This is false: the basis vectors |γ_t⟩ are orthonormal columns of a Haar unitary, so the blocks are dependent. In fact, summing over all blocks gives ∑_j Z_j = 0 up to normalization; for k=2 this gives Z_1 = -Z_2, so the variables are perfectly negatively correlated rather than independent. The Chernoff product step therefore collapses. Additionally, even if the blocks were independent, the expansion of M_{\\tilde U}(η/2) in Eq. (18) keeps only the first two moments and bounds the remainder by a universal c_ηη^3. A unitary 2-design fixes polynomials of degree at most 2 in U and U*, but the MGF and its Taylor remainder involve higher moments; Section B.1.1 asserts without proof that first and second Haar moments suffice for the tail bound. Both gaps affect exactly the step that yields k = c log(1/δ)/ι^2 independent of d, and the O(log^8 d) Clifford construction inherits the second gap. The theorem may be salvageable, but the proof does not establish it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes approximate versions of basic database operations for pure quantum states represented as classical sketches: equality test, search, join, selection, and sorting. It proposes two sketching tools. The first is a random k-outcome projective measurement sketch, claimed to embed the trace distance between two pure states into the ℓ1 or ℓ2 distance of the outcome distributions with distortion (1±ι) using k = O(log(1/δ)/ι^2) outcomes, independent of the state dimension, with a Clifford-group construction that samples the measurement in O(log^8 d) classical time. The second is a shadow-seed sketch, based on the classical shadow tomography of Huang, Kueng, and Preskill, used to estimate expectation values of k-local observables, with a proposed QCQC speedup. The paper then applies LSH-based ANN search to the vector sketches and the shadow-seed estimator to selection and sorting.","tokens_in":31100,"tokens_out":20983,"duration_ms":200845,"significance":"If Theorem 13 and its corollaries were correct, the vector-sketch contribution would be significant: a classical, dimension-independent sketch preserving trace distance would be a first step toward sustainable quantum data management, and the reduction to LSH-based sublinear search is conceptually attractive. The paper also gives creditably explicit problem definitions, a no-free-parameters analysis, and the shadow-seed part is built on established results with a self-contained estimator proof. However, the central concentration proof for Theorem 13 is not valid as written, and the empirical-distribution corollaries are ambiguous and currently unsupported. The significance of the paper therefore rests on a load-bearing claim that needs substantial additional work.","major_comments":[{"comment":"The assertion 'Since Z_j’s are i.i.d.' is false, and this invalidates the Chernoff step. The vectors |γ_t⟩ are columns of a single Haar-distributed unitary, so the block variables Z_j are not independent: summing the definition gives ∑_{j=1}^k Z_j = 0 up to normalization, because the |γ_t⟩ form an orthonormal basis. For k = 2 this forces Z_1 = −Z_2, so the moment-generating-function product factorization in Eq. (17) collapses. The same defect appears in the ℓ2 proof in Appendix B.2 around Eq. (32). This is exactly the step that yields the dimension-independent bound k = c log(1/δ)/ι^2 in Theorem 13.","section":"Appendix B.1, Eq. (17)"},{"comment":"A unitary 2-design is not sufficient for the tail bound as argued. The Chernoff/MGF argument requires control of the whole moment generating function of |Z_j|; Eq. (18) bounds the Taylor remainder ζη by cηη^3, which requires control of higher moments or of the MGF itself. A 2-design matches only polynomials of degree at most 2 in U and U*, so matching the first two moments of W_jℓ does not control E[exp(t|Z|)] or its remainder. Additionally, the Berry-Esseen lower bound in Eq. (23) is applied to the sum of W_ℓ^1 variables, which are not i.i.d. because they are entries from the same Haar unitary. Consequently the O(log^8 d) Clifford-based construction inherits an unsupported concentration claim.","section":"Appendix B.1.1"},{"comment":"The empirical-distribution corollaries are ambiguous and, on the natural reading, false. If each copy is measured with an independently sampled M_k, the empirical vector estimates E_{M_k}[M_k(φ)], which by unitary invariance is the uniform distribution for every φ; the difference of the two empirical vectors then has mean zero, so the claimed (1±ι)D preservation cannot hold. If instead a single sampled M_k is fixed for all copies and all states (the only reading that supports the subsequent LSH application), the text must say this explicitly and the algorithm must ensure the database sketches and the query sketch use the same measurement. As written, the search and join constructions in Section 4.1 are not supported.","section":"Corollaries 14 and 16"},{"comment":"The theorem statement omits necessary domain conditions. The described construction requires k ≤ d and also requires d/k to be a large enough constant for the Berry-Esseen lower bound in Eqs. (23)–(24). For fixed small d, the promised k = c log(1/δ)/ι^2 can exceed d, making the statement impossible; more generally, the proof's concentration conclusion cannot hold for k = 2, where Z_1 = −Z_2 and the averaged quantity has a non-degenerate distribution. The theorem should state the required relationship among d, k, δ, and ι, or the proof must handle these cases.","section":"Theorem 13"}],"minor_comments":[{"comment":"The binning instruction is inconsistent: measuring the first ⌈log k⌉ qubits gives 2^{⌈log k⌉} outcomes, and then taking the result mod k is a different partition of {0,1}^n unless k is a power of two. Please specify one concrete binning rule.","section":"Algorithm 1"},{"comment":"Reference [16] is cited for the O(n^8)-time uniform Clifford sampling algorithm, but that reference is titled 'Quantum data hiding' and does not appear to contain such a sampling algorithm; a correct citation should be supplied.","section":"References"},{"comment":"The reconstruction in Lemma 27 uses U_j|B_j⟩ rather than the standard classical-shadow convention U_j†|B_j⟩; please clarify the relationship to the inverse shadow channel, since the proof as written is easy to misread and may contain a transpose error.","section":"Appendix B.3, Lemma 27"},{"comment":"There are numerous typos and formatting errors, including 'dimentionality', 'Another ser', 'Articial Intelligence', and the placeholder venue 'CVIT 2016'; a careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is framed for a database audience, but its main technical hurdle is a quantum-information concentration proof. The shadow-seed portion appears sound and is a useful application of known results, but the vector-sketch contribution is currently unproven as written. I would recommend inviting a major revision only if the authors can either supply a rigorous concentration proof for a fixed, reusable random measurement or clearly restrict the theorem to the regime where their argument is valid; otherwise the central claim should not appear in its present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper is a mixed bag. The good news: it's the first serious attempt I know to define classical sketches of quantum states with database operations in mind. The approximate operation definitions (search, join, selection, sorting) are thoughtful, and the LSH-based query algorithms are a nice fit. The shadow-seed section is solid: it's a clean application of classical shadows, and the QCQC variant that estimates k-local observables with 3^k rather than 4^k overhead is a genuine, if modest, improvement. If the paper were just that, I'd be happy.\n\nThe problem is the headline result. Theorem 13 claims a dimension-independent, efficiently constructible vector sketch that preserves trace distance up to (1±ι). The proof in Appendix B.1 doesn't hold. The step where the Z_j are declared i.i.d. is false: the blocks come from a single Haar-distributed orthonormal basis, so they are dependent; in fact for k=2, Z_1 = -Z_2. The product form of the MGF in (17) is therefore unjustified. The second gap is in the 2-design argument: a unitary 2-design matches only first and second moments, but the Taylor expansion of the MGF in (18) leaves a remainder that involves higher moments. That remainder is exactly what you need to control for the Chernoff tail bound, so the efficient O(log^8 d) construction is unsupported. This is not a minor technicality; it is the step that gives k = O(log(1/δ)/ι^2) independent of d. The theorem may be true and salvageable, but the submitted proof does not establish it.\n\nThere is also a sloppy reference: the claim about uniform Clifford sampling in O(n^8) time cites [16], a quantum data hiding paper, not a Clifford sampling paper. That's an easy fix but a warning sign.\n\nThe exponential sample complexity (O(d/ε^2) copies per state) is real, but the authors explicitly frame it as a one-time cost and defer to database practice, which is defensible for a first theoretical step.\n\nBottom line: the shadow-seed part is publishable on its own, and the vector-sketch idea is worth serious work. The paper deserves peer review, not a desk reject, but it needs a major rewrite of the proof of Theorem 13 before it can be accepted. If the authors fix that gap, this could be a meaningful opening of a new subfield.\n\nRecommendation: send it to referees who know both quantum state learning and concentration of measure.","headline":"Promising framework for sketching quantum states for database operations, but the main vector-sketch theorem has a real proof gap; the shadow-seed part is solid.","tokens_in":31713,"tokens_out":3856,"would_cite":false,"duration_ms":35938,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68P15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that a random measurement with only $O(\\log(1/\\delta)/\\iota^2)$ outcomes can embed two pure $d$-dimensional quantum states into a low-dimensional probability space, preserving their trace distance up to a factor…","keywords":["quantum data representation","data sketching","query execution","trace distance","locality sensitive hashing","classical shadows","quantum database","state tomography"],"falsifier":"Compute the third moment (or the full moment generating function) of $W = d\\bigl(|\\langle 1|\\gamma\\rangle|^2 - |\\langle 2|\\gamma\\rangle|^2\\bigr)$ for a basis vector $\\gamma$ drawn from the Clifford 2-design and from the Haar measure; if the values differ, the Chernoff step in Section B.1 that yields the $O(\\log(1/\\delta)/\\iota^2)$ sketch size does not follow for the efficient construction.","tokens_in":30625,"feed_emoji":"⚛️","tokens_out":12214,"duration_ms":101377,"temperature":0.7,"pith_summary":"Quantum data—the states of photons, molecules, or other systems—live in spaces of dimension exponential in the number of qubits, so storing each state classically is infeasible. This paper asks what database operations can be supported by a small classical 'sketch' of each state, and it gives two sketches with size and query time independent of the state dimension. The main technical result is a vector sketch of size $O(\\log(1/\\delta)/\\iota^2)$ that preserves the trace distance between two pure states up to a $(1\\pm\\iota)$ distortion: a random measurement with $k$ outcomes produces outcome distributions whose scaled $\\ell_1$ distance concentrates around the trace distance. With these sketches, equality testing, search, and join become classical distance computations, and search and join can be accelerated by locality-sensitive hashing to run in time sublinear in the database size and independent of dimension. A second sketch, based on classical shadows, estimates the expectation value of any $k$-local observable to additive error $\\varepsilon$, enabling selection and sorting on quantum data.","feed_headline":"Log-sized sketches preserve quantum trace distances","feed_subtitle":"Database search and join become dimension-free and sublinear in table size.","key_machinery":"The central object is a random projective measurement $M_k$ built by drawing a Haar-random orthonormal basis (via complex Gaussian vectors and the pretty good measurement), grouping the $d$ basis vectors into $k$ equal-size groups, and using the group projectors as the $k$ measurement outcomes. The proof shows that for any two pure states $\\varphi$ and $\\psi$, the $\\ell_1$ distance between their outcome distributions, scaled by $\\sqrt{d/(k c_\\tau)}$ with $c_\\tau\\in[0.48,\\sqrt{2}]$, concentrates within $(1\\pm\\iota)$ of the trace distance $D(\\varphi,\\psi)$ as long as $k = c\\log(1/\\delta)/\\iota^2$; an $\\ell_2$ version scales by $\\sqrt{d/2}$. The efficient implementation replaces Haar sampling with the Clifford group, a unitary 2-design, sampled in $O(\\log^8 d)$ classical time and realized as a circuit with $O(\\log^2 d)$ gates. The shadow-seed sketch uses a different mechanism: random single-qubit Clifford rotations followed by computational-basis measurements produce a classical seed matrix, and at query time the $k$-local observable's expectation is estimated from these seeds, with a quantum-classical-quantum-classical (QCQC) procedure that reduces query time from $O(16^k)$ to $O(9^k)$.","core_discovery":"Let $\\varphi$ and $\\psi$ be two pure $d$-dimensional quantum states. The paper's main discovery is that there is a distribution over measurements with $k = c\\log(1/\\delta)/\\iota^2$ outcomes, where $k$ does not depend on the dimension $d$, such that a random measurement $M_k$ from this distribution yields outcome distributions whose $\\ell_1$ distance, after scaling by $\\sqrt{d/(k c_\\tau)}$ with a universal computable constant $c_\\tau \\in [0.48, \\sqrt{2}]$, lies within a factor $(1\\pm\\iota)$ of the trace distance $D(\\varphi,\\psi)$, with probability at least $1-\\delta$. An analogous $\\ell_2$ statement holds with scale $\\sqrt{d/2}$. This turns trace-distance estimation into an $\\ell_1$/ $\\ell_2$ problem in a fixed low-dimensional space, so equality testing becomes an $O(k)$-time distance computation and search and join become sublinear-time operations via locality-sensitive hashing. The paper also gives a shadow-seed sketch, based on classical shadows, that estimates the expectation of any $k$-local observable to additive error $\\varepsilon$ using $O(Nn)$ classical bits, with query time independent of $d$.","pith_inferences":["If the Clifford-replacement step survives scrutiny, the vector sketch becomes implementable on near-term quantum hardware ($O(\\log^2 d)$ gates per state), which would make quantum-data indexing a plausible near-term application; the open question is whether higher moments of the Clifford-sampled estimator match Haar.","The dimension-independence suggests a way around the general lower bound for $\\ell_1$ dimension reduction: the sketch exploits the special geometry of pure-state trace distance, so an analogous embedding for mixed (density-matrix) states is a natural next target.","A numerical study comparing Clifford-sampled and Haar-sampled sketch distances on random state pairs could both test the 2-design assumption empirically and potentially tighten the universal constant $c_\\tau$ beyond the $[0.48, \\sqrt{2}]$ interval.","The shadow-seed QCQC estimator trades more quantum time for fewer classical bits than storing full classical shadows, which points toward a design space for hybrid query engines that minimize either storage or quantum circuit depth depending on the workload."],"forward_implications":["The $(\\varepsilon,\\beta)$-equality-test reduces to computing the $\\ell_1$ or $\\ell_2$ distance between two $O(\\log(1/\\delta)/\\varepsilon^2)$-dimensional sketch vectors, using no fresh copies of the database states.","The $(\\varepsilon,\\beta)$-search problem can be answered with an LSH index of size $O(m \\log m/\\varepsilon^2 + m^{1+1.05/\\beta^2})$ and classical query time $O(m^{1.05/\\beta^2} \\log m/\\varepsilon^2)$, which is sublinear in $m$ for $\\beta > \\sqrt{1.05}$ and independent of the state dimension $d$.","The $(\\varepsilon,\\beta)$-natural-join can be done by hashing all sketch vectors and verifying each colliding pair, with time depending on the join output size but not on $d$.","For any $k$-local observable, $(\\eta,\\varepsilon)$-selection and $\\varepsilon$-sorting are solved with an index of $O(9^k n W^2 \\log m/\\varepsilon^2)$ classical bits and query time $O(9^k m \\log m W^2 \\mathrm{poly}(k)/\\varepsilon^2)$, where $W$ bounds the observable's operator norm.","The sketch construction uses only $O(d/\\varepsilon^2)$ copies of each state (a one-time preprocessing cost), far less than the $O(d^2/\\varepsilon^5)$ time of full tomography followed by dimension reduction."],"supporting_citations":[{"why":"Supplies the baseline result that the trace distance of two pure states is within a constant factor of the $\\ell_1$ distance of their outcome distributions under a dimension-$d$ random measurement; the paper's Theorem 13 improves the distortion to $(1\\pm\\iota)$ and removes the dimension factor.","marker":"[53]"},{"why":"Provides the Gaussian-ensemble construction of random pure states used to build a Haar-distributed orthonormal basis for the random measurement in the proof of Theorem 13.","marker":"[30]"},{"why":"Gives the pretty good measurement technique used to orthogonalize the random Gaussian basis vectors while preserving unitary invariance.","marker":"[36]"},{"why":"Establishes that the Clifford group is a unitary 2-design, the fact that lets the paper replace Haar sampling with efficient Clifford sampling in constructing $M_k$.","marker":"[14]"},{"why":"Supplies the algorithm that samples uniformly from the Clifford group in $O(\\log^8 d)$ classical time and outputs a circuit with $O(\\log^2 d)$ gates, giving the efficient construction claim of Theorems 13 and 15.","marker":"[16]"},{"why":"Introduces classical shadows, the seed-based representation that the shadow-seed sketch builds on to estimate $k$-local observable expectations for selection and sorting.","marker":"[37]"},{"why":"Provides the locality-sensitive hashing framework for approximate nearest neighbor search that the paper applies to the sketch vectors to obtain sublinear-time search and join.","marker":"[39]"}],"fun_headline_variants":["Quantum sketches cut search to sublinear in dimension","Dimension-free quantum sketches for database ops","Log-size quantum sketches enable fast queries","Sketches turn quantum search into a small-space problem","Trace distance via log-sized measurements in quantum data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that sampling the measurement from the Clifford group instead of the full Haar distribution leaves the tail behavior of the distance estimator unchanged, although the proof in Section B.1.1 establishes only a match of the first two moments.","fun_headline_variants_meta":{"raw":{"variants":["Quantum sketches cut search to sublinear in dimension","Dimension-free quantum sketches for database ops","Log-size quantum sketches enable fast queries","Sketches turn quantum search into a small-space problem","Trace distance via log-sized measurements in quantum data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000192,"raw_usage":{"total_tokens":1332,"prompt_tokens":915,"completion_tokens":417,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":348}},"tokens_in":531,"tokens_out":417,"duration_ms":5070,"temperature":1.0,"reasoning_tokens":348,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:54:56.891581+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the third moment (or the full moment generating function) of $W = d\\bigl(|\\langle 1|\\gamma\\rangle|^2 - |\\langle 2|\\gamma\\rangle|^2\\bigr)$ for a basis vector $\\gamma$ drawn from the Clifford 2-design and from the Haar measure; if the values differ, the Chernoff step in Section B.1 that yields the $O(\\log(1/\\delta)/\\iota^2)$ sketch size does not follow for the efficient construction.","supporting_citations":[{"cited_title":"Random measurement bases, quantum state distinction and applications to the hidden subgroup problem","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline result that the trace distance of two pure states is within a constant factor of the $\\ell_1$ distance of their outcome distributions under a dimension-$d$ random measurement; the paper's Theorem 13 improves the distortion to $(1\\pm\\iota)$ and removes the dimension factor."},{"cited_title":"Shor, and Andreas Winter","cited_arxiv_id":null,"evidence_quote":"Provides the Gaussian-ensemble construction of random pure states used to build a Haar-distributed orthonormal basis for the random measurement in the proof of Theorem 13."},{"cited_title":"On asymptotically optimal hypotheses testing in quantum statistics","cited_arxiv_id":null,"evidence_quote":"Gives the pretty good measurement technique used to orthogonalize the random Gaussian basis vectors while preserving unitary invariance."},{"cited_title":"Approximate nearest neighbors: Towards removing the curse of dimensionality","cited_arxiv_id":null,"evidence_quote":"Provides the locality-sensitive hashing framework for approximate nearest neighbor search that the paper applies to the sketch vectors to obtain sublinear-time search and join."}],"review_version":1}