{"id":"20b9f746-6dfc-4c5b-ba60-48d57f5f9ebd","arxiv_id":"2607.28260","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Sparse QROM has optimal Clifford+T cost Θ(√(sm)+√(sn)), yielding matching optimal T-counts for s-sparse state preparation and s-sparse block encoding.","lead":"The paper proves asymptotically optimal T-gate counts for sparse quantum read-only memory, scaling as the square root of the number of nonzero entries rather than the full address space. Matching bounds then follow for sparse state preparation and sparse matrix block encoding, which are core primitives in fault-tolerant quantum algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolated the only soft spot—the adaptive general-sparse gap and the Cn-vs-2^{(1-δ)n} windows—and correctly judged it non-fatal. Those limitations are author-flagged, do not affect promised QROM, state preparation, or block encoding, and are typical of counting lower bounds in the Clifford+T canonical-form model. The multilevel hashing argument (constant-fraction singleton deletion, geometric sum of √(s_i m)) and the direct (non-Choi) reductions to well-separated states are internally consistent and rest on cited primitives (SELECT-SWAP, Gosset–Kothari–Wu, Beverland et al.). No further load-bearing correctness risk surfaced on a full-text pass. Verdict remains ACCEPT at high confidence.","tokens_in":40894,"tokens_out":577,"duration_ms":38146,"concrete_test":"Re-read Remark 5.3 against abstract line 3 and Table 1 row ‘Adaptive sparse QROM’: confirm the abstract’s Θ(√(sm)+√(sn)) is understood as the unitary/non-adaptive claim, while the adaptive general-sparse entry remains a one-sided bound. If a fully adaptive O(√(sm)+√(sn)) circuit (or an adaptive Ω(√(sn)) lower bound) appears, the sole listed incompleteness closes; otherwise the paper’s own qualification stands and no correction is required.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central optimality claims hold where the paper states them most carefully. Promised sparse QROM is tight at Θ(√(sm)) even adaptively (Thm 3.1/5.1). Unitary/general sparse QROM is tight at Θ(√(sm)+√(sn)) in the stated window (Thm 3.2/5.4). Sparse state preparation and sparse block encoding receive matching adaptive upper and lower bounds (Thm 4.2/5.5, 4.4–4.7/5.7). The only genuine incompleteness is already disclosed: for fully adaptive general sparse QROM the upper bound is O(√(sm)+√(s log s)) while the support-identification lower bound √(sn) is proven only in the unitary model (Remark 5.3, Table 1). That gap does not undercut the applications or the promised-case theory, and the sparsity-window hypotheses on the counting lower bounds are standard for the 2^{O((n+t)²)} canonical-form overhead. No hidden assumption, circular step, or incorrect reduction was found in the multilevel-hashing analysis or the state-preparation/block-encoding reductions.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper initiates the study of T-count for sparse QROM (only s of 2^n addresses nonzero) and proves asymptotically optimal bounds Θ(√(sm)+√(sn)) in the unitary model, with promised sparse QROM tight at Θ(√(sm)) even adaptively. Upper bounds use a multilevel linear-hashing scheme that resolves a constant fraction of the remaining support per level, reducing to dense SELECT–SWAP QROM; general sparse QROM is obtained by index certification. Lower bounds reduce to state preparation and count Pauli-postselection Clifford canonical forms, holding for adaptive Clifford+T circuits. Matching adaptive bounds are obtained for s-sparse state preparation and for block encoding of row-and-column s-sparse matrices, with corollaries for QSVT, Hamiltonian simulation, linear systems, and rejection sampling.","tokens_in":41123,"tokens_out":964,"duration_ms":26117,"significance":"Coherent sparse data loading is a bottleneck in fault-tolerant quantum algorithms (sparse Hamiltonian simulation, linear systems, state preparation). Prior T-count work focused on dense QROM (SELECT–SWAP) or near-linear sparse state preparation; this paper supplies the first matching square-root T-count theory under sparsity, including adaptive lower bounds. The multilevel hashing construction is constructive and cleanly reduces to a black-box dense QROM, and the applications inherit tight asymptotics. The disclosed gap for fully adaptive general sparse QROM (upper O(√(sm)+√(s log s)) vs unitary lower √(sn)) does not undercut the promised case or the main applications. This is a substantial, self-contained contribution to fault-tolerant resource estimation.","major_comments":[],"minor_comments":[{"comment":"Table 1 and Remark 5.3 already flag the adaptive general-sparse gap, but the abstract and §1.1 lead with Θ(√(sm)+√(sn)) without immediately qualifying that the matching upper bound is for the unitary/non-adaptive model. A one-sentence qualification in the abstract or the table caption would prevent misreading.","section":"Abstract / Table 1 / Remark 5.3"},{"comment":"The lower-bound windows (e.g. C(n+m)² ≤ s ≤ 2^{(1-δ)n} in Thm 5.4; Cn ≤ s ≤ 2^{(1-δ)n} in Thms 5.5 and 5.7) are standard for canonical-form counting but are easy to miss. A short remark in §1.4 on the nearly-dense and ultra-sparse regimes would help practitioners.","section":"§1.4 / Theorems 5.4–5.7"},{"comment":"In Algorithm 3.1–3.2, the active-flag and singleton-flag bookkeeping is correct but dense; a one-line invariant (e.g. “after level i, T holds d_x iff x was resolved at some i★ ≤ i”) would make the uncomputation argument easier to audit.","section":"§3.1, Algorithms 3.1–3.2"},{"comment":"Theorem 2.6 is cited with an additive +m term restored in a footnote; when the paper invokes it inside multilevel hashing (m_i = O(log s_i)), the additive terms sum to O(m log s) and are absorbed under s ≥ m log² m. Stating this absorption once in the proof of Thm 3.1 would avoid repeated mental bookkeeping.","section":"§3.1, proof of Theorem 3.1"},{"comment":"Minor typos/notation: “F act 2.13” → “Fact 2.13”; in §4.2 the normalization is written both ¯s and S in Remark 5.8; ε vs ε_BE vs δ_BE are used consistently but a short notation paragraph at the start of §4 would help.","section":"§2.3 / §4 / Remark 5.8"}],"recommendation":"accept","confidential_remarks":"Strong accept. The reader and stress-test both found no load-bearing error; the only incompleteness (adaptive general sparse QROM) is already disclosed by the authors. Fit for a top theory/quantum-information venue is clear. No novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The new piece is a clean T-count theory for sparse coherent data loading. They get Θ(√(sm)) for promised sparse QROM and Θ(√(sm)+√(sn)) for general sparse QROM in the natural sparsity window, then push the same square-root sparsity dependence through to sparse state preparation and sparse block encoding, with adaptive lower bounds that survive mid-circuit measurement.\n\nWhat works: the multilevel linear-hashing upper bound is the real construction. Each level only needs a constant fraction of remaining support to land in singleton buckets; unresolved mass shrinks geometrically, so total T cost sums to O(√(sm)). The reduction from promised to general sparse QROM by returning the index and checking equality is simple and correct. Lower bounds follow the Gosset–Kothari–Wu adaptive-to-canonical-form route, with carefully chosen hard families (support variation, amplitude variation, and the Beverland-style single-qubit embedding for the log term). Dense QROM and dense state-prep are used as black boxes with proper citations, not redefined. Applications to QSVT, Hamiltonian simulation, linear systems, and rejection sampling are routine once you have the block-encoding and state-prep primitives, but the resource numbers are now tight where they matter.\n\nSoft spots are the ones the authors already flag. Fully adaptive general sparse QROM still has an O(√(sm)+√(s log s)) upper bound while the √(sn) support-identification lower bound is only proven in the unitary model (Remark 5.3). Lower bounds need C(n+m)² ≤ s ≤ 2^{(1-δ)n} (or the analogous windows for state prep / BE); that is standard for the 2^{O((n+t)²)} counting overhead and does not hide a hole in the argument. No circularity, no free parameters, no bad citation pattern.\n\nThis is for people who do fault-tolerant resource estimation or sparse quantum linear algebra. If you care about T count of data loading, you will use these bounds. It deserves a serious referee and should be engaged with; I would cite the sparse-QROM and sparse-state-prep theorems.","headline":"Tight T-count theory for sparse QROM, with matching applications to sparse state prep and block encoding; the one disclosed adaptive gap does not undercut the main claims.","tokens_in":41799,"tokens_out":551,"would_cite":true,"duration_ms":10953,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Sparse classical data can be loaded coherently with optimal square-root T-count in the support size, matching lower bounds even for adaptive circuits.","keywords":["sparse QROM","T-count","Clifford+T","state preparation","block encoding","multilevel hashing","adaptive circuits","quantum singular value transformation"],"falsifier":"Exhibit either an adaptive Clifford+T circuit for promised sparse QROM whose T-count is o(√(sm)) on a hard family of supports, or a counting argument showing that every such circuit needs ω(√(sm)) T gates outside the stated sparsity window.","tokens_in":41783,"feed_emoji":"⚛️","tokens_out":858,"duration_ms":16048,"temperature":0.7,"pith_summary":"Many quantum algorithms need coherent access to classical tables. When only s of the 2^n addresses hold nonzero data, the paper shows that the non-Clifford cost of implementing that access is governed by square roots of s rather than of the full table size. The upper bound is a multilevel hashing scheme that repeatedly resolves a constant fraction of the remaining support with dense lookups; the matching lower bounds come from reducing the task to state preparation and counting distinct adaptive Clifford+T circuits. The same square-root sparsity dependence is then tight for preparing s-sparse quantum states and for block-encoding row-and-column s-sparse matrices. A sympathetic reader cares because data-loading cost often dominates fault-tolerant resource estimates, and the new bounds replace near-linear sparsity dependence with the optimal square-root scaling in several standard primitives.","feed_headline":"Sparse data loads with optimal square-root T-count","feed_subtitle":"Matching bounds for QROM, state preparation and block encoding, even with mid-circuit measurement","key_machinery":"Multilevel hashing for promised sparse QROM: at each level a random linear hash isolates a constant fraction of still-unresolved addresses into singleton buckets that are resolved by one dense QROM call; the unresolved set shrinks geometrically, so total T-count sums to O(√(sm)).","core_discovery":"Sparse QROM with support size s, n-bit addresses and m-bit messages has asymptotically optimal T-count Θ(√(sm)+√(sn)); the promised-sparse variant is Θ(√(sm)). The same square-root dependence on s is tight for s-sparse state preparation and for block encoding of s-sparse matrices, even when mid-circuit measurements and classical feed-forward are allowed.","pith_inferences":["Once sparse data loading is no longer the asymptotic bottleneck, end-to-end T-counts for chemistry and linear-algebra algorithms will be dominated by the polynomial degree or condition number rather than by table size.","The remaining gap between the adaptive upper and lower bounds for general (non-promised) sparse QROM is a concrete target: either a better support-identification primitive or a tighter adaptive counting argument would close it.","The multilevel-hash idea may transfer to other coherent classical-data tasks whose cost is currently linear in support size, such as sparse isometries or dictionary-based encodings."],"forward_implications":["s-sparse n-qubit states prepare with T-count Θ(√(sn)+√(s log(1/ε))+log(1/ε)), matching the adaptive lower bound.","Row-and-column s-sparse matrices admit block encodings whose T-count is Θ(√(2^n s n)+√(2^n s log(s/ε_BE))+log(s/ε_BE)).","The same block-encoding cost propagates into QSVT, sparse Hamiltonian simulation and sparse linear-system solvers, replacing prior near-linear sparsity factors by square-root factors.","Quantum rejection sampling on an s-sparse distribution inherits an O(√(s log(1/δ))) T-cost per post-selection round."],"fun_headline_variants":["Sparse QROM achieves optimal Θ(√(sm)+√(sn)) T-count","Tight square-root T-counts for sparse QROM and state prep","Sparse QROM T-count lower bounds hold with mid-circuit measure","Matching √s T-count bounds for sparse block encodings","Optimal sparse state prep T-count Θ(√(sn)+√(s log(1/ε)))"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The matching lower bounds hold only when the support is neither tiny nor nearly dense, and the fully adaptive upper bound for ordinary sparse QROM still carries a small extra logarithmic term that is not yet matched.","fun_headline_variants_meta":{"raw":{"variants":["Sparse QROM achieves optimal Θ(√(sm)+√(sn)) T-count","Tight square-root T-counts for sparse QROM and state prep","Sparse QROM T-count lower bounds hold with mid-circuit measure","Matching √s T-count bounds for sparse block encodings","Optimal sparse state prep T-count Θ(√(sn)+√(s log(1/ε)))"]},"model":"grok-4.5","effort":"low","cost_usd":0.004564,"raw_usage":{"total_tokens":1337,"prompt_tokens":810,"num_sources_used":0,"completion_tokens":88,"cost_in_usd_ticks":45644000,"prompt_tokens_details":{"text_tokens":810,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":439,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":810,"tokens_out":88,"duration_ms":6712,"temperature":1.0,"reasoning_tokens":439,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T12:58:34.058755+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit either an adaptive Clifford+T circuit for promised sparse QROM whose T-count is o(√(sm)) on a hard family of supports, or a counting argument showing that every such circuit needs ω(√(sm)) T gates outside the stated sparsity window.","supporting_citations":[],"review_version":1}