How to Verify that a Small Device is Quantum, Unconditionally? (Delivered in English)
- LecturerDr. Tamer Mour (Bocconi University)
Host: Kai-Min Chung - Time2025-10-14 (Tue.) 14:30 ~ 16:30
- LocationAuditorium 101 at IIS new Building
Abstract
Arguably the most important goal in quantum computation is to demonstrate quantum advantage, namely a task that is feasible for quantum computers but not for classical ones.
Quantum advantage is practically demonstrated by a proof of quantumness (PoQ): a protocol where a quantum prover proves its quantumness to a classical verifier.
Known PoQs either cannot be verified efficiently or are far from being practical for experiment. Additionally, they all rely on conjectures (from complexity theory or cryptography).
In the talk, I will present two PoQs that are feasible for small-space quantum provers, but require any classical device large memory to succeed. Our PoQs are unconditional and do not rely on conjectures. The first is an exceptionally simple fine-grained PoQ, providing an approach for potential experiment. The second PoQ exhibits an exponential gap between the memory of the honest quantum prover and that of a successful classical cheater.
Quantum advantage is practically demonstrated by a proof of quantumness (PoQ): a protocol where a quantum prover proves its quantumness to a classical verifier.
Known PoQs either cannot be verified efficiently or are far from being practical for experiment. Additionally, they all rely on conjectures (from complexity theory or cryptography).
In the talk, I will present two PoQs that are feasible for small-space quantum provers, but require any classical device large memory to succeed. Our PoQs are unconditional and do not rely on conjectures. The first is an exceptionally simple fine-grained PoQ, providing an approach for potential experiment. The second PoQ exhibits an exponential gap between the memory of the honest quantum prover and that of a successful classical cheater.