[CS] Soumik Ghosh Candidacy Exam/Feb 19, 2025

[via cs]

This is an announcement of Soumik Ghosh's Candidacy Exam.
===============================================
Candidate: Soumik Ghosh

Date: Wednesday, February 19, 2025

Time: 11 am CST

Location: JCL 390

Title: Learning and cryptography with random circuits 

Abstract: 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.


Advisor: Bill Fefferman

Committee: Liang Jiang, Fred Chong, Bill Fefferman