Undecidability in Tensor Network States
arXiv:1205.3315 · doi:10.1103/PhysRevA.86.030301
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.
arXiv comment5 pages, 4 figures, RevTeX4-1
References in corpus (8)
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- Renormalization and tensor product states in spin chains and lattices
- Closed timelike curves via post-selection: theory and experimental demonstration
- Quantum measurement occurrence is undecidable
- Some Open Problems in Quantum Information Theory
- Categorical Tensor Network States
- Categorical Quantum Circuits
- Are problems in Quantum Information Theory (un)decidable?
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