Learning shallow quantum circuits and quantum states prepared by shallow circuits in polynomial time

In this talk we give polynomial time algorithms for the following two problems:  (1) Given access to an unknown constant depth quantum circuit U on a finite-dimensional lattice, learn a constant depth circuit that approximates U to small diamond distance.  (2) Given copies of an unknown quantum state |ψ>=U|0^n> that is prepared by an unknown constant depth circuit U on a finite-dimensional lattice, learn a constant depth circuit that prepares |ψ>.  These algorithms extend to the case when the depth of U is polylog(n) with a quasi-polynomial run-time. The key techniques are simple and efficient procedures that reconstruct a quantum many-body system of low circuit complexity from its local observables. The goal of this talk is to present simple and accessible pictures that convey the key ideas.  Based on arxiv 2401.10095, and upcoming work with Zeph Landau.

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*