PaperlayerView exact revision on arXiv

Source-linked AI summary

Phase transition in Random Circuit Sampling

A. Morvan, B. Villalonga, X. Mi, S. Mandrà, A. Bengtsson, P. V. Klimov, Z. Chen, S. Hong, C. Erickson, I. K. Drozdov, J. Chau, G. Laun, R. Movassagh, A. Asfaw, L. T. A. N. Brandão, R. Peralta, D. Abanin, R. Acharya, R. Allen, T. I. Andersen, K. Anderson, M. Ansmann, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, A. Bilmes, G. Bortoli, A. Bourassa, J. Bovaird, L. Brill, M. Broughton, B. B. Buckley, D. A. Buell, T. Burger, B. Burkett, N. Bushnell, J. Campero, H. S. Chang, B. Chiaro, D. Chik, C. Chou, J. Cogan, R. Collins, P. Conner, W. Courtney, A. L. Crook, B. Curtin, D. M. Debroy, A. Del Toro Barba, S. Demura, A. Di Paolo, A. Dunsworth, L. Faoro, E. Farhi, R. Fatemi, V. S. Ferreira, L. Flores Burgos, E. Forati, A. G. Fowler, B. Foxen, G. Garcia, E. Genois, W. Giang, C. Gidney, D. Gilboa, M. Giustina, R. Gosula, A. Grajales Dau, J. A. Gross, S. Habegger, M. C. Hamilton, M. Hansen, M. P. Harrigan, S. D. Harrington, P. Heu, M. R. Hoffmann, T. Huang, A. Huff, W. J. Huggins, L. B. Ioffe, S. V. Isakov, J. Iveland, E. Jeffrey, Z. Jiang, C. Jones, P. Juhas, D. Kafri, T. Khattar, M. Khezri, M. Kieferová, S. Kim, A. Kitaev, A. R. Klots, A. N. Korotkov, F. Kostritsa, J. M. Kreikebaum, D. Landhuis, P. Laptev, K. -M. Lau, L. Laws, J. Lee, K. W. Lee, Y. D. Lensky, B. J. Lester, A. T. Lill, W. Liu, W. P. Livingston, A. Locharla, F. D. Malone, O. Martin, S. Martin, J. R. McClean, M. McEwen, K. C. Miao, A. Mieszala, S. Montazeri, W. Mruczkiewicz, O. Naaman, M. Neeley, C. Neill, A. Nersisyan, M. Newman, J. H. Ng, A. Nguyen, M. Nguyen, M. Yuezhen Niu, T. E. O'Brien, S. Omonije, A. Opremcak, A. Petukhov, R. Potter, L. P. Pryadko, C. Quintana, D. M. Rhodes, E. Rosenberg, C. Rocque, P. Roushan, N. C. Rubin, N. Saei, D. Sank, K. Sankaragomathi, K. J. Satzinger, H. F. Schurkus, C. Schuster, M. J. Shearn, A. Shorter, N. Shutty, V. Shvarts, V. Sivak, J. Skruzny, W. C. Smith, R. D. Somma, G. Sterling, D. Strain, M. Szalay, D. Thor, A. Torres, G. Vidal, C. Vollgraff Heidweiller, T. White, B. W. K. Woo, C. Xing, Z. J. Yao, P. Yeh, J. Yoo, G. Young, A. Zalcman, Y. Zhang, N. Zhu, N. Zobrist, E. G. Rieffel, R. Biswas, R. Babbush, D. Bacon, J. Hilton, E. Lucero, H. Neven, A. Megrant, J. Kelly, I. Aleiner, V. Smelyanskiy, K. Kechedzhi, Y. Chen, S. Boixo

arXiv:2304.11119v2quant-ph

TL;DR

The paper addresses how noise affects the computational complexity and spoofability of Random Circuit Sampling. It combines experiments, XEB-based finite-size studies, statistical modeling, weak-link analysis, and tensor-network simulation to characterize noise-induced transitions. It reports a computationally complex phase and discusses limits on practical verification.

  • Problem

    The paper examines how noise can make Random Circuit Sampling outputs spoofable by classical computation, an issue tied to the cost of verifying large noisy circuits.

  • Method

    The authors combine noisy random-circuit theory, XEB analysis, weak-link modeling, and tensor-network contraction methods to study phase boundaries and simulation cost.

  • Results

    The work establishes a noise-induced transition and gives a lower bound below which spoofing algorithms cannot match experimental XEB.

  • Takeaways & Limitations

    Below the supported error boundary, spoofing algorithms cannot match the experimental XEB, while practical verification remains unresolved for the largest circuits.

  • Takeaways & Limitations

    The 70-qubit circuits are too large to verify with XEB, and the paper leaves efficient verification protocols unresolved.

