The complexity landscape of injective PEPS: the translation-invariant case, threshold sharpness, and the learning analogue

Harley, Witteveen and Malz recently proved that the difficulty of evaluating local observables of two-dimensional projected entangled pair states (PEPS) is controlled by injectivity, the inverse condition number $\delta$ of the tensors: below a constant threshold $\delta_{\mathrm{hard}}$ the task of estimating normalized expectation values of local observables (NEV) is postBQP-complete, above a different constant threshold $\delta_{\mathrm{easy}}$ it is solvable in classical polynomial time, and in the translation-invariant case computing the norm to exponential additive precision is #P-hard. This problem asks to complete the landscape those authors left open, along three linked axes: (i) the worst-case complexity of estimating normalized local observables in translation-invariant $\delta$-injective PEPS at constant injectivity — hard, or tractable; (ii) whether the hardness and easiness thresholds coincide, i.e. whether there is a sharp computational transition in injectivity, and what the complexity of the intermediate regime is; and (iii) whether the same injectivity-driven easy/hard dichotomy extends to learning PEPS from copies of the state. A resolution would locate the boundary of efficient classical and quantum simulation for the dominant two-dimensional variational ansatz, and determine whether that boundary also governs learnability from data.

Background

Projected entangled pair states (PEPS) parameterize many-body wavefunctions on a lattice by placing a maximally entangled pair of virtual particles of dimension $D$ (the bond dimension) on every edge and applying at each vertex a linear map (a tensor) $T_x$ from the incident virtual spaces to a local physical Hilbert space. They generalize matrix product states (MPS, the one-dimensional case) and are the dominant variational ansatz for two-dimensional quantum matter; their entanglement entropy obeys an area law. A tensor is injective if $T_x$ is injective as a linear map, and the strength of injectivity is quantified by $\delta$: after normalizing the largest singular value of every tensor to one, the PEPS is $\delta$-injective if all singular values of every tensor are at least $\delta$, i.e. $\delta$ is the inverse condition number ($0<\delta\le 1$; $\delta=1$ means every tensor is an isometry up to scale). Strong injectivity means injectivity persists when the tensors in any simply connected block are fused into one effective map. Injective PEPS are unique ground states of local frustration-free parent Hamiltonians (a parent Hamiltonian is a local Hamiltonian constructed directly from the PEPS tensors; frustration-free means its ground state simultaneously minimizes every local term), which are provably gapped for strong injectivity above a constant threshold — a fact implying exponentially decaying correlations.

Two computational tasks are central. NORM asks for the squared norm $\langle\Psi|\Psi\rangle$ of the (unnormalized) PEPS. NEV asks for a normalized local expectation value $\langle O_X\rangle=\langle\Psi|O_X|\Psi\rangle/\langle\Psi|\Psi\rangle$ with $O_X$ supported on a constant number of sites, to constant additive precision; its decision version asks to decide $\langle O_X\rangle\le 1/3$ versus $\ge 2/3$. For general (non-injective) two-dimensional PEPS, NEV is postBQP-complete (Schuch, Wolf, Verstraete and Cirac, 2007): postBQP is the class of problems solvable by polynomial-size quantum circuits with postselection (conditioning on observing a prescribed, possibly exponentially unlikely, measurement outcome), equals PP by a theorem of Aaronson, and is thus beyond efficient classical and quantum algorithms unless PP collapses. PEPS equivalence testing is even undecidable (Scarpa et al., 2020).

