Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Noise makes quantum sampling classically easy at sharp thresholds

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-04 07:49 UTC pith:YIMT2KWL

load-bearing objection Useful extension of MPS simulation to lossy boson sampling and noisy IQP; clean decompositions and numeric resource bounds, but the analytic Haar-random threshold rests on an unproven commutation approximation. the 3 major comments →

arxiv 2510.24137 v3 pith:YIMT2KWL submitted 2025-10-28 quant-ph

Matrix product state approach to lossy boson sampling and noisy IQP sampling

Sojeong Park , Changhun Oh This is my paper
classification quant-ph MSC 81P68
keywords matrix product statesboson samplingIQP samplingclassical simulabilityphoton lossPauli noiseRényi entanglement entropyquantum advantage benchmark
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 extends the matrix-product-state (MPS) approach—the tool behind the state-of-the-art classical simulator for Gaussian boson sampling—to two other central noisy sampling problems: lossy boson sampling and noisy IQP sampling. The key move is to decompose the noisy mixed input state into a probabilistic mixture of pure states, each of which stays only weakly entangled after the circuit runs, so the output admits an efficient MPS approximation. For boson sampling, this reproduces the known classical-simulability boundary at photon transmission rate η = O(1/√N) for single-photon, Fock, and cat-state inputs. For noisy IQP circuits, it gives classical simulability once the depth reaches d = O(log n / |log(1−2p)|) under dephasing or depolarizing noise. Unlike fixed-approximation methods, the MPS approach makes accuracy tunable by increasing the bond dimension, and the paper provides concrete bond-dimension and memory estimates for realistic circuits.

Core claim

The paper claims that the MPS paradigm for classical simulation of noisy quantum sampling extends beyond Gaussian states. The central identity is a pure-state decomposition of the noisy input: a lossy single photon σ̂ = (1−η)|0⟩⟨0| + η|1⟩⟨1| equals ½(|ψ+⟩⟨ψ+| + |ψ−⟩⟨ψ−|) with |ψ±⟩ = √(1−η)|0⟩ ± √η|1⟩; a dephased |+⟩ analogously equals ½(|ϕ+⟩⟨ϕ+| + |ϕ−⟩⟨ϕ−|). Sampling the mixture is equivalent to picking a pure component and evolving it unitarily. The paper proves that after the random circuit each component's entanglement, measured by Rényi entropy, is O(log N) when η = O(1/√N) (boson sampling) or (1−2p)^{2d} = O(log n / n) (IQP). Lower bounds show that below this loss/noise the required MPS

What carries the argument

The load-bearing object is the pure-state decomposition of the noisy input density matrix. For a lossy single photon, the identity σ̂ = (1−η)|0⟩⟨0| + η|1⟩⟨1| = ½(|ψ+⟩⟨ψ+| + |ψ−⟩⟨ψ−|) converts mixed-state simulation into sampling over two simple pure states. After a linear-optical circuit, each component factorizes across modes, and its bipartite entanglement can be computed in closed form using the split-operator decomposition b̂ᵢ† = cosθᵢ B̂_{u,i}† + sinθᵢ B̂_{d,i}†. The analytic step that makes everything work is that, for M = ω(N²) modes, the split operators approximately satisfy canonical commutation relations, so the reduced density matrix factorizes and its Rényi entropy is tightly bou

Load-bearing premise

The entire simulability threshold rests on the assumption that loss is uniform across modes (same transmission rate and depth per mode), so it can be commuted to the front of the circuit; with non-uniform loss, the proposed maximum-rate fix is not proven to preserve the Θ(1/√N) boundary.

What would settle it

For a lossy boson sampling instance with, say, N = 10 photons and M = 1000 modes, compute the exact von Neumann entropy of the output state for a Haar-random unitary at transmission rate η = 5/√N ≈ 1.58. If the entropy is not bounded by c log N for a constant c but scales roughly linearly with N, the claimed simulability threshold is false. Alternatively, search numerically over small random unitaries for any lossy circuit whose output entanglement exceeds the balanced-pairing bound used in the analysis; finding one would break the worst-case conjecture on which the threshold rests.

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

