Provable quantum advantage in Bell-type nonlocal games with the cyclic cluster state

We propose two Bell-type nonlocal games and perform proof-of-principle demonstrations on a trapped-ion quantum computer. These games can be used to prove quantum computational advantage in an objective and hardware-agnostic manner, as well as offer a practical and scalable set of quantitative benchmarks for quantum computers in the pre-fault-tolerant regime. The experimental result surpasses the conventional depth-0 classical bounds by a significant margin for the cubic Boolean function games, and is on the cusp of demonstrating advantage against the more difficult depth-1 classical bounds in the stabilizer submeasurement games.