Learning quantum states prepared by shallow circuits in polynomial time

Autor:	Landau, Zeph, Liu, Yunchao
Rok vydání:	2024
Předmět:	Quantum Physics Computer Science - Computational Complexity Computer Science - Machine Learning
Druh dokumentu:	Working Paper
Popis:	We give a polynomial time algorithm that, given copies of an unknown quantum state $\vert\psi\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\psi\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\psi\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. Comment: 19 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2410.23618 Zobrazit plný text záznamu View this record from Arxiv