If this is right

  • Lossy boson sampling experiments with transmission rate at or below the Θ(1/√N) frontier can be simulated classically with polynomial resources, giving experimenters a concrete benchmark for quantum-advantage claims.
  • For noisy IQP circuits, any experiment aiming at quantum advantage must run at depth d asymptotically larger than log n / |log(1−2p)|; below that depth the MPS simulator runs in polynomial time.
  • Because increasing the bond dimension continuously improves accuracy, the algorithm remains usable across the entire noise range, not only in the asymptotically easy regime, making it a practical benchmarking tool.
  • The resource estimates show that an experimentally motivated interferometer structure requires an order of magnitude smaller bond dimension than Haar-random unitaries, translating into roughly 100× less memory and 1000× less time.
  • Fock-state and cat-state boson sampling share the same η = O(1/√N) simulability threshold, indicating the threshold is tied to the loss channel and the single-photon superposition rather than to the specific input state.

Where Pith is reading between the lines

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

  • The pure-state decomposition technique is likely portable to other noise models—such as mode-dependent loss or correlated photon loss—provided one can find ensembles of pure states whose post-circuit entanglement stays low; the paper does not prove such extensions but the structure strongly suggests them.
  • The paper's worst-case entanglement conjecture, that the balanced-pairing circuit maximizes the Rényi entropy even under loss, is stated without proof; a numerical search over small random unitaries could confirm or refute whether the analytic threshold is truly worst-case.
  • The IQP simulability threshold is derived from the worst case over all phase functions; realistic IQP circuits with structured phases might become classically simulable at considerably shallower depths than the bound suggests.
  • If the uniform-loss assumption is relaxed, the proposed fix (using the maximum transmission rate) is not proven to preserve the Θ(1/√N) threshold, so a mode-dependent MPS ansatz is a natural target for future work.

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

3 major / 4 minor

Summary. The paper extends the MPS-based pure-state decomposition method previously applied to Gaussian boson sampling to two other noisy sampling settings: lossy boson sampling (with single-photon, Fock, and cat-state inputs) and IQP sampling under dephasing and depolarizing noise. For lossy single-photon boson sampling, the central analytic result is an upper bound on the Rényi entanglement entropy of the output state, S ≤ N η^{2α}/(1−α) (Eq. 36), giving a classically simulable regime at transmission rates η = O(1/√N) and a conjectured hard regime for larger η. For IQP sampling, the paper proves an upper bound on the ERE via a unital dephasing channel, yielding classical simulability for circuit depth d ≥ O(log n / |log(1−2p)|) under dephasing or depolarizing noise, consistent with an independent recent result [42]. The paper also provides numerical bond-dimension and memory estimates for realistic circuit families.

Significance. If the technical gaps are repaired, this is a valuable contribution: it generalizes a state-of-the-art classical simulation technique to new noisy sampling models, reproduces the known Θ(1/√N) boson-sampling threshold and the noisy-IQP depth threshold, and provides tunable accuracy and practical resource estimates. Strengths include the exact identity of the pure-state decomposition (Eq. 17), the rigorous IQP upper bound via the unital-channel majorization argument (Sec. V B), and the numerical comparison to an independent method [42]. The main weakness is that the analytic threshold for Haar-random lossy boson sampling rests on an approximate commutation statement whose proof is incorrect and whose induced error is unquantified.

