Abstract

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 (STOC 2024) and arxiv 2410.23618 (STOC 2025).

Personal information

Yunchao Liu is a Postdoctoral Fellow at the Harvard Quantum Initiative. He received his PhD in Computer Science from UC Berkeley, where he was advised by Umesh Vazirani. Before that, he completed his bachelor's degree in the Yao Class at Tsinghua University. His research focuses on quantum information, computation, and complexity theory, with an emphasis on establishing the theoretical foundations for quantum computational advantage on NISQ and early fault-tolerant devices.