Recognition: 2 theorem links
· Lean TheoremEfficient simulation of noisy IQP circuits with amplitude-damping noise
Pith reviewed 2026-05-10 19:49 UTC · model grok-4.3
The pith
A polynomial-time classical algorithm samples from amplitude-damped IQP circuits.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that there exists a polynomial-time classical algorithm to sample from the output distributions of amplitude-damped instantaneous quantum polynomial (IQP) circuits generated by arbitrary l-local diagonal gates with depth d = Ω(log(n)) under constant amplitude-damping noise.
What carries the argument
A classical sampling procedure that exploits the cumulative effect of constant-rate amplitude damping to reduce the noisy evolution to a form that can be sampled efficiently.
If this is right
- Amplitude-damped IQP circuits of logarithmic depth do not yield quantum advantage for sampling tasks.
- The classical simulation succeeds for arbitrary choices of the l-local diagonal gates without requiring randomness.
- Constant-rate amplitude damping alone is enough to render the circuits classically tractable once depth is adequate.
- The same damping mechanism can be used to simulate the noisy output distribution rather than only approximate it.
Where Pith is reading between the lines
- Experimental realizations of IQP circuits will need either very low damping rates or much shallower depths to retain any sampling advantage over classical methods.
- Other families of diagonal-gate circuits may admit similar classical simulations under non-unital noise.
- The algorithm could be tested directly on small noisy circuits to check whether its runtime remains practical before scaling.
Load-bearing premise
Amplitude damping must occur at a constant rate and the circuit depth must be at least logarithmic in the number of qubits so the noise accumulates enough to enable the efficient classical algorithm.
What would settle it
A concrete large-n instance of such a noisy IQP circuit for which the proposed classical algorithm produces samples whose distribution deviates measurably from the true output distribution obtained by exact quantum simulation.
Figures
read the original abstract
Efficient classical simulation of noisy intermediate-scale quantum (NISQ) circuits has been a topic of intense study over the past few years. The majority of results on efficient simulation assume that the circuits undergo some variant of unital noise or involve sufficient randomness. However, there are limited results for circuits undergoing non-unital noise in the absence of randomness. In this work, we present a polynomial-time classical algorithm to sample from the output distributions of amplitude-damped instantaneous quantum polynomial (IQP) circuits. Our algorithm works for circuits generated by arbitrary $l$-local diagonal gates with depth $d = \Omega(\log(n))$, undergoing constant amplitude-damping noise.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents a polynomial-time classical algorithm for sampling the output distributions of instantaneous quantum polynomial (IQP) circuits composed of arbitrary l-local diagonal gates. The algorithm applies when the circuit depth satisfies d = Ω(log n) and the circuit is subject to constant-rate amplitude-damping (non-unital) noise.
Significance. If the central claim holds, the result is significant because it identifies a concrete regime in which non-unital noise alone, without randomness or unital assumptions, renders a family of structured quantum circuits classically simulable in polynomial time. This strengthens the boundary between efficiently simulable and potentially hard noisy quantum circuits and supplies a falsifiable prediction for the depth at which amplitude damping becomes dominant.
minor comments (3)
- §2, paragraph following Definition 1: the precise range of the locality parameter l (constant versus slowly growing) is stated only implicitly; an explicit sentence clarifying whether l = O(1) or l = o(log n) is required for the depth threshold to be unambiguous.
- Figure 1 caption: the plotted quantity is labeled “effective rank” but the main text uses “support size after damping”; align the terminology or add a parenthetical definition in the caption.
- §4.3, line after Eq. (17): the phrase “the Kraus operators commute with the diagonal gates” is used without a short proof or reference; a one-sentence justification would remove ambiguity for readers unfamiliar with the commutation relation.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript and for recommending minor revision. The summary accurately reflects the scope and claims of our work.
Circularity Check
No significant circularity
full rationale
The paper claims a polynomial-time classical algorithm to sample output distributions of amplitude-damped IQP circuits with l-local diagonal gates at depth Ω(log n) under constant non-unital amplitude-damping noise. No equations, self-definitional reductions, fitted parameters renamed as predictions, or load-bearing self-citations appear in the abstract or stated claims. The central result is an algorithmic construction whose correctness is asserted to follow from noise accumulation suppressing coherences in the logarithmic-depth regime; this is not equivalent to the input assumptions by construction and remains externally falsifiable via simulation benchmarks or alternative noise models. The derivation is therefore self-contained.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption IQP circuits consist of l-local diagonal gates applied in a single layer or shallow depth.
- domain assumption Amplitude-damping noise acts independently on each qubit at a constant rate.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel (J-cost uniqueness) unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 1... depth threshold d_T = O(log(n)/log(1-p)−1)... truncation error... Chernoff bounds... operator frame I(a)=|0⟩⟨0|+a|1⟩⟨1|
-
IndisputableMonolith/Foundation/AlphaCoordinateFixation.leancostAlphaLog_high_calibrated_iff unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
amplitude-damping channel... unique fixed point... pushes states toward low Hamming-weight subspace
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Preskill, Quantum computing and the entanglement frontier, arXiv preprint arXiv:1203.5813 (2012)
J. Preskill, Quantum computing and the entanglement frontier (2012), arXiv:1203.5813 [quant-ph]
-
[2]
Shor, inProceedings 35th Annual Symposium on Foun- dations of Computer Science(1994) pp
P. Shor, inProceedings 35th Annual Symposium on Foun- dations of Computer Science(1994) pp. 124–134
1994
-
[3]
A. W. Harrow, A. Hassidim, and S. Lloyd, Physical Re- view Letters103, 150502 (2009)
2009
-
[4]
Lloyd, Science273, 1073 (1996)
S. Lloyd, Science273, 1073 (1996)
1996
-
[5]
Bluvstein, S
D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li,et al., Nature626, 58 (2024)
2024
-
[6]
Acharya, D
R. Acharya, D. A. Abanin, L. Aghababaie-Beni, I. Aleiner,et al., Nature638, 920 (2025)
2025
-
[7]
T. He, W. Lin, R. Wang, Y. Li,et al., Phys. Rev. Lett. 135, 260601 (2025)
2025
-
[8]
Preskill, Quantum2, 79 (2018)
J. Preskill, Quantum2, 79 (2018)
2018
-
[9]
Mind the gaps: The fraught road to quantum advantage
J. Eisert and J. Preskill, Mind the gaps: The fraught road to quantum advantage (2025), arXiv:2510.19928 [quant- ph]
-
[10]
How to factor 2048 bit RSA integers with less than a million noisy qubits
C. Gidney, arXiv preprint arXiv:2505.15917 (2025)
work page internal anchor Pith review arXiv 2025
-
[11]
Bouland, B
A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, Nature Physics15, 159 (2019)
2019
-
[12]
Aaronson and A
S. Aaronson and A. Arkhipov, Theory of Computing9, 143 (2013)
2013
-
[13]
M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proceed- ings of the Royal Society A: Mathematical, Physical and Engineering Sciences467, 459 (2010)
2010
-
[14]
M. J. Bremner, A. Montanaro, and D. J. Shepherd, Phys- ical Review Letters117, 080501 (2016)
2016
-
[15]
J. Denzler, J. Carrasco, J. Eisert, and T. Guaita, arXiv preprint arXiv:2601.05131 (2026)
- [16]
-
[17]
D. Hangleiter and J. Eisert, Reviews of Modern Physics 95, 035001 (2023), arXiv:2206.04079 [quant-ph]
-
[18]
Arute, K
F. Arute, K. Arya, R. Babbush, D. Bacon,et al., Nature 574, 505 (2019)
2019
-
[19]
Wu, W.-S
Y. Wu, W.-S. Bao, S. Cao, F. Chen,et al., Phys. Rev. Lett.127, 180501 (2021)
2021
-
[20]
Morvan, B
A. Morvan, B. Villalonga, X. Mi, S. Mandr` a,et al., Na- ture634, 328 (2024)
2024
- [21]
-
[22]
Neville, C
A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing, Nature Physics 13, 1153 (2017)
2017
-
[23]
F. Pan, K. Chen, and P. Zhang, Phys. Rev. Lett.129, 090502 (2022)
2022
-
[24]
Classical Simula- tion of Quantum Supremacy Circuits
C. Huang, F. Zhang, M. Newman, J. Cai, X. Gao, Z. Tian, J. Wu, H. Xu, H. Yu, B. Yuan, M. Szegedy, Y. Shi, and J. Chen, Classical simulation of quantum supremacy circuits (2020), arXiv:2005.06787 [quant-ph]
-
[25]
M. M. Wilde,Quantum information theory(Cambridge university press, 2013)
2013
-
[26]
E. Fontana, M. S. Rudolph, R. Duncan, I. Rungger, and C. Cˆ ırstoiu, Classical simulations of noisy variational quantum circuits (2023), arXiv:2306.05400 [quant-ph]
-
[27]
Schuster, C
T. Schuster, C. Yin, X. Gao, and N. Y. Yao, Physical Review X15, 041018 (2025)
2025
-
[28]
Cirstoiu, arXiv preprint arXiv:2410.13856 (2024)
C. Cirstoiu, arXiv preprint arXiv:2410.13856 (2024)
-
[29]
Y. Shao, F. Wei, S. Cheng, and Z. Liu, Physical Review Letters133, 10.1103/physrevlett.133.120603 (2024)
-
[30]
G. Gonz´ alez-Garc´ ıa, J. I. Cirac, and R. Trivedi, Pauli path simulations of noisy quantum circuits beyond aver- age case (2024), arXiv:2407.16068 [quant-ph]
-
[31]
Schuster, C
T. Schuster, C. Yin, X. Gao, and N. Y. Yao, Phys. Rev. X15, 041018 (2025)
2025
-
[32]
Simulating quantum circuits with arbitrary local noise using Pauli Propagation
A. Angrisani, A. A. Mele, M. S. Rudolph, M. Cerezo, and Z. Holmes, Simulating quantum circuits with ar- bitrary local noise using pauli propagation (2025), arXiv:2501.13101 [quant-ph]
work page internal anchor Pith review Pith/arXiv arXiv 2025
-
[33]
V. Martinez, A. Angrisani, E. Pankovets, O. Fawzi, and D. Stilck Fran¸ ca, Physical Review Letters134, 10.1103/j1gg-s6zb (2025)
-
[34]
A. Angrisani, A. Schmidhuber, M. S. Rudolph, M. Cerezo, Z. Holmes, and H.-Y. Huang, arXiv preprint arXiv:2409.01706 (2024)
- [35]
- [36]
-
[37]
J. Rajakumar, J. D. Watson, and Y.-K. Liu, Polynomial-time classical simulation of noisy iqp circuits with constant depth, inProceedings of the 2025 Annual ACM-SIAM Symposium on Dis- crete Algorithms (SODA)(2025) pp. 1037–1056, https://epubs.siam.org/doi/pdf/10.1137/1.9781611978322.30
-
[38]
Fefferman, S
B. Fefferman, S. Ghosh, M. Gullans, K. Kuroiwa, and K. Sharma, PRX Quantum5, 030317 (2024)
2024
- [39]
- [40]
- [41]
- [42]
-
[43]
Shepherd and M
D. Shepherd and M. J. Bremner, Proceedings of the Royal Society A: Mathematical, Physical and Engineer- ing Sciences465, 1413 (2009)
2009
-
[44]
See Supplemental Material
-
[45]
Vectorization of quantum operations and its use
A. Gilchrist, D. R. Terno, and C. J. Wood, Vec- torization of quantum operations and its use (2011), arXiv:0911.2539 [quant-ph]
work page Pith review arXiv 2011
-
[46]
Chernoff, The Annals of Mathematical Statistics , 493 (1952)
H. Chernoff, The Annals of Mathematical Statistics , 493 (1952)
1952
- [47]
-
[48]
M. A. Nielsen and I. L. Chuang,Quantum Computa- tion and Quantum Information: 10th Anniversary Edi- tion(Cambridge University Press, 2010)
2010
-
[49]
Bhatia,Matrix analysis(Springer Science & Business Media, 2013) pp
R. Bhatia,Matrix analysis(Springer Science & Business Media, 2013) pp. 62–64
2013
-
[50]
Flum and M
J. Flum and M. Grohe,Parameterized complexity theory (Springer, 2006)
2006
-
[51]
R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey, and D. E. Knuth, Advances in Computational mathe- matics5, 329 (1996)
1996
-
[52]
R. O’Donnell, Analysis of boolean functions (2021), arXiv:2105.10386 [cs.DM]. 7 Appendix A: Hamming weight basis In this section, we provide an explicit example to illustrate what we refer to as the Hamming weight (HW) basis. We define this basis by ordering vectorized computational basis strings according to increasing Hamming weight. This representation...
-
[53]
The coefficients of operators with Hamming weightsare damped by a prefactor (1−p) s/2
-
[54]
These coefficients carry a prefactorp t, wheretis the number of such replacements
In addition to the above damping, the coefficients of any operator containing at least one|0⟩⟨0|term receives re-feeding contributions from the coefficients of operators in which|0⟩⟨0|is replaced by|1⟩⟨1|. These coefficients carry a prefactorp t, wheretis the number of such replacements. To make this even more explicit, we consider local amplitude damping...
-
[55]
Since the unitary gates are diagonal in the computational basis, their action is limited to introducing phase factors in the coefficients
Intuition building a.m= 0 In this case, no re-feeding occurs, and the noise channel only induces damping. Since the unitary gates are diagonal in the computational basis, their action is limited to introducing phase factors in the coefficients. Consequently, they do not affect the absolute values of the coefficients. Therefore, the coefficients can be tra...
-
[56]
Formal proof of proposition 1 Proposition 1.Consider an initial|+⟩ ⊗n evolved under the noisy IQP circuitC, as defined in Thm 1. Letidenote the index, in the Hamming-weight basis, of an operator containingm i tensor factors of|0⟩⟨0|, and letα (r) i denote the corresponding coefficient afterrlayers of the noisy IQP circuit. Then, |αr i | ≤ (1−p) r[i]/2 2n ...
-
[57]
The maximum number of|0⟩⟨0|is when all the ones are paired up
Evenh Since the hamming weight ish, we need to havehones and 2n−hzeros in our operator. The maximum number of|0⟩⟨0|is when all the ones are paired up. Letµ h denote the maximum number of|0⟩⟨0|in an operator with a hamming weighth. By the above argument, µh =n− h 2 .(D1) To count the number of such operators, note that out ofnqubits we haveµ h |0⟩⟨0|and th...
-
[58]
The maximum number of|0⟩⟨0|is when the maximum number of ones are paired up, which would be all but 1
Oddh As before, since the hamming weight ish, we need to havehones and 2n−hzeros in our operator. The maximum number of|0⟩⟨0|is when the maximum number of ones are paired up, which would be all but 1. Letµ h denote the maximum number of|0⟩⟨0|in an operator with a hamming weighth. By the above argument, µh =n− h+ 1 2 .(D7) To count the number of such opera...
-
[59]
∆ − ̸= 0 and ∆ + = 0,
-
[60]
Case 1:We start by noting that ∆ − = 0 implies thatρ=σ
∆ − ̸= 0 and ∆ + ̸= 0. Case 1:We start by noting that ∆ − = 0 implies thatρ=σ. To see this, consider the Tr(σ) under the assumption that ∆− = 0, Tr(σ) = Tr(ρ) + Tr(∆) = 1 + Tr(∆+).(F16) The condition Tr(σ)≤1 and the above equation can only be satisfied if Tr(∆ +) = 0. Since by construction ∆ + ≥0, this implies that ∆ + = 0 and henceρ=σ. This implies that ...
-
[61]
commuting
Evaluating single qubit gates and “commuting” them through the circuit Recall that the diagonal gates in our gate set are drawn from the gate setG 2 ={e iθZ , C(ϕ)}, whereC(ϕ) is a controlled phase gate with arbitrary phase, C(ϕ) =|00⟩⟨00|+|01⟩⟨01|+|10⟩⟨10|+e iϕ |11⟩⟨11|.(G6) Single-qubit diagonal gates act trivially on diagonal operators and only modify ...
-
[62]
From the preceding discussion, the circuit componentC 2 can be evaluated efficiently for all strings inI ⊗n
Evaluating the controlled phase gates Consider the circuitCwritten as C=ED d · · ·D 2ED 1.(G15) Using the commuting trick we have established in the above subsection, we can re-write the circuit as follows, C=C 2C1 =R d · · ·R 1 EC d · · · EC 1,(G16) whereC r is the set of two-qubit controlled-phase gates acting on layerrandR r is the set of single-qubit ...
-
[63]
Scaling analysis Summarizing the above arguments, after a layer of controlled-phase gatesC (r) and amplitude-damping noise, the coefficientsβand⃗ achange as β→β(1−p) S(O) + + S(O) − /2 Y t∈S(s) 0 (1 + ˜atp) exp i X (x,y)∈S (r)++ u θxy −i X (x,y)∈S (r)−− u θxy , a t → ˜at(1−p) 1 +p˜at ,(G32) where the symbol ˜at is defined in Eq. (G31). Th...
-
[64]
The coefficients⃗ aare initialized as (1,
Places for potential speedups Though we report that the worst-case scaling of the algorithm can be bounded byO(n 3d), this bound is weak and can be strengthened in practice. The coefficients⃗ aare initialized as (1, . . . ,1) and decrease monotonically. Since we retain HW strings with at most aO(1) hamming weight, and since⃗ acoefficients only contribute ...
-
[65]
Setyto the empty string
-
[66]
, n: (a) IfS yz <0 for somez∈ {0,1}, sety← −y¯z, where ¯z= 1−z
Fori= 1, . . . , n: (a) IfS yz <0 for somez∈ {0,1}, sety← −y¯z, where ¯z= 1−z. (b) Otherwise: with probabilityS y0/Sy, sety← −y0; otherwise, sety← −y1
-
[67]
Appendix K: Extending the proof of Theorem 1 toℓ-local gate set In this section, we generalize the proof Theorem 1 tol-local gate sets
Returny Thus, each sample fromQ C can be produced with a worst-case time scaling ofO(n 2poly(δ −1)). Appendix K: Extending the proof of Theorem 1 toℓ-local gate set In this section, we generalize the proof Theorem 1 tol-local gate sets. As a natural extension of Theorem 1, we relax the two-qubit gate set restriction imposed therein. In particular, while a...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.