Learning quantum states prepared by shallow circuits in polynomial time
This addresses the challenge of efficiently characterizing quantum states in quantum computing, particularly for verification and testing applications, though it is incremental as it builds on prior work in quantum state learning.
The authors tackled the problem of learning quantum states prepared by shallow circuits, presenting a polynomial-time algorithm that reconstructs such states from local reduced density matrices, with extensions to polylog-depth circuits in quasi-polynomial time.
We give a polynomial time algorithm that, given copies of an unknown quantum state $\vertψ\rangle=U\vert 0^n\rangle$ that is prepared by an unknown constant depth circuit $U$ on a finite-dimensional lattice, learns a constant depth quantum circuit that prepares $\vertψ\rangle$. The algorithm extends to the case when the depth of $U$ is $\mathrm{polylog}(n)$, with a quasi-polynomial run-time. The key new idea is a simple and general procedure that efficiently reconstructs the global state $\vertψ\rangle$ from its local reduced density matrices. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.