PaperlayerView exact revision on arXiv

Source-linked AI summary

A polynomial-time classical algorithm for noisy random circuit sampling

Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh Vazirani

arXiv:2211.03999v1quant-ph

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.

    Source: §1 · pp. 1–2

  • Method

    The algorithm reformulates Fourier analysis as a Pauli-basis Feynman path integral and enumerates the non-trivial low-Hamming-weight paths.

    Source: §1 · p. 3, §2 · p. 9

  • 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.

    Source: §1 · p. 2

  • 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.

    Source: §1 · p. 2

    The result is complexity-theoretic, does not directly address finite-size experiments, and assumes anti-concentration, including depth at least Ω(log n).

    Source: §1 · p. 3, §1.3 · p. 6

Abstract

from arXiv · show

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.Source: §1 · pp. 1, 3

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.Source: §1 · p. 2, Figure 1 · p. 2

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.Source: §1 · p. 2

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/μ.Source: §1 · p. 2

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.Source: §1 · p. 3

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.Source: §1 · p. 3, §1.3 · pp. 5–6

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.Source: §2 · pp. 6, 10

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.Source: §2 · pp. 6–7, Table 1 · p. 7

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.Source: §2 · p. 7

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.Source: §2 · pp. 7–8

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.Source: §2 · pp. 9–10

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.Source: §3 · p. 12

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/ε.Source: §3 · p. 12, §3.1 · p. 13

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.Source: §3.2 · pp. 13–14
  • 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.Source: §3.2 · pp. 14, 16

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.Source: §3.3 · pp. 17–18

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.Source: §3.4 · p. 19

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.Source: §4 · pp. 19–20

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.Source: Figure 2 · p. 20, §4 · p. 20

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.Source: §4 · p. 20

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.Source: §4 · p. 20

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

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

Related papers

Loading 2211.03999v1…