Injective PEPS were expected to be better behaved. Anshu, Breuckmann and Nguyen (STOC 2024) reduced quantum circuits to injective PEPS at the cost that injectivity forces the embedded circuit to run at a constant noise rate, which they mitigate by error correction, obtaining BQP-hardness (BQP being the class of problems solvable efficiently by a quantum computer) and leaving open whether local observables of injective PEPS are easy or hard. Harley, Witteveen and Malz resolved this question with a two-threshold dichotomy. Hardness: there is a constant $\delta_{\mathrm{hard}}>0$, concretely $\delta_{\mathrm{hard}}=\sqrt{\eta_{\mathrm{hard}}/(4-3\eta_{\mathrm{hard}})}$ with $\eta_{\mathrm{hard}}=\min\{\eta_{\mathrm{thresh}},\eta_{1}\}$ the smaller of the fault-tolerance threshold $\eta_{\mathrm{thresh}}$ of noisy postselected computation and a constant $\eta_{1}$ chosen so that the accumulated output error does not close the promise gap, such that the decision version of NEV is postBQP-complete for $\delta$-injective PEPS with $\delta<\delta_{\mathrm{hard}}$ on the two-dimensional lattice, with bond dimension $D=2$ sufficing; the technical innovation is a threshold theorem for postselected quantum computation under constant depolarizing noise (which also establishes that computation with projected closed timelike curves is robust to noise). Easiness: there is $\delta_{\mathrm{easy}}<1$ (at most $0.982$ on the square lattice, from the gap analysis of Schuch, Pérez-García and Cirac) such that for $\delta>\delta_{\mathrm{easy}}$ NEV is solvable in classical time polynomial in the inverse precision, independent of system size, by combining the gapped parent Hamiltonian, exponential clustering, and a patch-contraction argument improving the quasipolynomial bound of Schwarz, Buerschaper and Eisert to polynomial in two dimensions. Uniform case: for translation-invariant PEPS (the same tensor at every site, periodic boundaries), computing NORM to exponential additive precision is #P-hard at constant injectivity (#P being the class of counting problems, e.g. counting valid Wang tilings — square tiles with matching edge colors — whose enumeration the construction encodes), via polynomial extrapolation in $\delta$ following Haferkamp, Hangleiter, Eisert and Gluza. The related isometric tensor networks (Zaletel and Pollmann), whose tensors are isometries so that the norm is fixed by construction, have NEV BQP-complete even at constant injectivity (Malz and Trivedi). For learning, the one-dimensional analogues of injective MPS — finitely correlated states, translation-invariant one-dimensional states generated by iterating a completely positive map along the chain — are learnable by stable spectral reconstruction, a procedure recovering the generating tensors from finitely many local correlation functions (Fanizza et al.), and states of bounded gate complexity are learnable (Zhao et al.); strongly injective PEPS are efficiently preparable on a quantum computer, but no learning theory for general PEPS exists.

Problem Statement

The common objective is to complete the characterization, initiated by Harley, Witteveen and Malz, of how the injectivity parameter $\delta$ governs the worst-case computational complexity of the basic tasks on two-dimensional PEPS — evaluating normalized local expectation values and learning the state from copies — beyond the two constant-injectivity regimes already classified. The requested results are:

(1) Translation invariance. For translation-invariant $\delta$-injective PEPS on the two-dimensional square lattice (the same tensor at every vertex, periodic boundary conditions), with constant bond dimension and constant $\delta$, determine the worst-case complexity of the decision version of NEV: is it postBQP-hard, as in the non-uniform case, or does uniformity at constant injectivity restore classical or quantum tractability? The known #P-hardness of NORM to exponential additive precision in this setting does not imply hardness of normalized expectation values (the normalization can be exponentially small and wash out the encoded signal), and the existing postBQP-hardness construction fundamentally uses different tensors at different sites (fault-tolerant decoding circuitry), so neither direction of implication is currently available.

(2) Threshold structure and the intermediate regime. Let $\delta_{\mathrm{hard}}^*$ be the supremum of constants $c$ such that NEV is postBQP-hard for all $\delta<c$, and $\delta_{\mathrm{easy}}^*$ the infimum of constants $c$ such that NEV is polynomial-time solvable for all $\delta>c$, in both cases for two-dimensional PEPS with constant bond dimension. Determine whether $\delta_{\mathrm{hard}}^*=\delta_{\mathrm{easy}}^*$, i.e. whether there is a single sharp computational transition in injectivity, and if an intermediate interval exists, determine the complexity of NEV there — in particular whether there are regimes where contraction is neither polynomial-time nor postBQP-hard, and when quantum computers without postselection can efficiently perform the contraction.

(3) Learning. Given copies of an unknown state together with the promise that it has a PEPS description on a given graph with a given bond dimension, determine the sample and computational complexity of learning tensors that reproduce the state (to small trace distance, or in local expectation values). In particular, decide whether a dichotomy analogous to the contraction result holds: efficient learnability at sufficiently high injectivity, and computational hardness at small injectivity (under standard complexity assumptions).

The components are linked: (1) and (2) complete the injectivity-complexity phase diagram of the contraction task (uniform versus non-uniform instances; sharp versus smeared transition), and (3) tests whether the same injectivity boundary reappears for acquiring such states from data, as the source authors explicitly propose.

References

