PaperlayerView exact revision on arXiv

Source-linked AI summary

Characterizing Quantum Supremacy in Near-Term Devices

Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, Hartmut Neven

arXiv:1608.00263v3quant-ph

TL;DR

The paper asks whether near-term, non-error-corrected quantum devices can sample random-circuit outputs beyond classical capabilities. It analyzes classical hardness and chaotic convergence, then proposes cross entropy as a fidelity-related benchmark and practical supremacy test.

  • Problem

    The central question is whether quantum devices without error correction can perform a well-defined sampling task beyond state-of-the-art classical computers.

  • Method

    The paper combines computational-complexity arguments, supercomputer simulations of random circuits, chaos-theory analysis, and cross-entropy measurements.

  • Results

    Classical simulation requires direct methods that fail for universal random circuits above approximately 48 qubits and depth ∼40, while cross entropy is closely related to circuit fidelity.

  • Takeaways & Limitations

    Cross entropy can benchmark complex multiqubit circuits and, beyond the simulation frontier, can be extrapolated and compared with theoretical fidelity estimates to define a quantum supremacy test.

  • Takeaways & Limitations

    Clifford-based verification may remain possible when the number of non-Clifford T gates is reduced, even where direct simulation is likely no longer possible.

Abstract

from arXiv · show

A critical question for the field of quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of state-of-the-art classical computers, achieving so-called quantum supremacy. We study the task of sampling from the output distributions of (pseudo-)random quantum circuits, a natural task for benchmarking quantum computers. Crucially, sampling this distribution classically requires a direct numerical simulation of the circuit, with computational cost exponential in the number of qubits. This requirement is typical of chaotic systems. We extend previous results in computational complexity to argue more formally that this sampling task must take exponential time in a classical computer. We study the convergence to the chaotic regime using extensive supercomputer simulations, modeling circuits with up to 42 qubits - the largest quantum circuits simulated to date for a computational task that approaches quantum supremacy. We argue that while chaotic states are extremely sensitive to errors, quantum supremacy can be achieved in the near-term with approximately fifty superconducting qubits. We introduce cross entropy as a useful benchmark of quantum circuits which approximates the circuit fidelity. We show that the cross entropy can be efficiently measured when circuit simulations are available. Beyond the classically tractable regime, the cross entropy can be extrapolated and compared with theoretical estimates of circuit fidelity to define a practical quantum supremacy test.

I. INTRODUCTION

The paper frames random-circuit sampling as a candidate quantum-supremacy task because chaotic quantum evolution appears to require exponentially costly classical simulation. It proposes cross entropy as an experimentally measurable benchmark and studies the circuit sizes and chaotic behavior relevant to near-term devices.

  • Numerical study: The study uses supercomputer simulations to examine convergence toward the chaotic regime and the tractability of random circuits.The introduction reports simulations and benchmarks approaching the regime relevant to quantum supremacy.
  • Quantum chaos: Chaotic quantum states become highly sensitive to small perturbations, with overlaps decreasing exponentially under perturbations and evolution time.Their amplitudes spread across Hilbert space, making high-fidelity classical descriptions difficult.
  • Circuit model: Random circuits use universal one- and two-qubit gates applied in parallel across a one- or two-dimensional lattice.The circuit is represented as a sequence of depth-d clock cycles.
  • Motivation: Random quantum circuits provide a benchmark task whose output sampling is argued to require direct classical simulation with resources exponential in qubit number.The argument connects this difficulty to the sensitivity and delocalization characteristic of chaotic systems.
  • Benchmark: Cross entropy is introduced as a benchmark that can be measured from experimental samples and related to circuit fidelity.Its sensitivity to the effective per-gate error rate supports comparison between experiment, simulation, and theory.

A. Ideal circuit vs. polynomial classical algorithm

