PaperlayerView exact revision on arXiv

Source-linked AI summary

Supplementary information for "Quantum supremacy using a programmable superconducting processor"

Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus R. Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandra, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, John M. Martinis

arXiv:1910.11333v2quant-ph

TL;DR

Efficiently evaluating random-circuit outputs is a central challenge for demonstrating quantum computational advantage. The paper develops scalable cross-entropy benchmarking methods and reports a nonzero 53-qubit, 20-cycle circuit fidelity inconsistent with the null hypothesis at 6σ.

Abstract

from arXiv · show

This is an updated version of supplementary information to accompany "Quantum supremacy using a programmable superconducting processor", an article published in the October 24, 2019 issue of Nature. The main article is freely available at https://www.nature.com/articles/s41586-019-1666-5. Summary of changes since arXiv:1910.11333v1 (submitted 23 Oct 2019): added URL for qFlex source code; added Erratum section; added Figure S41 comparing statistical and total uncertainty for log and linear XEB; new References [1,65]; miscellaneous updates for clarity and style consistency; miscellaneous typographical and formatting corrections.

I. DEVICE DESIGN AND ARCHITECTURE … A. XEB of a small number of qubits

This section describes the Sycamore processor’s architecture and the cross-entropy benchmarking methods used to estimate circuit and cycle fidelity. It covers XEB estimators, their relation to depolarization fidelity, validation through simulations, and fitting procedures that account for state-preparation and measurement errors.

I. DEVICE DESIGN AND ARCHITECTURE

  • Sycamore uses tunable transmons with adjustable capacitive couplers, enabling fast two-qubit gates, small frequency excursions, reduced flux sensitivity, and coupling shutdown during measurement.The coupling is tunable from 5 MHz to −40 MHz, with approximately −20 MHz used during the experiment; adjustable couplers trade simpler control for additional wiring and signals.Source: §I · p. 2

II. FABRICATION AND LAYOUT

  • The processor contains 54 individually controlled and read-out qubits plus 88 adjustable couplers arranged in a diagonal array.Nearest-neighbor pairs combine direct capacitive and indirect coupler-mediated interactions, whose net coupling can be tuned to zero at a specific flux bias.Source: §II · p. 2

A. Control

  • Synchronized control uses 54 microwave, 54 qubit-flux, and 88 coupler-flux signals, forming a phase-synchronous waveform generator with more than 250 channels and 20 ps interchannel jitter.Four chassis control the full chip, with each chassis supporting approximately 15 qubits and associated couplers and readout signals.Source: A. Control · p. 3

B. Readout

  • Dispersive readout infers qubit states from resonator phase shifts and simultaneously reads six qubits in each of nine frequency-multiplexed groups using FPGA demodulation.The reflected signals are amplified, mixed to intermediate frequency, digitized, and processed using experimentally calibrated demodulation windows.Source: B. Readout · pp. 3–5

IV. XEB THEORY

  • XEB estimates random-circuit fidelity by comparing measured bitstrings with simulated ideal probabilities, avoiding exponential reconstruction of experimental output probabilities.Standard XEB uses f(ps(q)) = log(ps(q)), whereas the main text uses linear XEB, f(ps(q)) = Dps(q) −1; Heavy Output Generation uses a step function.Source: §IV · p. 5, A. XEB of a small number of qubits · p. 6

A. XEB of a small number of qubits

  • The 2-qubit simulations show that depolarizing fidelity p_c^m closely matches the ensemble-averaged squared overlap across swap errors Δθ = 0.01–0.05.This agreement supports the depolarizing-channel connection for systematic swap-angle errors in random circuits.Source: Figure S6 · p. 6, A. XEB of a small number of qubits · p. 6
  • Alternative XEB functions, including f(p_s(q)) = log p_s(q), estimate total polarization through experimentally averaged functions and numerical simulations.The logarithmic estimator derives from sample log-likelihood and converges to cross entropy between experimental and simulated probabilities.Source: A. XEB of a small number of qubits · p. 7
  • Both the standard and logarithmic XEB formulations produce a linear equation for estimating total polarization, using numerical simulations and experimental averages.For multiple circuits with the same cycle count, least squares combines the circuit-specific estimates.Source: A. XEB of a small number of qubits · p. 7
  • Fitting total-polarization estimates to exponential decay in cycle count yields cycle polarization, independently of state-preparation and measurement errors.The exponential-decay fit follows the standard randomized-benchmarking approach [31] [32].Source: A. XEB of a small number of qubits · p. 7

B. XEB of a large number of qubits

For large-qubit random circuits, linear and logarithmic XEB estimate fidelity under an assumption about error-state independence from ideal probability speckles. Under Porter–Thomas statistics, logarithmic XEB is more precise above F=0.32, whereas linear XEB is better below that threshold; HOG is always noisier.

B. XEB of a large number of qubits

  • The large-qubit XEB derivation assumes error contributions are typically uncorrelated with the chaotic speckles of the ideal output probabilities.The required statistical fluctuation is ϵ≪F, with concentration-of-measure arguments motivating the assumption.Source: B. XEB of a large number of qubits · pp. 7–8
  • Linear and logarithmic XEB convert measured bitstrings into fidelity estimates, whose experimental averages converge with accuracy 1/√Ns using Ns samples.The linear form uses f(ps(q))=Dps(q)−1, while logarithmic XEB uses f(ps(q))=log ps(q).Source: B. XEB of a large number of qubits · p. 8
  • For sufficiently deep experimental circuits, Porter–Thomas measurement probabilities determine the estimator variances used to compare linear and logarithmic XEB.The comparison is illustrated with fidelity estimates from bitstrings collected using elided circuits.Source: B. XEB of a large number of qubits · p. 8, Figure S8 · p. 8
  • For F>0.32, logarithmic XEB has smaller standard deviation, while linear XEB is better for F<0.32 and approaches maximum likelihood when F≪1.The logarithmic estimator is best near F≈1.Source: B. XEB of a large number of qubits · p. 8, Figure S8 · p. 8
  • The HOG-based fidelity estimator counts bitstrings above the median-probability threshold, but its standard deviation is always larger than XEB’s.The HOG test is also related to a definition of quantum volume [39].Source: B. XEB of a large number of qubits · p. 8

C. Two limiting cases

This section analyzes two limiting cases of the XEB fidelity estimator: uniform sampling gives zero fidelity, while ideal Porter–Thomas sampling gives unit fidelity. Depolarizing errors are obtained by convexly combining these limits.

Uniform sampling

  • Uniformly sampled bitstrings have FXEB = 0, so the estimator correctly returns zero fidelity for a maximally mixed state.Every bitstring has sampling probability 1/D in this case.Source: C. Two limiting cases · p. 9

