{"id":"f804faec-e17f-4767-af43-1984e67768d2","arxiv_id":"2508.05386","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A synthesis algorithm prepares sparse n-qubit states with T-count O(sqrt(s log(1/epsilon)) + log(1/epsilon)), matching the optimal full-state preparation bound of Gosset et al.","lead":"This paper reports a new method for preparing sparse quantum states with quantum circuits, where the resources scale with the number of nonzero entries rather than the full system size. It matters because sparse state preparation is a common subroutine, and reducing non-Clifford gates lowers the cost of fault-tolerant quantum computation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed T-count relies on replacing Toffoli by adaptive Cliffords; if this replacement hides non-Clifford costs, the central bound is undercounted.","rationale":"The reader's verdict is UNVERDICTED with LOW confidence, based on the abstract only. My stress-test identifies the same weakest point: the adaptive-Clifford replacement of Toffoli gates. This is the single most load-bearing assumption in the abstract because the T-count bound is the paper's headline result, and the replacement is the mechanism that supposedly reduces the cost of the permutation circuit. The concern is not that the paper disagrees with standard results; rather, the abstract's phrasing suggests a deterministic non-Clifford operation can be implemented 'for free' by adaptive Cliffords, which would contradict the Gottesman-Knill theorem unless non-Clifford resources are hidden or the operation is restricted to a special subspace. Since the full text is unavailable, I cannot determine whether the paper provides a valid proof of the replacement on the W-state support. Therefore, the verdict remains UNVERDICTED; no change is needed. I agree with the reader's weakest_assumption, which also identified the resource-accounting risk. The proposed concrete test would settle the concern by checking the actual replacement circuit's resource count and correctness on the smallest non-trivial case.","tokens_in":838,"tokens_out":12385,"duration_ms":145328,"concrete_test":"Extract from the paper the explicit adaptive-Clifford circuit used to replace a single Toffoli gate in the smallest non-trivial case (e.g., s=2 or a 3-qubit permutation). Implement this replacement using only Clifford gates and Pauli measurements with feedforward, starting from the relevant W-state support, and check that the output equals the Toffoli output. If it does not, identify the non-Clifford ancilla states or measurements used, count the T gates required to prepare them (including magic-state distillation if needed), and recompute the total T-count against the claimed bound. An independent check is to run a stabilizer-simulator search over all Clifford+measurement circuits to see whether any implements the Toffoli truth table on all computational basis inputs; if none exists, the replacement must rely on hidden non-Clifford resources.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's central T-count bound, O(sqrt(s log(1/epsilon)) + log(1/epsilon)), depends on the assertion that all Toffoli gates in the permutation circuit can be replaced by adaptive Clifford circuits when the circuit is applied in one direction. This is load-bearing because the permutation circuit is the part of the construction that maps the W-state support to the target sparse state; if the replacement actually requires non-Clifford resources that are not counted in the T-count, the claimed asymptotic saving disappears. In the standard quantum circuit model, a deterministic Toffoli gate is not a Clifford operation, and Clifford gates plus Pauli measurements with feedforward map stabilizer states to stabilizer states (Gottesman-Knill). Therefore, an exact Toffoli cannot be implemented by adaptive Clifford operations on arbitrary inputs without a non-Clifford ancilla or non-Clifford measurement basis. The abstract does not state whether such non-Clifford resources are consumed and how their cost is accounted for, nor whether the replacement is valid only on the specific W-state support. This is a correctness risk, not merely a disagreement with a consensus: either the T-count must include the cost of preparing the non-Clifford resources, or the replacement must be proved to act as a Toffoli on the restricted subspace using only Clifford operations. Without the full proof, the central claim is unverified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript (abstract-only review) proposes an algorithm for synthesizing quantum circuits that prepare sparse quantum states, emphasizing non-Clifford cost. The construction first prepares a generalized W-state and then applies a permutation circuit implemented by classical reversible gates, reduced to diagonalizing a binary matrix via a custom Gauss-Jordan elimination. The abstract claims that, with arbitrary-angled rotations, circuit depth, ancilla count, and non-Clifford count are linear in sparsity s; compiled to Clifford+T, the most optimized construction achieves T-count O(sqrt(s log(1/epsilon)) + log(1/epsilon)), matching the full-state preparation bound of Gosset et al. The key asserted simplification is that all Toffoli gates in the permutation circuit can be replaced by adaptive Clifford circuits when the circuit is applied in one direction. The full text, proofs, and numerical/complexity analysis were not available for review.","tokens_in":1165,"tokens_out":4042,"duration_ms":43736,"significance":"If the claims are correct, this would be a substantial contribution: sparse state preparation with asymptotically optimal T-count and tunable trade-offs among depth, ancillae, and T gates would improve a building block for many quantum algorithms. The use of adaptive Clifford operations to simulate Toffoli-like behavior on a restricted subspace is surprising and would be the main novelty. The manuscript also appears to avoid parameter fitting and externally compares against an established optimal bound, which is a strength. However, because only the abstract was reviewed, the central correctness and resource-accounting arguments are unverified; the value of the contribution hinges on the missing proof.","major_comments":[{"comment":"The central T-count bound O(sqrt(s log(1/epsilon)) + log(1/epsilon)) rests on the sentence 'all occurrences of the expensive Toffoli gates can all be replaced by adaptive Clifford circuits.' The abstract does not specify whether this replacement is exact on all inputs or only on the particular W-state support, nor what non-Clifford resources are consumed by the adaptive measurements/ancillae. In the stabilizer formalism, adaptive Clifford operations on stabilizer inputs cannot compute a Toffoli gate exactly; if the replacement exploits the restricted input subspace, a proof of correctness on that subspace is needed and is not provided in the abstract. The T-count must include the cost of preparing any non-Clifford ancilla or the error from approximate synthesis. Without this, the claimed asymptotic saving is undercounted.","section":"Abstract, last sentence"},{"comment":"The abstract states that depth, ancilla count, and non-Clifford count are 'all linear in the sparsity' with arbitrary rotations, then later presents constructions with 'increasingly better T-count and depth at the expense of a larger number of ancillae.' The trade-off is not quantified: the optimized T-count construction's ancilla count and depth are not stated. The comparison to Gosset et al. is therefore incomplete; 'on par' may be misleading if ancilla or depth costs are hidden in a constant or log factor that changes the resource trade-off.","section":"Abstract, resource claims (linearity and trade-offs)"},{"comment":"No error model or metric is defined. The T-count depends on epsilon, but the abstract does not say whether epsilon is the total variation distance, trace distance, fidelity deviation, or a component-wise error, nor how errors from rotation synthesis and from the permutation circuit compose. Without an explicit error analysis, the bound cannot be verified.","section":"Abstract, 'error epsilon'"}],"minor_comments":[{"comment":"The abstract mentions Gosset et al. but gives no citation; it would be helpful to provide the reference and clarify whether the comparison is to a lower bound or to a constructive algorithm.","section":"Abstract, references"},{"comment":"The description is vague. Please specify the elementary matrix operations, the notion of parallel elimination, and how the resulting reversible circuit realizes the target permutation with bounded depth.","section":"Abstract, 'a new version of Gauss-Jordan elimination'"},{"comment":"There is a minor inconsistency in spelling ('optimised' vs 'optimized') and the phrase 'all occurrences of (the expensive) Toffoli gates' is ambiguous between occurrence count and T-count per Toffoli; the latter matters for the resource bound.","section":"Abstract, wording"}],"recommendation":"uncertain","confidential_remarks":"This is an abstract-only review; I cannot verify whether the full paper contains a rigorous proof of the adaptive-Clifford replacement on the W-state support and a complete error analysis. The central concern in my public report is the resource accounting for the replacement of Toffoli gates. If the full text provides a correct proof of that lemma and a clear error metric, the paper could be a strong contribution. I recommend obtaining the full manuscript before making a final editorial decision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper makes a strong, concrete claim—sparse state preparation with T-count O(sqrt(s log(1/epsilon)) + log(1/epsilon)), matching the full-state optimal bound from Gosset et al. The decomposition into a W-state preparation plus a reversible permutation circuit is a clean reduction, and the new Gauss-Jordan variant that minimizes depth looks like a genuine piece of work. But the central trick—replacing all Toffoli gates with adaptive Clifford circuits—is the make-or-break claim, and the abstract does not show how the non-Clifford resources are accounted for.\n\nI share the stress-test concern. A Toffoli is not a Clifford operation. Adaptive Clifford circuits (Clifford gates, Pauli measurements, feed-forward) map stabilizer states to stabilizer states, so they cannot deterministically implement a Toffoli on arbitrary inputs without consuming a non-Clifford ancilla or some other non-Clifford resource. The abstract says this replacement works when the circuit is applied in one direction, which might mean the input is restricted to the W-state support. But because the circuit is linear, it must act correctly on the entire subspace spanned by that support, and that is exactly where a rigorous proof is needed. If the replacement requires non-Clifford ancillas, their preparation cost has to be included in the T-count; if it does not, the claim is surprising enough that a referee should check the algebra carefully.\n\nThe abstract also leaves the epsilon dependence unanalyzed—no constants, no overhead in ancillas or depth. That is normal at the abstract level, so I do not hold it against the paper.\n\nOn the positive side, the approach is new as far as I know. The reduction to diagonalizing a binary matrix with a custom Gauss-Jordan elimination targeting circuit depth is clever and directly aimed at the fault-tolerant setting. If the adaptive-Clifford claim holds up, the asymptotic improvement is significant.\n\nMy honest take: this deserves a serious referee. I would not desk-reject it based on the abstract. Send it to review with an explicit instruction to focus on the adaptive-Clifford replacement and the resource accounting.","headline":"The sqrt-sparsity T-count bound is attractive and the algorithm is well-structured, but the load-bearing claim that all Toffolis can be replaced by adaptive Clifford circuits needs a rigorous proof before the bound is believable.","tokens_in":1586,"tokens_out":4356,"would_cite":true,"duration_ms":45594,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Sparse quantum state synthesis matches optimal non-Clifford cost","keywords":["sparse quantum states","state preparation","T-count","Clifford+T","reversible circuits","permutation synthesis","Gauss-Jordan elimination","adaptive Clifford circuits"],"falsifier":"Take a specific sparse state, say a uniform superposition over $s=4$ basis states on $n=4$ qubits, run the algorithm, and count the T gates in the compiled circuit for a fixed $\\epsilon$. If the count does not scale as $\\mathcal{O}(\\sqrt{s\\log(1/\\epsilon)} + \\log(1/\\epsilon))$—or if replacing the Toffolis with adaptive Clifford circuits requires additional T gates for the feed-forward operations—the central bound fails. A direct check is to verify that the one-directional permutation circuit after the replacement contains zero Toffoli gates while still implementing the correct permutation.","tokens_in":780,"feed_emoji":"⚛️","tokens_out":5379,"duration_ms":56166,"temperature":0.7,"pith_summary":"This paper shows how to prepare any sparse quantum state—one with at most $s$ nonzero amplitudes—with a non-Clifford gate count that is linear in $s$ when arbitrary angle rotations are available, and that, after compilation to Clifford+T, reaches $\\mathcal{O}(\\sqrt{s\\log(1/\\epsilon)} + \\log(1/\\epsilon))$ T gates for error $\\epsilon$. That matches the best known bound for preparing fully dense states, so sparsity stops being a reason to pay extra. The algorithm separates the task into building a generalized W-state and then applying a classical reversible permutation that relabels the W-state's basis states to the support of the target. The permutation is synthesized by diagonalizing a binary matrix with a new Gauss-Jordan elimination that minimizes circuit depth. The paper's key observation is that when the permutation circuit is run in one direction, every expensive Toffoli gate can be replaced by an adaptive Clifford circuit, which lowers the non-Clifford count.","feed_headline":"Sparse quantum state prep matches optimal T-count","feed_subtitle":"New algorithm splits the state into W-state plus permutation, then removes costly Toffolis with adaptive Clifford circuits.","key_machinery":"The central objects are (1) the decomposition of a sparse state into a generalized W-state followed by a classical reversible permutation, and (2) a Gauss-Jordan elimination over the binary field $\\mathrm{GF}(2)$ that diagonalizes the permutation's matrix using elementary operations that map to reversible gates. The elimination is designed to minimize depth by performing independent elimination steps in parallel. The second load-bearing mechanism is the replacement of all Toffoli gates by adaptive Clifford circuits when the circuit is applied in one direction; this is what brings the non-Clifford count down to the stated bound.","core_discovery":"The central claim is that the non-Clifford (T-gate) cost of preparing an $s$-sparse $n$-qubit state can be reduced to $\\mathcal{O}(\\sqrt{s\\log(1/\\epsilon)} + \\log(1/\\epsilon))$ T gates for error $\\epsilon$, matching the optimal asymptotic performance of full state preparation. The construction is modular: first synthesize a generalized W-state whose support matches the target state, then apply a classically specified reversible permutation that maps the W-state's basis states to the correct amplitudes. The reversible permutation is obtained by solving a binary-matrix diagonalization problem using elementary row operations that correspond to reversible logic gates, and the new elimination pro","pith_inferences":["The same binary-matrix diagonalization approach may extend to synthesizing other reversible circuits—for instance, isometries or sparse unitaries—by finding a minimal set of elementary row operations; the paper does not claim this.","The adaptive replacement of Toffoli gates suggests a general design principle: circuits applied only in one direction can shift non-Clifford costs into classical feed-forward. Testing this on other reversible subroutines could reveal broader T-count savings.","The depth-minimizing Gauss-Jordan elimination might also be useful outside quantum computing, as a classical algorithm for reversible circuit synthesis with bounded depth.","The paper's bound is asymptotic; a concrete open question is the constant factor and whether a tight lower bound exists for sparse-state preparation specifically."],"forward_implications":["Preparing an $s$-sparse state costs $\\mathcal{O}(\\sqrt{s\\log(1/\\epsilon)} + \\log(1/\\epsilon))$ T gates, so sparsity no longer forces a larger non-Clifford overhead than dense state preparation.","The circuit depth, ancilla count, and non-Clifford count are all linear in sparsity when arbitrary-angled rotations are allowed, giving a clean resource profile for early fault-tolerant settings.","With compilation to Clifford+T, the algorithm offers a family of constructions trading larger ancilla counts for lower T-count and depth, ending at the near-optimal T-count bound.","The permutation part of the construction is solved through binary-matrix diagonalization, meaning the reversible circuit's depth is controlled by parallel elimination steps."],"supporting_citations":[],"fun_headline_variants":["Sparse state prep hits optimal T-gate bound","Quantum sparse synthesis: optimal T-count achieved","W-state plus permutation matches full-state T-cost","Adaptive Clifford circuits remove costly Toffoli gates","Sparse state synthesis with optimal T-gate scaling"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The central resource savings assume that mid-circuit measurement and feed-forward are available at negligible non-Clifford cost; if a target fault-tolerant architecture charges real non-Clifford resources for adaptive operations, the promised T-count bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Sparse state prep hits optimal T-gate bound","Quantum sparse synthesis: optimal T-count achieved","W-state plus permutation matches full-state T-cost","Adaptive Clifford circuits remove costly Toffoli gates","Sparse state synthesis with optimal T-gate scaling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000666,"raw_usage":{"total_tokens":2928,"prompt_tokens":851,"completion_tokens":2077,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":2004}},"tokens_in":595,"tokens_out":2077,"duration_ms":16863,"temperature":1.0,"reasoning_tokens":2004,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:21:49.192851+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a specific sparse state, say a uniform superposition over $s=4$ basis states on $n=4$ qubits, run the algorithm, and count the T gates in the compiled circuit for a fixed $\\epsilon$. If the count does not scale as $\\mathcal{O}(\\sqrt{s\\log(1/\\epsilon)} + \\log(1/\\epsilon))$—or if replacing the Toffolis with adaptive Clifford circuits requires additional T gates for the feed-forward operations—the central bound fails. A direct check is to verify that the one-directional permutation circuit after the replacement contains zero Toffoli gates while still implementing the correct permutation.","supporting_citations":[],"review_version":1}