Classifying universal versus classically simulatable resources among the stabilizer states of the classical spin–quantum mapping (Hübener–Van den Nest–Dür–Briegel)

The mapping of Hübener, Van den Nest, Dür and Briegel (J. Math. Phys. 50, 083303 (2009)) expresses partition functions and correlation functions of arbitrary $q$-state classical spin models — inhomogeneous pairwise interactions and, in extended encodings, $m$-body terms — as overlaps between graph-determined stabilizer states $|\psi_G\rangle$ and $|\varphi_G\rangle$ and product states that encode the couplings and temperature. Because squared overlaps are probabilities of local measurements, the mapping ties the classical solvability of a spin model to the quantum computational power of the associated stabilizer state as a resource for measurement-based quantum computation (MQC): solvable models (1D Ising, 2D Ising without field) map to simulatable resources (GHZ, 1D cluster, toric-code states), while the NP-hard 2D Ising model with fields maps to the universal 2D (decorated) cluster state. The paper explicitly poses the resulting classification problem: which states among the $|\psi_G\rangle$ and $|\varphi_G\rangle$ are universal resource states for MQC, and which are fully classically simulatable? This problem remains open. Necessary conditions (unbounded entanglement width) and sufficient ones (2D-grid-type structure) are known, and several family members are classified, but no complete classification exists for these families or even for general graph states: a 2021 review describes the characterization of universal resources as lacking a systematic approach, and in 2025 circle graph states — graph states of circle graphs, the intersection graphs of chords of a circle, which satisfy the known necessary condition — were proven not to be efficiently universal, showing the gap between known necessary and sufficient conditions persists.

Background

