  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.
