Phase transitions in random circuit sampling

Abstract

Undesired coupling to the surrounding environment destroys long-range correlations in quantum processors and hinders coherent evolution in the nominally available computational space. This noise is an outstanding challenge when leveraging the computation power of near-term quantum processors¹. It has been shown that benchmarking random circuit sampling with cross-entropy benchmarking can provide an estimate of the effective size of the Hilbert space coherently available^2-8. Nevertheless, quantum algorithms' outputs can be trivialized by noise, making them susceptible to classical computation spoofing. Here, by implementing an algorithm for random circuit sampling, we demonstrate experimentally that two phase transitions are observable with cross-entropy benchmarking, 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 us to vary the strength of the noise versus coherent evolution. Furthermore, by presenting a random circuit sampling experiment in the weak-noise phase with 67 qubits at 32 cycles, we demonstrate that the computational cost of our experiment is beyond the capabilities of existing classical supercomputers. Our experimental and theoretical work establishes the existence of transitions to a stable, computationally complex phase that is reachable with current quantum processors.

Fig. 1. Phase transitions in RCS.

One phase transition goes between a concentrated output distribution of bit strings from RCS at a low number of cycles to a broad or anti-concentrated distribution. There is a second phase transition in a noisy system. A strong-enough error per cycle induces a phase transition from a regime where correlations extend to the full system to a regime where the system may be approximately represented by the product of several uncorrelated subsystems.

Fig. 2. Phase transitions in the linear cross-entropy.

a–d, At a low number of cycles, XEB grows with the size of the system. In a noiseless device, XEB will converge to 1 with the number of cycles. In the presence of noise, XEB becomes an estimator of the system fidelity. a,b, We experimentally observed a dynamical phase transition at a fixed number of cycles between these two regimes in one (a) and two dimensions (b). The random circuits have Haar random single-qubit gates and an iSWAP-like gate as an entangler. c,d, We experimentally probed a noise-induced phase transition using a weak-link model (see the main text), where the weak link is applied every 12 cycles (discrete gate set; see main text). c, The two different regimes. In the weak-noise regime, XEB converges to the fidelity, whereas in the strong-noise regime, XEB remains higher than predicted by the digital error model. d, We induced errors to scan the transition from one regime to the other.

Fig. 3. Noise-induced phase transitions.

a–c, Experimental noise-induced phase transitions as a function of the error per cycle for several periods T of the weak-link model (discrete gate set) (T = 8 (a), T = 12 (b) and T = 18 (c)). As T increases, the critical value of noise or error per cycle becomes lower. d, Phase diagram of the transition with analytical, numerical and experimental data. The experimental data were extracted from the crossing of the largest number of cycles scanned. e,f, Experimental transitions in two dimensions with different patterns: staggered ACBD (e) and unstaggered EGFH (f; discrete gate set). g, Numerical phase diagram of the two-dimensional phase transition. We show the critical point for different sizes and patterns. The qubits are arranged as shown in the inset of e. For fixed size, we increased the number of bridges (such as the red coupler in e) until all bridges were applied (four and six for the 4 × 4 and 4 × 6 systems, respectively), denoted as links per four cycles in g. For all the patterns, we delimited a lower bound on the critical error rate of 0.47 errors per cycle to separate the region of strong noise where XEB failed to characterize the underlying fidelity and where global correlations were subdominant. The experimental results shown in Fig. 4 (SYC-67) and in Supplementary Information section C1 (SYC-70) are represented by red stars, which are well within the weak-noise regime.

Fig. 4. Demonstration of a classically intractable computation.

a, Verification of RCS fidelity with logarithmic XEB. The full device is divided into two (green) or three (blue) patches to estimate the XEB fidelity for a modest computational cost. We used the discrete gate set of single-qubit gates chosen randomly from Z^pX^1/2Z^−p with p ∈ {−1, −3/4, −1/2, …, 3/4}. For each number of cycles, 20 circuit instances were sampled with 100,000 shots each. The solid lines indicate the XEB estimated from the digital error model. b, Verification of RCS fidelity with Loschmidt echo. The inversion was done by reversing the circuit and inserting single-qubit gates. In this case, the Loschmidt echo number of cycles doubled. c, Time complexity estimated as a function of the number of qubits and the number of cycles for a set of circuits. As a working definition of time complexity, we used the number of FLOPs needed to compute the probability of a single bit string under no memory constraints. The solid line indicates the depth at which correlations spread to the full device and the FLOPs with depth go from exponential to polynomial. d, Evolution of the time complexity of the RCS experiments. The dashed line represents doubly exponential growth as a guide for the eye.