major comments (3)
  1. [Appendix B, Eqs. (B4)–(B9)] The probability inequalities are reversed. Chebyshev gives Pr[|X| ≤ ε] ≥ 1 − Var/ε², not ≤. As written, Eqs. (B4), (B6), (B7), and (B9) do not establish that the split operators approximately commute with high probability. This is load-bearing because the exact commutation relation Eq. (27) is used to derive the factorized output state and the entropy bound Eqs. (33)–(36). Please correct the inequalities and redo the union bound; with the corrected direction, the statement is plausibly recoverable when M = ω(N²).
  2. [Sec. IV C, Eqs. (27)–(36)] Even if the commutator [B_u,j, B†_u,k] is O(1/M) with high probability, the paper does not bound the induced error in the reduced density matrix or in the Rényi entropy. The exact output state contains cross-mode terms connecting different j; these can increase entanglement. The claim S ≤ N η^{2α}/(1−α) for Haar-random circuits is therefore not rigorously established. A continuity argument (e.g., a trace-norm or fidelity bound on the reduced states) is needed. Absent this, the analytic simulability threshold for Haar-random circuits should be stated as conditional on the approximate commutation being valid to the required accuracy.
  3. [Sec. IV C, Eq. (43) and following paragraph] The paper states that the balanced-pairing circuit of Eq. (43) maximizes entanglement in the lossless case and conjectures that this also holds in the lossy case, without proof. This conjecture underlies the lower-bound/inapproximability claim in Eqs. (38)–(40). The upper bound (simulability) does not require the conjecture, but the transition statement 'hard to simulate using our MPS method' for η = Ω(1/√N) does. Please either prove the conjecture or clearly label the hard-regime part as conditional, including in the abstract/introduction where the Θ(1/√N) transition is claimed.
minor comments (4)
  1. [Sec. IV F, Eq. (71)] There is an extra factor 1/2 in Eq. (71) that is not present in Eq. (70); this appears to be a typo and should be corrected.
  2. [Sec. II A] The generalization to non-uniform loss via 'setting the overall transmission rate as the maximum among the modes' is asserted without justification. Since all analytic results assume uniform loss, this remark should be marked as a heuristic or supported by a proof.
  3. [Throughout] There are formatting/typo issues in the Rényi entropy notation ('R´ enyi') and in the rendering of some equations. Also, the notation B_u,j and B_d,j should specify the range of indices j (input photon modes) more explicitly.
  4. [Sec. V B, Eq. (92)] The inequality ln(q0^{2α}+q1^{2α}) ≤ (1−2p_d)^{2α} is stated without derivation; a short proof or reference would improve readability.

Circularity Check

0 steps flagged

No significant circularity: the lossy-state decompositions are exact identities, the entropy thresholds follow from those identities plus the standard ERE/MPS criterion, and the IQP threshold is benchmarked against an independent method.

full rationale

The paper's central reductions are self-contained algebraic identities rather than fitted or circular inputs. The lossy single-photon decomposition (Eqs. 17-18), the Fock-state phase-averaged decomposition (Eq. 47), and the cat-state decomposition (Eqs. 57-60) are exact representations of the stated loss channels; sampling from them exactly reproduces the mixed input. The subsequent Rényi-entropy bounds are computed from those decompositions (e.g., Eqs. 33-39 for boson sampling, Eqs. 87-94 for IQP) using the standard Schuch et al. criterion that O(log N) entropy implies efficient MPS simulation. No parameter is fitted to any target threshold, and the claimed O(1/√N) / O(log n / |log(1-2p)|) thresholds are outputs of the calculation rather than inputs. The IQP result is explicitly compared with the independent method of Ref. [42]. The paper does contain self-citations involving co-author Oh (Refs. [27,31,33,35]), and Sec. IV C invokes [33,35] for the lossless maximum-entanglement circuit, then explicitly concedes that the lossy generalization is only a conjecture: 'Although we do not prove that this also holds in the lossy case, we conjecture that this is true.' That is a rigor gap, and Appendix B's probability inequalities are written in the wrong direction for Chebyshev, but these are correctness concerns, not circular reductions: the central entropy derivation does not presuppose the claimed simulability thresholds. The honest finding is therefore no significant circularity, with the caveats noted.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 0 invented entities

No new physical entities are introduced. The derivation uses no fitted constants; the asymptotic thresholds follow from entanglement-entropy bounds. The only user-chosen parameter is the numerical target error ε=0.01. Standard MPS/majorization results and the uniform-loss model are the main background assumptions.

