Physics Department Colloquia |
(1) feasible on near-term, non-error-corrected, "NISQ" devices,
(2) hard to simulate classically, and
(3) easy to verify classically,
where right now we only have any two of the three. The agenda involves understanding the structure of otherwise-random quantum circuits that have been postselected to have the behavior that we want (such as producing verifiable outputs), and includes concrete open problems on which progress seems feasible. I'll also discuss potential applications to generating cryptographically certified random bits -- a proposal of mine from 2018 that was just experimentally demonstrated this year, albeit without efficient classical verification.