The section explains why samples from sufficiently chaotic random circuits differ statistically from samples produced by polynomial-time classical algorithms. Porter–Thomas output statistics make circuit-specific probabilities necessary for distinguishing the quantum distribution from uniform sampling.

  • Ideal circuit: Random-circuit amplitudes become approximately Gaussian, yielding Porter–Thomas measurement probabilities in the chaotic regime.The distribution approaches Ne^-Np, while the probability vector approaches a symmetric Dirichlet distribution.
  • Ideal circuit: The time to approach Porter–Thomas behavior scales with entanglement spreading as n^(1/D), where D is the lattice dimension.The relevant dimensions are D = 1 for linear arrays, D = 2 for square lattices, and effectively infinite for fully connected architectures.
  • Sampling hardness: Each random-circuit output probability is typically O(1/N), so polynomial-size samples contain nearly unique bit-strings.Distinguishing the circuit distribution from uniform sampling therefore requires precomputing circuit-specific probabilities.
  • Classical comparison: The cross entropy H(ppcl, pU) compares a classical sampler’s distribution with the circuit output distribution and exceeds H(pU) when the sampler favors lower-probability outcomes.The analysis averages this quantity over an ensemble of random circuits.
  • Classical comparison: Under the assumption that polynomial-time classical outputs are nearly uncorrelated with pU(x), quantum samples are exponentially more likely under the circuit distribution than classical samples in typical cases.The comparison is expressed through the probability ratio between quantum and classical samples.

B. Cross entropy difference

The cross entropy difference provides a normalized measure of how well an algorithm reproduces a random circuit’s output distribution. It can be estimated from experimental samples while simulations remain available, then extrapolated near or beyond the classical simulation frontier.

  • Definition: The cross entropy difference is one for an ideal random circuit and zero for a uniform classical sampler.This normalization uses the Porter–Thomas entropy and the uniform-sampler cross entropy as reference points.
  • Supremacy test: The supremacy criterion compares an experimental cross entropy difference with the performance of the best executed classical algorithm.The classical benchmark supplies a lower bound on the classical computational cost parameter C.
  • Classical frontier: 48 qubits require at least 2.252 petabytes to store a full wavefunction in single precision, near the memory limit of contemporary large-scale supercomputers.Direct simulation is viable below approximately 48 qubits but becomes impractical beyond that regime for sufficiently deep circuits.
  • Measurement: Experimental cross entropy is estimated from measured bit-strings by evaluating their ideal-circuit output probabilities.The statistical error scales as κ/√m with κ approximately one.