free parameters (1)
  • target MPS approximation error ε = 0.01
    Chosen by hand for bond-dimension/memory estimates (Figs. 6 and 10); it sets the truncation threshold but does not affect the asymptotic simulability threshold.
axioms (4)
  • standard math MPS entanglement-simulability criterion: Rényi entropy O(log L) for all bipartitions implies efficient MPS simulation, while algebraic scaling implies inefficiency.
    Invoked throughout Secs. IV and V, following Schuch et al. [41].
  • domain assumption Uniform per-mode transmission rate and equal circuit depth, allowing all loss channels to be commuted to the front.
    Sec. II A states this explicitly and uses it to reduce the circuit to a Haar-random interferometer preceded by uniform loss.
  • domain assumption M = ω(N²) and Haar-random unitaries make the split operators B_{u,j}, B_{d,j} approximately canonical.
    App. B proves the commutator is O(1/sqrt(M)) with high probability; the entropy formulas in Sec. IV C assume exact commutation.
  • ad hoc to paper The worst-case lossy linear-optical circuit is the balanced-pairing circuit of Eq. (43).
    Sec. IV C states this as a conjecture for the lossy case: 'Although we do not prove that this also holds in the lossy case, we conjecture that this is true.' It supports the worst-case resource estimates in Fig. 6.

pith-pipeline@v1.3.0-alltime-deepseek · 77360 in / 12819 out tokens · 124555 ms · 2026-08-04T07:49:27.115785+00:00 · methodology

0 comments
read the original abstract

Sampling problems have emerged as a central avenue for demonstrating quantum advantage on noisy intermediate-scale quantum devices. However, physical noise can fundamentally alter their computational complexity, often making them classically tractable. Motivated by the recent success of matrix product state (MPS)-based classical simulation of Gaussian boson sampling (Oh et al., 2024), we extend this framework to investigate the classical simulability of other noisy quantum sampling models. We develop MPS-based classical algorithms for lossy boson sampling and noisy instantaneous quantum polynomial-time (IQP) sampling, both of which retain the tunable accuracy characteristic of the MPS approach through the bond dimension. Our approach constructs pure-state decompositions of noisy or lossy input states whose components remain weakly entangled after circuit evolution, thereby providing a means to systematically explore the boundary between quantum-hard and classically-simulable regimes. For boson sampling, we analyze single-photon, Fock, and cat-state inputs, showing that classical simulability emerges at transmission rates scaling as $O(1/\sqrt{N})$, reaching the known boundary of quantum advantage with a tunable and scalable method. Beyond reproducing previous thresholds, our algorithm offers significantly improved control over the accuracy-efficiency trade-off. It further extends the applicability of MPS-based simulation to broader classes of noisy quantum sampling models, including IQP circuits.

Figures

Figures reproduced from arXiv: 2510.24137 by Changhun Oh, Sojeong Park.

