  We present a formalism that captures the process of proving quantum
superiority to skeptics as an interactive game between two agents, supervised
by a referee. Bob, is sampling from a classical distribution on a quantum
device that is supposed to demonstrate a quantum advantage. The other player,
the skeptical Alice, is then allowed to propose mock distributions supposed to
reproduce Bob's device's statistics. He then needs to provide witness functions
to prove that Alice's proposed mock distributions cannot properly approximate
his device. Within this framework, we establish three results. First, for
random quantum circuits, Bob being able to efficiently distinguish his
distribution from Alice's implies efficient approximate simulation of the
distribution. Secondly, finding a polynomial time function to distinguish the
output of random circuits from the uniform distribution can also spoof the
heavy output generation problem in polynomial time. This pinpoints that
exponential resources may be unavoidable for even the most basic verification
tasks in the setting of random quantum circuits. Beyond this setting, by
employing strong data processing inequalities, our framework allows us to
analyse the effect of noise on classical simulability and verification of more
general near-term quantum advantage proposals.
