Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.31459

Nonstabilizerness of quantum tensor network states is intractable in two dimensions

Gianluca Esposito, Georgios Styliaris

quant-phcond-mat.str-elSubmitted Sep 25, 2026• Announced Sep 28, 2026• 0 citations• Revised Oct 2, 2026 (v2)
v1 · Sep 25, 2026v2 · Oct 2, 2026v3 · Oct 5, 2026
arXivHTMLPDF

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 $\#\mathrm{P}$-hard for any integer $α\ge 2$, and deciding stabilizer membership is $\mathrm{C_=P}$-complete. The corresponding constant-accuracy problems remain $\mathrm{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 $\mathrm{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.

Comments
5 pages main text, 25 pages appendix. v2: added references, new results on local stabilizer equivalence

Related papers

Approximating Local Properties by Tensor Network States With Constant Bond Dimension

Yichen Huang

Classical simulation of quantum many-body systems is a fundamental challenge due to their exponentially large Hilbert spaces. Tensor network states are a powerful ansatz to efficiently represent many physically relevant quantum states. A key question is the bond dimension—which determines the number of parameters in the ansatz—required to approximate all local properties to accuracy δ. In one dimension, we prove that an area law for the Rényi entanglement entropyRαwith index αRα(αeO(1/δ). In both one and two dimensions, analogous results are obtained for states with logarithmic corrections to the area law. These findings rigorously justify the common practice of using a system-size-independent bond dimension in tensor network simulations.

arXiv:1903.10048•IEEE Transactions on Information Theory•May 18, 2026•10 citations

Quantifying nonstabilizerness of matrix product states

Tobias Haug, Lorenzo Piroli

Nonstabilizerness, also known as magic, quantifies the number of non-Clifford operations needed to prepare a quantum state. As typical measures either involve minimization procedures or a computational cost exponential in the number of qubits $N$, it is notoriously hard to characterize for many-body states. In this paper, we show that nonstabilizerness, as quantified by the recently introduced stabilizer R\'enyi entropies (SREs), can be computed efficiently for matrix product states (MPSs). Specifically, given an MPS of bond dimension $\ensuremath{\chi}$ and integer R\'enyi index $n>1$, we show that the SRE can be expressed in terms of the norm of an MPS with bond dimension ${\ensuremath{\chi}}^{2n}$. For translation-invariant states, this allows us to extract it from a single tensor, the transfer matrix, while for generic MPSs this construction yields a computational cost linear in $N$ and polynomial in $\ensuremath{\chi}$. We exploit this observation to revisit the study of ground-state nonstabilizerness in the quantum Ising chain, providing accurate numerical results up to large system sizes. We analyze the SRE near criticality and investigate its dependence on the local computational basis, showing that it is, in general, not maximal at the critical point.

arXiv:2207.13076•Physical review. B./Physical review. B•Jan 27, 2023•118 citations

Nonstabilizerness of neural quantum states

Alessandro Sinibaldi, Antonio Francesco Mello, Mario Collura +1 more

We introduce a methodology to estimate nonstabilizerness or “magic,” a key resource for quantum complexity, with neural quantum states (NQS). Our framework relies on two schemes based on Monte Carlo sampling to quantify nonstabilizerness via stabilizer Rényi entropy (SRE) in arbitrary variational wave functions. When combined with NQS, this approach is effective for systems with strong correlations and in dimensions larger than one, unlike tensor network methods. First, we study the magic content in an ensemble of random NQS, demonstrating that neural network parametrizations of the wave function capture finite nonstabilizerness besides large entanglement. Second, we investigate the nonstabilizerness in the ground state of the J 1 − J 2 Heisenberg model. In one dimension, we find that the SRE vanishes at the Majumdar-Ghosh point J 2 = J 1 / 2 , consistent with a stabilizer ground state. In two dimensions, a dip in the SRE is observed near maximum frustration around J 2 / J 1 ≈ 0.6 , suggesting a valence bond solid between the two antiferromagnetic phases.

arXiv:2502.09725•Physical Review Research•Nov 12, 2025•8 citations

Predicting Magic from Very Few Measurements

J. M. Varela, L. L. Keller, A. de Oliveira Junior +3 more

The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of $m$ $n$-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements $m$ and polynomial in the number of qubits $n$. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless $\mathrm{P} = \mathrm{NP}$, no algorithm polynomial in $m$ can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.

quant-pharXiv:2602.18939•Feb 24, 2026•0 citations

Area laws and efficient descriptions of quantum many-body states

Yimin Ge, Jens Eisert

It is commonly believed that area laws for entanglement entropies imply that a quantum many-body state can be faithfully represented by efficient tensor network states - a conjecture frequently stated in the context of numerical simulations and analytical considerations. In this work, we show that this is in general not the case, except in one dimension. We prove that the set of quantum many-body states that satisfy an area law for all Renyi entropies contains a subspace of exponential dimension. Establishing a novel link between quantum many-body theory and the theory of communication complexity, we then show that there are states satisfying area laws for all Renyi entropies but cannot be approximated by states with a classical description of small Kolmogorov complexity, including polynomial projected entangled pair states (PEPS) or states of multi-scale entanglement renormalisation (MERA). Not even a quantum computer with post-selection can efficiently prepare all quantum states fulfilling an area law, and we show that not all area law states can be eigenstates of local Hamiltonians. We also prove translationally invariant and isotropic instances of these results, and show a variation with decaying correlations using quantum error-correcting codes.

arXiv:1411.2995•Nov 11, 2014•5 citations

Area laws and efficient descriptions of quantum many-body states

Yimin Ge, Jens Eisert

It is commonly believed that area laws for entanglement entropies imply that a quantum many-body state can be faithfully represented by efficient tensor network states—a conjecture frequently stated in the context of numerical simulations and analytical considerations. In this work, we show that this is in general not the case, except in one-dimension. We prove that the set of quantum many-body states that satisfy an area law for all Renyi entropies contains a subspace of exponential dimension. We then show that there are states satisfying area laws for all Renyi entropies but cannot be approximated by states with a classical description of small Kolmogorov complexity, including polynomial projected entangled pair states or states of multi-scale entanglement renormalisation. Not even a quantum computer with post-selection can efficiently prepare all quantum states fulfilling an area law, and we show that not all area law states can be eigenstates of local Hamiltonians. We also prove translationally and rotationally invariant instances of these results, and show a variation with decaying correlations using quantum error-correcting codes.

New Journal of Physics•Aug 5, 2016•53 citations
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\#\mathrm{P}#P-hard for any integer α≥2α\ge 2α≥2, and deciding stabilizer membership is C=P\mathrm{C_=P}C=​P-complete. The corresponding constant-accuracy problems remain C=P\mathrm{C_= P}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\mathrm{C_= P}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.
Classical simulation of quantum many-body systems is a fundamental challenge due to their exponentially large Hilbert spaces. Tensor network states are a powerful ansatz to efficiently represent many physically relevant quantum states. A key question is the bond dimension—which determines the number of parameters in the ansatz—required to approximate all local properties to accuracy δ. In one dimension, we prove that an area law for the Rényi entanglement entropyRαwith index αRα(αeO(1/δ). In both one and two dimensions, analogous results are obtained for states with logarithmic corrections to the area law. These findings rigorously justify the common practice of using a system-size-independent bond dimension in tensor network simulations.
Nonstabilizerness, also known as magic, quantifies the number of non-Clifford operations needed to prepare a quantum state. As typical measures either involve minimization procedures or a computational cost exponential in the number of qubits NNN, it is notoriously hard to characterize for many-body states. In this paper, we show that nonstabilizerness, as quantified by the recently introduced stabilizer R\'enyi entropies (SREs), can be computed efficiently for matrix product states (MPSs). Specifically, given an MPS of bond dimension $\ensuremath{\chi}$ and integer R\'enyi index n>1n>1n>1, we show that the SRE can be expressed in terms of the norm of an MPS with bond dimension ${\ensuremath{\chi}}^{2n}$. For translation-invariant states, this allows us to extract it from a single tensor, the transfer matrix, while for generic MPSs this construction yields a computational cost linear in NNN and polynomial in $\ensuremath{\chi}$. We exploit this observation to revisit the study of ground-state nonstabilizerness in the quantum Ising chain, providing accurate numerical results up to large system sizes. We analyze the SRE near criticality and investigate its dependence on the local computational basis, showing that it is, in general, not maximal at the critical point.
We introduce a methodology to estimate nonstabilizerness or “magic,” a key resource for quantum complexity, with neural quantum states (NQS). Our framework relies on two schemes based on Monte Carlo sampling to quantify nonstabilizerness via stabilizer Rényi entropy (SRE) in arbitrary variational wave functions. When combined with NQS, this approach is effective for systems with strong correlations and in dimensions larger than one, unlike tensor network methods. First, we study the magic content in an ensemble of random NQS, demonstrating that neural network parametrizations of the wave function capture finite nonstabilizerness besides large entanglement. Second, we investigate the nonstabilizerness in the ground state of the J 1 − J 2 Heisenberg model. In one dimension, we find that the SRE vanishes at the Majumdar-Ghosh point J 2 = J 1 / 2 , consistent with a stabilizer ground state. In two dimensions, a dip in the SRE is observed near maximum frustration around J 2 / J 1 ≈ 0.6 , suggesting a valence bond solid between the two antiferromagnetic phases.
The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of mmm nnn-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements mmm and polynomial in the number of qubits nnn. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless P=NP\mathrm{P} = \mathrm{NP}P=NP, no algorithm polynomial in mmm can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.
It is commonly believed that area laws for entanglement entropies imply that a quantum many-body state can be faithfully represented by efficient tensor network states - a conjecture frequently stated in the context of numerical simulations and analytical considerations. In this work, we show that this is in general not the case, except in one dimension. We prove that the set of quantum many-body states that satisfy an area law for all Renyi entropies contains a subspace of exponential dimension. Establishing a novel link between quantum many-body theory and the theory of communication complexity, we then show that there are states satisfying area laws for all Renyi entropies but cannot be approximated by states with a classical description of small Kolmogorov complexity, including polynomial projected entangled pair states (PEPS) or states of multi-scale entanglement renormalisation (MERA). Not even a quantum computer with post-selection can efficiently prepare all quantum states fulfilling an area law, and we show that not all area law states can be eigenstates of local Hamiltonians. We also prove translationally invariant and isotropic instances of these results, and show a variation with decaying correlations using quantum error-correcting codes.
It is commonly believed that area laws for entanglement entropies imply that a quantum many-body state can be faithfully represented by efficient tensor network states—a conjecture frequently stated in the context of numerical simulations and analytical considerations. In this work, we show that this is in general not the case, except in one-dimension. We prove that the set of quantum many-body states that satisfy an area law for all Renyi entropies contains a subspace of exponential dimension. We then show that there are states satisfying area laws for all Renyi entropies but cannot be approximated by states with a classical description of small Kolmogorov complexity, including polynomial projected entangled pair states or states of multi-scale entanglement renormalisation. Not even a quantum computer with post-selection can efficiently prepare all quantum states fulfilling an area law, and we show that not all area law states can be eigenstates of local Hamiltonians. We also prove translationally and rotationally invariant instances of these results, and show a variation with decaying correlations using quantum error-correcting codes.