Figure 1
Figure 1. Figure 1: FIG. 1. Photon loss in boson sampling circuit. (a) Lossy [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Setup of a depolarizing-noisy IQP circuit. (a) The [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Simulation of lossy boson sampling using pure-state [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Entanglement (von Neumann) entropy of the output [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Required bond dimension and memory to achieve an MPS approximation error [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. ERE with respect to input photon number [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Pure-state sampling from mixed inputs in an IQP [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. Simulation of depolarizing noise in IQP circuit. (a) Pauli [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10. Required resource to achieve an MPS approximation error of 0 [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Coherent-disorder-driven complexity transitions in a quantum-advantage architecture

    quant-ph 2026-07 conditional novelty 6.0

    Spatial disorder in two-qubit gate angles of a square-lattice IQP circuit drives first a loss of anticoncentration and then a collapse of tensor-network entanglement, pointing to two complexity transitions toward clas...

Reference graph

Works this paper leans on

55 extracted references · 7 linked inside Pith · cited by 1 Pith paper

  1. [1]

    P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, inProceedings 35th annual symposium on foundations of computer science (Ieee, 1994) pp. 124–134

    1994

  2. [2]

    Lloyd, Universal quantum simulators, Science273, 1073 (1996)

    S. Lloyd, Universal quantum simulators, Science273, 1073 (1996)

    1996

  3. [3]

    P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical review A52, R2493 (1995)

    1995

  4. [4]

    A. M. Steane, Error correcting codes in quantum theory, Physical Review Letters77, 793 (1996)

    1996

  5. [5]

    Quantum error correction below the surface code threshold, Nature638, 920 (2025). 17

    2025

  6. [6]

    B. M. Terhal, Quantum error correction for quantum memories, Reviews of Modern Physics87, 307 (2015)

    2015

  7. [7]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The computational complexity of linear optics, inProceedings of the forty- third annual ACM symposium on Theory of computing (2011) pp. 333–342

    2011

  8. [8]

    Bouland, B

    A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling, Nature Physics15, 159 (2019)

    2019

  9. [9]

    Arute, K

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell,et al., Quantum supremacy using a programmable superconducting processor, Nature574, 505 (2019)

    2019

  10. [10]

    Wu, W.-S

    Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, et al., Strong quantum computational advantage using a superconducting quantum processor, Physical review letters127, 180501 (2021)

    2021

  11. [11]

    Morvan, B

    A. Morvan, B. Villalonga, X. Mi, S. Mandr` a, A. Bengtsson, P. Klimov, Z. Chen, S. Hong, C. Erickson, I. Drozdov,et al., Phase transitions in random circuit sampling, Nature634, 328 (2024)

    2024

  12. [12]

    Zhong, H

    H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.- C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, et al., Quantum computational advantage using photons, Science370, 1460 (2020)

    2020

  13. [13]

    Zhong, Y.-H

    H.-S. Zhong, Y.-H. Deng, J. Qin, H. Wang, M.-C. Chen, L.-C. Peng, Y.-H. Luo, D. Wu, S.-Q. Gong, H. Su, et al., Phase-programmable Gaussian boson sampling using stimulated squeezed light, Physical review letters 127, 180502 (2021)

    2021

  14. [14]

    L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins,et al., Quantum computational advantage with a programmable photonic processor, Nature606, 75 (2022)

    2022

  15. [15]

    Deng, Y.-C

    Y.-H. Deng, Y.-C. Gu, H.-L. Liu, S.-Q. Gong, H. Su, Z.- J. Zhang, H.-Y. Tang, M.-H. Jia, J.-M. Xu, M.-C. Chen, et al., Gaussian boson sampling with pseudo-photon- number resolving detectors and quantum computational advantage, arXiv preprint arXiv:2304.12240 (2023)

    Pith/arXiv arXiv 2023

  16. [16]

    A. W. Young, S. Geller, W. J. Eckner, N. Schine, S. Glancy, E. Knill, and A. M. Kaufman, An atomic boson sampler, Nature629, 311 (2024)

    2024

  17. [17]

    H.-L. Liu, H. Su, S.-Q. Gong, Y.-C. Gu, H.-Y. Tang, M.-H. Jia, Q. Wei, Y. Song, D. Wang, M. Zheng, et al., Robust quantum computational advantage with programmable 3050-photon gaussian boson sampling, arXiv preprint arXiv:2508.09092 (2025)

    Pith/arXiv arXiv 2025

  18. [18]

    Boixo, S

    S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near- term devices, Nature Physics14, 595 (2018)

    2018

  19. [19]

    M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences467, 459 (2011)

    2011

  20. [20]

    H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang,et al., Boson sampling with 20 input photons and a 60-mode interferometer in a 1 0 14-dimensional hilbert space, Physical review letters123, 250503 (2019)

    2019

  21. [21]

    Bluvstein, S

    D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter,et al., Logical quantum processor based on reconfigurable atom arrays, Nature626, 58 (2024)

    2024

  22. [22]

    Neville, C

    A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing, Classical boson sampling algorithms with superior performance to near- term experiments, Nature Physics13, 1153 (2017)

    2017

  23. [23]

    Clifford and R

    P. Clifford and R. Clifford, The classical complexity of boson sampling, inProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2018) pp. 146–155

    2018

  24. [24]

    Oszmaniec and D

    M. Oszmaniec and D. J. Brod, Classical simulation of photonic linear optics with lost particles, New Journal of Physics20, 092002 (2018)

    2018

  25. [25]

    Garc ´ ıa-Patr´ on, J

    R. Garc ´ ıa-Patr´ on, J. J. Renema, and V. Shchesnovich, Simulating boson sampling in lossy architectures, Quantum3, 169 (2019)

    2019

  26. [26]

    H. Qi, D. J. Brod, N. Quesada, and R. Garc ´ ıa-Patr´ on, Regimes of classical simulability for noisy gaussian boson sampling, Physical review letters124, 100502 (2020)

    2020

  27. [27]

    C. Oh, K. Noh, B. Fefferman, and L. Jiang, Classical simulation of lossy boson sampling using matrix product operators, Physical Review A104, 022407 (2021)

    2021

  28. [28]

    Quesada, R

    N. Quesada, R. S. Chadwick, B. A. Bell, J. M. Arrazola, T. Vincent, H. Qi, R. Garc ´ ıa,et al., Quadratic speed-up for simulating Gaussian boson sampling, PRX Quantum 3, 010306 (2022)

    2022

  29. [29]

    J. F. Bulmer, B. A. Bell, R. S. Chadwick, A. E. Jones, D. Moise, A. Rigazzi, J. Thorbecke, U.-U. Haus, T. Van Vaerenbergh, R. B. Patel,et al., The boundary for quantum advantage in gaussian boson sampling, Science advances8, eabl9236 (2022)

    2022

  30. [30]

    C. Oh, Y. Lim, B. Fefferman, and L. Jiang, Classical simulation of boson sampling based on graph structure, Physical Review Letters128, 190501 (2022)

    2022

  31. [31]

    C. Oh, L. Jiang, and B. Fefferman, On classical simulation algorithms for noisy boson sampling, arXiv preprint arXiv:2301.11532 (2023)

    Pith/arXiv arXiv 2023

  32. [32]

    M. Liu, C. Oh, J. Liu, L. Jiang, and Y. Alexeev, Simulating lossy gaussian boson sampling with matrix- product operators, Physical Review A108, 052604 (2023)

    2023

  33. [33]

    C. Oh, M. Liu, Y. Alexeev, B. Fefferman, and L. Jiang, Classical algorithm for simulating experimental gaussian boson sampling, Nature Physics20, 1461 (2024)

    2024

  34. [34]

    Oh, Recent theoretical and experimental progress on boson sampling, Current Optics and Photonics9, 1 (2025)

    C. Oh, Recent theoretical and experimental progress on boson sampling, Current Optics and Photonics9, 1 (2025)

    2025

  35. [35]

    Oh, Classical simulability of constant-depth linear- optical circuits with noise, npj Quantum Information11, 126 (2025)

    C. Oh, Classical simulability of constant-depth linear- optical circuits with noise, npj Quantum Information11, 126 (2025)

    2025

  36. [36]

    Aharonov, M

    D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan, Limitations of noisy reversible computation, arXiv preprint quant-ph/9611028 (1996)

    Pith/arXiv arXiv 1996

  37. [37]

    Rahimi-Keshari, T

    S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves, Sufficient conditions for efficient classical simulation of quantum optics, Physical Review X6, 021039 (2016)

    2016

  38. [38]

    Huang, W.-S

    H.-L. Huang, W.-S. Bao, and C. Guo, Simulating the dynamics of single photons in boson sampling devices with matrix product states, Physical Review A100, 032305 (2019)

    2019

  39. [39]

    Clifford and R

    P. Clifford and R. Clifford, Faster classical boson sampling, arXiv preprint arXiv:2005.04214 (2020). 18

    Pith/arXiv arXiv 2005

  40. [40]

    Vidal, Efficient classical simulation of slightly entangled quantum computations, Phys

    G. Vidal, Efficient classical simulation of slightly entangled quantum computations, Phys. Rev. Lett.91, 147902 (2003)

    2003

  41. [41]

    Schuch, M

    N. Schuch, M. M. Wolf, F. Verstraete, and J. I. Cirac, Entropy scaling and simulability by matrix product states, Physical review letters100, 030504 (2008)

    2008

  42. [42]

    Nelson, J

    J. Nelson, J. Rajakumar, D. Hangleiter, and M. J. Gullans, Polynomial-time classical simulation of noisy circuits with naturally fault-tolerant gates, arXiv preprint arXiv:2411.02535 (2024)

    arXiv 2024

  43. [43]

    N. J. Russell, L. Chakhmakhchyan, J. L. O’Brien, and A. Laing, Direct dialling of haar random unitary matrices, New journal of physics19, 033007 (2017)

    2017

  44. [44]

    H. Wang, W. Li, X. Jiang, Y.-M. He, Y.-H. Li, X. Ding, M.-C. Chen, J. Qin, C.-Z. Peng, C. Schneider, et al., Toward scalable boson sampling with photon loss, Physical review letters120, 230502 (2018)

    2018

  45. [45]

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, Achieving quantum supremacy with sparse and noisy commuting quantum computations, Quantum1, 8 (2017)

    2017

  46. [46]

    Rajakumar, J

    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 Discrete Algorithms (SODA) (SIAM, 2025) pp. 1037–1056

    2025

  47. [47]

    K. Noh, L. Jiang, and B. Fefferman, Efficient classical simulation of noisy random quantum circuits in one dimension, Quantum4, 318 (2020)

    2020

  48. [48]

    D. N. Page, Average entropy of a subsystem, Physical review letters71, 1291 (1993)

    1993

  49. [49]

    Fujita, Y

    H. Fujita, Y. O. Nakagawa, S. Sugiura, and M. Watanabe, Page curves for general interacting systems, Journal of High Energy Physics2018, 1 (2018)

    2018

  50. [50]

    Mart ´ ınez-Cifuentes, K

    J. Mart ´ ınez-Cifuentes, K. M. Fonseca-Romero, and N. Quesada, Classical models may be a better explanation of the jiuzhang 1.0 gaussian boson sampler than its targeted squeezed light model, Quantum7, 1076 (2023)

    2023

  51. [51]

    P. P. Rohde, K. R. Motes, P. Knott, J. Fitzsimons, W. Munro, and J. P. Dowling, Sampling generalized cat states with linear optics is probably hard, arXiv preprint arXiv:1310.0297 (2013)

    Pith/arXiv arXiv 2013

  52. [52]

    Watrous,The theory of quantum information (Cambridge university press, 2018)

    J. Watrous,The theory of quantum information (Cambridge university press, 2018)

    2018

  53. [53]

    A. W. Marshall, I. Olkin, and B. C. Arnold,Inequalities: theory of majorization and its applications(Springer, 1979)

    1979

  54. [54]

    I. L. Markov and Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM Journal on Computing38, 963 (2008)

    2008

  55. [55]

    lX m=1 UjmU ∗ km ≤ϵ # ≤1− 1 ϵ2 l(M−l) M 2(M+ 1) .(B4) We similarly investigate the denominator E

    D. Maslov, S. Bravyi, F. Tripier, A. Maksymov, and J. Latone, Fast classical simulation of harvard/quera iqp circuits, arXiv preprint arXiv:2402.03211 (2024). Appendix A: Analysis of the required bond dimension for classical simulation of boson sampling This section describes the algorithm for estimating the required bond dimension in the classical simula...

    Pith/arXiv arXiv 2024