Thermalization and Criticality on an Analog-Digital Quantum Simulator, Part 3: verification and computational complexity

Tensor networks (TNs) provide a powerful framework both for efficient simulation of quantum states with low-to-moderate entanglement and for exact contraction of quantum circuits. Thus TNs can be used to simulate short-time dynamics of even very large quantum systems, and they are a key competitor to overcome for any claim of quantum advantage. We use TNs to verify the high-fidelity operation of Google’s analog-digital quantum simulator at the full-chip scale of 69 qubits, well beyond the reach of state vector simulation. We also estimate the cost of TN simulations for the full time evolution on 69 qubits, concluding that the quantum experiments are indeed beyond the reach of any known classical algorithm.

To verify the fidelity for systems of 47 and 69 qubits, we simulate the short-time dynamics of the chip with matrix product state (MPS) and use the resulting states as the classical reference for cross-entropy benchmarking (XEB) of experimental measurements. The results are consistent with extrapolation of experimental fidelity from the smaller system sizes where it can be rigorously estimated.

To confirm that the experiments are beyond classical, we take two approaches to lower-bounding the classical complexity. First, we show that compressing the Hamiltonian dynamics into a sequence of projected entangled pair operators (PEPOs), followed by exact tensor network contraction, would take over 1 million years of computation time on the world’s most powerful supercomputer, Frontier, even taking into account the finite fidelity in the experiment. Second, we show that with MPS time evolution simulations, to reach the same fidelity as the experiment for 69 qubits would require storing individual tensors that exceed the entire hard disk of Frontier, and that faithfully sampling a single bitstring from the time-evolved state would take over 100 years on that cluster.