Abstract

from arXiv · show

Undesired coupling to the surrounding environment destroys long-range correlations on quantum processors and hinders the coherent evolution in the nominally available computational space. This incoherent noise is an outstanding challenge to fully leverage the computation power of near-term quantum processors. It has been shown that benchmarking Random Circuit Sampling (RCS) with Cross-Entropy Benchmarking (XEB) can provide a reliable estimate of the effective size of the Hilbert space coherently available. The extent to which the presence of noise can trivialize the outputs of a given quantum algorithm, i.e. making it spoofable by a classical computation, is an unanswered question. Here, by implementing an RCS algorithm we demonstrate experimentally that there are two phase transitions observable with XEB, which we explain theoretically with a statistical model. The first is a dynamical transition as a function of the number of cycles and is the continuation of the anti-concentration point in the noiseless case. The second is a quantum phase transition controlled by the error per cycle; to identify it analytically and experimentally, we create a weak link model which allows varying the strength of noise versus coherent evolution. Furthermore, by presenting an RCS experiment with 67 qubits at 32 cycles, we demonstrate that the computational cost of our experiment is beyond the capabilities of existing classical supercomputers, even when accounting for the inevitable presence of noise. Our experimental and theoretical work establishes the existence of transitions to a stable computationally complex phase that is reachable with current quantum processors.

Supplement to Phase transition in Random Circuit Sampling

This supplement is identified as “Supplement to Phase transition in Random Circuit Sampling,” attributed to Google Quantum AI and Collaborators and dated 22 December 2023.

  • The supplement is attributed to Google Quantum AI and Collaborators.
  • The version is identified as arXiv:2304.11119v2, dated 22 Dec 2023.

Appendix A: General RCS with XEB theory

This appendix develops a general XEB theory using Porter–Thomas statistics and a noise model, then establishes when XEB estimates fidelity and when output probabilities reach the Porter–Thomas regime.

  • For n qubits, the Hilbert-space dimension is D = 2^n, and Haar-random output probabilities have Porter–Thomas marginals.
  • Noise is modeled through ρ = F|ψ⟩⟨ψ| + (1 − F)Ξ, where F is fidelity and Ξ describes the noise contribution.
  • XEB assigns a smooth O(1) function f(p_j) to sampled bitstrings; linear XEB uses Dp_j − 1, while log XEB uses log(Dp_j) plus Euler’s constant.
  • Under the stated independence and normalization assumptions, averaged noise behaves like a totally depolarizing channel, supporting XEB estimators for linear and log XEB.
  • Numerically, probabilities follow Porter–Thomas only when linear XEB is exponentially close to its limit, but XEB can estimate fidelity earlier without exponential precision.

1. Gate Optimization

The gate-optimization program reduces leakage and cycle errors in iSWAP-like operations, then addresses system-size discrepancies caused by z-tails and frequency detunings.

  • Off-resonant |11⟩↔|02⟩ and |20⟩ oscillations cause leakage outside the computational space during two-qubit gates.
  • Increasing the coupler-pulse rise time makes these transitions adiabatic and suppresses leakage, especially relative to short-rise-time pulses.
  • 1.01 × 10^-2 to 8.4 × 10^-3: pulse-shape optimization reduces the median two-qubit cycle Pauli error in parallel two-qubit XEB.
  • Over 30%: measured four-qubit cycle errors exceed predictions from two-qubit XEB, with z-tails identified as the source of the discrepancy.
  • 4 ns: padding between two-qubit and single-qubit gates reduces the measured–predicted four-qubit error difference to nearly zero.
  • 24%: measured 16-qubit cycle errors initially exceed predictions, but frequency re-optimization and halved detunings restore close agreement.

2. Benchmarking of gates and readout

The benchmarking procedure combines randomized benchmarking for single-qubit errors with parallel XEB measurements for two-qubit dressed errors and iSWAP-like gate angles.

  • Single-qubit error is calibrated with randomized benchmarking using π/2 pulses across logarithmically spaced depths.
  • Two-qubit dressed error is measured through parallel XEB after gate-phase optimization.
  • Parallel XEB measurements find the iSWAP-like gate’s c-phase closer to π/10 than π/6 in the cited earlier work.

1. RCS experiment on a 70 qubits device: SYC-70