Porter–Thomas sampling

  • For samples from a random-circuit output distribution with Porter–Thomas statistics, the average sampled ideal probability yields FXEB = 1.The derivation uses the probability density of the ideal probability assigned to a sampled bitstring.Source: C. Two limiting cases · p. 9

Depolarizing errors

  • The general depolarizing-error case follows from a convex combination of the two limiting cases.Thus, the estimator interpolates between the uniform-sampling and ideal-sampling limits.Source: C. Two limiting cases · p. 9

D. Measurement errors · V. QUANTIFYING ERRORS

The sections derive how measurement and preparation errors modify fidelity estimates and present a depolarizing-error framework linking single- and two-qubit measurements to XEB fidelity. They recommend reporting dimension-independent Pauli error and explain how repeated-cycle measurements remove scaling factors from preparation and measurement errors.

D. Measurement errors

  • Measurement errors are modeled as independent bit-flip probabilities em0 and em1, making the probability of any measured bitstring a product of corresponding single-qubit factors.The model uses p(1|0) = em0 and p(0|1) = em1, with complementary probabilities for correct outcomes.Source: D. Measurement errors · p. 9
  • For large n, the number of ones in the actual bitstring is approximated by n/2 when evaluating the probability of a correct measurement result.Source: D. Measurement errors · p. 9
  • Assuming erroneous outcomes produce ideal probabilities uncorrelated with the actual outcomes, complete fidelity separates into circuit fidelity and measurement fidelity factors.Measurement fidelity pm can be estimated by preparing and immediately measuring random bitstrings, allowing FU to be obtained from the resulting relation; fitting fidelity across circuit depths provides another separation method.Source: D. Measurement errors · p. 9
  • State-preparation errors can be incorporated analogously by combining measurement fidelity with a corresponding state-preparation fidelity factor.Source: D. Measurement errors · p. 9

V. QUANTIFYING ERRORS

  • The error-quantification framework predicts XEB fidelity FXEB from simpler single- and two-qubit error measurements using Pauli errors and a depolarizing model.Depolarization is treated probabilistically: the no-error probability multiplies across qubit gates, while an error with probability ed mixes the state with the maximally mixed state of dimension D = 2^n.Source: §V · pp. 9–10
  • Repeated-cycle measurements set p = p_c^m, so the fractional polarization change per cycle can be extracted independently of state-preparation and measurement scaling factors.The measured signals are RB = p(1 − 1/D) + 1/D and FXEB = p before this repeated-cycle procedure removes offsets and prefactors.Source: §V · p. 10
  • The sections recommend reporting the dimension-independent Pauli error eP rather than entanglement fidelity or the commonly used RB fidelity with a D-dependent correction.Table I summarizes translations among the measured depolarization decay constant p, Pauli error, and other error metrics, including representative comparisons for 0.1% Pauli error.Source: §V · p. 10, Table I · p. 11
  • The framework extends to nondepolarizing errors such as energy decay and uses Kraus operators to connect physical error mechanisms with total and component error budgets.For random circuits, Pauli depolarization is appropriate when errors effectively decorrelate the state, while the explicit Pauli-to-depolarization assumption is mainly needed for small D; large-D FXEB then follows probabilistically.Source: §V · pp. 10–11

VI. METROLOGY AND CALIBRATION … 4. Optimizing qubit operating frequencies

The supplementary section presents automated, graph-based calibration for Sycamore and formulates qubit-frequency selection as an optimization problem. The Snake optimizer finds locally optimal frequencies in approximately 10 seconds for the 53-qubit processor while balancing multiple error mechanisms.

A. Calibration overview

  • Calibration must handle pulse-shaping errors, qubit-to-qubit parameter variation, temporal drift, bootstrapping, and independently calibrated single-qubit gates, two-qubit gates, and readout.These requirements make automated calibration necessary for maintaining target fidelities.Source: A. Calibration overview · p. 11
  • Calibration automation improved full-system fidelities by over an order of magnitude while reducing calibration time and improving reliability.The procedure is designed mainly around single- and two-qubit operations rather than system-level calibration to improve scalability.Source: A. Calibration overview · p. 11

1. Device registry

  • >100 parameters per qubit are stored in the device registry to populate optimal frequencies, biases, gate parameters, and circuit-model information.The registry is a database of control variables and configuration information used to control the quantum processors.Source: §1 · pp. 11–12

2. Scheduling calibrations: “Optimus”

  • 36 hours: initial Sycamore bringup takes approximately 36 hours after cooldown, followed by approximately 4 hours per day to maintain calibration.Optimus represents calibrations as nodes in a directed acyclic graph, with edges encoding bootstrapping dependencies and enabling minimal recalibration after drift.Source: §2 · p. 12, Figure S10 · p. 12

1. Device configuration

  • The calibration procedure progresses through root, single-qubit, and grid configurations, moving from coarse device characterization to isolated-qubit tuning and chip-scale high-fidelity operations.Active qubits operate at 5-7 GHz, while inactive qubits are biased near zero frequency; grid calibration then supports single-qubit gates, two-qubit gates, and readout.Source: §1 · pp. 12–13

2. Root config: procedure

  • Root calibration uses frequency-domain experiments to characterize qubit and coupler responses, resonators, bias-dependent frequencies, and low-coupling coupler settings.For each coupler, the procedure identifies a near-maximum-frequency region where qubit-qubit coupling is a few MHz and relatively insensitive to coupler bias.Source: §2 · p. 13

3. Single-qubit config: procedure

  • Single-qubit calibration tunes resonance, π and π/2 pulses, readout, timing, transfer functions, and T1 versus frequency before feeding the results into frequency placement.The resulting coherence and circuit-parameter information is used to identify optimal operating frequencies for full-processor operation.Source: §3 · p. 13

4. Optimizing qubit operating frequencies

  • ∼10 seconds: Snake returns locally optimal operating frequencies for the 53-qubit processor, which are sufficient for state-of-the-art system performance.Snake combines quantum-algorithm structure with physics intuition, exploiting the time-interleaved structure of single-qubit gates, two-qubit gates, and readout.Source: §4 · p. 14

5. Grid config: procedure … 4. Speckle purity benchmarking (SPB)

The supplementary sections describe grid calibration, tunable transmon two-qubit gates, XEB-based gate metrology, randomized-benchmarking validation, and SPB for extracting purity from raw XEB data. Together, they establish calibration procedures, model and benchmark fSim gates, and extend purity measurement to larger systems with reduced sequence requirements.

