How to Rewind a Quantum Computer

Classical computations are inherently "many-time": given a device that performs a computation on a provided input, we can always (at least in principle) run the computation on many different inputs by rewinding the device, returning it to its initial state. This principle does not apply to quantum computations: a quantum computation can irreversibly lose information, and so cannot in general be rewound. This causes serious problems for the analysis of interactive cryptographic protocols in the quantum setting: the classical security reduction typically relies on the ability to rewind the adversary in order to record its responses across different interactions. 

In this talk, I will present a new, general quantum rewinding technique that transforms a "one-time" quantum computation into a "many-time" computation. This opens the door to quantum security for many tasks. One key application is to prove that Kilian’s four-message succinct argument system for NP is secure against quantum attack (assuming the post-quantum hardness of the Learning with Errors problem).

Based on joint work with Alessandro Chiesa, Fermi Ma, Alex Lombardi, and Mark Zhandry.