Colloquium Details
The Cryptographic Nature of Quantum Computation
Speaker: Fermi Ma, The Simons Institute and UC Berkeley
Location: 60 Fifth Avenue 150
Date: April 1, 2025, 2 p.m.
Host: Marshall Ball
Synopsis:
Quantum computers are poised to revolutionize cryptography. On one hand, Shor's algorithm will render much of today’s cryptography insecure. On the other, quantum computers will enable new cryptographic protocols that leverage quantum mechanics to achieve capabilities far beyond what is possible classically. In this talk, I will present my work toward building a foundation for cryptography in the quantum era, and discuss its broader implications for complexity theory and fundamental physics.
The primary focus will be my recent work giving the first proof that pseudorandom unitaries (PRUs) exist. PRUs are a quantum analogue of pseudorandom functions (PRFs), and have wide-ranging applications across quantum computing, cryptography, and physics. The core of the proof is a new technique for performing "on-the-fly" simulation of a random unitary, which can be viewed as a quantum analogue of lazy sampling/evaluation of random functions.
Looking forward, I will also highlight central challenges for quantum computing theory—such as whether we can unconditionally prove that meaningful quantum tasks are hard, or what quantum complexity can reveal about physical phenomena—and discuss how cryptography will be essential in answering these questions.
This talk is aimed at a general audience, and will not assume any prior knowledge of cryptography or quantum computing.
Note: In-person attendance only available to those with active NYU ID cards.
Speaker Bio:
Fermi Ma is a postdoctoral fellow at the Simons Institute and UC Berkeley, hosted by Umesh Vazirani. He received his PhD from Princeton University, advised by Mark Zhandry. His research focuses on the foundations of quantum computing, with an emphasis on cryptography and complexity theory. His work has been recognized with plenary talks at QIP and has been featured in Quanta Magazine.