1. D. Harley, F. Witteveen, D. Malz, "Computational complexity of injective projected entangled pair states", arXiv:2509.19963 (2025). DOI: 10.48550/arXiv.2509.19963, https://arxiv.org/abs/2509.19963
2. N. Schuch, M. M. Wolf, F. Verstraete, J. I. Cirac, "Computational complexity of projected entangled pair states", Physical Review Letters 98, 140506 (2007). DOI: 10.1103/PhysRevLett.98.140506, https://doi.org/10.1103/PhysRevLett.98.140506
3. S. Aaronson, "Quantum computing, postselection, and probabilistic polynomial-time", Proceedings of the Royal Society A 461, 3473-3482 (2005). DOI: 10.1098/rspa.2005.1546, https://doi.org/10.1098/rspa.2005.1546
4. N. Schuch, D. Pérez-García, I. Cirac, "Classifying quantum phases using matrix product states and projected entangled pair states", Physical Review B 84, 165139 (2011). DOI: 10.1103/PhysRevB.84.165139, https://doi.org/10.1103/PhysRevB.84.165139
5. M. Schwarz, O. Buerschaper, J. Eisert, "Approximating local observables on projected entangled pair states", Physical Review A 95, 060102 (2017). DOI: 10.1103/PhysRevA.95.060102, https://doi.org/10.1103/PhysRevA.95.060102
6. 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 '24), pp. 585-595 (2024). DOI: 10.1145/3618260.3649690, https://doi.org/10.1145/3618260.3649690
7. D. Malz, R. Trivedi, "Computational complexity of isometric tensor-network states", PRX Quantum 6, 020310 (2025). DOI: 10.1103/PRXQuantum.6.020310, https://doi.org/10.1103/PRXQuantum.6.020310
8. J. Haferkamp, D. Hangleiter, J. Eisert, M. Gluza, "Contracting projected entangled pair states is average-case hard", Physical Review Research 2, 013010 (2020). DOI: 10.1103/PhysRevResearch.2.013010, https://doi.org/10.1103/PhysRevResearch.2.013010
9. G. Scarpa, A. Molnár, Y. Ge, 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, https://doi.org/10.1103/PhysRevLett.125.210504
10. M. P. Zaletel, F. Pollmann, "Isometric tensor network states in two dimensions", Physical Review Letters 124, 037201 (2020). DOI: 10.1103/PhysRevLett.124.037201, https://doi.org/10.1103/PhysRevLett.124.037201
11. H. Zhao, L. Lewis, I. Kannan, Y. Quek, H.-Y. Huang, M. C. Caro, "Learning quantum states and unitaries of bounded gate complexity", PRX Quantum 5, 040306 (2024). DOI: 10.1103/PRXQuantum.5.040306, https://doi.org/10.1103/PRXQuantum.5.040306
12. M. Fanizza, N. Galke, J. Lumbreras, C. Rouzé, A. Winter, "Learning finitely correlated states: stability of the spectral reconstruction", arXiv:2312.07516 (2023). DOI: 10.48550/arXiv.2312.07516, https://arxiv.org/abs/2312.07516
13. S. Midha, Y. F. Zhang, D. Malz, D. A. Abanin, S. Gopalakrishnan, "Algorithmic locality via provable convergence in quantum tensor networks", arXiv:2604.21919 (2026). DOI: 10.48550/arXiv.2604.21919, https://arxiv.org/abs/2604.21919
14. S. Midha, G. M. Sommers, J. Tindall, D. A. Abanin, "Belief propagation and tensor network expansions for many-body quantum systems: Rigorous results and fundamental limits", arXiv:2604.03228 (2026). DOI: 10.48550/arXiv.2604.03228, https://arxiv.org/abs/2604.03228
15. S. Midha, Y. F. Zhang, "Beyond belief propagation: Cluster-corrected tensor network contraction with exponential convergence", arXiv:2510.02290 (2025). DOI: 10.48550/arXiv.2510.02290, https://arxiv.org/abs/2510.02290
16. Y. Wu, Y. Zhang, X. Zhang, C. Wang, X. Yuan, "Quantum advantage with adaptive shallow circuits", arXiv:2608.15545 (2026). DOI: 10.48550/arXiv.2608.15545, https://arxiv.org/abs/2608.15545
17. G. Dünnweber, G. Styliaris, R. Trivedi, "Quantum memory and autonomous computation in two dimensions", arXiv:2601.20818 (2026). DOI: 10.48550/arXiv.2601.20818, https://arxiv.org/abs/2601.20818
18. A. Bulgarelli, M. Panero, P. Stornati, L. Tagliacozzo, "Mapping twist fields to local operators via tensor networks", arXiv:2605.26208 (2026). DOI: 10.48550/arXiv.2605.26208, https://arxiv.org/abs/2605.26208
19. G. Arora, M. Headrick, A. Lawrence, M. Sasieta, B. Swingle, C. Wolfe, "Twirled perfect tensor networks: Computationally covariant holographic tensor networks", arXiv:2605.23670 (2026). DOI: 10.48550/arXiv.2605.23670, https://arxiv.org/abs/2605.23670
20. J. Chen, J. Jiang, D. Hangleiter, N. Schuch, "Sign problem in tensor-network contraction", PRX Quantum 6, 010312 (2025). DOI: 10.1103/PRXQuantum.6.010312, https://doi.org/10.1103/PRXQuantum.6.010312
21. J. Jiang, J. Chen, N. Schuch, D. Hangleiter, "Positive bias makes tensor-network contraction tractable", arXiv:2410.05414 (2024). DOI: 10.48550/arXiv.2410.05414, https://arxiv.org/abs/2410.05414