5. Grid config: procedure

  • The grid-calibration procedure adds coupler adjustments to isolated-qubit calibration, using resonant swapping or conditional-phase experiments to minimize qubit-qubit coupling before restoring frequencies and calibrating entangling gates.Coupler pulse amplitudes are tuned for complete photon exchange, while qubit pulse amplitudes are fine-tuned for resonance and pulse-undershoot compensation.Source: §5 · p. 14

C. Two-qubit gate metrology

  • Tunable frequencies and interactions enable high-fidelity two-qubit control, while XEB provides a metrology strategy for learning the unitary model and separating total error from decoherence.Two-qubit XEB fidelity decay measures total error, purity decay measures decoherence, and their difference gives control error; the reported total error is about half control and half decoherence.Source: C. Two-qubit gate metrology · p. 15, §2 · p. 16

1. The natural two-qubit gate for transmon qubits

  • For transmons, nonleaking two-qubit controls decompose into partial-iSWAP and controlled-phase operations, motivating fSim gates and the supremacy choice fSim(θ ≊90° , φ ≊30°).The 12 ns control duration balances decoherence against leakage, and the chosen gate is natural, easy to calibrate, and intrinsically high fidelity.Source: §1 · pp. 15–16, Figure S14 · p. 16

2. Using cross entropy to learn a unitary model

  • Optimizing a generic unitary model with XEB produces nearly coherence-limited fidelity decay and identifies pairwise control parameters centered near 90° partial-iSWAP angles and 30° conditional phases.The model also tracks three required Z-rotations corresponding to pre-swap detuning, post-swap detuning, and a commuting overall frequency shift.Source: §2 · p. 16, Figure S16 · p. 17

3. Comparison with randomized benchmarking

  • XEB agrees with randomized benchmarking: the measured CZ XEB cycle error is 0.59%, close to the 0.57% predicted from RB, while π/2-only RB removes the single-qubit discrepancy caused by π-pulse reflections.The XEB gateset uses only π/2 pulses, whereas conventional RB includes π pulses with somewhat higher errors in this device.Source: §3 · pp. 17–18, Figure S17 · p. 18

4. Speckle purity benchmarking (SPB)

  • SPB models decoherence with a depolarizing-channel parameter p and obtains p^2 by comparing measured probability variance with the Porter-Thomas variance, relating XEB fidelity p to √Purity.For a fully decohered state, all bitstrings have probability 1/D and zero variance; increasing p shrinks the Porter-Thomas distribution toward that uniform limit.Source: §4 · pp. 18–19
  • SPB requires no knowledge of the specific gate sequence when Hilbert-space randomization is sufficient, because the resulting measured probabilities follow Porter-Thomas statistics.This enables purity extraction from raw XEB data while retaining the limitation that complete probability-distribution characterization scales exponentially in measurements.Source: §4 · pp. 18–19
  • SPB extracts state purity from raw XEB data with exponentially fewer pulse sequences than full tomography, although exponentially many measurements remain necessary to characterize each sequence’s probability distribution.The method applies when circuit randomization produces Porter-Thomas statistics, but full-processor purity measurements remain impractical.Source: §4 · pp. 18–19

5. “Per-layer” parallel XEB … B. Overview and technical requirements

The supplementary material develops scalable benchmarking and readout procedures for the processor, while outlining how random-circuit sampling supports both quantum-supremacy demonstrations and performance evaluation. It uses per-layer parallel XEB and calibrated, frequency-optimized readout to make characterization efficient and quantify the resulting errors.

5. “Per-layer” parallel XEB

  • Per-layer parallel XEB characterizes every two-qubit gate in four device-wide experiments while keeping optimization and classical simulation efficient for each pair.The method repeats one entangler layer with interleaved single-qubit gates, measures all qubits, and extracts pairwise XEB data.Source: §5 · p. 20
  • Simultaneous operation increases optimized XEB error by roughly 0.003, primarily through purity error from unintended interactions, while unitary changes are dominated by the ∆+ single-qubit phase.The simultaneous and isolated optimized errors are both close to purity-limited, but simultaneous-operation unitaries differ slightly because of control crosstalk and unintended interactions.Source: §5 · p. 20, Figure S19 · p. 21

1. Choosing qubit frequencies for readout

  • Readout frequencies are dynamically optimized because idling frequencies favor dephasing rather than readout, with constraints preventing qubit swaps and mitigating resonator cross-coupling.The procedure scans readout fidelity versus qubit and resonator-drive frequencies, avoids qubit resonance, biases couplers when needed, separates nearby resonator eigenfrequencies, and applies correlated discrimination to an eight-qubit chain.Source: §1 · p. 20, Figure S20 · p. 23

2. Single qubit calibration

  • Single-qubit readout calibration uses 1 µs drive pulses and demodulation windows, target separation below a 0.3% error threshold, optimized weighting, and discrimination lines.The resonator drive frequency maximizes |0⟩–|1⟩ separation, while drive power avoids amplifier saturation and unwanted state transitions [17] [53].Source: §2 · pp. 20–21
  • The median isolated identification errors are 0.97% for |0⟩ and 4.5% for |1⟩, attributed respectively to thermal excitation and energy relaxation during readout.These calibrations define identification error as the probability that the measured state differs from the prepared state.Source: §2 · p. 21, Figure S21 · p. 23

3. Characterizing multi-qubit readout

  • 53-qubit simultaneous readout identifies the prepared 150-state bitstrings in 13.6% of trials, with median errors rising to 1.8% for |0⟩ and 5.1% for |1⟩.Each state was measured in 3000 trials; the most likely multiqubit error was one lost excitation, and the increase in simultaneous-readout error was not yet understood.Source: §3 · p. 21, Figure S21 · p. 23

E. Summary of system parameters

  • Aggregate system parameters summarize 53 single-qubit samples and 86 two-qubit pairs, with distributions of gate, readout, and device parameters reported across the Sycamore processor.Table II reports aggregate values, while complete single-qubit values are provided in Ref. and illustrated in Figs. S22–S24.Source: E. Summary of system parameters · p. 22, Table II · p. 22, Figure S22 · p. 24

A. Background

  • Random quantum circuits serve both quantum-supremacy sampling and performance evaluation, using n = 53 qubits and m = 20 cycles for the demonstration while balancing classical hardness against simulability.Large n hinders Schrödinger simulation, high m impedes tensor-network simulation, and XEB’s analytical cross-entropy expression applies when depth exceeds 12 because probabilities approach Porter–Thomas behavior. Similar transformed circuits can estimate fidelity when direct simulation is infeasible.Source: A. Background · p. 27, B. Overview and technical requirements · p. 27

C. Circuit structure … 1. Decomposition of CZ into fSim gates

