{"id":"cba174ee-a5d1-405e-8910-5b8e3c51a7f6","arxiv_id":"2504.15128","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A polynomial-time approximate simulation of Clifford circuits with small sparse Markovian errors, including coherent errors, demonstrated on circuits with up to 241 qubits.","lead":"Sandia researchers introduce a classical algorithm that can simulate Clifford quantum circuits with small coherent errors, not just random stochastic noise, by tracking sparse error generators and expanding the circuit error perturbatively. It scales to hundreds of qubits, and the authors use it to show coherent gate errors can roughly triple or reduce effective error rates in surface code syndrome extraction circuits.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Deep random-circuit benchmark violates the stated small-total-error condition, leaving the million-gate demonstration without a controlled expansion parameter.","rationale":"The reader's weakest assumption is the expansion-validity premise, and my analysis lands on the same point. The central claim of an efficient approximate simulation algorithm requires a controlled approximation error, but the paper states only a heuristic condition (total error ε small) and gives no theorem bounding the truncation error. The deep random-circuit example, which is a headline demonstration, has a naive summed rate ε≈18.4 and includes data points with non-negligible exact infidelity, so the stated condition is not met there. The GHZ example provides useful but limited support because it uses commuting Z errors and a small total rate; the supplemental BiRB example explicitly shows that first-order Taylor truncation can be inaccurate at modest depth, increasing the concern that order-dependent effects are uncontrolled in the deep circuits. This does not refute the algorithm for genuinely small total error, but it does mean the paper's strongest application is not backed by its stated validity condition. The reader's CONDITIONAL verdict already requires clarification of this issue, so my read does not move the verdict; the concrete convergence check identified here would settle whether the concern actually lands.","tokens_in":22980,"tokens_out":8954,"duration_ms":92314,"concrete_test":"Recompute one deep random-circuit point used in Fig. 3d, e.g. n=225, d=8196, θ=1e-5, ξ=0.25, at two expansion orders: k=1,l=2 and k=2,l=3 (or, if the full k=2,l=3 expansion is infeasible, compare the k=1 process-fidelity formula in Eq. (28) against the k=2 BCH correction). In the same run, report the operator norm of the first-order generator Ω_1 and the naive total error ε≈18.4. If the process infidelity changes by more than about 10% between orders, or if ||Ω_1|| is not small (say >0.1), then the deep-circuit results are outside the controlled regime and the benchmark should be re-scaled so that ε≤O(1), or accompanied by a validated effective small parameter.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing premise is the expansion-validity condition stated in the Simulation algorithm section: the BCH and Taylor truncations are valid only when the total error ε = Σ_{i,G∈S_i}|ε_{i,G}| is small. No rigorous error bound is provided for these truncations, and the deep random-circuit example violates the stated condition by a wide margin. With n=225, d=8196, and θ=1e-5 per qubit per layer, ε ≈ 225 × 8196 × 1e-5 ≈ 18.4. At ξ=0 the exact analytic infidelity is already non-perturbative (1−cos^{450}(dθ/2) ≈ 0.3), so the plotted range is not confined to a small-error regime. The paper does not identify a replacement effective small parameter, such as the actual operator norm of the first-order BCH generator Ω_1 after Clifford averaging, so the reported infidelity curves in Fig. 3d are not controlled by the stated assumptions. The supplemental BiRB validation also shows that truncation order matters: at depth 16 with small rates, first-order Taylor visibly overestimates energies and second-order is needed (Supplemental Figs. 5–6). No equivalent convergence check is provided at depth 8196. Thus the central demonstration of simulating circuits with over a million gates under coherent errors rests on an unverified expansion-validity assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces an efficient classical algorithm for approximate strong simulation of Clifford circuits subject to sparse, small Markovian noise, including coherent errors. The algorithm propagates each layer's error generator to the end of the circuit using Clifford-conjugation rules for the elementary error generator (EEG) basis, combines the propagated generators with a k-th order Baker-Campbell-Hausdorff (BCH) expansion, and evaluates outcome probabilities or Pauli expectation values using an l-th order Taylor expansion. The authors claim polynomial runtime for fixed k and l when sparsity and depth are polynomial in n, and they demonstrate the method on three examples: a 100-qubit GHZ preparation/un-creation circuit validated against an analytic solution; 225-qubit random Clifford circuits up to depth 8196 (over 1.8 million gates); and syndrome extraction circuits for rotated surface codes of distance 3 to 11 (up to 241 qubits). The surface-code study reports that coherent errors can increase or decrease marginal error rates by factors of about 3 and 0.33, respectively, relative to stochastic models with the same gate fidelity.","tokens_in":23192,"tokens_out":11663,"duration_ms":104618,"significance":"If the approximation error is controlled, the paper provides a substantial extension of efficient noisy-Clifford simulation beyond stochastic Pauli noise to general small sparse Lindbladian noise, including coherent errors. The supplemental derivations of EEG commutation relations and of measurement/expectation-value formulae are self-contained, and the GHZ and binary randomized benchmarking (BiRB) validations provide meaningful checks; the BiRB comparison against exact simulation in particular demonstrates that the algorithm can capture the energy distribution, not just its mean, for 10 qubits. The surface-code results on coherent amplification and suppression are physically interesting and, to the best of my knowledge, go beyond what existing specialized methods (e.g., tensor networks or z-error-only models) can efficiently access at this scale. The open-source implementation in pyGSTi with the use of stim is a further practical strength. However, the central demonstration on deep random circuits appears to operate outside the stated small-total-error regime, so the claimed performance there is not yet supported by the paper's own validity condition.","major_comments":[{"comment":"The stress-test concern is well-founded: the deep random-circuit benchmark violates the stated expansion-validity condition. The text says the expansions are valid when the total error ε = Σ_{i,G∈S_i}|ε_{i,G}| is small. For the random circuits, n=225, d=8196, and each qubit receives a coherent rotation θ=1e-5 per layer, giving ε ≈ n d θ ≈ 18.4, which is not O(1). At ξ=0 the exact analytic infidelity is 1−cos^{450}(dθ/2) ≈ 0.31, so the plotted range is not confined to a small-error regime. No alternative effective small parameter is identified, and no convergence check (e.g., comparing k=1 vs. k=2 or l=1 vs. l=2) is reported at depth 8196. Since the BiRB validation in the supplement (Supplemental Figs. 5–6) shows that at depth 16 the first-order Taylor expansion systematically overestimates energies and second-order is needed, the depth-8196 curves in Fig. 3d require either a rigorous error bound, a demonstration of an effective small parameter in this regime, or additional convergence checks at representative depths.","section":"Simulation algorithm and Fig. 3d"},{"comment":"The computation of process fidelity in the random-circuit example is not fully specified. The Methods state that the process fidelity is well-approximated by Eq. (28), and the main text says that at ξ=0 the algorithm's prediction agrees closely with the exact formula cos^{2n}(dθ/2). However, for the stated parameters, the leading-order formula (28) with per-qubit cumulative rotation dθ gives a process infidelity of order n(dθ)^2 ≈ 1.5, whereas the exact infidelity is approximately 0.31. The manuscript should explain how the process fidelity is actually evaluated in this example (e.g., whether the exact exponential of the commuting first-order generator is used, and how this is done efficiently) and why Eq. (28) is applicable, or state which alternative formula is used.","section":"Methods: Computing a circuit's process fidelity"},{"comment":"The expansion orders (k,l) are not stated for the random-circuit example. The GHZ example explicitly sets k=1, l=2, but the random-circuit section does not specify the orders. Because the truncation error depends strongly on the Taylor order at large depth, as shown by the BiRB validation, the authors should state k and l for each example and provide evidence that the retained orders suffice, for instance by reporting the difference between l=1 and l=2 (or k=1 and k=2) for a subset of the plotted parameters at depth 8196.","section":"Example applications: Coherent error scrambling in random circuits"},{"comment":"The validity condition for the perturbative expansions is given without a precise error bound. The text defines ε twice with different meanings: within the BCH term-size statement ε bounds the maximum per-gate rate, while the validity condition uses the summed rates Σ|ε_{i,G}|. These are different quantities, and the accuracy of the approximation depends on both the sizes of the individual rates and the commutation structure of the propagated generators. A precise statement of the approximation error, such as an operator-norm bound on the difference between E_c and the BCH/Taylor approximation in terms of the summed rates, the expansion orders, and the number of non-commuting terms, would make the algorithm's guarantees testable. This is particularly important because the surface-code example uses θ=0.001 across many gates, so its summed error may also be borderline.","section":"Methods: Perturbative expansions"}],"minor_comments":[{"comment":"The symbol k is used for the BCH order in the algorithm description but is reused for the Taylor order in Eq. (30) and the following paragraph. Using distinct symbols (e.g., k_B and k_T) would eliminate ambiguity.","section":"Notation (Eq. 30 and surrounding text)"},{"comment":"The Introduction and the random-circuit section give different depth values: the Introduction says depth up to 8192, while the Example applications section says 8196 layers (and Fig. 3c caption says 8192). These should be harmonized.","section":"Introduction vs. Example applications"},{"comment":"The sentence 'To simulate these circuits, we set k = 1 and l = 2 in our algorithm' appears immediately after the GHZ description, but it could be misread as applying to the subsequent random-circuit example. Rephrase to make clear that these orders are for the GHZ example.","section":"Example applications: GHZ setup"},{"comment":"The statement that Python notebooks 'will be released shortly' is weaker than the usual availability expectation and does not provide a persistent repository or version. Providing a DOI or a stable public repository link would improve reproducibility.","section":"Code and Data Availability"},{"comment":"The convention for θ differs between examples: in the random-circuit section θ appears to be the rotation angle, while in the surface-code section θ corresponds to twice the rotation angle (as stated in the text). Making this convention explicit at each use is important because it directly affects the total-error estimates and the comparison to the analytic formula.","section":"Throughout the examples"},{"comment":"The paper does not report the actual runtime of the three example simulations beyond saying they are feasible on a laptop. A brief table of runtimes and the parameters (n, d, k, l, κ) would help readers assess the practical scalability of the method.","section":"Methods: Random circuits simulation"}],"recommendation":"major_revision","confidential_remarks":"This is a strong submission from a well-established group, and the core algorithm is likely correct and useful. The main problem is the mismatch between the stated small-total-error validity condition and the deep random-circuit demonstration, which currently acts as the paper's flagship 'million gates' result. I believe this is fixable within the scope of a major revision: the authors can either add a rigorous error analysis and convergence checks at large depth, or reframe the random-circuit example as a demonstrated scaling of the method without claiming it is in the rigorous small-error regime. I would not recommend rejection, but I would want to see the expansion-validity question resolved before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is the first efficient strong-simulation method I know of for Clifford circuits with general small Markovian errors, including coherent ones, and the core idea is clean: propagate sparse error generators through the Clifford circuit using exact conjugation formulas, then combine them with BCH and Taylor expansions. The supplement is real work, not hand-waving, and the GHZ and BiRB validations are honest checks against exact answers. Second, the flagship demonstration—225 qubits, depth 8196, over a million gates—operates outside the paper's own stated validity condition. The text says the expansions are valid when the total error epsilon = sum of all |epsilon_i,G| is small. For that example epsilon is roughly n*d*theta/2 ≈ 9, not O(1). No replacement small parameter is identified, and there is no convergence check at depth 8196. That does not sink the algorithm, but it means the headline capability is not controlled by the stated theory.\n\nWhat is genuinely new: the combination of the EEG basis from Blume-Kohout et al. with Clifford conjugation, BCH, and Taylor expansion to compute outcome probabilities and Pauli expectations in polynomial time. The sign rules for conjugation, the EEG commutator formulas, and the stabilizer-state expectation formulas are all derived in the supplement, and the derivations are self-contained. The GHZ test agrees with the analytic result, and the BiRB comparison against exact simulation shows the Taylor order matters, which is the right kind of sanity check. The surface-code amplification results are timely and concrete, and the sensitivity-matrix approach for scanning the 18-parameter noise model is a nice practical bonus.\n\nSoft spots, in proportion. The lack of a rigorous error bound on the BCH/Taylor truncation is the deepest issue. The paper states a small-epsilon condition but does not prove a bound, and the BiRB supplement itself shows that first-order Taylor visibly overestimates at depth 16, requiring second order. For the deep random circuits, the paper does not demonstrate that the series is converging at all. This is addressable—for instance, by identifying the actual small parameter after Clifford averaging or by comparing expansion orders at the depths used—but as written it leaves the million-gate claim unsupported. Also, the code and notebooks are promised but not yet released, so the exact numbers in Figs. 1 and 3 are not independently reproducible yet; that is a real but minor issue.\n\nWho this is for: anyone doing QCVV or QEC simulation who cares about coherent errors. The algorithm fills a gap that has been annoying for years, and the applications are meaningful. It deserves a serious referee, and I would send it out with the expectation of heavy revision: the authors should be asked to clarify the expansion parameter, add a convergence check at depth, and release code. I would not desk-reject this.","headline":"A genuinely new poly(n) strong-simulation algorithm for Clifford circuits with small coherent errors, but the flagship million-gate benchmark runs outside the stated small-error regime and no truncation bound is supplied.","tokens_in":23775,"tokens_out":4133,"would_cite":true,"duration_ms":42044,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"Clifford circuits with small coherent errors can be simulated classically in polynomial time.","keywords":["Clifford circuits","classical simulation","coherent errors","Lindbladian noise","elementary error generators","surface codes","randomized benchmarking","stabilizer states"],"falsifier":"Run the algorithm with $k=1, l=2$ on the 100-qubit GHZ create-and-uncreate circuit while increasing the per-gate rotation angle $\\theta$ so that the accumulated phase $\\theta_{\\mathrm{acc}}$ approaches order one, and compare the predicted success probability to the exact value $p_0 = \\cos^2(\\theta_{\\mathrm{acc}}/2)$; a growing discrepancy would confirm that the expansion's small-total-error premise, not the sparsity representation, is the limiting precondition.","tokens_in":1643,"feed_emoji":"⚛️","tokens_out":6318,"duration_ms":87282,"temperature":0.7,"pith_summary":"This paper claims that noisy Clifford circuits with small, sparse Markovian errors—including coherent (unitary) errors—can be classically simulated in polynomial time, a task previously out of reach whenever the noise is not purely stochastic. The algorithm writes each layer's error as a sparse Lindbladian in an elementary-error-generator basis, propagates all errors to the end of the circuit using Clifford conjugation, and then combines them with Baker-Campbell-Hausdorff and Taylor expansions. If correct, it provides an efficient strong simulator for this error class and makes concrete problems tractable, such as quantifying how coherent errors amplify or suppress syndrome flips in surface-code circuits with hundreds of qubits. Demonstrations include 100-qubit GHZ circuits with analytic cross-checks, 225-qubit random circuits with over a million gates, and syndrome extraction circuits for distance-3 through 11 rotated surface codes.","feed_headline":"Coherent errors on Clifford circuits simulated in polynomial time","feed_subtitle":"A new algorithm handles sparse Lindbladian noise, including unitary errors, on hundreds of qubits.","key_machinery":"The machinery is the elementary error generator (EEG) basis for n-qubit Lindbladians, together with three analytic capabilities it enables: exact symbolic commutation of any two basis elements, conjugation of any element by a Clifford superoperator to another signed element, and evaluation of expectation values after an element acts on a stabilizer state. These turn 'propagate all noise to the end, then expand' into a polynomial algorithm. Sparsity is the load-bearing structural fact: a noise model with $\\kappa$ generators per layer stays $\\kappa$-sparse under Clifford conjugation, and the BCH and Taylor steps produce only $O((d\\kappa)^k)$ and $O((d\\kappa)^{kl})$ terms, respectively, for expansion orders $k$ and $l$.","core_discovery":"The central discovery is that sparsity of an n-qubit error process is preserved when its generators are conjugated by Clifford gates, so a whole noisy Clifford circuit can be compressed into a single sparse Lindbladian before any perturbative approximation. Because the elementary error generators form a basis and transform under Clifford conjugation to signed basis elements, the error channels can be pushed to the end of the circuit exactly and efficiently. The remaining exponential cost is avoided by a kth-order BCH combination of the propagated Lindbladians and an lth-order Taylor expansion of the resulting channel, yielding a polynomial-term approximation to the circuit's error map. From that approximation, outcome probabilities, Pauli expectation values, and process fidelities are evaluated with stabilizer-state formulas. The paper reports simulations on up to 241 qubits and circuits of over a million gates.","pith_inferences":["A direct stress test suggested by the paper's own validity condition would be to fix k=1, l=2 and increase the total error epsilon to order one on a shallow Clifford circuit where exact simulation remains feasible, checking where the approximate outcome probabilities diverge from exact ones.","Because the algorithm returns entire sensitivity matrices, one could close the loop on calibration: use coherent amplification factors as an objective to tune single-qubit rotation angles so that errors cancel within a surface-code syndrome extraction cycle, an optimization the paper suggests but does not run.","The poly(n) guarantee holds for fixed expansion orders k and l; a useful benchmark is to measure how quickly approximation error degrades as circuit depth grows at fixed per-gate error rate, since total error typically grows with depth.","The approach is likely to combine with gate-set-tomography-style fitting, since the same sparse Lindbladian representation is the natural parameterization for fitting noise models to experimental data; the paper notes this possibility but stops short of demonstrating it."],"forward_implications":["Syndrome extraction circuits for distance-3 through 11 rotated surface codes can be simulated with coherent gate errors, revealing up to roughly a 3-fold enhancement and a 0.33-fold suppression of marginal qubit error rates relative to stochastic noise of equal gate fidelity.","Deep random 225-qubit Clifford circuits of depth up to 8196 show process infidelities that grow by up to about 1000-fold as scrambling power decreases, and remain roughly 10-fold above the perfect-scrambling limit even at the highest simulated Hadamard density.","The algorithm computes analytic sensitivity matrices, such as S_omega for syndrome bit-flip rates, giving leading-order dependence of observables on all coherent error parameters simultaneously and with little additional computational cost.","The method extends beyond the demonstrated examples to non-Markovian noise by promoting error rates to time-dependent stochastic processes, and to learning sparse Lindblad noise models from experimental data.","The algorithm also applies to randomized benchmarking circuits, as demonstrated on binary randomized benchmarking circuits with mixed coherent, incoherent, and non-unital errors, where second-order Taylor terms correct a systematic overestimate at larger depths."],"supporting_citations":[{"why":"Supplies the elementary error generator basis and the taxonomy of sparse Markovian errors that the whole simulation representation relies on.","marker":"[21]"},{"why":"Provides the stabilizer-state and Clifford simulation primitives used to carry out the Pauli and stabilizer computations efficiently.","marker":"[2]"},{"why":"Gives the symplectic representation of Clifford unitaries used to compute how Pauli operators and error generators transform under conjugation.","marker":"[3]"},{"why":"Underlies the Baker-Campbell-Hausdorff expansion used to combine propagated layer error generators into a single circuit-level Lindbladian.","marker":"[59]"},{"why":"Defines the process fidelity and error-generator quantities the algorithm computes, and motivates the fidelity approximation in terms of stochastic and Hamiltonian rates.","marker":"[15]"},{"why":"Defines unitary 2-designs, used as the analytic perfect-scrambling limit against which the random-circuit infidelity simulations are compared.","marker":"[60]"}],"fun_headline_variants":["Sparse Lindbladians enable polynomial-time simulation of coherent errors","Clifford circuits with coherent noise: efficient simulation now possible","Polynomial-time algorithm simulates coherent errors on Clifford circuits","Millions of gates and hundreds of qubits: coherent errors simulated","Sparse noise model tames coherent errors in Clifford simulation"],"cache_read_input_tokens":25856,"weakest_assumption_plain":"The algorithm's accuracy rests on the total error $\\epsilon = \\sum_{i,G\\in S_i}|\\epsilon_{i,G}|$ being small enough that low-order BCH and Taylor truncations dominate the error map.","fun_headline_variants_meta":{"raw":{"variants":["Sparse Lindbladians enable polynomial-time simulation of coherent errors","Clifford circuits with coherent noise: efficient simulation now possible","Polynomial-time algorithm simulates coherent errors on Clifford circuits","Millions of gates and hundreds of qubits: coherent errors simulated","Sparse noise model tames coherent errors in Clifford simulation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000259,"raw_usage":{"total_tokens":1537,"prompt_tokens":847,"completion_tokens":690,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":463,"completion_tokens_details":{"reasoning_tokens":605}},"tokens_in":463,"tokens_out":690,"duration_ms":6670,"temperature":1.0,"reasoning_tokens":605,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:33:30.851349+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm with $k=1, l=2$ on the 100-qubit GHZ create-and-uncreate circuit while increasing the per-gate rotation angle $\\theta$ so that the accumulated phase $\\theta_{\\mathrm{acc}}$ approaches order one, and compare the predicted success probability to the exact value $p_0 = \\cos^2(\\theta_{\\mathrm{acc}}/2)$; a growing discrepancy would confirm that the expansion's small-total-error premise, not the sparsity representation, is the limiting precondition.","supporting_citations":[{"cited_title":"Blume-Kohout, M","cited_arxiv_id":null,"evidence_quote":"Supplies the elementary error generator basis and the taxonomy of sparse Markovian errors that the whole simulation representation relies on."},{"cited_title":"Blanes and F","cited_arxiv_id":null,"evidence_quote":"Underlies the Baker-Campbell-Hausdorff expansion used to combine propagated layer error generators into a single circuit-level Lindbladian."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the process fidelity and error-generator quantities the algorithm computes, and motivates the fidelity approximation in terms of stochastic and Hamiltonian rates."}],"review_version":1}