The SYC-70 experiment benchmarks circuit elements and examines how phase matching and injected single-qubit noise affect RCS characterization. The device characterization includes gate, readout, coherence, and error-distribution measurements.

  • Device benchmarking: Device benchmarking measures single-qubit Pauli errors, readout errors, two-qubit Pauli errors, T1, T2 echo times, and error distributions.The benchmarking panels use Randomized Benchmarking, random-bitstring readout tests, parallel two-qubit XEB, and cumulative distributions.
  • Phase matching: Phase matching compiles extra fSim-associated Z rotations into the pulse sequence, whereas unphase-matched circuits account for them in simulation.The extra rotations arise from qubit detuning and time-dependent interaction phases.
  • Injected noise: Random rotations are added after each single-qubit layer to artificially increase the single-qubit error rate.The added gates vary between layers and circuits to avoid correlated noise, and they are excluded from the classical simulation.

3. Noise phase transition extended data

The extended data examines noisy RCS through weak-link and two-dimensional experiments, using XEB to track fidelity, noise sensitivity, and limiting behavior. The results include decay, saturation, and a weak-link criterion for when XEB estimates circuit fidelity.

  • Local noise: Adding noise on one side of a weak-link chain initially lowers linear XEB, but sufficiently strong noise makes XEB insensitive to further added noise.The plateau occurs when the contributions associated with the noisy side become negligible.
  • Weak-link model: In the weak-link model, XEB is poorly predicted in strong noise but agrees with component fidelity at sufficient depth in weak noise.The XEB ratio is also reported as a diagnostic across the measured error-per-cycle range.
  • Limiting behavior: In the noisy long-depth limit, the vacuum configuration is the only remaining configuration and yields XEB=0.In contrast, noise-free long-time dynamics approach the Porter-Thomas limit with XEB approximately 1.
  • Weak-link model: The weak-link analysis assumes each half independently reaches a thermal or Porter-Thomas state before the weak-link gate acts.Four population configurations represent vacuum and thermal states of the two halves, and the weak-link update includes an iSWAP-dependent factor.
  • Fidelity estimation: The weak-link criterion identifies when XEB serves as a good fidelity estimate for the chain.This criterion follows from the population-dynamics treatment of the four weak-link configurations.

4. Numerical analysis of the phase transitions

Numerical population-dynamics simulations resolve finite-size scaling near both the dynamical and noise-induced transitions. They show distinct order-parameter limits and compare transition locations across noise models, sizes, geometries, and gate ensembles.

  • Numerical method: Population dynamics predicts noisy linear XEB while using memory exponential in qubit number and being quadratically more efficient than direct noisy-density-matrix simulation.The simulations evolve the full probability vector through transfer matrices and use a simplified single-qubit noise model.
  • Dynamical transition: At fixed error rate ϵ = 0.01, linear XEB changes from growth to decay with depth, with a transition point τ ≈1 that is approximately size independent.The correction from the per-cycle error scales as ϵn ∼O(n^0).
  • Noise-induced transition: The noise-induced order parameter converges to a constant at low error and to zero at sufficiently large error per cycle.The reported range is 0 ≤ϵn ≤1.34 for the 18-qubit chain.
  • Transition identification: For weak-link frequency 1/T < 1 in 1D, crossings of the order parameter across depths provide a less data-intensive way to identify the noise-induced transition.This crossing procedure was used for the experimental transition estimate.
  • Gate-ensemble comparison: The transition point is not significantly affected by the single-qubit gate ensemble in the compared 16-qubit chain and 4 × 4 geometries.The comparison includes the discrete experimental gate set and uniformly random single-qubit gates.

1. XEB phase diagram in 1D

The 1D XEB phase diagram contains a dynamical transition at anti-concentration and a separate noise-induced transition between weak- and strong-noise regimes. Statistical-mechanics analysis gives different asymptotic XEB behaviors on either side of these lines.

  • Population-dynamics analysis: The analysis represents circuit evolution with population dynamics over configurations whose initial populations are equal.The transfer-matrix treatment solves the large-system behavior as a function of system size and depth.
  • Dynamical transition: The dynamical transition at α = 1 is a phase-transition line because the asymptotic XEB expressions change from algebraic to logarithmic behavior.The noise-free expression has no singularity at α = 1.
  • Noise-induced transition: The noise-induced phase-transition line separates weak and strong noise regimes in the thermodynamic limit.The analysis defines the line through the depth and noise scaling of XEB.
  • Strong-noise regime: In the strong-noise regime f > fc, XEB is much larger than the circuit fidelity.This distinguishes the strong-noise asymptotic behavior from the weak-noise fidelity-estimation regime.

2. XEB phase diagram in 2D and higher dimensions

