Decidability of normalizability, symmetry classification, canonical forms, and the parent-Hamiltonian spectral gap within physically relevant subclasses of projected entangled pair states

Scarpa et al. (Phys. Rev. Lett. 125, 210504 (2020)) proved by reduction from the domino tiling problem that four decision problems for general projected entangled pair states (PEPS) are algorithmically undecidable: testing whether a PEPS is normalizable (nonzero for some boundary conditions at every system size), deciding invariance under an on-site symmetry in the thermodynamic limit, deciding whether two tensors define the same state (which excludes any computable canonical form and any general fundamental theorem of PEPS), and deciding whether the parent Hamiltonian is gapped or gapless (the latter at least for finite but unbounded local physical dimension). The undecidability constructions use block-diagonal direct-sum tensors that destroy injectivity, so they live outside the classes arising in approximation theorems and stable numerical simulation, and the authors posed the complementary question of which physically relevant restrictions restore decidability. Substantial partial progress exists: fundamental theorems and exhaustive symmetry characterizations are known for injective, normal, semi-injective, and gauge-invariant PEPS; a minimal canonical form based on geometric invariant theory makes gauge equivalence, and equality of the generated states when all contraction graphs are allowed (arbitrary graph topologies, as opposed to the grid family), decidable for arbitrary tensors; and quantitative injectivity gives provably uniformly gapped parents together with efficient contraction. However, for the grid geometries of physical interest, the decidability of normalizability and of state equality within natural subclasses, the existence of a decidable necessary-and-sufficient criterion for the parent-Hamiltonian gap of injective or MPO-injective PEPS, and worst-case finite-computation certification of membership in such subclasses all remain open. The problem posed here is to chart this decidability boundary: determine, with proofs, which structural restrictions on PEPS tensors are sufficient (and where possible necessary) to circumvent the tiling-based obstructions for each of the four problems.

Background

