Quantifying Quantum Computational Advantage on a Processor of Ultracold Atoms

Nonequilibrium dynamics of quantum many-body systems is challenging for classical computing, providing opportunities for demonstrating practical quantum computational advantage with analog quantum simulators. Owing to the intimate connection with a random matrix ensemble, it is proposed to be classically intractable to sample the driven thermalized many-body states of a Bose-Hubbard system and further extract multipoint correlations from the output strings for characterizing quantum systems. Here, leveraging dedicated precise manipulations and atom-number-resolved detection through a quantum gas microscope with bichromatic superlattices, we perform sampling of the driven Hubbard chains and two-leg ladders in the thermalized phase involving up to 64 sites with 20 atoms, yielding a Hilbert space dimension of 10 19 and outpacing the most powerful supercomputer in terms of sampling rate by 3 orders of magnitude. The volume law scaling of the Rényi entanglement entropy in the thermalized phase is observed, which hinders efficient classical simulation for large systems. We employ the Bayesian tests to verify that our prepared systems operate in the driven thermalized phase. Multipoint correlations of up to 14th-order extracted from the experimental samples offer clear distinctions between the thermalized and many-body-localized phases, where classical computations such as tensor network fail to give accurate and faithful predictions within a reasonable time cost. Our work demonstrates the sampling of an interacting chaotic system performed on a quantum processor of ultracold atoms and opens the door of utilizable quantum computational advantage in simulating Floquet dynamics of many-body systems.