Source-linked AI summary
A polynomial-time classical algorithm for noisy random circuit sampling
Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh Vazirani
TL;DR
The paper asks whether noisy random circuit sampling remains classically hard when each gate incurs a constant noise rate. It develops a Pauli-basis path-enumeration algorithm and shows that, under anti-concentration, noisy RCS can be sampled with polynomial resources, while practical finite-size experiments and some circuit regimes remain outside scope.
Problem
The paper studies whether random circuit sampling with a constant rate of noise per gate can support an experimental violation of the extended Church-Turing thesis.
Method
The algorithm reformulates Fourier analysis as a Pauli-basis Feynman path integral and enumerates the non-trivial low-Hamming-weight paths.
Results
Assuming anti-concentration, a classical algorithm samples an ε-close noisy RCS distribution in time poly(n, 1/ε, 1/δ), making M samples indistinguishable from experiment outputs in polynomial time.
Takeaways & Limitations
Under the stated assumptions, noisy RCS cannot provide a scalable experimental separation from classical computation based on statistical tests of polynomially many samples.
Takeaways & Limitations
The result is complexity-theoretic, does not directly address finite-size experiments, and assumes anti-concentration, including depth at least Ω(log n).
Abstract
from arXiv · showhide
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments.
1 Introduction
The paper studies noisy random circuit sampling under constant per-gate depolarizing noise and presents a polynomial-time classical sampler under anti-concentration. Its complexity-theoretic conclusion is limited by practicality, finite-size experiments, sublogarithmic depth, and gate-set assumptions.
- Problem setting: Random circuit sampling uses random two-qubit gates over n qubits, depth d, and m = Θ(nd) gates, with anti-concentration central to experiments and the algorithm.The paper focuses on circuits whose depth is at least Ω(log n) for anti-concentration.
- Problem and result: Constant per-gate depolarizing noise makes the noisy output distribution approximately classically samplable within small total variation distance.The noise model applies an arbitrarily small constant amount of depolarizing noise to each qubit at each time step.
- Main result: Assuming anti-concentration, the main algorithm runs in time poly(n, 1/ε, 1/δ) and produces an ε-close sample with success probability at least 1 − δ.The guarantee applies to random circuits on any fixed architecture.
- Implication: For an experiment collecting M samples, choosing ε = μ/M yields classical samples indistinguishable from experimental samples by any statistical test beyond probability 1/2 + μ.The resulting runtime is polynomial in n, M, and 1/μ.
- Method: The algorithm reformulates Fourier analysis as a Pauli-basis Feynman path integral and enumerates only non-trivial low-Hamming-weight paths.This sparsity enables polynomial-time enumeration of the paths contributing to the simulation.
- Scope and limitations: The conclusions do not directly address finite-size experiments, and the current algorithm is impractical because its runtime has a large exponent or constant tied to noise.The analysis also assumes at least Ω(log n) depth and randomness in the gate set, leaving sublogarithmic-depth and less-random experimental gates unresolved.
2 The Pauli basis framework
The Pauli basis framework rewrites circuit evolution as a path integral over Pauli operators, including depolarizing noise, and exploits gate-set orthogonality and anti-concentration to analyze random circuits.
- Random-circuit properties: Anti-concentration requires at least Ω(log n) depth for Haar-random two-qubit circuits, with established results for 1D and stochastic all-to-all architectures.For stochastic all-to-all connectivity, Θ(n log n) two-qubit gates are necessary and sufficient.
- Pauli basis representation: The framework represents density matrices in the normalized Pauli-operator basis and treats circuit layers as unitary channels.This parallels computational-basis path integrals while using operator-ket notation for Pauli states.
- Pauli path integral: The Pauli path integral expresses output probabilities as sums over sequences of Pauli operators across circuit layers.Each sequence is a Pauli path indexed by the circuit depth.
- Noisy circuits: Depolarizing noise preserves the identity Pauli and multiplies each non-identity Pauli by 1 − γ at every noisy layer.This gives each path a noise-dependent attenuation determined by its Hamming weight.
- Random-circuit properties: Gate-set orthogonality makes distinct Fourier coefficients orthogonal on average for circuit ensembles invariant under right-multiplication by random Pauli operators.Haar-random two-qubit gates satisfy this property, and the main result also assumes anti-concentration.
3 Simulating noisy random circuit sampling
The section develops a classical simulation by truncating a Fourier expansion of noisy RCS and efficiently computing the surviving legal Pauli paths. Anti-concentration controls both approximation error and path enumeration, yielding polynomial-time sampling for inverse-polynomial total variation accuracy.
- 3 Simulating noisy random circuit sampling: The algorithm approximates the noisy output distribution by summing its low-degree Fourier coefficients, producing a quasi-probability that need not be positive.A sampling-to-computing reduction then converts estimates of this quasi-probability and its marginals into samples close to the noisy distribution.
- 3.1 Bounds for the total variation distance: Choosing ℓ = O(log 1/ε) suffices to achieve ε total variation distance.The bound follows from exponential decay of the Fourier weights, with ℓ roughly proportional to γ^-1 log 1/ε.
- 3.2 Counting and enumerating legal Pauli paths: Illegal Pauli paths contribute zero, so the computation can restrict enumeration to legal paths satisfying the two defining boundary and gate-transition conditions.This restriction is the central combinatorial simplification used to make low-weight path enumeration efficient.
- 3.2 Counting and enumerating legal Pauli paths: The number of legal paths with Hamming weight at most ℓ is at most n^ℓ/d · 2^O(ℓ), and they can be enumerated in that time using ˜O(nd) memory.In the anti-concentration regime, this matches the 2^O(ℓ) asymptotic bound up to constants in the exponent.
- 3.3 Putting everything together: The resulting procedure computes the truncated quasi-probability efficiently and samples from a distribution O(Δ)-close to the noisy output distribution.Obtaining one sample requires O(n) calls, and for polynomial circuit depth the total runtime is polynomial in n after choosing the truncation parameter.
- 3.4 Statistical indistinguishability: For statistical indistinguishability of M samples, choosing ε = 0.01/M and δ = 0.01 gives running time polynomial in n and M.The guarantee uses subadditivity of total variation distance under tensor products.
4 Generalizing to an approximation of Google and USTC’s gate sets
The paper extends its gate-set analysis toward gate sets related to Google and USTC experiments by identifying gate-set orthogonality as the relevant proof property. A modified fSim-based set with inserted random Z rotations satisfies this condition, while the exact experimental sets do not.
- Gate-set conditions: Assuming anti-concentration and depth at least Ω(log n), gate-set dependence enters the proof through gate-set orthogonality of Pauli paths.This property implies the orthogonality condition required by the main result.
- Scope: The main result holds for the related gate set shown in Figure 2, but whether it holds for the exact Google and USTC gate sets remains open.The paper explicitly leaves necessity of orthogonality and applicability to the exact experimental sets as open questions.
- Experimental gate sets: The Google and USTC gate sets violate the required condition because they use fixed two-qubit fSim gates with randomly chosen single-qubit gates.The paper therefore analyzes a related rather than exact experimental gate set.
- Modified fSim construction: Inserting random Z rotations around the fixed fSim gate enables an equivalent gate-set representation by borrowing randomness through a special fSim commutation property.The resulting single-qubit set is invariant under random Pauli and satisfies gate-set orthogonality.
A Refuting XQUATH for sublinear depth random circuits
Using the Pauli path integral, the paper gives efficient classical procedures that refute XQUATH for random circuits below linear depth and achieve comparable XEB behavior with a single path.
- A Refuting XQUATH for sublinear depth random circuits: The Pauli path integral is highly non-uniform, so low-Hamming-weight paths can dominate contributions that are hard to capture in the computational basis.The paper contrasts exponentially many uniform computational-basis paths with Pauli paths whose contributions decay with Hamming weight.
- A Refuting XQUATH for sublinear depth random circuits: A single Pauli path suffices to refute XQUATH below linear depth.The result uses the Pauli path integral to construct the refutation.
- A Refuting XQUATH for sublinear depth random circuits: Therefore XQUATH is false for random circuits with depth d = o(n).
- A Refuting XQUATH for sublinear depth random circuits: The algorithm computes a correction to the trivial estimate 1/2^n using a selected Pauli-path contribution.The construction evaluates the path contribution f(C, s*, 0^n) in time O(nd).
- A Refuting XQUATH for sublinear depth random circuits: One Pauli path already suffices to achieve 2^-O(d) XEB for noisy random circuits.The paper treats this as a demonstration because its main sampling result already rules out statistical-test distinctions within the stated scope.
- A Refuting XQUATH for sublinear depth random circuits: An efficient classical algorithm samples in time O(nd), with the first qubit sampled non-trivially and the remaining qubits uniformly.
B Improved bounds on the convergence of noisy random circuits to the uniform distribution
The paper improves bounds on how noisy random-circuit output distributions approach uniformity by applying Fourier-weight and Pauli-path techniques to depolarizing noise.
- B Improved bounds on the convergence of noisy random circuits to the uniform distribution: The paper improves an earlier average total-variation bound using Fourier weight and the Pauli path integral technique.The comparison is made against the bound summarized from prior work.
- B Improved bounds on the convergence of noisy random circuits to the uniform distribution: The analysis targets total variation distance for Haar-random two-qubit gates with depolarizing noise on parallel circuit architectures.
- B Improved bounds on the convergence of noisy random circuits to the uniform distribution: The proof lower-bounds total variation distance by considering nonzero Pauli paths of weight d + 1.The argument uses their Fourier weights and contributions to the marginal output probability.
- B Improved bounds on the convergence of noisy random circuits to the uniform distribution: The path count at the relevant stage is 2^d · 3^(d−1), after fixing the final endpoint.
- B Improved bounds on the convergence of noisy random circuits to the uniform distribution: The resulting contribution is bounded by 1/12 · (1 − γ)^(2d) · 2^d.
- B Improved bounds on the convergence of noisy random circuits to the uniform distribution: The upper-bound analysis uses anti-concentration, while the corresponding lower bound does not require it.