The sections describe Sycamore’s programmable random circuits, including their geometry, repeated gate patterns, randomized single-qubit operations, and native two-qubit gates. They establish universality by decomposing CZ into two fSim gates and single-qubit rotations, with the construction verified for all 86 device fSim gates.

C. Circuit structure

  • The qubit layout usually partitions circuits below 51 qubits into similarly sized blocks joined by five couplers, while 51-qubit circuits use seven couplers and are much harder to simulate.The resulting geometry creates a substantial hardness gap between most evaluation circuits and the 53-qubit supremacy circuits.Source: C. Circuit structure · p. 27
  • Each random quantum circuit has m full cycles plus a single-qubit half cycle, with alternating one-qubit gates and patterned two-qubit couplings before measurement.Supremacy circuits repeat ABCDCDAB, whereas evaluation circuits repeat EFGH; the coupling sequence strongly affects simulation cost.Source: C. Circuit structure · p. 27, Figure S25 · p. 28

D. Randomness

  • The PRNG seed s determines all single-qubit gates, so matching seeds produce matching gates wherever circuits share qubits and cycles, while two-qubit gates are seed-independent.The seed is the sole circuit property governing single-qubit gate choices.Source: D. Randomness · pp. 27–28

E. Quantum gates

  • Single-qubit gates are π/2 equatorial rotations selected from three gates, with successive cycles excluding the preceding gate to prevent simulation-path simplifications.The first cycle samples independently and uniformly from all three gates; later cycles sample uniformly from the other two.Source: E. Quantum gates · p. 28
  • Native two-qubit gates preserve excitation number and consist of three Z-rotation parameters plus an fSim(θ, φ) gate, with θ ≈π/2 and φ ≈π/6 tuned per qubit pair.The Z-rotation parameters vary with gate timing, whereas θ and φ are constant across cycles for a given pair; omitting corrections increases interactions and implicit non-Clifford gates.Source: E. Quantum gates · pp. 28–29

F. Programmability and universality

  • The supremacy gate set is universal because CZ can be composed from two fSim gates and single-qubit rotations, while X1/2 and W1/2 generate SU(2) by adapting the H-and-T universality proof [58].The argument combines universality of CZ plus SU(2) with the programmable native gate set.Source: F. Programmability and universality · p. 29

1. Decomposition of CZ into fSim gates

  • For typical fSim parameters, a large set of controlled-phase gates is realizable, except gates very close to identity, by matching Schmidt coefficients in the two-fSim construction.The intermediate unitary has Schmidt rank two, matching the target controlled-phase gate’s rank-two structure.Source: §1 · pp. 29–30
  • The CZ decomposition works for all 86 fSim gates tested on the device, and the construction implements a controlled-phase gate up to single-qubit Z rotations.Setting δ = π gives CZ; the construction uses two fSim gates and local X rotations.Source: §1 · pp. 29–30

2. Universality for SU(2) · G. Circuit variants

The X1/2 and W 1/2 gates are shown universal for SU(2) by adapting the H- and T-gate argument: both generate single-qubit rotations by irrational multiples of π. Circuit variants control classical simulation cost while approximately preserving experimental fidelity through transformations that reduce bond dimensions.

2. Universality for SU(2)

  • X1/2 and W 1/2 are universal for SU(2) because their composed rotations have angles that are irrational multiples of π, extending the H- and T-gate argument.The argument uses T ≡ RZ(π/4) followed by HTH ≡ RX(π/4), and analogously W 1/2 ≡ RX+Y(π/2) followed by X1/2 ≡ RX(π/2).Source: §2 · p. 30
  • The irrationality of the H- and T-derived angle follows because eiα has a non-cyclotomic monic minimal polynomial with rational coefficients, as established using Theorem B.1 of.The supplied polynomial expression is x4 + x3 + 1, while equation (75) is shown as 4x2 + x + 1; the non-cyclotomic criterion is that not all coefficients are integers.Source: §2 · p. 30
  • The W 1/2 and X1/2 rotation angle is also irrational because eiβ has the same monic minimal polynomial as eiα, so the remainder of the H- and T-based proof applies.The passage identifies the shared polynomial as (75).Source: §2 · p. 30

G. Circuit variants

  • Circuit variants are needed because XEB requires classical simulation, which becomes hard near the supremacy frontier, while performance evaluation remains costly and direct fidelity estimation is desired.The RQCs are designed so effective SFA partitioning exists below 51 qubits, creating a simulation-cost gap between supremacy and most evaluation circuits.Source: G. Circuit variants · p. 30
  • Experimental fidelity depends mainly on gate number and quality, whereas simulation cost is highly structure-sensitive; transformed circuits therefore approximate hard-circuit fidelity without substantially changing it.The approximation uses similar RQCs whose simulation cost is reduced while experimental fidelity is intended to remain largely unaffected.Source: G. Circuit variants · pp. 30–31
  • Gate elision reduces simulation cost by removing some or all cross-partition gates, thereby lowering the bond dimension of promising circuit cuts.The removed gates are called elided gates.Source: G. Circuit variants · p. 31
  • Changing coupler-activation sequences forms wedges that slow entanglement spread across circuit cuts and reduce their bond dimensions.The coupler patterns are the sequences shown in Fig. S25.Source: G. Circuit variants · p. 31
  • Each experimental RQC is uniquely specified by qubit count n, cycle count m, PRNG seed s, elided-gate count, and coupler-activation sequence.The variants include the non-simplifiable full circuits used for the supremacy demonstration and five other variants used for performance evaluation.Source: G. Circuit variants · p. 31, Table III · p. 31

1. Gate elision … E. Understanding system performance: error model prediction

Large-scale XEB performance can be estimated with patch and elided circuits, while simultaneous-operation calibration and a digital error model closely predict full-system fidelities. Gate elision and circuit scheduling reduce classical simulation costs by controlling bond dimension and entanglement.

1. Gate elision

  • Eliding cross-partition gates from initial cycles reduces partition bond dimension by factors of two or four, with fully disconnected patch circuits as the limiting case.When elided-gate errors resemble substituted identity-gate errors, elided-circuit fidelity can remain similar to full-circuit fidelity.Source: §1 · p. 31

2. Wedge formation

  • A cross-partition wedge has Schmidt rank at most four, so each wedge reduces partition bond dimension by a factor of four; the ABCDCDAB schedule prevents wedges.The EFGH schedule enables wedges and efficient SFA simulation, whereas ABCDCDAB is used for quantum-supremacy and largest evaluation circuits.Source: §2 · p. 31, Figure S26 · p. 32