Projected entangled pair states (PEPS) generalize matrix product states (MPS) to two-dimensional lattices. A translational-invariant PEPS is specified by a single local tensor $A$ with one physical index (ranging over the local Hilbert space of dimension $d$) and four virtual indices (each of bond dimension $D$) that are contracted between neighboring sites; contracting all virtual legs of an $L\times L$ lattice, with boundary vectors or open boundary conditions, produces a many-body wavefunction. Contracting a single row of the lattice defines a linear map on the row's open virtual indices, called the transfer operator, whose spectral properties control how boundary effects and correlations decay with system size. The family of states on arbitrarily large lattices generated this way is called the PEPS of $A$ on grids, and bulk observables become independent of the boundary in the thermodynamic limit precisely when the state is normalizable, meaning nonzero for some choice of boundary conditions at every system size. The contraction is redundant: inserting invertible matrices on paired virtual legs (a gauge transformation) leaves every generated state unchanged. A canonical form is a systematic procedure fixing this gauge, and a fundamental theorem for the ansatz characterizes when two tensors generate the same state. In one dimension the theory is complete: two normal MPS generate the same state if and only if they are related by a gauge transformation, and every global symmetry of the state acts as a virtual matrix (or, for fermionic and topologically ordered states, matrix product operator) symmetry on the tensor, which underlies provably unbiased symmetry classification in numerical algorithms. A tensor is called injective if, after blocking finitely many sites together (a normal tensor), the resulting map from the virtual boundary indices of a region to its physical indices is one-to-one. Injectivity implies that the PEPS is the unique ground state of a frustration-free parent Hamiltonian built from local projectors onto the complement of the blocked tensor's image. MPO-injectivity enlarges the admissible gauge freedom to matrix product operators (MPOs, operator-valued analogues of MPS obtained when the physical index runs over matrix units) forming a virtual symmetry algebra that can be pulled through the network, i.e. moved across the tensor at the cost of acting on its virtual legs; this describes topologically ordered PEPS such as the toric code and lattice gauge theories, where separate matter and gauge-field tensors sit on vertices and edges. Related restrictions are $G$-injectivity, where the tensor is invariant under a virtual action of a finite group $G$ and becomes injective after blocking $|G|$ sites, semi-injectivity, a variant of MPO-injectivity in which the virtual symmetry algebra has a one-dimensional invariant subspace and which covers two-dimensional symmetry-protected phases, and isometric tensor networks, whose tensors are isometries from a subset of their virtual legs onto the remaining legs together with the physical index, a constraint that enables provably efficient contraction. Scarpa et al. reduced the classical domino tiling problem (given a finite set of square tiles with colored edges, decide whether the infinite plane can be tiled with matching edge colors, undecidable since Berger 1966) to PEPS questions. Encoding tiling rules into the virtual structure of a tensor and taking direct sums of a tiling sector with an Ising-model sector, they proved undecidable, for general PEPS tensors: (1) zero testing, i.e. normalizability on grids; (2) invariance under a given on-site symmetry in the thermodynamic limit; (3) equality of the states generated by two tensors on grids, so no computable canonical form and no fundamental theorem of PEPS can exist in general; (4) distinguishing a gapped parent Hamiltonian (gap at least 1) from one whose spectrum becomes dense in $[0,\infty)$, at least when the local physical dimension is finite but unbounded. The constructions are highly non-injective, and the paper's conclusion states that the limitations could potentially be overcome by restricting to a physically relevant subclass whose additional structure (as in the states appearing in approximation proofs or numerical simulations) may restore decidability. The restricted landscape known so far is the following. For injective and normal PEPS the fundamental theorem and an exhaustive symmetry characterization hold, with extensions to semi-injective tensors and to gauge-invariant PEPS whose matter and gauge-field blocks are injective after blocking. Parent Hamiltonians of normal MPS are always gapped, but in two dimensions injectivity alone does not imply a gap: the critical Ising PEPS on the honeycomb lattice is injective yet has power-law correlations, hence no gapped parent. Sufficient conditions for gapped parents include strong (quantitative) injectivity, a uniform condition-number bound on the blocked tensor, and the approximate factorization of boundary states as Gibbs states of a one-dimensional short-range Hamiltonian (the boundary-locality condition); whether the latter is also necessary (the boundary-Gibbs conjecture) is open. Even membership in the natural classes is not known to be decidable in the worst case: no computable bound on the number of blocking steps required for injectivity (an injectivity index) is known for PEPS, only existence bounds that may be uncomputable and generic-case estimates. Finally, a minimal canonical form based on geometric invariant theory decides gauge equivalence of arbitrary tensors and equality of the generated states on all contraction graphs (arbitrary surface topologies rather than grids alone), deliberately routing around the grid-based undecidability; the grid versions of equality and zero testing remain undecidable in general, and their status within structured subclasses is open.

Problem Statement

Determine which physically relevant restrictions of projected entangled pair states restore algorithmic decidability of the four decision problems proved undecidable for general PEPS by Scarpa et al. Concretely, fix the following six subclasses $S$ of PEPS tensors, each defined in the Background by a structural condition on the tensor: injective and normal tensors; MPO-injective tensors; $G$-injective tensors; semi-injective tensors; gauge-invariant matter-gauge tensor pairs; and isometric tensor networks. The families produced by approximation theorems or arising as fixed points of variational algorithms motivate the question, but they are not defined by a condition on the tensor and are not among the adjudicated classes. Each problem is a promise problem on each class: the input tensor is assumed to lie in $S$, and deciding membership in $S$ is not part of any cell, that certification question being the separate concern noted above as open. Determine, with proof, for each of the four problems and each of these six classes: (a) Normalizability on grids: is it decidable, for tensors in $S$, whether some choice of boundary conditions (chosen separately at each system size) yields a nonzero state at every system size, i.e. whether the thermodynamic-limit state is well-defined? (b) Symmetry classification (restricted fundamental theorem): is it decidable, for tensors in $S$, whether a given on-site, gauge, or virtual symmetry acts on the tensor, i.e. whether the corresponding invariance holds in the thermodynamic limit; equivalently, does a decidable, exhaustive characterization of the ways such symmetries can act on tensors in $S$ exist? (c) Canonical form on grids: does there exist a computable canonical form (or gauge-fixing procedure) for tensors in $S$ such that two tensors in $S$ generate the same state on grids if and only if their canonical forms coincide, equivalently, is grid-equality decidable within $S$? (d) Spectral gap: is it decidable, for tensors in $S$, whether the parent Hamiltonian is gapped or gapless in the thermodynamic limit? The single unifying objective is to chart the decidability boundary of the four problems across the landscape of PEPS subclasses used in physics. A full resolution is a determination of every one of the $4\times 6$ problem–class cells, the determination of a cell being the verdict for that problem within that class, i.e. a proof of decidability or an undecidability reduction. A verdict already recorded in the Background may be adopted for a cell by stating it and citing the Background instead of reproving it, but every cell must be covered explicitly, so the mandatory delivery is the same for every reader. A determination of only a proper subset of the cells is a partial resolution: it is an acceptable partial answer, but not by itself a resolution of the task. Statements of necessity are an optional strengthening beyond a cell's verdict and are sought only where the sources allow.

