PaperlayerView exact revision on arXiv

Source-linked AI summary

Achieving quantum supremacy with sparse and noisy commuting quantum computations

Michael J. Bremner, Ashley Montanaro, Dan J. Shepherd

arXiv:1610.01808v4quant-ph

TL;DR

The paper asks whether IQP circuits can demonstrate classical intractability under sparse architectures and physical noise. It constructs sparse lattice-implementable circuits, proves that noise can make anticoncentrated circuits easy to simulate, and shows that classical error correction can preserve conditional hardness. These results frame both the vulnerability and possible mitigation of noise in quantum-supremacy experiments.

  • Problem

    Existing IQP hardness results concern ideal computations or rely on demanding assumptions, leaving sparse implementations and realistically noisy, non-fault-tolerant experiments unresolved.

  • Method

    The paper combines sparse-circuit constructions, Fourier-based noisy simulation, and classical repetition-code error correction within the IQP model.

  • Results

    Sparse IQP circuits can be implemented on a square lattice in depth O(√n log n), while any constant depolarising noise enables polynomial-time simulation for sufficiently anticoncentrated circuits; error-corrected IQP circuits remain conditionally hard for every ϵ < 1.

  • Takeaways & Limitations

    Noise can undermine the classical hardness of apparently hard IQP circuits, but simple classical error correction can preserve hardness without full quantum fault tolerance.

  • Takeaways & Limitations

    The sparse-circuit hardness argument relies on an unproven conjecture about complex-temperature partition functions on random sparse graphs, and the noisy-simulation theorem depends on anticoncentration.

Abstract

from arXiv · show

The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.

1 Introduction

The paper examines whether IQP circuits can remain classically hard under physical constraints, focusing on sparse architectures and local depolarising noise. It shows that noise can make anticoncentrated circuits efficiently simulable, while classical error correction can restore hardness.

  • Motivation and limitations: Theoretical hardness results for ideal IQP sampling do not by themselves establish hardness for realistically noisy, non-fault-tolerant experiments.Prior results also assume long-range interactions, which impose substantial physical overhead in many architectures.
  • Sparse IQP circuits: O(n log n) two-qubit gates and depth O(√n log n) suffice for a family of sparse IQP circuits likely hard to simulate classically.The circuits use a √n × √n square-lattice architecture, assuming a sparse version of the relevant complexity conjecture.
  • Noisy simulation: Any constant depolarising noise makes most sufficiently anticoncentrated IQP circuits polynomial-time classically simulable up to fixed ℓ1 accuracy.Theorem 4 gives runtime n^O(log(α/δ)/ϵ) + T poly(n), and random circuit families have expected α = O(1).
  • Noisy simulation: The noise-simulation result applies precisely to circuits previously shown hard under the stated assumptions, because those circuits have α = O(1).The parameter α measures how spread out the output distribution is.
  • Fault tolerance: Classical error correction produces an IQP circuit on O(n) qubits whose noisy output remains arbitrarily close to the original distribution for every noise rate ϵ < 1.The construction uses repetition coding and majority decoding, and supports broader local noise models concentrated on errors of small Hamming weight.
  • Fault tolerance: Under either stated conjecture, efficiently sampling noisy IQP circuits to fixed ℓ1 accuracy would collapse the polynomial hierarchy to its third level.Thus the error-corrected circuits retain conditional classical hardness despite output depolarising noise.

2 Sparse IQP circuits

The paper constructs sparse IQP circuits that remain conditionally hard to simulate, parallelizes them efficiently, and places them on a square lattice with depth O(√n log n).

  • Sparse circuit construction: The sparse circuit ensemble uses random two-qubit gates with inclusion probability p = γ(ln n)/n and random one-qubit diagonal gates.Two-qubit gates are selected from diag(1, 1, 1, ω^k), while one-qubit gates are selected from diag(1, ζ^k).
  • Hardness evidence: The ensemble satisfies an anticoncentration bound: E_C[|⟨0|C|0⟩|^2] = 2^-n and E_C[|⟨0|C|0⟩|^4] ≤ 5 · 2^-2n.The resulting Paley-Zygmund bound gives a constant probability that |⟨0|C|0⟩|^2 is at least α · 2^-n.
  • Parallelization: O(log n) depth suffices to parallelize a random sparse IQP circuit with O(n log n) gates when long-range interactions are allowed.Vizing’s theorem converts a bound on the interaction graph’s maximum degree into a proper edge coloring.
  • Sparse circuit construction: Sparse IQP circuits contain O(n log n) gates with high probability and are conjectured to remain hard to simulate classically.The hardness claim assumes Conjecture 8 and that the polynomial hierarchy does not collapse to the third level.
  • Square-lattice implementation: O(√n log n) depth implements these circuits on a 2d √n × √n square lattice.A sorting network contributes the O(√n) routing factor.

3 Approximating the output probability distribution of noisy IQP circuits