VIII. LARGE SCALE XEB RESULTS

  • Large-scale XEB uses patch circuits, unitary-model comparisons, and stability monitoring to benchmark Sycamore beyond the regime where direct full-system analysis is practical.The modular patch approach estimates larger-system XEB fidelities without exponential classical resources.Source: §VIII · pp. 31–32

A. Limitations of full circuits

  • Full-circuit XEB required exponentially increasing classical resources, progressing from Schrödinger simulation through hybrid Schrödinger–Feynman methods and supercomputing above 38 qubits.Simplified patch and elided circuits provided approximate performance predictions into the quantum-supremacy regime.Source: A. Limitations of full circuits · pp. 32–33

B. Patch circuits: a quick performance indicator for large systems

  • Patch XEB matched full XEB within a typical 5% fidelity deviation across 12–53 qubits, providing a rapid performance indicator with exponentially reduced computational cost.The worst-case disagreement was 10% at 34 qubits, and patch analysis can scale to arbitrary qubit counts with roughly constant patch size.Source: B. Patch circuits: a quick performance… · p. 33, Figure S28 · p. 33

C. Elided circuits: a more rigorous performance estimator for large systems

  • Elided circuits predicted full-circuit fidelities with an average ratio of 1.01 and 5% standard deviation, enabling extrapolation where full analysis is too expensive.They retain weak entanglement between patches and reduce simulation cost; for 53-qubit circuits, their inter-patch entanglement should approach that of full circuits.Source: C. Elided circuits: a more rigorous… · p. 34

D. Choice of unitary model for two-qubit entangling gates

  • Simultaneous pair XEB unitaries produced the best full-system fidelities at every tested size, while alternative models differed by less than a factor of 2 at 50 qubits.The simultaneous model captures coherent modifications from parallel operation, including flux-control crosstalk and dispersive shifts.Source: D. Choice of unitary model for… · p. 35

E. Understanding system performance: error model prediction

  • Measured fidelities agreed with predictions from constituent entanglement fidelities within 10–20%, supporting the digital error model even across entangled systems.The model assumes no space or time error correlations and uses gate entanglement fidelities plus simultaneous readout fidelities, which include state-preparation errors.Source: E. Understanding system performance:… · pp. 35–36

F. Distribution of bitstring probabilities · G. Statistical uncertainties of XEB measurements

The bitstring-probability distributions agree with theoretical models at estimated fidelity, while strongly rejecting zero fidelity. Bootstrap and multi-circuit analyses validate the XEB uncertainty estimates and show consistent linear and cross-entropy fidelities.

F. Distribution of bitstring probabilities

  • The Kolmogorov-Smirnov test compares sampled ideal probabilities with theoretical PDFs for estimated and zero fidelity in both linear- and log-XEB parameterizations.The analysis uses x = Dp for linear XEB and x = log(Dp) for cross entropy, with 3 × 10^6 samples from each of ten 53-qubit circuits.Source: F. Distribution of bitstring… · pp. 36, 38
  • For the 20-qubit circuit, experiment agrees with theory, while the uniform-random null is rejected with very high confidence.The comparison uses 0.5 million experimental, uniformly random, and ideal-output bitstrings; goodness of fit is quantified by the Kolmogorov-Smirnov statistic and p-value.Source: F. Distribution of bitstring… · p. 37
  • For each 53-qubit circuit, estimated-fidelity distributions fit well, with p-values 0.18–0.98 for linear XEB and 0.33–0.98 for log XEB.The zero-fidelity null has maximum p-value 0.045, so it is rejected above 95% confidence for every circuit.Source: F. Distribution of bitstring… · p. 38, Figure S36 · p. 39
  • For combined samples, the null hypothesis of F = 0 is rejected at p-value < 2.2 × 10−16, with much higher confidence than for individual circuits.The scipy result is p-value = 3 × 10−24; the table reports the more conservative R-package value.Source: F. Distribution of bitstring… · p. 39

G. Statistical uncertainties of XEB measurements

  • p-value = 0.99 for linear-XEB and 0.41 for cross-entropy bootstrap distributions supports Gaussianity and the central-limit-theorem approximation.The bootstrap uses 4000 resamples, and both distributions are fit with Gaussian maximum likelihood.Source: G. Statistical uncertainties of XEB… · p. 39, Figure S37 · p. 40
  • 5.78 × 10^-3 matches 5.78 × 10^-3 for the linear-XEB uncertainty estimate and bootstrap standard deviation, while all ten circuits agree within 3.1%.For cross entropy, the corresponding values are 7.40 × 10^-3 and 7.46 × 10^-3; relative differences are below 1% in the example circuit.Source: G. Statistical uncertainties of XEB… · p. 39
  • (2.24 ± 0.18) × 10^-3 is the combined linear-XEB fidelity versus (2.34 ± 0.23) × 10^-3 for cross entropy, with both agreeing with theory.The predicted statistical uncertainties are 1.8 × 10^-4 and 2.3 × 10^-4, respectively; linear XEB has the smaller uncertainty.Source: G. Statistical uncertainties of XEB… · p. 39
  • Fidelities across elided circuit instances vary consistently with finite-sample statistical noise, while averaging ten instances yields smaller uncertainties at each depth.Figure S38 reports linear-XEB fidelities with 5σ uncertainties for all ten instances and the reduced uncertainty of their averages.Source: G. Statistical uncertainties of XEB… · pp. 39–40

H. System stability and systematic uncertainties · I. The fidelity result and the null hypothesis on quantum supremacy · IX. SENSITIVITY OF XEB TO ERRORS

The system’s final 53-qubit fidelity was (2.24 ± 0.10(syst.) ± 0.18(stat.)) × 10−3, rejecting F ≤10−3 at 6σ, while stability measurements quantified drift and systematic fluctuations. XEB remained sensitive to discrete and continuous errors, but further work is needed to establish its diagnostic efficacy.

H. System stability and systematic uncertainties

  • The measured fidelity drifted over 17.4 hours, with total σp0 = 1.92×10−4, 3.5 times the statistical-only value, yielding a 4.4% relative systematic uncertainty.A linear fit gave χ2 per degree of freedom 26.3/11 and p-value 0.0058, indicating systematic fluctuation beyond degradation and statistical uncertainty.Source: H. System stability and systematic… · p. 40, Figure S39 · p. 42
  • Systematic fluctuations are consistent with unstable TLS interactions and readout-constrained qubits, while moving a problematic qubit away from a TLS restored stability.Most pair fidelities fluctuated downward by ∼1% at depth 14, corresponding to either ∼1% measurement-fidelity or ∼0.08% two-qubit-gate-fidelity fluctuations.Source: H. System stability and systematic… · pp. 40–41, Figure S40 · p. 43