In two and higher dimensions, XEB exhibits noise-induced phase transitions whose location depends on finite-depth dynamics, boundaries, and coupling between subsystems. The weak-link model connects these transitions to whether correlations remain global or become locally representable and spoofable.

  • Higher-dimensional dynamics: The higher-dimensional update equation generalizes the one-dimensional population dynamics using nearest-neighbor couplings on a D-dimensional lattice.The interaction term accounts for segment differences, neighbor double-counting, and iSWAP application frequency.
  • Noise-induced transition: The noise-induced phase transition terminates at α = 1, and its condition matches the one-dimensional case with a boundary.The weak and strong noise regimes have XEB values similar to those in one dimension.
  • Noise-induced transition: In the weak-noise regime f < fc(α), linear XEB equals circuit fidelity, whereas strong noise f > fc(α) makes local correlations dominate XEB.The weak-noise contribution comes from the thermal or Porter–Thomas state; the strong-noise contribution comes from local correlations above the vacuum.
  • Boundary effects: Boundary effects introduce a phase transition at α = 1 even without noise, unlike the one-dimensional case without boundaries.The transition results from competition between prefactor terms with different dependence on n.
  • Spoofing implications: Spoofing algorithms can omit entangling gates across a weak link, exploiting subsystem structure to produce XEB values that may exceed the noisy circuit’s value.For the weak-link model, this comparison distinguishes the spoofing threshold from the noise-induced phase-transition threshold.

2. Spoofing for general models

The paper analyzes how spoofing algorithms amplify XEB by approximating global states with subsystems and selecting high-probability bitstrings. Local-correlation contributions dominate the spoofing signal, but their depth-dependent decay bounds spoofing performance.

  • Spoofing mechanism: Finite-depth local correlations provide the dominant spoofing contribution outside the thermal or Porter–Thomas state.In the weak-link model, these contributions correspond to vacuum–thermal and thermal–vacuum configurations and decay exponentially with depth.
  • Post-processing: Post-processing changes only a multiplicative factor, not the exponential decay rate of spoofing performance.Splitting the system into more than two subsystems can increase the prefactor but worsens the approximation by ignoring inter-subsystem correlations.
  • Spoofing mechanism: Spoofing algorithms approximate the wavefunction and then sample or select bitstrings to maximize XEB without full exponential simulation.The two stages are wavefunction approximation followed by bitstring post-processing.
  • Bound and experiment: For d = 24, n = 70, and ln λ ≃ −1.95, the upper bound on spoofing XEB is below the experimental value, indicating unsuccessful spoofing.The decay rate λ is extracted from numerical simulations, while the reported bound uses the experiment’s depth and system size.
  • Alternative XEB: For large N ≫ 1, logarithmic XEB of spoofed bitstrings gives the same result as linear XEB.Logarithmic XEB is less sensitive to rare spikes in wavefunction amplitudes.

Appendix G: Simulation of random circuit sampling using tensor network contraction

Tensor-network contraction reduces the classical cost of RCS simulation through optimized contraction, slicing, sparsification, and reuse of intermediate computations. Approximate tensor methods remain limited by the bond dimension required to represent highly entangled states.

  • Exact contraction: Tensor-network contraction represents one- and two-qubit gates as rank-2 and rank-4 tensors and the input product state as rank-1 tensors.Contraction order strongly affects runtime and memory, with time complexity bounded by tensor-network treewidth.
  • Exact contraction: Slicing lowers memory requirements by projecting selected indices, at the cost of contracting exponentially many sliced networks.Later methods optimize contraction orderings, sliced indices, output sparsification, and reuse of computations.
  • Simulation estimates: The present optimizer estimates FLOP counts about two orders of magnitude below prior methods and a runtime of 2 days on one CPU.The estimate assumes a Google Cloud CPU with 12 TB of memory and 20% FLOP efficiency.
  • Approximate representations: Truncating across a bipartition limits fidelity because gates crossing the partition increase Schmidt rank, while fixed χ discards components of the entangled state.The best rank-χ approximation retains the largest χ Schmidt coefficients and is exact only when χ exceeds the Schmidt rank.
  • Approximate representations: Linear XEB remains a good fidelity estimator for these approximate representations, and the analysis identifies a sharp transition to typical entanglement.The paper supplies numerical and analytical bounds on χ required for a target fidelity.
  • Approximate representations: Approximate tensor representations require bond dimension χ much smaller than the half-system Hilbert-space dimension to remain practically useful.For 70 qubits and 24 cycles, achieving F ≈ 10^-4 requires χ of order 10^7, beyond practical implementations.

2. Fidelity bound for arbitrary states

