Nonstabilizerness of quantum tensor network states is intractable in two dimensions
Abstract
Nonstabilizerness is a necessary resource for quantum systems to lie beyond the classically simulable regime. With the advent of stabilizer α-Rényi entropies, nonstabilizerness has also become a many-body diagnostic, complementary to entanglement. While deciding whether an arbitrary quantum state has nonstabilizerness is provably hard, such states already require a description exponentially large in the number of qubits and are thus out of reach for many-body physics. Here we instead consider 2D tensor network (TN) states, which compactly capture states obeying an entanglement area law, and ask whether they admit a simpler algorithm for the same task. In contrast to the 1D case, we prove that, even at small, constant bond dimension, computing the stabilizer entropy of 2D TN states is #P-hard for any integer α≥ 2, and deciding stabilizer membership is C=P-complete. The corresponding constant-accuracy problems remain C= P-hard. We further prove that deciding whether a PEPS can be transformed into a stabilizer state by local unitaries over a specified bipartition is C= P-hard. Under standard complexity assumptions, these results rule out classical or quantum algorithms with polynomial resources for all three tasks in the worst case.
Related
- Extensions of the Haldane gap proof: higher dimensions, near degeneracy, fermions and tensor-network states
- Tensor-network approach to quantum optical state evolution beyond the Fock basis
- Quantum Circuit and Tensor Network Implementation of the 2D Acoustic Wave Equation
- QTN-RQNN: Quantum Tensor Network-Based Recurrent Quantum Neural Network
- Sampling isometric tensor network states with monitored quantum circuits
BibTeX
@misc{esposito2026nonstabilizerness,
title = {{Nonstabilizerness of quantum tensor network states is intractable in two dimensions}},
author = {Gianluca Esposito and Georgios Styliaris},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.31459},
eprint = {2609.31459},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31459},
}
RIS
TY - UNPB
TI - Nonstabilizerness of quantum tensor network states is intractable in two dimensions
AU - Gianluca Esposito
AU - Georgios Styliaris
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.31459
UR - https://arxiv.org/abs/2609.31459
AB - Nonstabilizerness is a necessary resource for quantum systems to lie beyond the classically simulable regime. With the advent of stabilizer α-Rényi entropies, nonstabilizerness has also become a many-body diagnostic, complementary to entanglement. While deciding whether an arbitrary quantum state has nonstabilizerness is provably hard, such states already require a description exponentially large in the number of qubits and are thus out of reach for many-body physics. Here we instead consider 2D tensor network (TN) states, which compactly capture states obeying an entanglement area law, and ask whether they admit a simpler algorithm for the same task. In contrast to the 1D case, we prove that, even at small, constant bond dimension, computing the stabilizer entropy of 2D TN states is #P-hard for any integer α≥ 2, and deciding stabilizer membership is C_=P-complete. The corresponding constant-accuracy problems remain C_= P-hard. We further prove that deciding whether a PEPS can be transformed into a stabilizer state by local unitaries over a specified bipartition is C_= P-hard. Under standard complexity assumptions, these results rule out classical or quantum algorithms with polynomial resources for all three tasks in the worst case.
ER -