I. The fidelity result and the null hypothesis on quantum supremacy

  • (2.24 ± 0.21) × 10−3 total fidelity for ten 53-qubit, 20-cycle circuits rejects the null hypothesis F ≤10−3 with 6σ significance.The final benchmark is (2.24 ± 0.10(syst.) ± 0.18(stat.)) × 10−3; the total uncertainty combines systematic and statistical components in quadrature.Source: §I · p. 41, Figure S41 · p. 44
  • For quantum-supremacy claims, systematic fluctuations are multiplicative and cannot create nonzero XEB from zero, so additive statistical fluctuations alone determine false-positive significance.The 6σ significance is therefore described as conservative, although systematic errors remain relevant when comparing XEB fidelities across circuit types.Source: §I · pp. 41–42

IX. SENSITIVITY OF XEB TO ERRORS

  • XEB tests error sensitivity by inserting discrete or continuous errors into reference circuits and comparing the resulting fidelity estimate with the error-free estimate.The method identifies circuit locations producing the same output distribution because XEB cannot differentiate between them.Source: §IX · pp. 42–43
  • A single-qubit Pauli insertion reduced XEB fidelity by almost 100-fold, implying an error probability on the order of 1%, comparable to e2c/2 ≃0.5%.The modified-to-reference XEB ratio is approximately the probability of the inserted error, though multiple gate failures may explain the factor-of-two discrepancy.Source: §IX · p. 43
  • XEB is established as a calibration and performance-evaluation tool, but more work is required to assess its efficacy as a diagnostic tool for quantum processors.The error-modification analysis provides a framework for investigating processor behavior and performance.Source: §IX · p. 43

X. CLASSICAL SIMULATIONS · A. Local Schr¨odinger and Schr¨odinger-Feynman simulators · B. Feynman simulator

The section presents Schrödinger, Schrödinger–Feynman, and Feynman tensor-network simulators, detailing their algorithms, optimizations, and scaling. qFlex simulates 12-cycle Sycamore circuits efficiently but makes 16-cycle-and-beyond simulations impractical, while SFA is expected to lead for large samples.

A. Local Schr¨odinger and Schr¨odinger-Feynman simulators

  • qsim computes all 2^n state amplitudes through repeated gate matrix–vector multiplications, using gate fusion, single precision, AVX/FMA vectorization, and OpenMP.It simulates 38-qubit circuits on one 3844-GB Google cloud node with four 20-core CPUs.Source: A. Local Schr¨odinger and… · p. 44
  • qsimh cuts the lattice into two parts, expands each cut gate by Schmidt decomposition, and sums r^g paths for unit fidelity, with independent paths enabling parallelization.Summing only a fraction F of paths produces simulations with fidelity F; cached prefixes avoid restarting simulations for remaining paths.Source: A. Local Schr¨odinger and… · pp. 44–45

B. Feynman simulator

  • qFlex computes selected output amplitudes by tensor-network contractions and uses frugal rejection sampling, making cost linear in the number of sampled bitstrings.Tensor-network simulators are advantageous for low-depth or large-qubit circuits and small sample sizes.Source: B. Feynman simulator · p. 45
  • qFlex improves time-to-solution through slicing that avoids distributed contractions, high-arithmetic-intensity orderings, and asynchronous GPU tensor operations with out-of-core support.Its implementation also uses noisy simulation, fast correlated-batch sampling, and multi-GPU out-of-core contractions that reduce cuts and support larger tensors.Source: B. Feynman simulator · pp. 45, 46, 48
  • 1.29 hours yields 1M Sycamore bitstrings at 12 cycles and approximately 0.5% fidelity; 14 cycles requires an estimated 68 days, while 3M samples at approximately 1.0% require 1.1 years.At 16 cycles and beyond, the required Feynman paths exceed Summit-node memory and make computation impractical.Source: B. Feynman simulator · p. 46, Table VII · p. 46
  • Transforming suitable boundary fSim gates reduces their remaining bond dimension from 4 to 2, although the approximate identity lowers fidelity to about 95%.Subsequent index cuts decompose contractions into simpler independently computed paths, whose results are summed.Source: B. Feynman simulator · p. 47
  • Feynman simulators scale exponentially with circuit depth, whereas SFA is expected to lead for supremacy circuits with large qubit and cycle dimensions when sample sizes are large.This expectation reflects Feynman simulation’s linear sample-size dependence, absent for SFA, and its difficulty at 16 cycles and beyond.Source: B. Feynman simulator · p. 49

C. Supercomputer Schr¨odinger simulator · D. Simulation of random circuit sampling with a target fidelity · 1. Optimality of the Schmidt decomposition for gates embedded in a random circuit

The supplementary sections describe supercomputer Schrödinger simulations, a low-fidelity classical sampling method with cost proportional to F_XEB, and the optimality of Schmidt decompositions for gates embedded in random circuits. They also characterize simulator limitations and explain why the resulting speedup is close to linear in F_XEB for the gates studied.

C. Supercomputer Schr¨odinger simulator

  • JUQCS-E computes the full double-precision output distribution, its cumulative distribution, and samples bitstrings, while also supporting probability calculations for a specified set of bitstrings.The simulator defines p_U(j) over D = 2^n output strings and can save probabilities for all strings in a user-specified set Q.Source: C. Supercomputer Schr¨odinger simulator · p. 49
  • JUQCS-A is an approximate simulator without a general guarantee that p_A(j) approximates p_U(j), and computing its cumulative distribution for random states requires careful high-precision summation.The required sampling feature also reduces the maximum simulable qubit count by three, while the simulations reported here are limited by JUQCS-E’s memory requirements.Source: C. Supercomputer Schr¨odinger simulator · p. 49
  • The simulations support Porter–Thomas behavior for both JUQCS-E and JUQCS-A, but increasing α_A,U deviations indicate that JUQCS-A produces a random state different from JUQCS-E.The discrepancy is consistent with JUQCS-A storing coefficients using two single-byte numbers rather than JUQCS-E’s double-precision floating-point coefficients.Source: C. Supercomputer Schr¨odinger simulator · p. 50
  • Experimental full-XEB estimates α_M,U and bα_M,U are close to fidelity estimates from the probabilistic model, patch XEB, and elided XEB.The passage states that α_X,U and bα_X,U for X = A, M, C are mutually consistent, with the experimental comparison shown in Fig. 4(a) of the main text.Source: C. Supercomputer Schr¨odinger simulator · p. 50

