Learning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
3Yunchao Liu (UC Berkeley)
https://simons.berkeley.edu/talks/yunchao-liu-uc-berkeley-2024-04-24
Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms
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 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