Verifiable Quantum Supremacy: What I Hope Will Be Done

Описание: Scott Aaronson (University of Texas at Austin)
Verifiable Quantum Supremacy: What I Hope Will Be Done
Quantum Summer Cluster Workshop

I'll advocate a research agenda for designing quantum computations that are

(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). It includes concrete open problems on which progress seems feasible.

I'll also advocate "Quantum Information Supremacy," which unlike computational supremacy, doesn't rely on any unproved computational assumptions, and instead relies on separations between classical and quantum one-way communication complexity. I'll explain a recent observation by me, Harry Buhrman, and William Kretschmer, that FBQP/poly != FBQP/qpoly unconditionally, and describe how this complexity separation suggests a possible direct experimental demonstration that n qubits require ＞＞ n classical bits to simulate. The experiment might be feasible using (for example) current or near-future trapped-ion devices.