2024/02/12 by Daniel Malz, Rahul Trivedi, Malz, Daniel +1 · 6 citations
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2402.07975
openalex publication_date 2024/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We determine the computational power of isometric tensor network states (isoTNS), a variational ansatz originally developed to numerically find and compute properties of gapped ground states and topological states in two dimensions. By mapping 2D isoTNS to 1+1D unitary quantum circuits, we find that computing local expectation values in isoTNS is \textsfBQP-complete. We then introduce injective isoTNS, which are those isoTNS that are the unique ground states of frustration-free Hamiltonians, and which are characterized by an injectivity parameter δ∈(0,1/D], where D is the bond dimension of the isoTNS. We show that injectivity necessarily adds depolarizing noise to the circuit at a rate η=δ2D2. We show that weakly injective isoTNS (small δ) are still \textsfBQP-complete, but that there exists an efficient classical algorithm to compute local expectation values in strongly injective isoTNS (η≥0.41). Sampling from isoTNS corresponds to monitored quantum dynamics and we exhibit a family of isoTNS that undergo a phase transition from a hard regime to an easy phase where the monitored circuit can be sampled efficiently. Our results can be used to design provable algorithms to contract isoTNS. Our mapping between ground states of certain frustration-free Hamiltonians to open circuit dynamics in one dimension fewer may be of independent interest.