Pith. sign in

REVIEW 3 minor 85 references

This paper proves that, assuming the standard conjecture that ideal random circuit sampling (RCS) is #P-hard, noisy RCS under local depolarizing noise remains classically hard to simulate for noise strength up to O(log n/(nd)), matching the

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 09:21 UTC pith:FO2H3SQI

load-bearing objection A technically careful paper proving noisy-RCS hardness at γ = O(log n/(nd)) conditional on the standard ideal-RCS conjecture, with a clean monotonicity reduction; the main caveat is the open conjecture, which the paper openly flags.

arxiv 2607.20804 v1 pith:FO2H3SQI submitted 2026-07-23 quant-ph

Hardness and Complexity Transition of Noisy Random Circuit Sampling

Byeongseon Go , Changhun Oh , Hyunseok Jeong This is my paper
classification quant-ph MSC 81P6868Q1568Q17 PACS 03.67.Lx
keywords random circuit samplingquantum advantagedepolarizing noiseclassical simulation hardness#P-hardnesspolynomial hierarchycomplexity transitionlow-degree extrapolation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks where the boundary lies between classically easy and classically hard regimes for noisy random circuit sampling (RCS), a leading candidate for quantum advantage. It proves that, under the standard conjecture that ideal RCS is #P-hard on average, noisy RCS on the same architecture remains hard to simulate classically at inverse-polynomial accuracy for local depolarizing noise strength up to γ = O(log n/(nd)), unless the polynomial hierarchy collapses. The proof transfers ideal hardness directly to the noisy output distribution using two ingredients: a low-degree polynomial extrapolation that recovers ideal probabilities from noisy ones, and a monotonicity argument showing that adding more noise never makes simulation harder. Combined with known results that RCS becomes classically simulable when γ = ω(log n/(nd)), this identifies the asymptotic complexity-transition scale on overlapping architectures. A sympathetic reader should care because it sharpens the promised boundary for noisy quantum advantage without adding a new hardness assumption.

Core claim

The central claim is Theorem 4: for any circuit architecture satisfying the standard average-case #P-hardness conjecture for ideal RCS, no polynomial-time classical sampler can approximately simulate noisy RCS within inverse-polynomial total variation distance at local depolarizing noise strength γ* = O(log n/(nd)), unless the polynomial hierarchy collapses to a finite level. The hardness is inherited from the ideal case without any additional conjectural or architecture-specific assumption. The supporting results are Theorem 2, which shows that estimating noisy output probabilities at input noise strengths γ ∈ [γ*, 1] is #P-hard when γ* = O(log n/(nd)), and Theorem 3, a monotonicity reducti

What carries the argument

The load-bearing objects are the noisy output probability expressed as a degree-N polynomial in the depolarizing strength γ, with N = n(d+1), and the compositional closure of depolarizing channels. The proof approximates this polynomial by a truncated Chebyshev expansion on an interval, queries a noisy-probability oracle at l+1 noise levels, and extrapolates to γ = 0, where the noisy probability equals the ideal one; the condition ndγ* = O(log n) keeps the interpolation overhead polynomial. Separately, the identity Eγ2 = Eγ1 ∘ Eγadd lets any sampler at strength γ1 sample at any larger strength γ2 by drawing a Pauli path from the added noise and calling the γ1-sampler, preserving total-variat

Load-bearing premise

The entire conclusion rests on Conjecture 1—that some circuit architecture exists for which estimating ideal random-circuit output probabilities to inverse-polynomial additive error is #P-hard—plus the standard assumption that the polynomial hierarchy does not collapse.

What would settle it

