Gregory Meyer: Classical Verification of Quantum Computational Advantage

ABSTRACT: Recently, a number of quantum computing experiments have for the first time performed computations that seem to be infeasible classically, for even the world's top supercomputers. An outstanding challenge, however, is that none of these experiments are efficiently verifiable---checking the result of the experiment is as hard as, or even harder than, performing the full computation classically. In this talk I will explore how quantum computers can demonstrate their computational power to a computationally bounded, classical verifier, through a "proof of quantumness" relying on standard cryptographic assumptions. While this goal is theoretically achievable through integer factorization via Shor's algorithm, a demonstration of integer factorization at cryptographic sizes is impossible on today's small, noisy quantum devices. Instead, this talk will pursue the practical question of how novel protocols can reduce the quantum resources required, in particular through the use of interactive arguments, which may allow such a protocol to be implemented in the near term. The main results presented are contained in this paper: https://arxiv.org/abs/2104.00687 I will also discuss a structural attack on another proof of quantumness protocol; the attack is fast in practice and allows a classical impostor to fully extract the verifier's secret key and thus impersonate an honest quantum prover: https://arxiv.org/abs/1912.05547.

email: dlehto@mit.edu for link or for a Tim Ticket to join others to watch virtually in 32-370