3. Compute the quantities log 1/pU(xexp

Beyond the classically tractable regime, the ideal output probabilities cannot be obtained numerically, so the cross entropy difference must be inferred indirectly. The paper proposes extrapolating circuit fidelity from smaller or otherwise simulable circuits.

  • For large enough circuits, pU(xexp) can no longer be obtained numerically, and C becomes approximately zero.
  • Circuit fidelity α can be extrapolated from circuits with fewer qubits, mostly Clifford gates, or smaller depth.
  • The practical supremacy threshold is constrained by measurement counts, experimental biases, and agreement precision between theory and experiment.

III. FIDELITY ANALYSIS

The paper models circuit errors, relates cross entropy difference to circuit fidelity, and tests this relationship numerically. Simulations show good agreement, while errors progressively deform the Porter–Thomas output distribution toward uniform sampling.

  • The experimental output is modeled as ρK = α|ψd⟩⟨ψd| + (1 − α)I/N, separating the ideal circuit state from a uniform component.
  • Under incoherent-error assumptions and weak correlations, the average cross entropy difference approximately equals circuit fidelity.
  • Depolarizing channels are inserted after gates to simulate Pauli errors, with separate rates for one-qubit, two-qubit, initialization, and measurement operations.
  • The cross entropy difference and estimated fidelity show good agreement, with small discrepancies attributed to residual correlations.
  • The ideal circuit’s cross entropy difference is almost exactly one, indicating Porter–Thomas behavior at the simulated depth.
  • Errors alter the Porter–Thomas distribution’s shape, driving it toward uniform sampling as α approaches zero.

IV. CONVERGENCE TO PORTER-THOMAS

The simulations examine how planar random circuits approach Porter–Thomas statistics using hardware-motivated gate layouts and multiple distributional diagnostics. Entropy and moments converge rapidly, while a stronger sustained-entropy criterion requires sublinear depth growth.

  • Circuit construction: Neighboring CZ gates cannot be performed simultaneously on current superconducting hardware, so eight layouts are applied sequentially.
  • Circuit construction: The circuits begin with Hadamard gates and repeat alternating CZ layouts with randomly selected single-qubit gates from {X1/2, Y1/2, T}.
  • Entropy convergence: Approximately ten cycles bring circuits of up to 7 × 6 qubits to the Porter–Thomas entropy regime.
  • Moment convergence: Moments through k = 10 converge at similar depth for 7 × 6-qubit circuits.
  • Strong convergence criterion: The sustained 4-sigma entropy criterion has a required depth that grows sublinearly with the number of qubits.
  • Strong convergence criterion: The standard deviation of Porter–Thomas entropy scales as approximately 0.75·2^-n/2.
  • Strong convergence criterion: The output distribution of the studied circuits has the same entropy as Porter–Thomas up to statistical fluctuations of order 2^-n/2.

V. COMPUTATIONAL HARDNESS OF THE CLASSICAL SAMPLING PROBLEM

Random-circuit output distributions are highly delocalized: quantum devices can sample them efficiently, while estimating individual probabilities is infeasible. Complexity-theoretic arguments extend this distinction to support the hardness of classical sampling.

  • The highly delocalized distribution pU(x) prevents estimating any individual probability without exponentially many measurements, even on a quantum computer.
  • A shallow random circuit can nevertheless sample pU(x) efficiently by measuring the produced quantum state.
  • The paper extends earlier hardness arguments for commuting random circuits to universal random circuits.
  • Approximating pU(x) is argued to belong to a complexity class harder than probabilities generated by polynomial classical samplers, ruling out efficient classical sampling under the argument’s assumptions.

A. General overview of the computational complexity argument

The paper argues that efficiently sampling random-circuit output distributions would imply efficient approximation of complex Ising-model partition functions, which is considered implausible under stated complexity assumptions.

  • A classical sampler receives a circuit description and must output bit-strings with probabilities approximating the circuit’s output distribution.
  • The output probability pU(x) can encode the partition function of a random complex Ising model with energy, local fields, coupling matrix, and imaginary inverse temperature.
  • For imaginary temperatures, estimating the partition function requires resolving cancellations among exponentially large terms, so multiplicative approximations of term counts are insufficient.
  • Under a conjecture that sufficiently many random instances are as hard to approximate as worst-case instances, an efficient approximate classical sampler cannot exist.

B. The partition function for random circuits

The circuit amplitudes are rewritten as a Feynman path integral and then as a classical Ising-model partition function at purely imaginary inverse temperature. The resulting coupling graph has worldlines for qubits and exponentially distributed lateral couplings.

  • Each path is a sequence of computational-basis states, with its final state fixed by the measured bit-string x.
  • The circuit wavefunction amplitude takes the form of an Ising-model partition function with energy Hs and purely imaginary inverse temperature iπ/4.
  • For a square grid, pCZ ≃ 1/4, and the coupling distribution decays exponentially, with P(r+1)/P(r) ≃ pCZ/8 ≃ 1/32.
  • The Ising coupling graph forms qubit worldlines with nearest-neighbor temporal couplings and lateral couplings between neighboring qubit worldlines.
  • The partition function is exponentially smaller than its exponentially large individual terms, producing strong cancellation that prevents accurate efficient estimation of amplitudes.

VI. CONCLUSION

The conclusion presents cross entropy as a practical benchmark for comparing random-circuit devices with classical simulation and fidelity estimates. It argues that classical simulation becomes infeasible near roughly fifty qubits while emphasizing error-model validation.

  • Cross entropy provides a well-defined metric for random-circuit sampling and can be measured with supercomputer simulations up to the quantum-supremacy frontier.
  • Beyond the tractable regime, cross entropy can be extrapolated by varying qubit count, non-Clifford-gate count, or circuit depth and compared with fidelity estimates.
  • Quantum supremacy can be claimed when theoretical fidelity estimates agree well with experimental cross-entropy extrapolations.
  • State-of-the-art supercomputers fail to simulate universal random circuits with more than approximately 48 qubits and depth ∼40 using the studied direct methods.
  • The proposed sampling task is general, and qualitative superiority over classical computers would not simply amount to a device simulating itself.
  • Large-scale universal-circuit error models are difficult to evaluate because of circuit complexity, motivating cross entropy as a way to characterize and validate them.

Appendix A: Residual correlations after discrete errors

The appendix analyzes residual correlations caused by single bit- and phase-flip errors at different circuit depths. Their effects depend on measurement basis, gate placement, and subsequent gates.

  • Residual correlations from a single X or Z error account for slight curvature and disparity between cross-entropy difference and estimated fidelity.
  • A phase-flip near the circuit end does not affect computational-basis output distributions because measurement is insensitive to phase errors.
  • CZ gates commute with Z errors, preserving the phase-flip’s limited effect when it occurs near the end of the circuit.
  • Bit-flip errors have no effect after the initial Hadamard cycle, which rotates the computational-basis initial state into the x basis.
  • Some late bit-flip errors also leave correlations unchanged when a Hadamard-like gate rotates them into the measured z basis.

Appendix B: Quantum Simulation Details

The appendix describes a distributed gate-level simulator and optimizations for scaling random-circuit simulations across many sockets. Results quantify communication costs, optimization gains, and simulation limits for circuits up to 42 qubits.

  • Implementation: The simulator evolves a 2^n state vector using general single-qubit and two-qubit controlled gates on distributed systems.Its implementation uses vectorization, multithreading, cache blocking, and gate specialization to reduce communication and memory costs.
  • Communication costs: Communication-intensive gates are slowed by the lower network bandwidth, with an expected slowdown of approximately 8× on Edison.Higher-order qubits require communication, and qubit 41 took 29 seconds per Hadamard gate in a 42-qubit simulation.
  • Scale: 36- and 42-qubit circuits were simulated on 64 and 4,096 sockets, respectively.The 42-qubit simulation used the Edison supercomputer.
  • Optimization results: For a 36-qubit depth-25 circuit, specialization and cache blocking nearly halved average gate time and total runtime.Average time per gate decreased from 1.5 seconds without specialization to 1.08 seconds with specialization and 0.76 seconds with both optimizations.
  • Optimization results: A 42-qubit depth-25 circuit required 1,589 seconds, including 989 seconds for gate simulation and 600 seconds for statistics.Its average time per gate was 1.72 seconds, a 2.3× increase over the 36-qubit simulation.
  • Simulation boundaries: An improved simulator reported elsewhere achieved an order-of-magnitude speedup for 42-qubit circuits and simulations up to 45 qubits.The relative speedup is substantially diminished when statistics are collected after every circuit cycle.
  • Simulation boundaries: Clifford-only circuits remain efficiently simulable, while the tested circuits rely on non-Clifford T gates and their number affects tractability.The authors state that reducing T gates could permit verification of larger circuits when direct simulation is otherwise difficult.

Appendix F: Outline of Stockmeyer Counting Theorem

The appendix outlines how Stockmeyer counting connects an efficient classical sampler to approximate output probabilities and, through Porter–Thomas statistics, to complex Ising-model partition functions. Hashing supplies threshold counts, while the resulting approximations support the paper’s complexity-theoretic argument.

  • Counting strategy: Stockmeyer counting uses an NP oracle and randomized hashing to approximate the number of solutions to a polynomial-time computable function.Pairwise-independent hash functions distinguish whether a solution set is above or below a power-of-two threshold, with success probability amplified through repeated calls.
  • Application to sampling: Assuming a polynomial-time classical sampler close in variational distance to a random-circuit distribution, Stockmeyer counting would approximate selected output probabilities.The argument treats such an efficient sampler as a route to probability estimates that are conjectured to be computationally difficult.
  • Application to sampling: Under the Porter–Thomas assumption, the approximation reaches multiplicative error 1/4 + o(1) with probability at least (2e)^-1.The passage gives the bound as a consequence of the stated equations and a random-output assumption.
  • Ising-model connection: Because p_U(x) = λ|Z|^2, approximating p_U(x) multiplicatively yields the same multiplicative approximation for the squared magnitude of an Ising-model partition function.Here λ is a known positive constant and Z is the complex Ising-model partition function.
  • Bayesian approximation: The appendix also develops a polynomial classical approximation based on sampling spin configurations or Feynman paths in the circuit’s Ising-model representation.The posterior distribution describes an approximation to p_U(x) after sampling a large number Q of configurations or paths.
  • Bayesian approximation: The posterior probability explicitly contains the target output probability, with a term of order Q^2/L.The paper compares this posterior with the circuit-fidelity distribution to obtain an equivalent fidelity for the Bayesian approximate sampler.
Loading 1608.00263v3…