Experimentally quantifying the boundary between classical and quantum advantage

Which is the better representation of some ideal quantum evolution, a classical computer using an approximate simulation algorithm, or a noisy quantum simulator? We experimentally test this question by producing maximum-entanglement entropy states with as many as 60 atoms using a Rydberg atom array with state-of-the-art fidelity, and compare against similarly state-of-the-art classical simulation algorithms. In this high-entanglement regime, neither the classical nor quantum device has perfect fidelity, but the classical algorithm's limited accuracy can be precisely controlled by varying the degree of classical resources employed. This allows us to define the equivalent classical cost to perform evolution with the same fidelity as the quantum experiment. We show that with incremental experimental improvements, the classical cost required to "beat" the quantum device increases by orders-of-magnitude, and even in the present day we find the quantum experiment can outperform the classical computer in finite sampling from these high-entanglement states. Our results include advances in classically simulating quantum evolution, benchmarking quantum devices in the naively beyond-classical regime, and quantitatively understanding the boundary between classical and quantum advantage.