References

1. G. Scarpa, A. Molnár, Y. Ge, J. J. García-Ripoll, N. Schuch, D. Pérez-García, S. Iblisdir, 'Projected Entangled Pair States: Fundamental Analytical and Numerical Limitations', Physical Review Letters 125, 210504 (2020). DOI: 10.1103/PhysRevLett.125.210504, arXiv:1802.08214, https://arxiv.org/abs/1802.08214
2. T. Cubitt, D. Perez-Garcia, M. M. Wolf, 'Undecidability of the spectral gap', Nature 528, 207-211 (2015). DOI: 10.1038/nature16059, arXiv:1502.04135, https://arxiv.org/abs/1502.04135
3. J. Bausch, T. S. Cubitt, A. Lucia, D. Perez-Garcia, 'Undecidability of the spectral gap in one dimension', Physical Review X 10, 031038 (2020). DOI: 10.1103/PhysRevX.10.031038, https://doi.org/10.1103/PhysRevX.10.031038
4. L. Castilla-Castellano, A. Lucia, 'Undecidability of the spectral gap in rotationally symmetric Hamiltonians', Physical Review Research 8, 013033 (2026). DOI: 10.1103/5lrn-h3cg, arXiv:2410.13589, https://arxiv.org/abs/2410.13589
5. A. Acuaviva, V. Makam, H. Nieuwboer, D. Pérez-García, F. Sittner, M. Walter, F. Witteveen, 'The minimal canonical form of a tensor network', Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023). DOI: 10.1109/FOCS57990.2023.00027, arXiv:2209.14358, https://arxiv.org/abs/2209.14358
6. D. Perez-Garcia, M. Sanz, C. E. Gonzalez-Guillen, M. M. Wolf, J. I. Cirac, 'Characterizing symmetries in a projected entangled pair state', New Journal of Physics 12, 025010 (2010). DOI: 10.1088/1367-2630/12/2/025010, arXiv:0908.1674, https://arxiv.org/abs/0908.1674
7. A. Molnár, J. Garre-Rubio, D. Pérez-García, N. Schuch, J. I. Cirac, 'Normal projected entangled pair states generating the same state', New Journal of Physics 20, 113017 (2018). DOI: 10.1088/1367-2630/aae9fa, arXiv:1804.04964, https://arxiv.org/abs/1804.04964
8. J. I. Cirac, J. Garre-Rubio, D. Pérez-García, 'Mathematical open problems in Projected Entangled Pair States', Revista Matemática Complutense 32, 579-599 (2019). DOI: 10.1007/s13163-019-00318-x, arXiv:1903.09439, https://arxiv.org/abs/1903.09439
9. M. J. Kastoryano, A. Lucia, D. Perez-Garcia, 'Locality at the boundary implies gap in the bulk for 2D PEPS', Communications in Mathematical Physics 366, 895-926 (2019). DOI: 10.1007/s00220-019-03404-9, arXiv:1709.07691, https://arxiv.org/abs/1709.07691
10. F. Verstraete, M. M. Wolf, D. Perez-Garcia, J. I. Cirac, 'Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States', Physical Review Letters 96, 220601 (2006). DOI: 10.1103/PhysRevLett.96.220601, arXiv:quant-ph/0601075, https://arxiv.org/abs/quant-ph/0601075
11. J. I. Cirac, D. Pérez-García, N. Schuch, F. Verstraete, 'Matrix product states and projected entangled pair states: Concepts, symmetries, theorems', Reviews of Modern Physics 93, 045003 (2021). DOI: 10.1103/RevModPhys.93.045003, arXiv:2011.12127, https://arxiv.org/abs/2011.12127
12. D. Blanik, J. Garre-Rubio, A. Molnár, E. Zohar, 'Internal structure of gauge-invariant Projected Entangled Pair States', Journal of Physics A: Mathematical and Theoretical 58, 065301 (2025). DOI: 10.1088/1751-8121/adae83, arXiv:2410.18947, https://arxiv.org/abs/2410.18947
13. Y. Jia, A. Capel, 'A generic quantum Wielandt's inequality', Quantum 8, 1331 (2024). DOI: 10.22331/q-2024-05-02-1331, arXiv:2301.08241, https://arxiv.org/abs/2301.08241
14. D. Harley, F. Witteveen, D. Malz, 'Computational complexity of injective projected entangled pair states', arXiv:2509.19963 (2025). https://arxiv.org/abs/2509.19963
15. M. Michałek, T. Seynnaeve, F. Verstraete, 'A tensor version of the quantum Wielandt theorem', SIAM Journal on Matrix Analysis and Applications 40, 1125-1130 (2019). DOI: 10.1137/18M1227664, arXiv:1811.05502, https://arxiv.org/abs/1811.05502
16. N. Schuch, D. Perez-Garcia, I. Cirac, 'Classifying quantum phases using Matrix Product States and PEPS', Physical Review B 84, 165139 (2011). DOI: 10.1103/PhysRevB.84.165139, arXiv:1010.3732, https://arxiv.org/abs/1010.3732
17. Á. Perales-Eceiza, T. Cubitt, M. Gu, D. Pérez-García, M. M. Wolf, 'Undecidability in physics: A review', Physics Reports 1138, 1-29 (2025). DOI: 10.1016/j.physrep.2025.06.004, arXiv:2410.16532, https://arxiv.org/abs/2410.16532
18. A. Anshu, N. P. Breuckmann, Q. T. Nguyen, 'Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance', Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pp. 585-595. DOI: 10.1145/3618260.3649690, https://doi.org/10.1145/3618260.3649690
19. T. Barthel, J. Lu, G. Friesecke, 'On the closedness and geometry of tensor network state sets', Letters in Mathematical Physics 112, 72 (2022). DOI: 10.1007/s11005-022-01552-z, arXiv:2108.00031, https://arxiv.org/abs/2108.00031
20. A. Klingler, M. van der Eyden, S. Stengele, T. Reinhart, G. De las Cuevas, 'Many bounded versions of undecidable problems are NP-hard', SciPost Physics 14, 173 (2023). DOI: 10.21468/SciPostPhys.14.6.173, arXiv:2211.13532, https://arxiv.org/abs/2211.13532
21. T. Carette, E. Moutot, 'Aperiodicity in quantum Wang tilings', Theoretical Computer Science 1082, 116159 (2026). DOI: 10.1016/j.tcs.2026.116159, arXiv:2302.04503, https://arxiv.org/abs/2302.04503
22. N. Bultinck, M. Mariën, D. J. Williamson, M. B. Şahinoğlu, J. Haegeman, F. Verstraete, 'Anyons and matrix product operator algebras', Annals of Physics 378, 183-233 (2017). DOI: 10.1016/j.aop.2017.01.004, arXiv:1511.08090, https://arxiv.org/abs/1511.08090
23. A. Molnár, Y. Ge, N. Schuch, J. I. Cirac, 'A generalization of the injectivity condition for Projected Entangled Pair States', Journal of Mathematical Physics 59, 021902 (2018). DOI: 10.1063/1.5007017, arXiv:1706.07329, https://arxiv.org/abs/1706.07329