{"id":"ecaf0449-63be-415f-8ff9-d6393a1f69dd","arxiv_id":"2608.00414","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An n-qubit state supported on at most s basis states can be prepared to constant error with Õ(min{s, n^{3/4}√s}) T gates, and some such states require Ω(min{s, √(ns)}) T gates.","lead":"Sparse quantum states, ones with at most s nonzero entries, can be prepared with far fewer T gates than previously known once the support is large, using a new support-aware circuit synthesis technique. The paper also proves lower bounds showing when the old linear-in-s cost is unavoidable, which matters for estimating the fault-tolerant overhead of quantum algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 12's lower bound is only proved for s≤n or s≥Cn, leaving a gap for n<s<Cn despite the universal claim.","rationale":"The paper's central upper bound (Theorem 9 via the support-aware synthesis of Theorem 8) appears sound: the recursion in Lemma 11 correctly accounts for persistent ancillas from Case-1 steps and reusable scratch from uncomputed subroutines, and the Toffoli algebra checks out with c=√n. The main defect is in the lower-bound theorem. The proof of Theorem 12 splits into two regimes, but the two lemmas do not cover the interval n<s<Cn (for the constant C in Lemma 15) nor the tiny-s cases below 4/(1-ε^2). The reader's weakest_assumption about Lemma 11 is not the actual soft spot; the proof explicitly handles ancilla reuse and support-independent synthesis via Theorem 5. However, the reader's CONDITIONAL verdict is still appropriate because the lower-bound statement in Theorem 12 and the abstract overclaims the range of s. The gap is likely patchable by either restricting the theorem to s≤n or s≥Cn, or by finding a different argument for the intermediate range, so the paper should be accepted only after the statement is corrected or the gap is closed.","tokens_in":16745,"tokens_out":53238,"duration_ms":389247,"concrete_test":"Symbolically evaluate the packing lower-bound inequality for s=2n and ε=1/6: compute log|F| ≥ (1-18ε^2)s(n−log s) − (s/2)log(2e) − log(s+1) and compare with the counting bound n^2+t^2. If the coefficient of n^2 on the right-hand side is ≤1, then the packing argument yields no t=Ω(√(ns)) lower bound for s=2n, confirming that Lemma 15 does not cover this case and the theorem's universal claim is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 12 claims that for every 0<ε≤1/6 and every 2≤s≤2^{n/2}, some s-sparse state requires Ω(min{s,√(ns)}) T gates. The proof splits into s=O(n) and s=Ω(n). The s=O(n) case is Lemma 18, which applies only for 4/(1-ε^2)≤s≤n. The s=Ω(n) case is Lemma 15, which applies only for s≥Cn with a sufficiently large absolute constant C. For n<s<Cn, neither lemma applies: Lemma 18 requires s≤n, and Lemma 15 requires s≥Cn. For 2≤s<4/(1-ε^2), Lemma 18 also fails, and the first claim of Theorem 12 only gives Ω(√(s log(1/ε)))=Ω(√n) for constant ε, which is strictly weaker than the claimed Ω(n) for s=Θ(n). Thus the proof does not establish the theorem's universal range. This is a proof gap rather than a demonstrated counterexample, but it means the central lower-bound statement is overclaimed as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies approximate preparation of s-sparse n-qubit pure states in the Clifford+T model, using T-count as the cost. It proves an upper bound (Theorem 9/Corollary 2) of O~(min{s, n^{3/4} sqrt(s)}) T gates for constant error, via a reduction in which a dense label state is prepared, the support strings are loaded by a sparse Boolean function synthesis theorem (Theorem 8), and the label register is erased by implementing the zero-extension of the inverse labeling map. Theorem 8 is proved by a small-support compression argument and a large-support recursive prefix-compression/peeling algorithm. The paper also proves lower bounds (Theorem 12): for 0<epsilon<=1/6 and 2<=s<=2^{n/2}, some s-sparse state requires Omega(min{s, sqrt(ns)}) T gates. The small-support lower bound uses the stabilizer nullity of W states and an overlap bound for stabilizer subgroups; the large-support lower bound uses a packing of uniform superpositions together with a counting argument from [GKW26]. A gap in the proof of the lower-bound range is identified below.","tokens_in":16874,"tokens_out":39920,"duration_ms":329442,"significance":"If the results hold, the paper gives the first sublinear-in-s T-count for sparse states with sufficiently large support, and establishes that linear T-count is unavoidable for s=O(n) and that an Omega(sqrt(ns)) barrier persists up to s=2^{n/2}; in the large-support regime the gap between upper and lower bounds is only an n^{1/4} factor. The support-aware synthesis theorem for sparse Boolean functions (Theorem 8) is a useful contribution in its own right, and the reduction from state preparation to label-prepare/load/erase is clean. The lower-bound machinery is standard but carefully applied. The main weakness is the proof gap in Theorem 12; because that gap is easily closed, the substantive contributions appear sound.","major_comments":[{"comment":"The second lower bound is not established over the full stated range 2<=s<=2^{n/2}. The proof splits into Lemma 18 (which requires s<=n) and Lemma 15 (which requires s>=Cn for an absolute constant C), so the interval n<s<Cn is not covered by either lemma. In this interval the claimed bound is Omega(min{s,sqrt(ns)})=Omega(n), whereas the first claim of Theorem 12 gives only Omega(sqrt(s log(1/epsilon)))=Omega(sqrt(n)). The small constant range 2<=s<4/(1-epsilon^2) is also not covered by Lemma 18, although there the first claim already provides a constant lower bound and this part is harmless. Because the abstract and conclusion repeat the universal claim, the proof must be repaired. A simple repair is to observe that for n<=s<Cn, the n-qubit state |W_n> has support size n<=s and is therefore s-sparse, and Lemma 18 with s=n gives, for large enough n, T_epsilon(|W_n>)=Omega(n)=Omega(min{s,sqrt(ns)}); the authors should add this case explicitly.","section":"Section 5.2, proof of Theorem 12"},{"comment":"The sentence 'The case s=O(n) is proved in Section 5.2, see Theorem 18' is inaccurate, since Lemma 18 has the hypothesis s<=n rather than s=O(n); the intermediate regime n<s<Cn is therefore not covered by the cited lemma. Please correct the split and reconcile the numbering (the result is Lemma 18, not Theorem 18).","section":"Section 5.2, proof of Theorem 12"}],"minor_comments":[{"comment":"The text says 'By Theorem 7' where Lemma 7 is meant; the same numbering confusion appears in Section 5, where 'Theorem 18' refers to Lemma 18, and in Section 4, where 'Theorems 10 and 11' refer to Lemmas 10 and 11.","section":"Section 3, proof of Theorem 9"},{"comment":"The claim that unary iteration implements H with O(2^{ell+1}) Toffoli gates and O(log s) ancillas could benefit from a precise construction or citation, because standard unary iteration uses a one-hot register of size 2^{ell+1}; if the intended method is the low-ancilla QROM variant of [KG25], a sentence describing the register reuse would remove ambiguity.","section":"Section 4.1, Lemma 10"},{"comment":"In the simplification leading to Eq. (13), the term n^{1/4} sqrt(ell s) is dropped; a one-line justification of its dominance over n^{3/4} sqrt(s log(s/sqrt(n))) in the regime s>n^{3/2} log n, or keeping the unsimplified expression, would improve rigor.","section":"Section 3, proof of Theorem 9"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the upper bound is the main novelty. The lower-bound gap is real but easy to patch (use |W_n> for n<=s<Cn). I recommend requiring the authors to make that patch and to correct the lemma/theorem numbering before publication. No concerns about citation patterns: the authors' own prior work is cited in the introduction but is not load-bearing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the first sublinear-in-s T-count upper bound for sparse state preparation in the large-support regime, and the support-aware Boolean synthesis behind it is a real idea. The main upper bound should survive review in its Õ form. But don't let the lower bound through as stated: Theorem 12 claims Ω(min{s,√ns}) for all 2≤s≤2^{n/2}, and the proof only covers s≤n (W-state argument) and s≥Cn (packing argument). For n<s<Cn neither applies. The first part of Theorem 12 gives only Ω(√s) there, which is weaker than the claimed Ω(√ns). This is a genuine proof gap, not a manufactured nit. It may be patchable, but the universal statement overreaches.\n\nWhat's good: the label-prep/load/erase reduction is clean, and the recursive compression/peeling lemma is the right mechanism. Corollary 2's Õ(min{s,n^{3/4}√s}) is new relative to VTM25 and RW26. The small-s lower bound via stabilizer nullity of W states is a nice argument. The citation pattern looks fine; the authors' own prior work is not load-bearing.\n\nWhere it's soft: (1) the intermediate-s gap in Theorem 12 described above; (2) Lemma 11's stated big-O bound drops the O(n^{3/2} log n) leaf term, which is not dominated by n^{3/4}√s in ordinary big-O near the threshold. The abstract uses Õ, so the main claim is okay, but Theorems 8 and 9 as written are not literally correct. (3) Minor: the split into s=O(n) and s=Ω(n) in Theorem 12's proof is sloppy with constants, and that sloppiness is the source of the gap.\n\nBottom line: the upper bound is a solid contribution, and the lower-bound gap is localized rather than a sign of a broken approach. I'd send this to peer review and ask for a repair of Theorem 12's range (or a corrected statement) and a cleanup of the O/Õ notation. A serious referee will get value from this.","headline":"A genuinely new sublinear T-count upper bound for sparse state preparation, with a lower-bound theorem that is slightly overclaimed as written.","tokens_in":17511,"tokens_out":6061,"would_cite":true,"duration_ms":48940,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"For any $n$-qubit $s$-sparse state, constant-error preparation costs $\\widetilde{O}(\\min\\{s, n^{3/4}\\sqrt{s}\\})$ T gates, and some states require $\\Omega(\\min\\{s,\\sqrt{ns}\\})$.","keywords":["quantum state preparation","sparse quantum states","T-count","Clifford+T circuits","Toffoli complexity","sparse Boolean functions","stabilizer nullity"],"falsifier":"Implement the relabeling map $\\gamma_G$ for a worst-case $s$-sparse support with few active prefixes and count the Toffoli gates needed; if any instance costs more than $O(\\sqrt{(r-1)2^r})$ Toffoli gates, the recursive Step-1 cost accounting in Lemma 11 fails and the $\\widetilde{O}(n^{3/4}\\sqrt{s})$ upper bound collapses.","tokens_in":16447,"feed_emoji":"⚛️","tokens_out":12510,"duration_ms":93679,"temperature":0.7,"pith_summary":"This paper asks whether the fault-tolerant cost of preparing an $n$-qubit state supported on at most $s$ computational-basis states must grow linearly with $s$. It shows that once the support is large enough the answer is no: any $s$-sparse state can be prepared up to constant error with $\\widetilde{O}(\\min\\{s, n^{3/4}\\sqrt{s}\\})$ T gates, which is sublinear in $s$ when $s$ is much larger than $n^{3/2}$. It also proves a lower bound of $\\Omega(\\min\\{s, \\sqrt{ns}\\})$ T gates for some $s$-sparse states, showing that linear cost is unavoidable when $s=O(n)$ and that a dependence on $n$ persists across the whole range. The practical consequence is that T gates are the expensive fault-tolerant resource, so moving from linear to $\\widetilde{O}(n^{3/4}\\sqrt{s})$ changes which sparse superpositions can plausibly be initialized on early error-corrected machines.","feed_headline":"Sparse states get sublinear T-count once support is large","feed_subtitle":"New support-aware synthesis makes non-Clifford cost sublinear in s, within a small factor of the proven lower bound.","key_machinery":"The load-bearing object is a support-aware synthesis theorem for sparse Boolean functions (Theorem 8). For $F:\\{0,1\\}^n\\to\\{0,1\\}^b$ with $|\\operatorname{supp}(F)|=s$, it gives NCT implementations with $O(s+n)$ Toffoli gates when $s\\le n^{3/2}\\log n$, and $\\widetilde{O}(n^{3/4}\\sqrt{s} + n^{1/4}\\sqrt{bs})$ Toffoli gates when $s>n^{3/2}\\log n$. The recursive algorithm fixes a prefix length $r=\\lceil\\log(s/\\lceil\\sqrt{n}\\rceil)\\rceil$; if few $r$-bit prefixes are active, it injectively relabels them, shortening the input length while keeping the support size fixed, and if many are active, it peels one supported input from each active prefix, cutting the support by $\\Omega(s/\\sqrt{n})$. Choosing the balance parameter $c=\\lceil\\sqrt{n}\\rceil$ makes the two costs meet at $\\widetilde{O}(n^{3/4}\\sqrt{s})$. On the lower-bound side the machinery is stabilizer nullity: a rank bound for stabilizer subgroups with large overlap on $|W_s\\rangle|0^{n-s}\\rangle$ gives $\\Omega((1-\\epsilon^2)s)$ T gates in the small-support regime, and a packing lemma for uniform sparse states combined with the counting bound for states preparable with $t$ T gates gives $\\Omega(\\sqrt{ns})$ in the large-support regime.","core_discovery":"On the paper's own terms, the central discovery is a two-sided T-count characterization for sparse state preparation. The upper-bound side says that every $n$-qubit $s$-sparse state can be $\\epsilon$-approximately prepared from $|0^n\\rangle$ by a Clifford+T circuit using $\\widetilde{O}(\\min\\{s, n^{3/4}\\sqrt{s}\\} + \\sqrt{s\\log(1/\\epsilon)} + \\log(1/\\epsilon))$ T gates, with the sublinear term active once $s>n^{3/2}\\log n$. The lower-bound side says that for every $0<\\epsilon\\le 1/6$ and $2\\le s\\le 2^{n/2}$ there exists an $s$-sparse state requiring $\\Omega(\\min\\{s, \\sqrt{ns}\\})$ T gates for $\\epsilon$-approximate preparation. Together these show that the earlier linear-in-$s$ construction is optimal in the small-support regime, while in the large-support regime a sublinear dependence on $s$ is possible and comes with an unavoidable factor depending on $n$.","pith_inferences":["Inference: the same prefix-compression and support-peeling recursion may transfer to sparse isometry synthesis and to coherent data-loading tasks where the support is known in advance, potentially giving sublinear non-Clifford cost there as well.","Inference: the W-state stabilizer argument suggests that other highly symmetric sparse families, such as Dicke states of fixed Hamming weight, may yield similar approximate lower bounds and could test optimality at intermediate $s$.","Inference: varying the balance parameter $c$ away from $\\lceil\\sqrt{n}\\rceil$ could reveal whether the crossover near $s\\approx n^{3/2}$ is an artifact of this particular choice or a genuine feature of the problem.","Inference: a partial Boolean-function synthesis that only needs correctness on the support might close part of the gap; the paper notes its current construction does not exploit this relaxation in the large-support regime."],"forward_implications":["For $s=O(n)$, the linear $O(s)$ upper bound is tight up to constants, so no sublinear T-count algorithm exists in the small-support regime.","For $\\Omega(n)\\le s\\le 2^{n/2}$, the new construction matches the lower bound up to an $\\widetilde{O}(n^{1/4})$ factor.","The sparse Boolean synthesis theorem stands on its own: any sparse Boolean function with $b$-bit output has the stated Toffoli and ancilla bounds in the NCT model.","Approximate preparation inherits the bounds with an added $\\sqrt{s\\log(1/\\epsilon)}+\\log(1/\\epsilon)$ term."],"supporting_citations":[{"why":"Supplies the linear O(s) Toffoli sparse-state construction and the sparse-support indexing lemma behind the small-support regime.","marker":"[RW26]"},{"why":"Earlier O(s) non-Clifford sparse-state algorithm with max(s-n,0) ancillas; the baseline the new sublinear bound must beat.","marker":"[VTM25]"},{"why":"Provides optimal dense-state preparation with O(sqrt(2^n log(1/epsilon)) + log(1/epsilon)) T gates and the adaptive counting theorem used for the large-s lower bound.","marker":"[GKW26]"},{"why":"Boolean-function synthesis lemma giving O(sqrt(b 2^n)) Toffoli gates, used to implement relabeling, peeling, and support-loading maps.","marker":"[LKS24]"},{"why":"Stabilizer-nullity lower bound on exact T-count, adapted in Lemma 18 to approximate W-state preparation.","marker":"[BCHK20]"},{"why":"Flag-computation and multi-controlled Toffoli gadgets used to detect zero suffixes and compute flags at O(n) Toffoli cost.","marker":"[KG25]"}],"fun_headline_variants":["Sparse-state T-count goes sublinear for large support","First sublinear T-count synthesis for sparse states","Sublinear T-count achieved for sparse quantum states","Sparse states: sublinear T-count via support-aware method","T-count for sparse states drops below linear"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recursive cost accounting assumes each relabeling step costs only $O(\\sqrt{(r-1)2^r})$ Toffoli gates, each peeling step only $O(\\sqrt{(m-r)2^r}+\\sqrt{b2^{r+1}}+m)$, and that all temporary ancillas can be reused in a single scratch space across recursive levels.","fun_headline_variants_meta":{"raw":{"variants":["Sparse-state T-count goes sublinear for large support","First sublinear T-count synthesis for sparse states","Sublinear T-count achieved for sparse quantum states","Sparse states: sublinear T-count via support-aware method","T-count for sparse states drops below linear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000238,"raw_usage":{"total_tokens":1560,"prompt_tokens":1047,"completion_tokens":513,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":663,"completion_tokens_details":{"reasoning_tokens":438}},"tokens_in":663,"tokens_out":513,"duration_ms":4861,"temperature":1.0,"reasoning_tokens":438,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:23:33.118661+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the relabeling map $\\gamma_G$ for a worst-case $s$-sparse support with few active prefixes and count the Toffoli gates needed; if any instance costs more than $O(\\sqrt{(r-1)2^r})$ Toffoli gates, the recursive Step-1 cost accounting in Lemma 11 fails and the $\\widetilde{O}(n^{3/4}\\sqrt{s})$ upper bound collapses.","supporting_citations":[],"review_version":2}