The paper bounds fidelity for bipartite tensor approximations using singular-value structure and validates the bounds numerically. It also compares open and close simulation protocols, with close simulations achieving fidelity F = F1F2 but requiring multiple runs.

  • Arbitrary-state fidelity bounds: The fidelity of a Schmidt-decomposed approximation is bounded using the singular-value distribution of the bipartitioned state.For Haar-random states, the singular values follow the Marčenko–Pastur distribution, which determines the fidelity retained by bond dimension χ.
  • Arbitrary-state fidelity bounds: The numerical upper bound Fλ is compared with exact fidelity across Sycamore layouts, system sizes, depths, and bond dimensions χ.The bound is evaluated against exact numerical results for different circuit instances.
  • Open simulations: Open simulations repeatedly truncate evolved states, yielding final fidelity F = f1f2 · · · fk for random circuits.A variational procedure avoids explicitly forming intermediate states and singular values for large systems.
  • Close simulations: Close simulations use three circuit segments and produce amplitudes corresponding to fidelity F = F1F2.They can improve target fidelity over open simulations at the same χ, but require multiple runs to obtain enough bitstrings.
  • Close simulations: Close-simulation fidelity is tested at fixed χ = 8 against exact fidelity across circuits split into 8, 4, and 8 cycles.The comparison uses amplitudes sampled with the close protocol and averages over bitstrings.

4. XEB for approximate tensor representations

The paper explains when linear XEB estimates fidelity for approximate tensor representations, deriving the role of Haar-random singular vectors and identifying a small-bond-dimension limitation. Numerical results confirm the correspondence for close simulations.

  • Analytical argument: The paper derives why linear XEB remains a good fidelity estimator for approximate tensor representations at sufficiently large depth.The argument uses the tensor representation and averages over random states or circuits.
  • Analytical argument: At large depth, the left and right singular vectors of the approximate state are modeled as Haar-random states.The approximation treats the singular vectors as independent random states with Gaussian real and imaginary parts.
  • Limitation: For very small χ, including χ = 1, linear XEB overestimates the fidelity.The χ = 1 approximation is a product state, and its associated fidelity is very small.
  • Numerical validation: Numerical results confirm correspondence between exact fidelity and XEB for close simulations using approximate quantum states.The comparison is shown for fixed bond dimension χ = 8 and circuits divided into three sections of 8, 4, and 8 cycles.
  • Purity analysis: The reduced-purity analysis uses two replicas of the output state and a Markov-chain description over Pauli strings.The average reduced purity is the same for the corresponding Clifford and non-Clifford circuit ensembles.

6. Reduced purity and distribution of singular values

The paper uses reduced purity to track convergence toward Haar-like singular-value statistics and to bound tensor-network resources for close simulations. These analyses connect entanglement growth, fidelity targets, and classical cost.

  • Singular-value transition: Reduced purity is proposed as a witness for the sharp transition of singular values to their limiting distribution.The comparison uses the distance from the purity limit and the Kolmogorov-Smirnov p-value against the Haar distribution.
  • Purity growth: The depth required for reduced purity to become exponentially close to its limit increases with system size.The variance of the purity decreases exponentially.
  • Simulation bounds: The paper supplies analytical and numerical upper bounds on bond dimension as functions of qubit number and circuit depth.The bounds target a specified fidelity and remain valid for arbitrary depths and bond dimensions.
  • Simulation bounds: For F = 10^-4, the numerical bond-dimension bound is approximately 25 times the analytical bound for an equal bipartition.The required FLOPs scale as O(2^nχ) when the state is represented with two equal-size tensors.

b. Benchmark results

This section benchmarks Trevisan randomness extraction and discusses a more efficient HMAC-based alternative. The proven extractor can repeatedly produce statistically near-uniform bits when the input has sufficient min-entropy, but its implementation is slow.

  • Benchmark results: At input size 2^30, Trevisan extraction throughput is 8.4 bits/s for a fixed 4096-bit output.The benchmark used 64 threads; Python-to-C++ conversion took about 24 seconds at that input size.
  • Alternative construction: HMAC offers a more efficient but heuristic alternative to the theoretically proven Trevisan extractor.The HMAC construction requires a relatively large seed and addresses the limited output length of a single HMAC call.
  • Extractor construction: The extractor analysis combines two extractor outputs and recursively extends them to longer outputs.The stated construction preserves extractor guarantees while adjusting min-entropy and error parameters.
  • Extractor construction: Trevisan’s extractor can be repeatedly applied with fresh seeds to produce statistically near-uniform output when input min-entropy is sufficient.The construction extends the output by recursively combining extractor applications.
Loading 2304.11119v2…