<div dir="ltr"><div dir="ltr">Hi all — please join us this <b>Wednesday at 12pm</b> for the theory lunch! Details below:<div><br></div><div>***</div><div><b>Date: </b>February 5, 2025, 12pm</div><div><b>Location: </b>JCL 298</div><div><b><br></b></div><div><b>Title: </b>Learning and cryptography with random circuits</div><div><b><br></b></div><div><b>Speaker: </b>Soumik Ghosh (UChicago)</div><div><b><br></b></div><div><b>Abstract: </b>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:
</div><br>a) An optimal lower bound on the depth required for ε-approximate unitary designs; 
<br><br>b) A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit;
<br><br>c) A polynomial-time algorithm that learns log-depth circuits up to polynomially small diamond distance, given oracle access to the circuit.
 
<br><br>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.

<br><br>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.</div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div>