Quantum Pseudorandomness: Constructions and Applications
Abstract: Computational notions of randomness — objects that may be far from random but look random to algorithms — have had a big impact on the development of cryptography and theoretical computer science in general. In this talk, we will look at the emerging theory of quantum pseudorandomness — quantum states and transformations that look random to quantum algorithms, such as pseudorandom states and transformations.
We will introduce how these notions are defined, and motivate them by their applications to tomography, black hole physics, quantum cryptography and more. We will then explore one of the central questions about such objects: do they exist and how do we construct them? I will talk about some recent joint works, which present new constructions of some such pseudorandom objects. Typically known constructions of such objects make a fundamental cryptographic assumption --- the existence of one-way functions, but we will see that some constructions could work under a plausibly weaker assumption than the existence of one-way functions.
Bio: Makrand Sinha is an Assistant Professor in the Department of Computer Science at the University of Illinois Urbana-Champaign. His research is in the area of theoretical computer science, in particular, in the foundations of quantum and classical computation and optimization. In a previous life, he was a Simons-Berkeley postdoctoral fellow at the Simons Institute at the University of California at Berkeley and a postdoctoral researcher at Centrum Wiskunde & Informatica in Amsterdam. He obtained his PhD in 2018 from the University of Washington.
To watch online go to the IQUIST youtube channel: https://www.youtube.com/channel/UCCzAySwQXF8J4kRolUzg2ww
For Zoom link you may check the IQUIST calendar weekly email or contact Hannah Stites (hstites2@illinois.edu). To subscribe to our weekly email for event announcements, please go to https://lists.illinois.edu/lists/subscribe/iquist-announcements.
