CS/YQI Colloquium - Henry Yuen - Columbia

Event time: 
Friday, October 18, 2024 - 12:00pm to 1:00pm
Audience: 
YQI Researchers
Location: 
YQI Seminar Room See map
Event description: 

The Hardness of Learning Random Quantum Circuits and its Cryptographic Applications

In classical computer science, the theory of machine learning and the theory of cryptography are really two sides of the same coin. Cryptosystems can be broken by nontrivial learning algorithms, and conversely computationally hard learning problems can serve as the basis for secure cryptography.  Does the same tight-knit correspondence hold in the quantum world? Recently, both quantum learning theory and quantum cryptography have seen a flurry of new models, new algorithms, new protocols, and many new questions.

In this talk I will connect these two developments. In particular, I will discuss some well-motivated hardness assumptions about the learning and cloning of outputs of random quantum circuits, and how these assumptions yield secure forms of quantum cryptography.  Remarkably, the security of these cryptographic primitives appear to rely on fewer mathematical assumptions than is required for any classical cryptosystem. I will discuss a quantum digital signature scheme that is (in principle) NISQ friendly: it can be implemented on a noisy quantum computer, but still remains secure against adversaries with noiseless quantum computers.This opens the door to the intriguing possibility of having a near-term experimental proposal of quantum cryptographic advantage.

No background in quantum learning theory or quantum cryptography will be assumed. Based on joint work with Bill Fefferman, Soumik Ghosh, and Makrand Sinha. 

Livestream the event on Zoom (Yale login required)