arXiv:2609.31459
Nonstabilizerness of quantum tensor network states is intractable in two dimensions
Gianluca Esposito, Georgios Styliaris
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.
AI Summary
The paper asks whether the compact description of a two-dimensional tensor-network state makes its nonstabilizerness tractable to evaluate. It studies stabilizer Rényi entropies and stabilizer membership for nonzero, rational-entry qubit PEPS on square lattices, contrasting them with polynomial-time evaluation of fixed-integer-order stabilizer entropies for one-dimensional MPS. For every fixed integer $\alpha\ge2$, evaluating the stabilizer $\alpha$-Rényi entropy to sufficiently many polynomially bounded binary digits is $\#\mathrm{P}$-hard already at bond dimension $D=4$, and is computable with a $\#\mathrm{P}$ oracle and polynomial-time postprocessing. Constant-additive-accuracy estimation is $\mathrm{C}_{=}\mathrm{P}$-hard at $D=33$; for $\alpha=2$, error $1/100$ suffices. Exact stabilizer membership is $\mathrm{C}_{=}\mathrm{P}$-complete at $D=33$. Approximate membership remains hard with a constant distance promise gap, including completeness for distance zero versus at least $1/16$. Deciding equivalence to a stabilizer state under arbitrary unitaries acting separately on a specified bipartition is also $\mathrm{C}_{=}\mathrm{P}$-hard. The reductions encode Boolean counts or differences of counts into scalar tensor contractions, then into one- or two-qubit amplitude ratios of PEPS. A rational saturation gadget converts zero versus nonzero integer counts into constant observable gaps. The hard instances can therefore represent product states, or states entangled only between two marked qubits. These are worst-case results for tensor descriptions, not typical physically generated states. Additional restrictions—including injectivity, translation invariance, and uniformly gapped parent Hamiltonians—remain open, as does $\#\mathrm{P}$-hardness at constant additive accuracy.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 5 pages main text, 25 pages appendix. v2: added references, new results on local stabilizer equivalence