Learning quantum states prepared by shallow circuits in polynomial time

[2025-06-06 Yunchao Liu] 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)

Post Date

June 6, 2025

Topic

Quantum Computing