[Theory] [Theory Lunch] Soumik Ghosh, Wednesday 2/5, 12-1pm, JCL 298

[Gabe Schoenbach via Theory]

Hi all — please join us this *Wednesday at 12pm* for the theory
lunch! Details below:

***
*Date: *February 5, 2025, 12pm
*Location: *JCL 298

*Title: *Learning and cryptography with random circuits

*Speaker: *Soumik Ghosh (UChicago)

*Abstract: *The talk is in two parts. In the first part, we prove a lower
bound on the scrambling speed of a random quantum circuit. We give three
applications of this:

a) An optimal lower bound on the depth required for ε-approximate unitary
designs;

b) A polynomial-time quantum algorithm that computes the depth of a
bounded-depth circuit, given oracle access to the circuit;

c) A polynomial-time algorithm that learns log-depth circuits up to
polynomially small diamond distance, given oracle access to the circuit.

In the second part, we show that concrete hardness assumptions about
learning or cloning the output state of a random quantum circuit can be
used as the foundation for secure quantum cryptography.

Our random circuit-based constructions provide concrete instantiations of
quantum cryptographic primitives whose security do not depend on the
existence of one-way functions. The use of random circuits in our
constructions also opens the door to NISQ-friendly quantum cryptography.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250203/c60ae458/attachment.html>