Limitations of Noisy Geometrically Local Quantum Circuits

• URL: http://arxiv.org/abs/2510.06346v1
• Date: Tue, 07 Oct 2025 18:08:23 GMT
• Title: Limitations of Noisy Geometrically Local Quantum Circuits
• Authors: Jon Nelson, Joel Rajakumar, Michael J. Gullans,
• Abstract summary: 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.
• Score: 0.2039123720459736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It has been known for almost 30 years that quantum circuits with interspersed depolarizing noise converge to the uniform distribution at $\omega(\log n)$ depth, where $n$ is the number of qubits, making them classically simulable. We show that under the realistic constraint of geometric locality, this bound is loose: these circuits become classically simulable at even shallower depths. Unlike prior work in this regime, we consider sampling from worst-case circuits and noise of any constant strength. First, we prove that the output distribution of any noisy geometrically local quantum circuit can be approximately sampled from in quasipolynomial time, when its depth exceeds a fixed $\Theta(\log n)$ critical threshold which depends on the noise strength. This scaling in $n$ was previously only obtained for noisy random quantum circuits (Aharonov et. al, STOC 2023). We further conjecture that our bound is still loose and that a $\Theta(1)$-depth threshold suffices for simulability due to a percolation effect. To support this, we provide analytical evidence together with a candidate efficient algorithm. Our results rely on new information-theoretic properties of the output states of noisy shallow quantum circuits, which may be of broad interest. On a fundamental level, we demonstrate that unitary quantum processes in constant dimensions are more fragile to noise than previously understood.

Related papers

• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity [0.616870773176256]
  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.
  arXiv  Detail & Related papers  (2025-10-07T18:00:03Z)
• Classically estimating observables of noiseless quantum circuits [36.688706661620905]
  We present a classical algorithm for estimating expectation values of arbitrary observables on random unstructured quantum circuits.<n>Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries.
  arXiv  Detail & Related papers  (2024-09-03T08:44:33Z)
• A quantum implementation of high-order power method for estimating geometric entanglement of pure states [39.58317527488534]
  This work presents a quantum adaptation of the iterative higher-order power method for estimating the geometric measure of entanglement of multi-qubit pure states.<n>It is executable on current (hybrid) quantum hardware and does not depend on quantum memory.<n>We study the effect of noise on the algorithm using a simple theoretical model based on the standard depolarising channel.
  arXiv  Detail & Related papers  (2024-05-29T14:40:24Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
  Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve quantum advantages. We present a novel $gammaPPP method based on the integral path of observables back-propagation on paths. We conduct classical simulations of IBM's zeronoised experimental results on the 127-qubit Eagle processor.
  arXiv  Detail & Related papers  (2023-06-09T10:42:07Z)
• 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)
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation [5.746732081406236]
  We develop a phase estimation method with a distinct feature. The total cost of the algorithm satisfies the Heisenberg-limited scaling $widetildemathcalO(epsilon-1)$. Our algorithm may significantly reduce the circuit depth for performing phase estimation tasks on early fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2022-11-22T03:15:40Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Unimon qubit [42.83899285555746]
  Superconducting qubits are one of the most promising candidates to implement quantum computers. Here, we introduce and demonstrate a superconducting-qubit type, the unimon, which combines the desired properties of high non-linearity, full insensitivity to dc charge noise, insensitivity to flux noise, and a simple structure consisting only of a single Josephson junction in a resonator.
  arXiv  Detail & Related papers  (2022-03-11T12:57:43Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
  We show a strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. A key component of this reduction is showing average-case hardness for the classical simulation tasks. We show that is true even for quantum tasks which are $oplus$L-hard to simulate.
  arXiv  Detail & Related papers  (2021-02-13T00:54:45Z)
• Fault-tolerant quantum speedup from constant depth quantum circuits [0.0]
  We show that there is no classical algorithm which can sample according to its output distribution in $poly(n)$ time. We present two constructions, each taking $poly(n)$ physical qubits, some of which are prepared in noisy magic states.
  arXiv  Detail & Related papers  (2020-05-23T13:53:27Z)
• 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)

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.