Soumik Ghosh

---

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.

---

University of Chicago
0.03
Contact: Markus Heinrich