D. Simulation of random circuit sampling with a target fidelity

  • Low-fidelity approximate sampling can be simulated with classical computational cost proportional to F_XEB by retaining selected Feynman paths from Schmidt-decomposed gates.The approach assumes paths produce orthogonal output states; the section argues that Schmidt decomposition maximizes retained fidelity for a given fraction of paths, while Sec. XI argues the scaling is complexity-theoretically optimal.Source: D. Simulation of random circuit… · p. 50

1. Optimality of the Schmidt decomposition for gates embedded in a random circuit

  • Replacing a two-qubit gate embedded in a sufficiently scrambling random circuit by a product operator reduces to optimizing the gate as a standalone operator.The argument assumes the gate lies sufficiently in the middle of the computation that the preceding two-qubit reduced state is maximally mixed; for sufficiently large depth, the correction term can be ignored because ε ≤ (4/5)D in one dimension [82, 83].Source: §1 · pp. 51–52
  • The optimal rank-one replacement uses the leading operator-Schmidt components, achieving fidelity λ1 with M_a = R_a,1 and N_b = S_b,1.For Schmidt rank k, the optimal replacement is obtained by retaining the leading Schmidt terms.Source: §1 · p. 52
  • For the fSim gates considered, |δθ| is approximately 0.05 radians on average, limiting the potential low-fidelity sampling speedup to less than an order of magnitude.The deviation from θ ≈ π/2 determines the relevant Schmidt-spectrum imbalance and therefore the exploitable runtime speedup.Source: Figure S46 · p. 52

2. Classical speedup for imbalanced gates · 3. Verifiable and supremacy circuits · E. Treewidth upper bounds and variable elimination algorithms

The supplementary analysis finds that typical Schmidt-coefficient imbalance yields only modest practical classical speedups, while fused gate structures can substantially accelerate verifiable circuits but are mitigated in supremacy circuits. A projected-variable elimination heuristic reduces contraction widths, yet sampling Sycamore supremacy circuits at m = 16 and beyond remains out of reach under optimistic assumptions.

2. Classical speedup for imbalanced gates

  • For g = 35 gates, typical Schmidt imbalance gives an upper-bound speedup of 25.4, but the practical speedup at fidelities around 0.1% or higher is far smaller.The bound follows from a geometric-mean largest Schmidt coefficient of about 1.047, while only an exponentially small fraction of paths have weights near 25.4.Source: §2 · p. 53
  • At m = 20 with g = 35 decomposed gates and fidelity F ≈0.2%, the estimated speedup from imbalance is well below an order of magnitude for |δθ| ≈0.05 radians.The estimate is obtained by sorting path weights and retaining enough largest-weight paths to reach the target fidelity.Source: §2 · p. 53

3. Verifiable and supremacy circuits

  • Fusing wedge sequences reduces four separately decomposed two-qubit gates from 4^2 paths to 4 paths, giving a factor-of-4 speedup per wedge across a circuit cut.Verifiable circuits contain many wedges and support full XEB through depth m = 14, whereas supremacy circuits mitigate such structures.Source: §3 · p. 54
  • The DCD sequence offers a factor-of-4 speedup, and its two occurrences at m = 20 imply a total factor-of-16 speedup that was not included in reported timings.Beyond such short sequences, useful fusion requires groups of more than two cycles whose large unitaries are impractical to build explicitly.Source: §3 · p. 54

E. Treewidth upper bounds and variable elimination algorithms

  • Variable elimination maps circuit amplitudes to graph contractions, with optimal complexity exponential in treewidth; QuickBB supplies heuristic orderings because exact treewidth is NP-hard.Projecting variables creates 2^p independently contractable subgraphs, and the heuristic repeatedly chooses projections minimizing estimated contraction cost before a final QuickBB pass.Source: E. Treewidth upper bounds and variable… · p. 54
  • The projection procedure reaches contraction width 28 or below for Sycamore after projecting 8–63 variables, depending on circuit depth, and matches Bristlecone widths of 28 and 26.The Bristlecone results require 10 projections at depth (1+32+1) and 22 projections at depth (1+40+1), respectively.Source: E. Treewidth upper bounds and variable… · p. 55
  • Sampling Sycamore supremacy circuits at m = 16 and beyond is out of reach for projected-variable elimination, although the method speeds up verifiable-circuit simulation at m = 16.The estimates assume fast sampling applies; without it, estimated times increase by about an order of magnitude.Source: E. Treewidth upper bounds and variable… · pp. 55–56
  • Sycamore’s fSim structure simplifies its graphical model to two variables by representing cphase and logical SWAP explicitly, lowering complexity relative to arbitrary two-qubit gates.The runtime estimates are optimistic because they assume fast sampling is applicable to the heuristic variable-elimination algorithm.Source: E. Treewidth upper bounds and variable… · pp. 55–56

F. Computational cost estimation for the sampling task … H. Energy advantage for quantum computing

Classical simulation of the hardest 53-qubit, 20-cycle circuits is estimated to require 1.6 × 10^14 core hours at 0.002 fidelity and cost $3.1 trillion, while the quantum processor uses roughly seven orders of magnitude less energy for the same computation. Runtime and memory estimates depend exponentially on circuit width and depth and rely on optimistic assumptions, whereas the quantum apparatus consumes approximately 26 kW largely independently of circuit depth.

F. Computational cost estimation for the sampling task

  • 1.6 × 10^14 core hours at 0.002 fidelity and $3.1 trillion are estimated for simulating a 53-qubit, 20-cycle circuit, with perfect-fidelity costs extrapolated higher.The estimate uses 1000 machines, 430 qsimh runs, and an average job time of 246 seconds; the authors regard these costs and times as lower bounds.Source: F. Computational cost estimation for… · p. 56, Figure S50 · p. 56

1. Runtime scaling formulas

  • Runtime scaling is modeled as SA · mn · 2^n, while SFA scales with patch-state simulation and the exponentially increasing number of cross-gate paths.SFA is embarrassingly parallelizable; for supremacy layouts, cross-gates scale with circuit depth and approximately √n, while fused wedges reduce path growth in verifiable circuits.Source: §1 · p. 57

2. Assumptions and corrections

  • The runtime predictions are rough because SA assumes ideal scaling to 1M cores, wave-function storage beyond 49 qubits is hypothetical, and finite-size effects can shift estimates by around an order of magnitude.SFA’s amortized time per path is treated as approximately depth-independent, and separate fitted constants are used for supremacy and verifiable circuits.Source: §2 · pp. 57–58

3. Fitting constants

  • The fitted 1M-core estimates use a 0.1-hour SA runtime at n = 43 and m = 14, and SFA reference runtimes of 5 hours for verifiable and 4 years for supremacy circuits at n = 53 and m = 14.These fits determine the constants used for contour plots of runtime versus circuit width and depth.Source: §3 · pp. 58–59

