{"id":"2852d4b4-28bd-4062-9188-0af62b7475d9","arxiv_id":"2501.13050","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Pauli backpropagation classically simulates parameterized quantum circuits under non-unital noise in polynomial time in the average (L2) sense over the parameter landscape.","lead":"This paper proves that a classical algorithm can efficiently simulate noisy quantum circuits from a family used in variational quantum algorithms, even under amplitude damping noise, which is more realistic than the depolarizing noise studied before. The guarantee holds on average over all rotation angles, not for a single chosen parameter setting.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's high-probability L2 bound does not follow: the proof applies Hoeffding to the L2 norm, but Hoeffding controls a fixed scalar, and the stated constant is too small even for pointwise [-1,1]-valued samples.","rationale":"The paper's main contribution is the claim that Pauli backpropagation remains efficient for non-unital amplitude-damping noise, with Theorem 4 providing the only unconditional worst-case guarantee via Monte-Carlo sampling. The algebraic tree-expansion and damping analysis in Appendix B/C are mostly careful and internally consistent, and the L2-average caveat is openly acknowledged. The reader correctly notes the L2 metric as a limitation and flags the normal-form Lemma 5 sign issue. However, the most load-bearing gap is in the very last step of the proof of Theorem 4: the high-probability bound on the L2 error is obtained by an invalid application of Hoeffding. Since this is the step that converts the expectation bound into the theorem's advertised 'with probability at least 1-delta' guarantee, the central unconditional result is not fully established as written. The gap is plausibly repairable using McDiarmid or vector-valued concentration, and the algorithmic idea and runtime claim may survive with adjusted constants, so the appropriate verdict is still conditional rather than rejection. The recommended action is to require the authors to supply a correct concentration argument and to fix the normal-form lemma, after which the central claim could be accepted.","tokens_in":23495,"tokens_out":22967,"duration_ms":259628,"concrete_test":"Re-derive the final step of Appendix C using a valid concentration inequality for the L2 functional. Concretely: (1) For a fixed theta, redo Hoeffding with range-2 variables and verify that the stated constant sqrt(2 log(delta^(-1/2))/K) cannot be obtained; (2) apply McDiarmid's inequality to Delta(f,~f_hat) viewed as a function of the K independent sampled trees, whose sup-norm sensitivity is at most 2/K, and compare the resulting high-probability bound with the theorem. If the corrected bound is trunc + O(sqrt(log(1/delta)/K)) with the same runtime, the central efficiency claim survives with revised constants; if no such bound is obtained, Theorem 4's guarantee is weaker than stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central unconditional claim rests on Algorithm 2 and Theorem 4, whose proof in Appendix C ends with: 'By applying Hoeffding's inequality and noting that each of the sampled trees yields an expectation value in the range of [-1,1], we can conclude that with probability at least 1-delta, Delta(f,~f_hat) <= (1-gamma)^((ell+1)/2) + sqrt(2 log(delta^(-1/2))/K).' This step is not justified. Hoeffding's inequality applies to a fixed scalar random variable, e.g. the pointwise error |f(theta)-~f_hat(theta)| for one theta. Here the quantity being bounded is the L2 norm over the whole angle space [0,2pi]^m, which is not an average of K independent bounded scalars. Pointwise, for ~f_k(theta) in [-1,1] and f(theta)=E[~f_k(theta)], the difference has range 2, so Hoeffding gives sqrt(2 log(2/delta)/K) for a fixed theta, not sqrt(2 log(delta^(-1/2))/K)=sqrt(log(1/delta)/K). Passing to the L2 norm requires an additional covering/union bound or a vector-valued concentration argument, neither of which appears. The earlier bound E[Delta] <= trunc + 1/sqrt(K) is only an expectation statement; it does not yield the stated high-probability guarantee. A concrete symptom: for K=100 and delta=0.01, the claimed additive term is about 0.215, but for a mean-zero Bernoulli +/-1 estimator the actual Hoeffding tail at this threshold is P(|average|>0.215) ~ 0.032 > 0.01. This does not necessarily doom the qualitative efficiency claim, because a McDiarmid argument on Delta as a function of K samples may repair it, but the theorem as written is not proven by the supplied argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends Pauli backpropagation (LOWESA) to parametrized quantum circuits subject to non-unital noise, focusing on amplitude damping and general normal-form non-unital channels. The authors decompose noisy Rz rotations in the Pauli transfer matrix formalism into tree-structured processes, truncate the tree by the number of splittings, and propose a deterministic algorithm (Algorithm 1) and a Monte Carlo version (Algorithm 2). The main theorems claim L2-average approximation guarantees: Algorithm 1 achieves error at most (1−γ)^{r/2} in time O(n^2 m 2^ℓ), and Algorithm 2 achieves, with probability at least 1−δ, error at most (1−γ)^{(ℓ+1)/2} + sqrt(2 log(δ^{−1/2})/K) in time O(K n^2 m 2^ℓ). An extension to normal-form non-unital channels is presented in Appendix D.","tokens_in":23802,"tokens_out":7875,"duration_ms":88083,"significance":"If the proofs were correct, this would be a valuable extension of Pauli backpropagation beyond unital noise and beyond the random-circuit assumptions of previous work, and the tree-splitting analysis in Lemma 2 and Proposition 3 is a genuine technical contribution. The algorithms are concrete, with explicit runtimes, and the QAOA numerical experiments in Appendix A provide a useful sanity check. However, the high-probability bound for Algorithm 2 is not established by the submitted proof, and the extension to general normal-form channels rests on an unjustified sign assumption in Lemma 5. These issues are load-bearing for the paper's central claims, so the manuscript needs substantive revision before the results can be accepted.","major_comments":[{"comment":"The final step of the proof of Theorem 4 applies Hoeffding's inequality to the L2 error Δ(f, f_hat), but Hoeffding's inequality controls a fixed scalar random variable, not a norm of a function-valued estimator. The quantity Δ(f, f_hat) is not an average of K independent bounded scalars, and bounding it with probability 1−δ requires an additional uniform bound over the angle space or a vector-valued concentration argument (e.g., a covering argument or McDiarmid applied to Δ as a function of all K samples). Moreover, even pointwise the stated constant is wrong: for independent samples bounded in [−1,1], Hoeffding gives sqrt(2 log(2/δ)/K), not sqrt(2 log(δ^{−1/2})/K). As written, Eq. (C11) and the corresponding part of Theorem 1 are unsupported. The preceding expectation bound E[Δ] ≤ (1−γ)^{(ℓ+1)/2} + 1/sqrt(K) does not imply the claimed high-probability guarantee.","section":"Appendix C, Theorem 4 (Eq. C11) and Theorem 1 (Eq. 13)"},{"comment":"The proof of Lemma 5 asserts at the last equality that 'the coefficients D_P have all the same sign', but this is not proven and is not a property of every normal-form non-unital channel. CPTP constraints alone do not force D_X, D_Y, and D_Z to share a common sign. Without this assumption, the identity |∑_P b_P^2 D_P + |b_P t_P| sign(D_P)| = ∑_P (b_P^2 |D_P| + |b_P t_P|) can fail, and the conclusions |D_P| + |t_P| ≤ 1 and uniqueness of equality do not follow. Since Theorem 6's truncation bound depends on these conclusions, the claimed extension to general normal-form non-unital noise is not established as stated. The authors should either prove the sign property from complete positivity or restrict the noise class accordingly.","section":"Appendix D, Lemma 5, proof around Eq. (D9)"},{"comment":"The abstract and introduction state that the paper shows how to 'efficiently simulate' parameterized quantum circuits under non-unital noise, but the theorems provide guarantees only in the L2 norm averaged over all rotation angles, and the paper itself acknowledges after Eq. (4) that convergence in this metric does not imply success for a given set of angles. This is a serious scope limitation for the practical interpretation of the results: for applications that require a pointwise accurate expectation value at specific optimized parameters, the theorems give no bound. The headline claims should be consistently qualified as average-case-over-parameters guarantees so that the reader is not misled about the strength of the simulation result.","section":"Abstract and Section II (Eq. 4)"}],"minor_comments":[{"comment":"The line '˜ˆf(θ) ← 1/K ˜f_k(θ)' inside the for-loop overwrites the accumulator, so the algorithm as written does not compute the empirical average of Eq. (C3). It should be an accumulating update of the form '˜ˆf(θ) ← ˜ˆf(θ) + (1/K) ˜f_k(θ)'.","section":"Appendix C, Algorithm 2, line 8"},{"comment":"The sentence 'the runtime of the algorithm is independent of both the quantum chip geometry and the depth of the quantum circuit' appears inaccurate, because Theorem 1 reports a runtime of O(n^2 m 2^ℓ), which depends linearly on m, the number of layers/rotations and hence on the circuit depth.","section":"Introduction, Section I"},{"comment":"The notation for the zero-like processes is inconsistent: the text uses both '0Z' and '0z' (e.g., below Eq. (7) versus Appendix B), and the set of modes is written with both '0z' and '0Z'. Please unify the notation.","section":"Notation throughout"},{"comment":"The statement that the diagonalizing Cliffords can be absorbed into the circuit 'without loss of generality' is terse: absorbing them changes the positions of the rotations relative to the noise channel, so this reduction needs a short justification or a pointer to a previous argument.","section":"Appendix D, paragraph after Eq. (D12)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses a timely and relevant problem, and the core combinatorial idea is promising. However, the two main proof gaps (the concentration step for Theorem 4 and the sign assumption in Lemma 5) are central, and the L2-average scope of the results should be clearly flagged in the abstract. I do not see evidence of misconduct or inappropriate citation behavior; the issues are technical and, in principle, fixable within a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is real progress on an open question, but don't let the intro's 'depth independent' claim and the Theorem 4 concentration step pass review. I'd send it to referees, with a request for a revised proof.\n\nWhat's actually new: they extend LOWESA Pauli backpropagation to amplitude damping and to normal-form non-unital channels, removing the random-circuit assumptions that earlier non-unital results needed. The tree-splitting analysis cleanly separates damped splits (D±1) from undamped Z-splits, and the Monte Carlo scheme for sampling Z-branches is a sensible way to keep the tree efficient. The error bounds are derived from the channel structure with no fitted parameters, and the appendices are detailed enough to check. The paper is also upfront that the L2 norm is an average over angles and that Algorithm 1's r can be zero, so it doesn't oversell its worst-case guarantees.\n\nThe main problem is Theorem 4. The proof ends by invoking Hoeffding on the L2 error because each sampled tree gives values in [-1,1]. That doesn't follow: Hoeffding controls a fixed scalar, not a norm over the whole parameter space. The L2 error is a bounded-differences function of the K sampled trees, so a McDiarmid argument would give the right kind of concentration, but the constant in the theorem, sqrt(2 log(delta^{-1/2})/K), is too small even for pointwise Hoeffding with range 2. Using McDiarmid with the stated bound gives tail sqrt(delta), not delta. So the theorem as written is not proven. I think it's repairable — the estimator is unbiased and the truncation bound is fine — but the proof needs to be rewritten.\n\nTwo smaller issues. Lemma 5 in Appendix D uses 'the coefficients DP have all the same sign' without justification; that's true if the normal form is taken to be the singular-value decomposition, but the paper doesn't say that, so it needs a sentence. And the introduction and conclusion claim the runtime is independent of circuit depth, which contradicts the stated O(n^2 m 2^ell) — m is the depth. That's an overclaim, not a technical flaw.\n\nWho should read it: people working on classical simulation of noisy variational circuits, especially anyone building on LOWESA. It's a solid extension of an established program, not a breakthrough. I'd accept it for peer review and ask for a corrected Theorem 4 proof and a cleanup of the depth claim. The core idea is likely right; the current write-up just doesn't close the concentration argument.","headline":"Solid extension of LOWESA to non-unital noise, but Theorem 4's concentration proof doesn't close as written and the depth-independence claim is overstated.","tokens_in":24434,"tokens_out":8093,"would_cite":true,"duration_ms":84551,"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":"This paper establishes that Pauli backpropagation, a classical simulation technique for parameterized quantum circuits, works for non-unital noise—specifically amplitude damping—not just the unital noise covered by earlier guarantees.","keywords":["Pauli backpropagation","amplitude damping","non-unital noise","parameterized quantum circuits","classical simulation","L2 approximation","Clifford circuits","Monte Carlo tree sampling"],"falsifier":"Run Algorithm 1 on a concrete instance—say, a QAOA circuit on a 3-regular graph with amplitude damping $\\gamma = 0.1$—compute the exact expectation value by state-vector simulation on a dense grid of angles, and compare the empirical L2 error with the certificate $(1-\\gamma)^{r/2}$. If the empirical error exceeds that bound with a clear margin, Theorem 1 is false; the paper's own warning that L2 convergence does not imply pointwise accuracy can be demonstrated by fixing an angle where the surrogate deviates by more than the bound, though that alone would not refute the theorem.","tokens_in":23218,"feed_emoji":"⚛️","tokens_out":7222,"duration_ms":67434,"temperature":0.7,"pith_summary":"This paper proves that Pauli backpropagation, a classical simulation technique for parameterized quantum circuits, remains efficient when the circuit noise is non-unital, specifically amplitude damping. It presents two polynomial-time algorithms that approximate the expectation value of any Pauli observable as a function of the rotation angles, with error measured in L2 norm over the full angle range. This matters because real hardware noise is often non-unital, whereas earlier Pauli backpropagation guarantees covered unital noise such as depolarizing. The paper also extends the result to any single-qubit noise channel that can be brought into normal form with Clifford diagonalizing unitaries.","feed_headline":"Pauli backpropagation handles amplitude-damping noise efficiently","feed_subtitle":"Same backpropagation trick that works for depolarizing noise now covers realistic amplitude damping.","key_machinery":"The engine is the Pauli transfer matrix decomposition of the noisy rotation $R_z(\\theta) \\circ \\mathcal{N}_{AD}$ into five quantum processes $D_0$, $D_{0Z}$, $D_{0I}$, $D_1$, $D_{-1}$, so that backpropagating a Pauli string through the circuit builds a binary tree of paths. Each split corresponds to one of those processes; the vector $\\omega$ records which process occurred at each layer, and the trigonometric monomials $\\Phi_\\omega(\\theta)$ carry the angle dependence. The key analysis shows that when two discarded paths contribute to the L2 error, they must share the same $h(\\omega)$ (where $0$, $0Z$, and $0I$ are identified), and a split through $D_{\\pm 1}$ multiplies the contribution by $1-\\gamma$ while a split through $D_{0Z}/D_{0I}$ leaves it unchanged, yielding the exponential-in-$\\ell$ damping that makes truncation effective.","core_discovery":"The central claim is that for circuits built from alternating layers of Clifford gates, single-qubit $Z$-rotations, and amplitude-damping channels with parameter $\\gamma > 0$, the expectation value $f(\\theta) = \\mathrm{tr}(\\mathcal{U}_\\theta(|0\\rangle\\langle 0|)P)$ can be approximated in time $O(n^2 m 2^{\\ell})$ to L2 error at most $(1-\\gamma)^{r/2}$ (Algorithm 1), and with an additional Monte-Carlo sampling overhead $K$ in time $O(K n^2 m 2^{\\ell})$ to error $(1-\\gamma)^{(\\ell+1)/2} + \\sqrt{2\\log(\\delta^{-1/2})/K}$ with probability at least $1-\\delta$ (Algorithm 2). The L2 error is the root-mean-square deviation over the parameter space $[0,2\\pi]^m$. The proof works by decomposing each noisy rotation in the Heisenberg picture into five quantum processes and tracking how often the dampening processes $D_{\\pm 1}$ occur on discarded branches, showing that every such split reduces the error by a factor $1-\\gamma$, while splits through $D_{0Z}/D_{0I}$ leave it unchanged.","pith_inferences":["If variational algorithms mostly care about the shape of the energy landscape rather than pointwise accuracy at one angle, this result suggests classical simulation can track noisy landscapes under realistic hardware noise, not just depolarizing.","The L2-only guarantee means the surrogate is not trustworthy for reporting a specific expectation value at a fixed optimized angle; a practical simulator should pair it with a pointwise check at the angles it actually uses.","Because the known results on non-unital noise show that structured circuits can sustain long computations, the boundary between classically simulable and not is likely set by circuit structure rather than by whether the noise is unital; extending this to noisy continuous-time evolution is a natural next step."],"forward_implications":["Any circuit in the alternating Clifford-plus-$R_z$ family under amplitude damping can be simulated classically in polynomial time, with runtime independent of circuit depth and hardware geometry.","Algorithm 2 removes the \"almost any circuit\" caveat: the Monte-Carlo sampling guarantees the L2 error bound for every circuit in the family, not just typical ones.","Algorithm 1 returns a certificate $r$, the minimum number of dampening splits on discarded branches, giving a per-instance error bound that can be computed directly from the circuit and observable.","The same machinery covers compositions and probabilistic mixes of amplitude damping, dephasing, and depolarizing noise, since these fit the normal-form class of single-qubit channels handled in Appendix D."],"supporting_citations":[{"why":"introduces the Pauli backpropagation tree method and its unital-noise guarantees that this paper extends to amplitude damping","marker":"[19]"},{"why":"provides the normal-form treatment of arbitrary local noise used in Lemma 5 and Appendix D","marker":"[30]"},{"why":"gives a prior polynomial-time simulation under depolarizing and randomized amplitude damping, which this work generalizes by removing the randomization or input-state assumptions","marker":"[14]"},{"why":"established non-unital noise simulation for random circuits, a setting this paper broadens to the alternating Clifford-$R_z$ circuit family","marker":"[15]"},{"why":"shows non-unital noise permits exponential-time quantum computation, explaining why pointwise simulation is impossible and why L2-average guarantees are the target","marker":"[18]"},{"why":"supplies the known $O(n^2)$ cost of pushing a Pauli string through a Clifford unitary, setting the per-branch runtime","marker":"[34]"},{"why":"gives the normal form for single-qubit channels that Appendix D uses to generalize beyond amplitude damping","marker":"[35]"}],"fun_headline_variants":["Amplitude damping no longer blocks Pauli backprop","Non-unital noise now yields to Pauli backprop","Pauli backprop tames non-unital noise","Pauli backprop now handles amplitude damping","Backpropagation stays efficient under amplitude damping"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The approximation is only guaranteed to be close on average over all rotation angles in the L2 sense; for a specific set of angles, the surrogate can be arbitrarily far from the true expectation value.","fun_headline_variants_meta":{"raw":{"variants":["Amplitude damping no longer blocks Pauli backprop","Non-unital noise now yields to Pauli backprop","Pauli backprop tames non-unital noise","Pauli backprop now handles amplitude damping","Backpropagation stays efficient under amplitude damping"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00109,"raw_usage":{"total_tokens":4568,"prompt_tokens":972,"completion_tokens":3596,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":588,"completion_tokens_details":{"reasoning_tokens":3522}},"tokens_in":588,"tokens_out":3596,"duration_ms":28504,"temperature":1.0,"reasoning_tokens":3522,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:31:27.562674+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a concrete instance—say, a QAOA circuit on a 3-regular graph with amplitude damping $\\gamma = 0.1$—compute the exact expectation value by state-vector simulation on a dense grid of angles, and compare the empirical L2 error with the certificate $(1-\\gamma)^{r/2}$. If the empirical error exceeds that bound with a clear margin, Theorem 1 is false; the paper's own warning that L2 convergence does not imply pointwise accuracy can be demonstrated by fixing an angle where the surrogate deviates by more than the bound, though that alone would not refute the theorem.","supporting_citations":[{"cited_title":"Angrisani, A","cited_arxiv_id":null,"evidence_quote":"provides the normal-form treatment of arbitrary local noise used in Lemma 5 and Appendix D"},{"cited_title":"An Analysis of Completely-Positive Trace-Preserving Maps on 2x2 Matrices","cited_arxiv_id":"quant-ph/0101003","evidence_quote":"gives the normal form for single-qubit channels that Appendix D uses to generalize beyond amplitude damping"}],"review_version":1}