Learning quantum states prepared by shallow circuits in polynomial time

Abstract

We give a polynomial time algorithm that, given copies of an unknown quantum state $|\psi ⟩=U|0^n⟩$ that is prepared by an unknown constant depth circuit $U$ on a finite-dimensional lattice, learns a constant depth quantum circuit that prepares $|\psi ⟩$. 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 $|\psi ⟩$ 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.

19 pages

References in corpus (11)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• The randomized measurement toolbox
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Computational advantage of quantum random sampling
• Quantum Circuits assisted by LOCC: Transformations and Phases of Matter
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Learning shallow quantum circuits

Cited by in corpus (3)

• On the average-case complexity of learning output distributions of quantum circuits
• Artificial intelligence for representing and characterizing quantum systems
• Sample optimal tomography of quantum Markov chains