Exhibit a circuit architecture A satisfying Conjecture 1 and give a polynomial-time classical sampler for its noisy RCS at noise strength γ = log n/(nd) within inverse-polynomial total variation distance; by Theorem 4 this would force the polynomial hierarchy to collapse, directly refuting the theorem. A softer falsifier is to disprove Conjecture 1 by finding an architecture-independent efficient algorithm for average-case ideal probability estimation.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For any architecture where ideal RCS satisfies the average-case #P-hardness conjecture, noisy RCS inherits hardness up to noise O(log n/(nd)) with no extra conjectures.
  • In the logarithmic-depth regime d = Θ(log n), this yields hardness at γ = O(1/n), roughly a factor of log n beyond previously known white-noise-route thresholds.
  • Efficient classical simulation at one noise level automatically extends to every larger noise level, so existing simulability results can be pushed upward without new proofs.
  • On architectures satisfying both the ideal-hardness conjecture and the convergence-to-uniformity conditions, hardness and simulability bounds match asymptotically, fixing γ = Θ(log n/(nd)) as the complexity-transition scale.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: The monotonicity lemma is stated for exact, average-case, and probabilistic samplers, so it likely extends many existing noisy-RCS simulability results to all larger noise strengths, potentially sharpening the simulable side of the phase diagram.
  • Editorial inference: The proof structure suggests the same ideal-to-noisy transfer should work for other noise models whose output probabilities are polynomial in the noise parameter and reduce to the ideal at zero noise, though the precise threshold constant may change.
  • Editorial inference: A practical corollary for experiments is that complexity-theoretic hardness claims are on firmest ground when the noise rate is below O(log n/(nd)); above that scale, the burden shifts toward finding classical algorithms.
  • Editorial inference: At finite sizes, one could empirically probe the predicted transition by comparing state-of-the-art classical samplers against noisy RCS at noise rates around log n/(nd), while recognizing that asymptotic hardness cannot be directly tested numerically.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper proves a conditional hardness result for random circuit sampling (RCS) under local depolarizing noise. Assuming Conjecture 1 (the existence of an architecture A0 for which average-case ideal output-probability estimation to additive error eps0 2^{-n} with eps0 = 1/poly(n) is #P-hard), the authors show that sampling from the noisy output distribution at noise strength gamma* = O(log n/(nd)) within inverse-polynomial total variation distance is classically hard unless the polynomial hierarchy collapses (Theorem 4). The proof combines a low-degree Chebyshev approximation and Lagrange interpolation to reduce ideal probability estimation to noisy probability estimation (Lemmas 2 and 3, Appendices A, B, D), together with a monotonicity theorem (Theorem 3, Section VI) that converts variable-noise estimation hardness into fixed-noise sampling hardness. Combining the monotonicity theorem with the convergence-to-uniformity result of Dalzell et al. yields classical simulability for gamma = omega(log n/(nd)) on overlapping architectures, giving a claimed transition scale.

Significance. Conditional on Conjecture 1, the transfer from ideal to noisy RCS is clean and improves on the white-noise route: it avoids the structural and anti-concentration assumptions of Ref. [16] and, in the logarithmic-depth regime, reaches gamma = O(1/n) rather than gamma << 1/(n log n). The proof is unusually explicit: the Chebyshev tail bounds, Bernstein-ellipse estimate, and interpolation error budgets are spelled out with constants. I found no hidden assumption beyond the stated conjecture. The main caveat is real but honestly acknowledged: the inverse-polynomial-error form of Conjecture 1 is open, and the currently proved versions have exponentially small error (Section IV.A). The theorem is therefore a conditional transfer, not an unconditional hardness proof.

minor comments (3)
  1. [Section VI, Lemma 5 and Theorem 3] The channel identity in Eq. (36) is correct, but the implementation claim that C_s is always a valid circuit in the architecture A fails for a Pauli inserted after the final unitary layer before measurement. This is easily fixed: a final Pauli only permutes computational-basis output labels, so the gamma_1-sampler can be called on the Pauli-absorbed circuit and its output relabeled accordingly. Please make this explicit, since as written the oracle is asked to accept inputs outside A.
  2. [Section IV.A, Conjecture 1] The conditionality of Theorem 4 is handled transparently, and Remark 1 together with the progress paragraph correctly state that the inverse-polynomial-error form of the conjecture is open (current best is exponentially small error). I suggest adding one sentence to the abstract and conclusion clarifying that no architecture satisfying Conjecture 1 is currently known, so the result is a conditional transfer.
  3. [Section II.A, Corollary 1] The statement that the hard and simulable bounds 'meet' at gamma = Theta(log n/(nd)) should be read at the level of asymptotic scaling. The simulability result of Ref. [16] also carries a weak-noise constraint gamma = O(1/n), so for fixed constants at d = Theta(log n) the overlap can be empty. A sentence noting this constant/regime caveat would prevent overstatement.

Circularity Check

0 steps flagged

No circularity: the noisy-RCS hardness result is a genuine conditional reduction from the stated ideal-RCS conjecture, with all internal lemmas proved self-contained.

full rationale

The derivation chain is conditional on two external assumptions: Conjecture 1 (average-case #P-hardness of ideal probability estimation) and non-collapse of the polynomial hierarchy. These are not derived from the conclusion and are explicitly stated as hypotheses. Theorem 2 is a genuine reduction: Eq. (10)/(15) expresses the noisy probability as an explicit polynomial in the noise strength γ whose value at γ=0 is the ideal probability (only the all-identity Pauli path survives), so recovering p(C) from noisy evaluations at γ∈[γ*,1] is interpolation of a polynomial from distinct data points, not recovery of a fitted parameter. Lemma 2 (Chebyshev truncation) is proved in Appendix A with standard approximation theory, and Lemma 3 is proved in Appendix B using the external interpolation bound of Kondo et al. [3]. Theorem 3 uses only the semigroup property of depolarizing channels (Lemma 4) and a convex-mixture/TVD argument; it does not assume the conclusion. The self-citations (Refs. [52,54,55]) are used for an alternative low-degree truncation and for related boson-sampling settings; the main proof re-derives its truncation in Appendices C–D, so these citations are not load-bearing. The paper itself acknowledges that Conjecture 1 remains open for the required inverse-polynomial error, and this is a stated limitation rather than a circular step. No prediction reduces by construction to its input, and no parameter is fitted and then renamed as a prediction.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

The paper is a conditional complexity-theoretic result. It introduces no physical free parameters or invented entities. The Chebyshev truncation parameter ρ and degree l are proof-optimization devices, not free physical parameters. The load-bearing axioms are Conjecture 1, the non-collapse of PH, and standard Haar/Pauli-invariance properties of local random circuits; the simulability side additionally imports the published convergence-to-uniformity theorem of Dalzell et al.

axioms (6)
  • domain assumption Conjecture 1: there exists a circuit architecture A0 such that A0-Ideal-Probability-Estimation (Definition 6) is #P-hard with inverse-polynomial additive error.
    Used to transfer ideal hardness to noisy hardness; Theorems 2 and 4 are conditional on it. It is the standard average-case #P-hardness conjecture in the RCS literature, still open for inverse-polynomial error.
  • domain assumption The polynomial hierarchy does not collapse to a finite level.
    Standard complexity assumption invoked in Lemma 1 and Theorem 4; the conclusion 'unless PH collapses' is the contrapositive.
  • standard math Local Haar-random circuit ensemble H_A is Pauli-invariant (left- and right-multiplication by Paulis preserves the ensemble).
    Used in Theorem 3 to ensure Cs is drawn from the same ensemble, and in fixing the output string to 0^n; follows from Haar measure invariance.
  • standard math Depolarizing channels compose as E_{γ1} ∘ E_{γ2} = E_{γ'} with γ' = γ1 + γ2 − γ1γ2.
    Lemma 4; elementary composition rule used in the monotonicity reduction.
  • standard math Lemma 8 (Kondo et al.): interpolation error bound for equally spaced points with factor (e/Δ)^l.
    External cited theorem used in Appendix B to bound extrapolation error.
  • domain assumption Dalzell et al. convergence-to-uniformity theorem: efficient classical simulation for γ = ω(log n/(nd)) on layered, regularly connected architectures within γ = O(1/n).
    External published theorem [16]; used only for Corollary 1 (the matching transition), not for the hardness theorem.

pith-pipeline@v1.3.0-alltime-deepseek · 27222 in / 29027 out tokens · 284348 ms · 2026-08-01T09:21:19.793034+00:00 · methodology

0 comments
read the original abstract

Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength $\gamma$. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever $\gamma=O(\log n/(nd))$ for $n$-qubit circuits of depth $d$, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for $\gamma=\omega(\log n/(nd))$ on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies $\gamma=\Theta(\log n/(nd))$ as the asymptotic complexity-transition scale.

Figures

Figures reproduced from arXiv: 2607.20804 by Byeongseon Go, Changhun Oh, Hyunseok Jeong.

Figure 1
Figure 1. Figure 1: FIG. 1. Complexity phase diagram for simulating (sampling) [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Schematics of our RCS settings. (a) Schematic of idea [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Logical flow of the noisy-RCS sampling-hardness proo [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

85 extracted references · 13 linked inside Pith

  1. [1]

    Subsequently, Ref

    Reference [1] established the #P-hardness of A-Ideal-Probability- Estimation in the setting of exact computation (ε0 = 0). Subsequently, Ref. [4] strengthened this result by improving the tolerated additive-error scale to ε0 = e−O(m3), where m denotes the number of gates in an n-qubit circuit. Further robustness was obtained in Refs. [3, 53], achieving th...

  2. [2]

    Noise and the frontier of quantum supremacy

    Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu. Noise and the frontier of quantum supremacy. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1308–

    2021

  3. [3]

    We begin by reviewing prior analyses on ideal RCS, highlighting the key requirements in proving its hardness. Building on this foundation, we then introduce our main hardness results for noisy RCS and identify the noise-strength thresholds below which noisy RCS retains the hardness of ideal RCS. A. Hardness framework for ideal RCS We start with hardness a...

  4. [4]

    VII, we conclude with remarks and directions for future work

    Finally, in Sec. VII, we conclude with remarks and directions for future work. II. MAIN RESULT AND RELATION TO PRIOR WORK In this section, we summarize our main hardness result and compare it with the most closely related hardness and simulability results for noisy RCS. Our result has two principal implications. First, the noisy- RCS hardness theorem reli...

  5. [5]

    Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent

    Hari Krovi. Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent. arXiv preprint arXiv:2206.05642, 2022

    Pith/arXiv arXiv 2022

  6. [6]

    ( 10), respectively

    and Eq. ( 10), respectively. IV. MAIN PROBLEMS AND RESULTS This section presents our main classical-simulation hardness results for noisy RCS, where the overall argument is outlined in Fig

  7. [7]

    simulation

    Specifically, we show that if there exists a polynomial-time classical sampler that approximates noisy RCS at noise strength γ1 within TVD error β, then for any γ2 ≥ γ1 there also exists a polynomial- time classical sampler that approximates noisy RCS at noise strength γ2 within the same TVD error β. Here, “simulation” refers to the standard classical 10 a...

  8. [8]

    Quantum computational advantage via 60-qubit 24-cycle random circuit sampling

    Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, et al. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. Science bulletin , 67(3):240–245, 2022

    2022

  9. [9]

    Phase transitions in random circuit sampling

    Alexis Morvan, B Villalonga, X Mi, S Mandr` a, A Bengtsson, PV Klimov, Z Chen, S Hong, C Erickson, IK Drozdov, et al. Phase transitions in random circuit sampling. Nature, 634(8033):328–333, 2024

    2024

  10. [10]

    Computational power of random quantum circuits in arbitrary geometries

    Matthew DeCross, Reza Haghshenas, Minzhao Liu, Enrico Rinaldi, Johnnie Gray, Yuri Alexeev, Charles H Baldwin, John P Bartolotta, Matthew Bohn, Eli Chertkov, et al. Computational power of random quantum circuits in arbitrary geometries. Physical Review X, 15(2):021052, 2025

    2025

  11. [11]

    On the complexity and verification of quantum random circuit sampling

    Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics , 15(2):159–163, 2019

    2019

  12. [12]

    Limitations of noisy reversible computation

    Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan. Limitations of noisy reversible computation. arXiv preprint quant-ph/9611028 , 1996

    Pith/arXiv arXiv 1996

  13. [13]

    Thus, under Conjecture 1, this yields the #P-hardness claimed in Theorem 2

    ensures that the reduction has only polynomial overhead. Thus, under Conjecture 1, this yields the #P-hardness claimed in Theorem 2. C. Hardness of classically simulating noisy RCS In the preceding arguments, we identified the boundary of γ∗ such that the ( A0, γ∗)-Noisy-Probability- Estimation task is #P-hard under Conjecture 1. By the standard reduction ...

  14. [14]

    Quantum supremacy and hardness of estimating output probabilities of quantum circuits

    Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh. Quantum supremacy and hardness of estimating output probabilities of quantum circuits. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1296–1307. IEEE, 2022

    2021

  15. [15]

    over k ≥ l + 1 and then multiplying the resulting expression by (1 − 3γ/4)−N +l, in analogy with the low-degree truncation method of Ref. [54]. This approach yields the bound ε = poly( nd, ε−1 0 , δ−1 0 )−1 exp(−Cn(d + 1)γ∗) with C ≈ 60, which achieves the same asymptotic scaling of the noise-strength threshold γ∗ = O(log n/(nd)), but with an exponent con...

  16. [16]

    (15) for each fixed γ ∈ [0, γmax] by Pr C∼HA [ |˜p(C, γ) −˜pl(C, γ)| > ε′ 2n ] ≤ δ, (18) where the approximation error ε′ can be chosen as ε′ := 4N 2γmax lδ ( 3e N γmax 8l ) l

    close to ˜p(C, γ) in Eq. (15) for each fixed γ ∈ [0, γmax] by Pr C∼HA [ |˜p(C, γ) −˜pl(C, γ)| > ε′ 2n ] ≤ δ, (18) where the approximation error ε′ can be chosen as ε′ := 4N 2γmax lδ ( 3e N γmax 8l ) l . (19) Proof. See Appendix A We now state the main reduction lemma for proving Theorem 2, in which we explicitly establish a complexity- theoretic reduction....

  17. [17]

    The hardness of random quantum circuits

    Ramis Movassagh. The hardness of random quantum circuits. Nature Physics, pages 1–6, 2023

    2023

  18. [18]

    Quantum supremacy using a programmable superconducting processor

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019

    2019

  19. [19]

    Strong quantum computational advantage using a superconducting quantum processor

    Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al. Strong quantum computational advantage using a superconducting quantum processor. Physical review letters, 127(18):180501, 2021

    2021

  20. [20]

    Classically sampling noisy quantum circuits in quasi-polynomial time under approximate markovianity

    Yifan F Zhang, Su-un Lee, Liang Jiang, and Sarang Gopalakrishnan. Classically sampling noisy quantum circuits in quasi-polynomial time under approximate markovianity. arXiv preprint arXiv:2510.06324 , 2025

    arXiv 2025

  21. [21]

    Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor

    Dongxin Gao, Daojin Fan, Chen Zha, Jiahao Bei, Guoqing Cai, Jianbin Cai, Sirui Cao, Fusheng Chen, Jiang Chen, Kefu Chen, et al. Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor. Physical Review Letters, 134(9):090601, 2025

    2025

  22. [22]

    Noisy random quantum circuit sampling and its classical simulation

    Meng Zhang, Chao Wang, and Yongjian Han. Noisy random quantum circuit sampling and its classical simulation. Advanced Quantum Technologies , 6(7):2300030, 2023

    2023

  23. [23]

    Efficient classical simulation of noisy quantum computation.arXiv preprint arXiv:1810.03176, 2018

    Xun Gao and Luming Duan. Efficient classical simulation of noisy quantum computation.arXiv preprint arXiv:1810.03176, 2018

    Pith/arXiv arXiv 2018

  24. [24]

    Tight bounds on the convergence of noisy random circuits to the uniform distribution

    Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V Gorshkov, Bill Fefferman, and Michael J Gullans. Tight bounds on the convergence of noisy random circuits to the uniform distribution. PRX Quantum, 3(4):040329, 2022

    2022

  25. [25]

    A polynomial-time classical algorithm for noisy random circuit sampling

    Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 945–957, 2023

    2023

  26. [26]

    Random quantum circuits transform local noise into global white noise

    Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brand˜ ao. Random quantum circuits transform local noise into global white noise. Communications in Mathematical Physics , 405(3):78, 2024

    2024

  27. [27]

    Limitations of noisy geometrically local quantum circuits

    Jon Nelson, Joel Rajakumar, and Michael J Gullans. Limitations of noisy geometrically local quantum circuits. arXiv preprint arXiv:2510.06346 , 2025

    arXiv 2025

  28. [28]

    Polynomial-time classical simulation of noisy quantum circuits with naturally fault-tolerant gates

    Jon Nelson, Joel Rajakumar, Dominik Hangleiter, and Michael J Gullans. Polynomial-time classical simulation of noisy quantum circuits with naturally fault-tolerant gates. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1309–

    2026

  29. [29]

    By construction, ¯p(C, γ2, x) = E s∼wγadd [ ¯p(Cs, γ1, x)]

    and (ii) sampling x according to ¯p(Cs, γ1, x). By construction, ¯p(C, γ2, x) = E s∼wγadd [ ¯p(Cs, γ1, x)] . (42) The TVD between ¯p(C, γ2, x) and ˜p(C, γ2, x) is bounded by 1 2 ∑ x∈{0,1}n ⏐ ⏐¯p(C, γ2, x) −˜p(C, γ2, x) ⏐ ⏐ = 1 2 ∑ x∈{0,1}n ⏐ ⏐ E s∼wγadd [¯p(Cs, γ1, x) −˜p(Cs, γ1, x)] ⏐ ⏐ (43) ≤ E s∼wγadd   1 2 ∑ x∈{0,1}n ⏐ ⏐¯p(Cs, γ1, x) −˜p(Cs, γ1, x) ...

  30. [30]

    Classical simulation of noisy random circuits from exponential decay of correlation

    Su-un Lee, Soumik Ghosh, Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang. Classical simulation of noisy random circuits from exponential decay of correlation. arXiv preprint arXiv:2510.06328 , 2025

    arXiv 2025

  31. [31]

    Efficient classical simulation of noisy random quantum circuits in one dimension

    Kyungjoo Noh, Liang Jiang, and Bill Fefferman. Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum, 4:318, 2020

    2020

  32. [32]

    Density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity

    Thomas Ayral, Thibaud Louvet, Yiqing Zhou, Cyprien Lambert, E Miles Stoudenmire, and Xavier Waintal. Density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity. PRX Quantum, 4(2):020304, 2023

    2023

  33. [33]

    Classical simulation of intermediate-size quantum circuits

    Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. arXiv preprint arXiv:1805.01450, 2018

    Pith/arXiv arXiv 2018

  34. [34]

    A fourier analysis framework for approximate classical simulations of quantum circuits

    Cristina Cirstoiu. A fourier analysis framework for approximate classical simulations of quantum circuits. arXiv preprint arXiv:2410.13856 , 2024

    Pith/arXiv arXiv 2024

  35. [35]

    Classical simulation of quantum supremacy circuits

    Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, et al. Classical simulation of quantum supremacy circuits. arXiv preprint arXiv:2005.06787, 2020

    Pith/arXiv arXiv 2005

  36. [36]

    Computational advantage of quantum random sampling

    Dominik Hangleiter and Jens Eisert. Computational advantage of quantum random sampling. Reviews of Modern Physics, 95(3):035001, 2023

    2023

  37. [37]

    A polynomial-time classical algorithm for noisy quantum circuits

    Thomas Schuster, Chao Yin, Xun Gao, and Norman Y Yao. A polynomial-time classical algorithm for noisy quantum circuits. Physical Review X, 15(4):041018, 2025

    2025

  38. [38]

    Simulation of quantum circuits using the big-batch tensor network method

    Feng Pan and Pan Zhang. Simulation of quantum circuits using the big-batch tensor network method. Physical Review Letters, 128(3):030501, 2022

    2022

  39. [39]

    Classical simulations 20 of noisy variational quantum circuits

    Enrico Fontana, Manuel S Rudolph, Ross Duncan, Ivan Rungger, and Cristina Cˆ ırstoiu. Classical simulations 20 of noisy variational quantum circuits. npj Quantum Information, 11(1):84, 2025

    2025

  40. [40]

    Enabling large-depth simulation of noisy quantum circuits with positive tensor networks

    Ambroise M¨ uller, Thomas Ayral, and Corentin Bertrand. Enabling large-depth simulation of noisy quantum circuits with positive tensor networks. arXiv preprint arXiv:2403.00152, 2024

    Pith/arXiv arXiv 2024

  41. [41]

    Simulating noisy quantum circuits with matrix product density operators

    Song Cheng, Chenfeng Cao, Chao Zhang, Yongxiang Liu, Shi-Yao Hou, Pengxiang Xu, and Bei Zeng. Simulating noisy quantum circuits with matrix product density operators. Physical review research, 3(2):023005, 2021

    2021

  42. [42]

    and ( 31), the first inequality follows from convexity of TVD, and the final inequality follows from Eq. ( 41). We can now prove Theorem 3. Proof of Theorem 3. Suppose we are given oracle access to an approximate sampler for noisy RCS at a noise strength γ1. For an input circuit C0 ∼ H A over a fixed architecture A, the sampler outputs x ∈ { 0, 1}n according...

    2024

  43. [43]

    Scalable projected entangled-pair state representation of random quantum circuit states

    Sung-Bin B Lee, Hee Ryang Choi, Daniel Donghyon Ohm, and Seung-Sup B Lee. Scalable projected entangled-pair state representation of random quantum circuit states. Physical Review Research , 7(3):033252, 2025

    2025

  44. [44]

    Relative entropy convergence for depolarizing channels

    Alexander M¨ uller-Hermes, Daniel Stilck Fran¸ ca, and Michael M Wolf. Relative entropy convergence for depolarizing channels. Journal of Mathematical Physics , 57(2), 2016

    2016

  45. [45]

    Noise-induced shallow circuits and absence of barren plateaus

    Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck Fran¸ ca, and Yihui Quek. Noise-induced shallow circuits and absence of barren plateaus. arXiv preprint arXiv:2403.13927 , 2024

    Pith/arXiv arXiv 2024

  46. [46]

    Limitations of optimization algorithms on noisy quantum devices

    Daniel Stilck Fran¸ ca and Raul Garcia-Patron. Limitations of optimization algorithms on noisy quantum devices. Nature Physics , 17(11):1221–1227, 2021

    2021

  47. [47]

    Efficient classical simulation of random shallow 2d quantum circuits

    John C Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow. Efficient classical simulation of random shallow 2d quantum circuits. Physical Review X , 12(2):021021, 2022

    2022

  48. [48]

    Efficient sampling of noisy shallow circuits via monitored unraveling

    Zihan Cheng and Matteo Ippoliti. Efficient sampling of noisy shallow circuits via monitored unraveling. PRX Quantum, 4(4):040326, 2023

    2023

  49. [49]

    Optimized trajectory unraveling for classical simulation of noisy quantum dynamics

    Zhuo Chen, Yimu Bao, and Soonwon Choi. Optimized trajectory unraveling for classical simulation of noisy quantum dynamics. Physical Review Letters , 133(23):230403, 2024

    2024

  50. [50]

    Efficient simulation of one-dimensional quantum many-body systems

    Guifr´ e Vidal. Efficient simulation of one-dimensional quantum many-body systems. Physical review letters , 93(4):040502, 2004

    2004

  51. [51]

    Simulating quantum computation by contracting tensor networks

    Igor L Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing , 38(3):963–981, 2008

    2008

  52. [52]

    On the simulation of quantum circuits

    Richard Jozsa. On the simulation of quantum circuits. arXiv preprint quant-ph/0603163 , 2006

    Pith/arXiv arXiv 2006

  53. [53]

    On approximation algorithms for# p

    Larry Stockmeyer. On approximation algorithms for# p. SIAM Journal on Computing , 14(4):849–861, 1985

    1985

  54. [54]

    Exponential improvements to the average- case hardness of bosonsampling

    Adam Bouland, Ishaun Datta, Bill Fefferman, and Felipe Hern´ andez. Exponential improvements to the average- case hardness of bosonsampling. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 912–933. IEEE, 2025

    2025

  55. [55]

    Characterizing quantum supremacy in near-term devices

    Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, 2018

    2018

  56. [56]

    Fourier analysis of sampling from noisy chaotic quantum circuits

    Sergio Boixo, Vadim N Smelyanskiy, and Hartmut Neven. Fourier analysis of sampling from noisy chaotic quantum circuits. arXiv preprint arXiv:1708.01875 , 2017

    Pith/arXiv arXiv 2017

  57. [57]

    Effect of nonunital noise on random-circuit sampling

    Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. Effect of nonunital noise on random-circuit sampling. PRX Quantum , 5(3):030317, 2024

    2024

  58. [58]

    Entanglement dynamics of noisy random circuits

    Zhi Li, Shengqi Sang, and Timothy H Hsieh. Entanglement dynamics of noisy random circuits. Physical Review B , 107(1):014307, 2023

    2023

  59. [59]

    Entanglement entropy scaling of noisy random quantum circuits in two dimensions

    Meng Zhang, Chao Wang, Shaojun Dong, Hao Zhang, Yongjian Han, and Lixin He. Entanglement entropy scaling of noisy random quantum circuits in two dimensions. Physical Review A , 106(5):052430, 2022

    2022

  60. [60]

    Noise-induced entanglement transition in one-dimensional random quantum circuits

    Qi Zhang and Guang-Ming Zhang. Noise-induced entanglement transition in one-dimensional random quantum circuits. Chinese Physics Letters , 39(5):050302, 2022

    2022

  61. [61]

    The computational complexity of linear optics

    Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty- third annual ACM symposium on Theory of computing , pages 333–342, 2011

    2011

  62. [62]

    Exploring shallow-depth boson sampling: Toward a scalable quantum advantage

    Byeongseon Go, Changhun Oh, Liang Jiang, and Hyunseok Jeong. Exploring shallow-depth boson sampling: Toward a scalable quantum advantage. Physical Review A , 109(5):052613, 2024

    2024

  63. [63]

    Complexity classification of conjugated clifford circuits

    Adam Bouland, Joseph F Fitzsimons, and Dax Enshan Koh. Complexity classification of conjugated clifford circuits. arXiv preprint arXiv:1709.01805 , 2017

    Pith/arXiv arXiv 2017

  64. [64]

    Quantum computational advantage of noisy boson sampling with partially distinguishable photons

    Byeongseon Go, Changhun Oh, and Hyunseok Jeong. Quantum computational advantage of noisy boson sampling with partially distinguishable photons. PRX Quantum, 6(3):030362, 2025

    2025

  65. [65]

    Sufficient conditions for hardness of lossy gaussian boson sampling

    Byeongseon Go, Changhun Oh, and Hyunseok Jeong. Sufficient conditions for hardness of lossy gaussian boson sampling. arXiv preprint arXiv:2511.07853 , 2025

    arXiv 2025

  66. [66]

    Complexity-theoretic foundations of bosonsampling with a linear number of modes

    Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, and Michal Oszmaniec. Complexity-theoretic foundations of bosonsampling with a linear number of modes. arXiv preprint arXiv:2312.00286, 2023

    Pith/arXiv arXiv 2023

  67. [67]

    Pp is as hard as the polynomial-time hierarchy

    Seinosuke Toda. Pp is as hard as the polynomial-time hierarchy. SIAM Journal on Computing , 20(5):865–877, 1991

    1991

  68. [68]

    Efficient classical algorithm for boson sampling with partially distinguishable photons

    Jelmer J Renema, Adrian Menssen, William R Clements, Gil Triginer, William S Kolthammer, and Ian A Walmsley. Efficient classical algorithm for boson sampling with partially distinguishable photons. Physical review letters, 120(22):220502, 2018

    2018

  69. [69]

    Classically simulating near- term partially-distinguishable and lossy boson sampling

    Alexandra E Moylett, Ra´ ul Garc´ ıa-Patr´ on, Jelmer J Renema, and Peter S Turner. Classically simulating near- term partially-distinguishable and lossy boson sampling. Quantum Science and Technology , 5(1):015001, 2019

    2019

  70. [70]

    Noise in boson sampling and the threshold of efficient classical simulatability

    Valery S Shchesnovich. Noise in boson sampling and the threshold of efficient classical simulatability. Physical Review A, 100(1):012340, 2019

    2019

  71. [71]

    Simulating boson sampling in lossy architectures

    Ra´ ul Garc´ ıa-Patr´ on, Jelmer J Renema, and Valery Shchesnovich. Simulating boson sampling in lossy architectures. Quantum, 3:169, 2019

    2019

  72. [72]

    Classical simulation of photonic linear optics with lost particles

    Micha/suppress l Oszmaniec and Daniel J Brod. Classical simulation of photonic linear optics with lost particles. New Journal of Physics , 20(9):092002, 2018

    2018

  73. [73]

    Classical simulation of linear optics subject to nonuniform losses

    Daniel Jost Brod and Micha/suppress l Oszmaniec. Classical simulation of linear optics subject to nonuniform losses. 21 Quantum, 4:267, 2020

    2020

  74. [74]

    Classical simulation of lossy boson sampling using matrix product operators

    Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang. Classical simulation of lossy boson sampling using matrix product operators. Physical Review A , 104(2):022407, 2021

    2021

  75. [75]

    On classical simulation algorithms for noisy boson sampling

    Changhun Oh, Liang Jiang, and Bill Fefferman. On classical simulation algorithms for noisy boson sampling. arXiv preprint arXiv:2301.11532 , 2023

    Pith/arXiv arXiv 2023

  76. [76]

    Classical simulability of constant- depth linear-optical circuits with noise

    Changhun Oh. Classical simulability of constant- depth linear-optical circuits with noise. npj Quantum Information, 11(1):126, 2025

    2025

  77. [77]

    Achieving quantum supremacy with sparse and noisy commuting quantum computations

    Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1:8, 2017

    2017

  78. [78]

    Polynomial-time classical simulation of noisy iqp circuits with constant depth

    Joel Rajakumar, James D Watson, and Yi-Kai Liu. Polynomial-time classical simulation of noisy iqp circuits with constant depth. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1037–1056. SIAM, 2025

    2025

  79. [79]

    Recent theoretical and experimental progress on boson sampling

    Changhun Oh. Recent theoretical and experimental progress on boson sampling. Current Optics and Photonics, 9(1):1–18, 2025

    2025

  80. [80]

    Faster algorithms via approximation theory

    Sushant Sachdeva, Nisheeth K Vishnoi, et al. Faster algorithms via approximation theory. Foundations and Trends in Theoretical Computer Science , 9(2):125–210, 2014

    2014

Showing first 80 references.