Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity

• URL: http://arxiv.org/abs/2510.06324v1
• Date: Tue, 07 Oct 2025 18:00:03 GMT
• Title: Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
• Authors: Yifan F. Zhang, Su-un Lee, Liang Jiang, Sarang Gopalakrishnan,
• Abstract summary: We present a classical algorithm that runs in $nrmpolylog(n)$ time for simulating quantum circuits under local depolarizing noise.<n>Our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markovianity and classical simulability.
• Score: 0.616870773176256
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While quantum computing can accomplish tasks that are classically intractable, the presence of noise may destroy this advantage in the absence of fault tolerance. In this work, we present a classical algorithm that runs in $n^{\rm{polylog}(n)}$ time for simulating quantum circuits under local depolarizing noise, thereby ruling out their quantum advantage in these settings. Our algorithm leverages a property called approximate Markovianity to sequentially sample from the measurement outcome distribution of noisy circuits. We establish approximate Markovianity in a broad range of circuits: (1) we prove that it holds for any circuit when the noise rate exceeds a constant threshold, and (2) we provide strong analytical and numerical evidence that it holds for random quantum circuits subject to any constant noise rate. These regimes include previously known classically simulable cases as well as new ones, such as shallow random circuits without anticoncentration, where prior algorithms fail. Taken together, our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markovianity and classical simulability, thereby highlighting the limitation of noisy quantum circuits in demonstrating quantum advantage.

Related papers

• Classical simulation of a quantum circuit with noisy magic inputs [0.6287298138084187]
  We characterize how noise on magic resources changes the classical simulability of quantum circuits.<n>We adopt a resource-centric noise model in which only the injected magic components are noisy, while the baseline states, operations, and measurements belong to an efficiently simulable family.
  arXiv  Detail & Related papers  (2026-01-15T06:40:28Z)
• Matrix product state approach to lossy boson sampling and noisy IQP sampling [0.7066293026438526]
  We develop classical algorithms for lossy boson sampling and noisy instantaneous quantum-time sampling.<n>Our algorithm offers significantly improved control over the accuracy-efficiency trade-off.<n>It further extends the applicability of MPS simulation to broader classes of noisy quantum sampling models.
  arXiv  Detail & Related papers  (2025-10-28T07:23:10Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits [1.0874100424278175]
  We introduce the $textitdisplacement propagation$ algorithm for simulating noisy bosonic circuits.<n>We identify several computational phase transitions, revealing regimes where even modest noise levels render bosonic circuits efficiently classically simulable.<n>In particular, our analysis reveals a surprising phenomenon: computational resources usually associated with bosonic quantum advantage, namely non-Gaussianity and symplectic coherence, can make the system easier to classically simulate in presence of noise.
  arXiv  Detail & Related papers  (2025-10-08T17:25:47Z)
• Limitations of Noisy Geometrically Local Quantum Circuits [0.2039123720459736]
  We show that noisy quantum circuits with interspersed noise converge to the uniform distribution at $omega(log n)$ depth, where $n$ is the number of qubits.<n>We conjecture that our bound is still loose and that a $Theta(1)$-depth threshold suffices for simulability due to a percolation effect.
  arXiv  Detail & Related papers  (2025-10-07T18:08:23Z)
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings [0.2796197251957244]
  We present a highly parallelizable tensor-network-based classical algorithm for simulating noisy quantum circuits.<n>Our algorithm represents the state of a noisy quantum system by a particular ensemble of matrix product states.
  arXiv  Detail & Related papers  (2025-08-07T18:00:20Z)
• Non-perturbative switching rates in bistable open quantum systems: from driven Kerr oscillators to dissipative cat qubits [72.41778531863143]
  We use path integral techniques to predict the switching rate in a single-mode bistable open quantum system.<n>Our results open new avenues for exploring switching phenomena in multistable single- and many-body open quantum systems.
  arXiv  Detail & Related papers  (2025-07-24T18:01:36Z)
• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• Bayesian Quantum Amplitude Estimation [46.03321798937855]
  We present BAE, a problem-tailored and noise-aware Bayesian algorithm for quantum amplitude estimation.<n>In a fault tolerant scenario, BAE is capable of saturating the Heisenberg limit; if device noise is present, BAE can dynamically characterize it and self-adapt.<n>We propose a benchmark for amplitude estimation algorithms and use it to test BAE against other approaches.
  arXiv  Detail & Related papers  (2024-12-05T18:09:41Z)
• A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
  We provide a-time classical algorithm for noisy quantum circuits. Our approach is based upon the intuition that noise exponentially damps non-local correlations. For constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.
  arXiv  Detail & Related papers  (2024-07-17T17:48:39Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  We consider biased-noise qubits affected only by bit-flip errors, which is motivated by existing systems of stabilized cat qubits. For realistic noise models, phase-flip will not be negligible, but in the Pauli-Twirling approximation, we show that our benchmark could check the correctness of circuits containing up to $106$ gates.
  arXiv  Detail & Related papers  (2023-05-03T11:27:50Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Quantum noise protects quantum classifiers against adversaries [120.08771960032033]
  Noise in quantum information processing is often viewed as a disruptive and difficult-to-avoid feature, especially in near-term quantum technologies. We show that by taking advantage of depolarisation noise in quantum circuits for classification, a robustness bound against adversaries can be derived. This is the first quantum protocol that can be used against the most general adversaries.
  arXiv  Detail & Related papers  (2020-03-20T17:56:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.