A classical $q$-state spin system on an interaction graph $G$ (vertices are spin sites, edges are interacting pairs) has partition function $Z_G=\sum_{\mathbf{s}}e^{-\beta H(\mathbf{s})}$, which encodes its thermodynamics and correlations. Exact evaluation is intractable in general: already the Ising model on a 2D square lattice in an external field is NP-hard (Barahona 1982). A line of work initiated by Van den Nest, Dür and Briegel (Phys. Rev. Lett. 98, 117207 (2007)) and generalized in the source paper of this problem (Hübener, Van den Nest, Dür, Briegel, J. Math. Phys. 50, 083303 (2009)) rewrites such partition functions as quantum amplitudes. The relevant quantum formalism is the stabilizer formalism: an abelian subgroup of the Pauli group on $N$ qudits ($q$-level systems) that excludes $-\mathbb{1}$ and has size $q^N$ uniquely determines a pure state, called a stabilizer state; a graph state is the stabilizer state fixed by one generator per vertex of a graph, each acting with Pauli $X$ on that vertex and Pauli $Z$ on each of its neighbors, a cluster state is the graph state of a regular lattice, and a GHZ state is the maximally correlated state $\sum_j |j\rangle^{\otimes N}$. Fixing an orientation of $G$, with incidence matrix $B^{\sigma}$ (the vertex-by-edge matrix whose column for an edge carries entries $\pm 1$ at its two oriented endpoints), the source paper associates to $G$ two stabilizer states: $|\psi_G\rangle$, with one qudit per edge of $G$ and stabilizer generators of $X(v)Z(u)$ form with $v$ in the cut space of $G$ (the row space of $B^{\sigma}$ over $\mathbb{Z}_q$) and $u$ in the cycle space (the orthogonal complement of the cut space); and the decorated state $|\varphi_G\rangle$, with one qudit per vertex and per edge of $G$. All interaction strengths, local fields and the temperature enter a product state $|\alpha\rangle$, and $Z_G$ equals the overlap $\langle\alpha|\eta_G\rangle$ where $|\eta_G\rangle$ denotes either construction. Extended encodings (products of GHZ-type entangled states over edge subsets) cover $m$-body interactions with each site in at most $n$ terms, though the contraction cost then scales unfavorably in $m$ and $n$. The key computational link is measurement-based (one-way) quantum computation (MQC), in which a computation is driven solely by adaptive local single-qudit measurements on a prepared entangled resource state; a family of resource states is universal if every quantum computation on polynomially many qubits can be simulated on family members of polynomially related size with polynomial overhead. The 2D cluster state is universal (Raussendorf and Briegel 2001); 1D cluster states, GHZ states and the toric code state (the topological surface-code ground state of Kitaev's toric code, which is $|\psi_G\rangle$ for a 2D square lattice) are efficiently classically simulatable resources. Crucially, Gottesman–Knill-type simulatability covers only Pauli measurements, whereas universality of a resource hinges on non-Pauli adaptive measurements — whose outcome probabilities are, via the mapping above, exactly the partition functions of the associated classical model. Hence a classically solvable model yields a simulatable resource (Bravyi and Raussendorf 2007 proved simulatability for planar/toric code states via exactly this route), while the NP-hard 2D Ising model with fields corresponds to the universal 2D (decorated) cluster state. On the classical side, the source paper also proves that all inhomogeneous $q$-state models on graphs of tree-width scaling logarithmically in system size (tree-width measures how close a graph is to a tree; Markov and Shi 2008 showed such parameters govern tensor-network contraction cost) can be evaluated exactly in polynomial time via a tree-tensor-network construction — a sufficient criterion with no necessity claim, since planar zero-field models are exactly solvable at unbounded tree-width. For universal graph-state resources, a necessary condition is unbounded entanglement width (a multi-partite entanglement measure defined via the Schmidt ranks appearing across successive bipartitions of the qubits; Van den Nest, Miyake, Dür and Briegel 2006, 2007). The source paper poses, at the end of its applications section, the following classification question: which states among the $|\psi_G\rangle$ and $|\varphi_G\rangle$ are universal resource states for MQC, and which are fully simulatable classically.

Problem Statement

For the stabilizer states $|\eta_G\rangle\in\{|\psi_G\rangle,|\varphi_G\rangle\}$ that the classical-spin–stabilizer mapping associates to arbitrary interaction graphs $G$ and local dimension $q$, determine which are universal resource states for measurement-based quantum computation and which are fully classically simulatable. Concretely: classify the families $\{|\eta_G\rangle\}$, as $G$ ranges over graph families of growing size for each $q$, into (i) universal resource families, meaning that adaptive single-qudit measurements on family members can efficiently simulate arbitrary quantum computations with polynomial overhead; and (ii) efficiently classically simulatable families, meaning that the outcome probabilities of arbitrary adaptive single-qudit measurement sequences — equivalently, via the mapping, the associated classical partition functions — can be computed exactly in classical polynomial time (sequential sampling of these probabilities then also yields efficient sampling of measurement outcomes). A complete classification would cover both constructions ($|\psi_G\rangle$ and $|\varphi_G\rangle$), general graph classes (planar and non-planar, bounded and unbounded degree), and general local dimension $q$; graph-theoretic formulations (for example in terms of large grid minors, where $G$ contains a rectangular grid as a graph minor; vertex-minor structure, where graphs are related by sequences of local complementations and vertex deletions; or entanglement-width-type structure) are natural candidates but are not required. A resolution need not attain that full scope, but it must state exactly which restriction it proves — naming the construction(s), the graph class, and the local dimension $q$ it covers — and why the remaining cases are not covered by the same argument. Known partial results in the literature include: unbounded entanglement width is necessary but not sufficient (circle graph states — graph states of circle graphs, the intersection graphs of chords of a circle — have unbounded entanglement width yet are efficiently simulatable); 2D-grid-type graphs give universal resources (2D cluster states); planar/toric-code states are simulatable when the measured and unmeasured qubit regions are connected, and surface-code states on genus-$g$ surfaces are simulatable at cost $2^{2g}$.

References

1. R. Hübener, M. Van den Nest, W. Dür, H. J. Briegel, 'Classical spin systems and the quantum stabilizer formalism: general mappings and applications', Journal of Mathematical Physics 50, 083303 (2009). DOI: 10.1063/1.3190486, arXiv:0812.2127. https://doi.org/10.1063/1.3190486
2. M. Van den Nest, W. Dür, H. J. Briegel, 'Classical Spin Models and the Quantum-Stabilizer Formalism', Physical Review Letters 98, 117207 (2007). DOI: 10.1103/PhysRevLett.98.117207. https://doi.org/10.1103/PhysRevLett.98.117207
3. F. Barahona, 'On the computational complexity of Ising spin glass models', Journal of Physics A: Mathematical and General 15, 3241 (1982). DOI: 10.1088/0305-4470/15/10/028. https://doi.org/10.1088/0305-4470/15/10/028
4. R. Raussendorf, H. J. Briegel, 'A One-Way Quantum Computer', Physical Review Letters 86, 5188 (2001). DOI: 10.1103/PhysRevLett.86.5188. https://doi.org/10.1103/PhysRevLett.86.5188
5. S. Bravyi, R. Raussendorf, 'Measurement-based quantum computation with the toric code states', Physical Review A 76, 022304 (2007). DOI: 10.1103/PhysRevA.76.022304. https://doi.org/10.1103/PhysRevA.76.022304
6. M. Van den Nest, A. Miyake, W. Dür, H. J. Briegel, 'Universal Resources for Measurement-Based Quantum Computation', Physical Review Letters 97, 150504 (2006). DOI: 10.1103/PhysRevLett.97.150504. https://doi.org/10.1103/PhysRevLett.97.150504
7. M. Van den Nest, W. Dür, A. Miyake, H. J. Briegel, 'Fundamentals of universality in one-way quantum computation', New Journal of Physics 9, 204 (2007). DOI: 10.1088/1367-2630/9/6/204. https://doi.org/10.1088/1367-2630/9/6/204
8. M. Van den Nest, W. Dür, G. Vidal, H. J. Briegel, 'Classical simulation versus universality in measurement-based quantum computation', Physical Review A 75, 012337 (2007). DOI: 10.1103/PhysRevA.75.012337. https://doi.org/10.1103/PhysRevA.75.012337
9. I. L. Markov, Y. Shi, 'Simulating Quantum Computation by Contracting Tensor Networks', SIAM Journal on Computing 38, 963 (2008). DOI: 10.1137/050644756. https://doi.org/10.1137/050644756
10. G. De las Cuevas, W. Dür, M. Van den Nest, H. J. Briegel, 'Completeness of classical spin models and universal quantum computation', Journal of Statistical Mechanics: Theory and Experiment P07001 (2009). DOI: 10.1088/1742-5468/2009/07/P07001. https://doi.org/10.1088/1742-5468/2009/07/P07001
11. M. Kargarian, H. Bombin, M. A. Martin-Delgado, 'Topological color codes and two-body quantum lattice Hamiltonians', New Journal of Physics 12, 025018 (2010). DOI: 10.1088/1367-2630/12/2/025018. https://doi.org/10.1088/1367-2630/12/2/025018
12. A. G. D'Souza, J. Briët, D. L. Feder, 'Testing equivalence of pure quantum states and graph states under SLOCC', International Journal of Quantum Information 8, 395 (2010). DOI: 10.1142/S0219749910006368. https://doi.org/10.1142/S0219749910006368
13. Y. Xu, G. De las Cuevas, W. Dür, H. J. Briegel, M. A. Martin-Delgado, 'The U(1) lattice gauge theory universally connects all classical models with continuous variables, including background gravity', Journal of Statistical Mechanics: Theory and Experiment P02013 (2011). DOI: 10.1088/1742-5468/2011/02/P02013. https://doi.org/10.1088/1742-5468/2011/02/P02013
14. V. Karimipour, M. H. Zarei, 'Completeness of classical $\phi^4$ theory on two-dimensional lattices', Physical Review A 85, 032316 (2012). DOI: 10.1103/PhysRevA.85.032316. https://doi.org/10.1103/PhysRevA.85.032316
15. V. Karimipour, M. H. Zarei, 'Algorithmic proof for the completeness of the two-dimensional Ising model', Physical Review A 86, 052303 (2012). DOI: 10.1103/PhysRevA.86.052303. https://doi.org/10.1103/PhysRevA.86.052303
16. L. Goff, R. Raussendorf, 'Classical simulation of measurement-based quantum computation on higher-genus surface-code states', Physical Review A 86, 042301 (2012). DOI: 10.1103/PhysRevA.86.042301. https://doi.org/10.1103/PhysRevA.86.042301
17. G. De las Cuevas, 'A quantum information approach to statistical mechanics', Journal of Physics B: Atomic, Molecular and Optical Physics 46, 243001 (2013). DOI: 10.1088/0953-4075/46/24/243001. https://doi.org/10.1088/0953-4075/46/24/243001
18. K. Fujii, T. Morimae, 'Commuting quantum circuits and complexity of Ising partition functions', New Journal of Physics 19, 033003 (2017). DOI: 10.1088/1367-2630/aa5fdb. https://doi.org/10.1088/1367-2630/aa5fdb
19. M. H. Zarei, A. Montakhab, 'Dual correspondence between classical spin models and quantum Calderbank-Shor-Steane states', Physical Review A 98, 012337 (2018). DOI: 10.1103/PhysRevA.98.012337. https://doi.org/10.1103/PhysRevA.98.012337
20. H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, M. Van den Nest, 'Measurement-based quantum computation', Nature Physics 5, 19 (2009). DOI: 10.1038/nphys1157. https://doi.org/10.1038/nphys1157
21. T.-C. Wei, 'Measurement-Based Quantum Computation', Oxford Research Encyclopedia of Physics, Oxford University Press (2021). DOI: 10.1093/acrefore/9780190871994.013.31, arXiv:2109.10111. https://doi.org/10.1093/acrefore/9780190871994.013.31
22. B. Harrison, V. Iyer, O. Parekh, K. Thompson, A. Zhao, 'Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources', arXiv:2510.05557 (2025). https://arxiv.org/abs/2510.05557
23. F. Hahn, R. McCarty, H. P. Nautrup, N. Claudet, 'The Structure of Circle Graph States', arXiv:2603.08847 (2026). https://arxiv.org/abs/2603.08847