4. Memory usage scaling

  • Using 2-byte complex-number encoding, SA requires 2^n × 2 bytes for the full wave function, whereas SFA stores two n/2-qubit patch states per path.These are lower-bound memory estimates; single- and double-precision representations require factors of 4 and 8 more memory, respectively.Source: §4 · p. 59

H. Energy advantage for quantum computing

  • The energy cost of qFlex simulation grows exponentially with circuit depth, while superconducting-processor energy use is dominated by refrigeration and supporting electronics.The refrigerator consumes approximately 10 kW directly plus 10 kW or more for chilled-water cooling, and supporting electronics consume nearly 3 kW.Source: H. Energy advantage for quantum… · p. 59
  • 26 kW of average apparatus power yields approximately 5×10^6 J, or 1 kWh, to acquire 1M samples in 200 s, roughly seven orders of magnitude below qFlex’s energy use on Summit.The processor’s power is nearly unchanged between idle and running states and is independent of circuit depth.Source: H. Energy advantage for quantum… · p. 59
  • The quantum processor’s data-acquisition duty cycle can be as low as 2% because control-hardware communications dominate acquisition time, leaving substantial room for further energy-efficiency gains.This limitation concerns the current apparatus rather than circuit-depth-dependent power consumption.Source: H. Energy advantage for quantum… · p. 59

XI. COMPLEXITY-THEORETIC FOUNDATION OF THE EXPERIMENT … C. Computational hardness of unbiased-noise sampling

The section defines quantum supremacy through a precise computational task and a scalable quantum–classical runtime separation, then formulates unbiased-noise circuit sampling and proves complexity-theoretic hardness under explicit assumptions. Its theorem relates noisy-sampling cost to ideal computation cost, while clarifying asymptotic, finite-size, and noise-model limitations.

XI. COMPLEXITY-THEORETIC FOUNDATION OF THE EXPERIMENT

  • Quantum supremacy requires a well-defined computational task and a quantum–classical runtime separation that grows with problem size.Random-circuit sampling is presented as a candidate whose quantum scaling can remain polynomial while classical scaling becomes exponential at sufficient depth.Source: §XI · p. 59, §2 · p. 60

2. Programmable computational device

  • Because formal complexity results are asymptotic, near-term claims require comparison with highly optimized classical algorithms on state-of-the-art supercomputers.The classical benchmark is moving because algorithms and computing power improve over time; exact simulation costs are exponential in circuit treewidth [70].Source: §2 · p. 60

A. Error model

  • The hardness argument assumes global depolarizing noise with fidelity F, typically 10−2–10−3 experimentally, while the rest of the paper does not rely on this model.The model is used specifically to lower-bound noisy simulation cost by ideal computation cost.Source: §2 · pp. 60–61, A. Error model · p. 61

B. Definition of computational problem

  • Circuit Sampling samples from pU(x) := |⟨x|U|0⟩|2 for a described circuit, whereas Random Circuit Sampling samples from the same distribution for most circuits in an ensemble.Assuming the polynomial hierarchy does not collapse, Circuit Sampling cannot be solved classically efficiently in n for several circuit classes, including short depth circuits.Source: B. Definition of computational problem · p. 61
  • Because achieved ε is far from zero, the section uses Unbiased-Noise F-Approximate Random Circuit Sampling rather than prior near-ideal approximate-sampling results.The experiment is interpreted as solving b-Heavy Output Generation with b = 1 + F, although direct verification of high-entropy sampling is impractical [27, 30].Source: B. Definition of computational problem · pp. 61–62

C. Computational hardness of unbiased-noise sampling

  • If classical sampling of rU,F takes time T, Theorem 1 yields an AM protocol with runtime LT + 2Lm for deciding the stated problem.The result is used with L = c/F, making the reduction cost scale linearly with 1/F.Source: C. Computational hardness of… · p. 62
  • The theorem shows unbiased-noise sampling is as hard as estimating a transition probability up to a linear reduction in F, but does not itself prove an additive-error lower bound for that estimation task.For random circuits, estimating |⟨0|U|0⟩|2 is #P-hard under the stated assumptions [92].Source: C. Computational hardness of… · p. 62
  • Under SETH, some n-qubit circuit distributions rU,F require time F2^(1−o(1))n to sample, unless SETH is false.This combines finite-size hardness for estimating transition probabilities with Theorem 1.Source: C. Computational hardness of… · p. 62

D. Proof of Theorem 1 · ERRATUM

The proof shows that efficient classical sampling from rU,F yields an AM protocol for estimating |⟨0|U|0⟩|2 by approximate counting and noise subtraction. The erratum clarifies that Figure 4 error bars show statistical uncertainty only, while both statistical and systematic uncertainties were included in the analysis.

D. Proof of Theorem 1

  • Efficient sampling from rU,F in time T implies an AM protocol estimating |⟨0|U|0⟩|2 with classical verification time of order LT.The reduction uses rU,F(0)=F|⟨0|U|0⟩|2+(1−F)/2^n and subtracts unbiased noise.Source: D. Proof of Theorem 1 · pp. 62–63
  • Lemma 1 distinguishes rU,F(0)≥θ(1+2/L) from rU,F(0)≤θ(1−2/L) using an AM[LT+2Lm] protocol.The protocol uses pairwise-independent linear hashing to test whether Merlin’s witness is consistent with the sampled output distribution.Source: D. Proof of Theorem 1 · p. 63
  • For a YES instance with rU,F(0) ≥ θ(1+2/L), choosing s yields, with high probability, between (1/2)M^L/2^s and 2M^L/2^s solutions; since the lower bound is at least 1, Merlin can provide w making Arthur accept.Source: D. Proof of Theorem 1 · p. 63
  • For NO instances, Lemma 2 implies no witness can satisfy the acceptance conditions, so Arthur accepts only with small probability.The bound M=2^m rU,F(0)≤2^mθ(1−2/L) prevents a solution to the hashed constraint.Source: D. Proof of Theorem 1 · p. 63
  • Setting θ=Fλ+(1−F)/2^n converts Lemma 1 into the AM protocol for deciding the theorem’s bounds on |⟨0|U|0⟩|2.This completes the reduction from estimating the noisy probability rU,F(0) to estimating the ideal output probability.Source: D. Proof of Theorem 1 · p. 63

ERRATUM

  • Figure 4’s error bars represent statistical uncertainty, not both statistical and systematic uncertainty.Figure S41 compares the two uncertainty types; both were included in the analysis, so the conclusions remain intact.Source: ERRATUM · p. 64

Related papers

Loading 1910.11333v2…