Undecidability in Tensor Network States

Abstract

Recent work has examined how undecidable problems can arise in quantum information science. We augment this by introducing three new undecidable problems stated in terms of tensor networks. These relate to ideas of Penrose about the physicality of a spin-network representing a physical process, closed timelike curves, and Boolean relation theory. Seemingly slight modifications of the constraints on the topology or the tensor families generating the networks leads to problems that transition from decidable, to undecidable to even always satisfiable.

5 pages, 4 figures, RevTeX4-1

References in corpus (4)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Closed timelike curves via post-selection: theory and experimental demonstration
• Some Open Problems in Quantum Information Theory
• Categorical Quantum Circuits

Cited by in corpus (13)

• Undecidability of the Spectral Gap (short version)
• Matrix product operators and states: NP-hardness and undecidability
• Encoding Hypergraphs into Quantum States
• Tensor Network Contractions for #SAT
• Undecidability of the Spectral Gap in One Dimension
• Lectures on Quantum Tensor Networks
• Tensor Network Methods for Invariant Theory
• Undecidability of the Spectral Gap (full version)
• Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits
• Undecidability in Physics: a Review
• Tensor network non-zero testing
• Belief propagation in monoidal categories
• Undecidability of the spectral gap in rotationally symmetric Hamiltonians