The paper uses Fourier analysis to truncate and approximate the noisy IQP distribution, compute its marginals, and sample efficiently from a nearby distribution under anticoncentration assumptions.

  • Simulation strategy: The algorithm approximates the noisy distribution with a function having only poly(n) nonzero Fourier coefficients, computes its marginals, and samples from a distribution within O(δ) ℓ1 error.This three-step plan underlies the classical simulation result.
  • Noise and Fourier coefficients: Noise acts as the Boolean-cube noise operator, multiplying each Fourier coefficient by (1 − ϵ)^|s|.Here |s| is the Hamming weight of s.
  • Fourier truncation: For sufficiently spread-out output distributions satisfying p_x ≤ α2^-n, retaining coefficients with |s| ≤ ℓ achieves ℓ1 error δ using ℓ = O(log(α/δ)/ϵ).The required coefficient accuracy is O(δ n^-O(log(α/δ)/ϵ) 2^-n).
  • Coefficient estimation: IQP Fourier coefficients can be approximated by sampling evaluations of f(x)f(x+s), where ⟨x|D|x⟩ = f(x).Each evaluation is polynomial-time, and all required coefficients are obtained with failure probability o(1).
  • Sampling from marginals: The marginal-based sampler satisfies ∥Alg(p′) − p∥1 ≤ 4δ/(1 − δ) whenever ∥p′ − p∥1 ≤ δ < 1.This remains valid even when p′ is not itself a probability distribution.
  • Overall complexity: The complete algorithm runs in time n^O(log(α/δ)/ϵ), while each generated sample takes polynomial time.It first stores enough approximate Fourier coefficients and then samples using the computed marginals.

4 Extensions

The extension discusses when classical simulation methods generalize beyond IQP and clarifies the limitations of anticoncentration-based simulation and related sparse-output approaches.

  • Other algorithms: The proposed classical simulation approach applies beyond IQP to circuit classes with sufficiently anticoncentrated output distributions and efficiently computable Fourier coefficients.Its IQP specificity is therefore limited.
  • Other algorithms: Simon’s algorithm illustrates that Fourier coefficients can sometimes be evaluated efficiently by determining whether s = t.This example uses the hidden string structure of Simon’s problem.
  • Other algorithms: Exact computation of arbitrary output probabilities does not generally suffice to approximate Fourier coefficients efficiently, even for relatively anticoncentrated distributions.The paper instead requires exact state Fourier coefficients, or sufficiently accurate values of ⟨s|H^⊗n|ψ⟩.
  • Reducing the anticoncentration requirement: The simulation method’s polynomial-time guarantee depends on the output distribution being sufficiently spread out, creating an anticoncentration boundary.Random IQP circuits have α = O(1) with high probability, but the method is not universal across output distributions.
  • Reducing the anticoncentration requirement: IQP circuits close to t-sparse distributions can also be classically simulated, but this condition is not precisely converse to the paper’s spread-outness condition.A circuit with paired CZ gates can be 2^k-sparse while remaining outside the relevant L-sparse regime.
  • Reducing the anticoncentration requirement: For k = n/2 in the paired-CZ example, neither the present method nor the method of Schwarz and Van den Nest gives an efficient algorithm.The example has ∑_x p_x^2 = 2^-k.

5 Fault-tolerance

The paper uses classical error-correcting codes to protect IQP sampling against depolarising noise, transforming encoded noisy outputs back toward the original distribution.

  • Noise resilience: The encoded circuit C′ preserves sampling close to the original distribution p after output depolarising noise, up to arbitrarily small ℓ1 distance.The construction applies noise to every output qubit of C′ and decodes the result classically.
  • Encoding IQP outputs: Linear transformations over F2 map IQP output distributions into encoded distributions suitable for classical error-correcting codes.Replacing an X-program matrix C with CM implements the corresponding output transformation efficiently.
  • Repetition coding: A repetition code copies each bit into r bits and decodes by majority vote.For odd r, the generator matrix consists of r identity copies.
  • Repetition coding: For any ϵ < 1, repetition coding makes individual-bit decoding errors exponentially small in r.Taking r = O(log n) allows all n bits to decode successfully except with low probability.
  • Implementation considerations: The error-corrected IQP circuits may require gates acting on up to n qubits, although some cases permit replacement by O(1)-qubit gates.The cited example restricts angles to multiples of π/8.

A Anticoncentration bound

The appendix bounds the fourth moment of a random sparse IQP circuit’s output amplitude, establishing the moment estimates used for anticoncentration analysis.

  • Second moment: E_C[|⟨0|C|0⟩|^2] = 2^-n for random sparse IQP circuits.This follows from symmetry arguments.
  • Fourth moment: E_C[|⟨0|C|0⟩|^4] ≤ 5 · 2^-2n for a sufficiently large constant γ.The proof partitions terms according to the sizes of combinatorial parameters b, c, and d.
  • Combinatorial organization: The combinatorial case analysis uses bit-pattern counts a, b, c, and d to organize pairs of strings contributing to the moment calculation.These counts classify coordinatewise combinations of x and y.
  • Fourth-moment proof: The fourth-moment bound is obtained by separately controlling terms where max{b, c, d} is small and terms where one parameter exceeds αn.The argument then sums over the three possible choices of the large parameter.

B Sampling from an approximate distribution

The appendix analyzes a recursive correction procedure for approximate distributions and proves that its output remains close to the target distribution when the input error is small.

  • Procedure analyzed: The procedure Alg produces the normalized vector Fix(p′)/S from an approximate distribution p′.Here S is the sum of the entries of Fix(p′).
  • Properties of Fix: Fix preserves nonnegative entries and sets entries corresponding to negative components of p to zero.The appendix also gives an ℓ1 characterization of the change introduced by Fix.
  • Proof strategy: The proof establishes the properties of Fix by induction on the vector dimension while ensuring the recursion is applied only to vectors with positive entry sum.The base case is n = 0, and the induction examines the recursive cases.
  • Properties of Fix: For vectors with positive total sum, the modification obeys ∥Fix(p) − p∥1 = 2 Σ_{x:px<0}|px|.This identity relates the correction distance to the mass of negative entries.
  • Approximate sampling guarantee: Lemma 10 bounds the corrected distribution’s error by 4δ/(1 − δ) when the input distribution is within δ < 1 in ℓ1 distance.This is the principal guarantee for applying Alg to an approximate distribution.
Loading 1610.01808v4…