Completing the solvability–simulability correspondence between classical spin models and quantum circuits: integrability, approximate solutions, positive Boltzmann weights, and non-unitary circuits

A 2008 framework of Van den Nest, Dür, Raussendorf, and Briegel maps the partition function of a classical lattice spin model to a quantum circuit amplitude, $Z^{L,R}_{\mathrm{vm}}=\langle L|C|R\rangle$, with each local Boltzmann-weight matrix read as a quantum gate. Read one way, exactly solvable classical models yield efficiently classically simulable quantum gate sets (matchgates from the free-fermion eight-vertex model; 3-local gates from the 32-vertex model on a tilted triangular lattice); read the other way, unitary weight matrices give Hadamard-test quantum algorithms that additively approximate partition functions — with BQP-completeness results that, however, require negative or complex Boltzmann weights. The authors' outlook left open three linked challenges — incorporating Yang–Baxter-equation and Bethe-ansatz integrability into the framework; extending to the physical regime of real, positive Boltzmann weights; and determining when approximate classical solvability of partition functions suffices for efficient simulation of the corresponding circuits — and pointed to a further direction: extending the framework's simulability results, which the source notes are not restricted to unitary quantum circuits, to non-unitary (including postselected) circuit families. Since that work, the positive-weight and non-unitary axes have advanced, through quantum Gibbs-sampling and simulated-annealing algorithms with conditional guarantees and through PostBQP-type characterizations respectively, while approximate-solvability limits are bounded by BQP-completeness of approximate tensor-network contraction and polynomial-hierarchy collapse barriers; braid circuits built from certain unitary Yang–Baxter gates are efficiently classically simulable by direct circuit compression rather than via classical-model solvability. Integrability-based solvability has not been incorporated into the mapping, and a general simulable-versus-quantum-hard boundary for model-derived circuit families is not established: the problem remains open.

Background

A classical lattice spin model assigns to each configuration $s$ of discrete variables a product of local Boltzmann weights, and its partition function $Z=\sum_s\prod_a w_a(s)$ sums this product over all configurations; the weights are called physical when they are real and positive, $w_a=e^{-\beta E_a}$, but the same mathematics admits negative or complex weights. A vertex model is a classical lattice model whose variables live on edges, with the local Boltzmann weights at each site organized into a matrix indexed by the surrounding edge configurations. A model is called exactly solvable when $Z$ can be evaluated in time polynomial in the system size — famously true for the two-dimensional Ising model without fields, for the eight-vertex model under the free-fermion condition (a linear constraint on the weights that makes the model mappable to non-interacting fermions), and for the 32-vertex model on a tilted triangular lattice, again via free fermions.

On the quantum side, BQP (bounded-error quantum polynomial time) is the class of problems solvable efficiently on a quantum computer. A family of quantum circuits is efficiently classically simulable when quantities such as amplitudes $\langle L|C|R\rangle$ (a strong simulation) or output distributions can be computed to polynomial precision by a classical polynomial-time algorithm. The paradigmatic example is Valiant's matchgates: two-qubit gates $G(A,B)$ acting as the single-qubit unitaries $A$ and $B$ on the even and odd parity subspaces of two qubits, restricted to nearest-neighbor qubit lines, simulable precisely because the Jordan–Wigner transform (a standard rewriting of spin operators as fermionic operators) maps them to non-interacting fermions.

Van den Nest, Dür, Raussendorf, and Briegel observed that both pictures are readings of one identity: the partition function of a classical vertex or edge model on a tilted lattice, with boundary conditions fixed by classical states $L$ and $R$, equals a quantum circuit amplitude,

$$Z^{L,R}_{\mathrm{vm}}=\langle L|C|R\rangle$$

where each local Boltzmann-weight matrix of the classical model is interpreted as a (possibly $k$-local) quantum gate $w_a$. Read one way, any classically solvable model (efficiently computable $Z$) yields a class of efficiently simulable quantum circuits — recovering matchgate simulability from the free-fermion eight-vertex model and producing simulable 3-local gate sets from the 32-vertex model. Read the other way, whenever the weight matrices $w_a$ are unitary, the Hadamard test (a standard quantum subroutine estimating the real or imaginary part of an amplitude) gives an efficient quantum algorithm approximating $Z$ additively, i.e. returning a number within a prescribed additive error such as $p(N)^{-1}$ in polynomial time; the authors proved such additive approximation BQP-complete (as hard as arbitrary quantum computation) for the six-vertex model and a two-dimensional Ising-type model. Concurrent work connected quantum computation to tensor networks on the same grounds: Arad and Landau showed that quantum computation and additive approximation of tensor-network values are polynomially interreducible, and Schuch, Wolf, Verstraete, and Cirac proved that approximating projected entangled pair states (two-dimensional tensor networks) is likewise BQP-complete.

Two structural limitations motivated the open problem. First, the Hadamard-test reading needs the local matrices $w_a$ to be unitary, and unitarity is in tension with physical positivity: a real orthogonal matrix with nonnegative entries is necessarily a permutation matrix, so strictly positive Boltzmann weights cannot furnish nontrivial unitary gates of this form. The known constructions therefore live in regimes where some weights are negative or complex, outside the physically relevant ensemble. Second, all solvable models used in the construction are free-fermion solvable; the grand machinery of integrability was left outside the framework. The Yang–Baxter equation (YBE) is the consistency condition guaranteeing that transfer matrices (the matrices propagating one row of the lattice to the next, whose traces build the partition function) built from local $R$-matrices commute, which underlies exact solvability and the Bethe ansatz, an exact solution method for interacting one-dimensional quantum and two-dimensional classical models. But YBE solutions typically hold in the thermodynamic limit, in restricted parameter regimes, and for systems with high translational symmetry, whereas the circuits in the mapping are finite, site-dependent objects.

Two further facts frame the boundary question. Allowing postselected measurements (keeping only runs with a prescribed outcome) boosts quantum computation from BQP to PostBQP, which Aaronson showed equals PP, the class of decision problems solvable in polynomial time with unbounded error — so postselected analogues of simulable circuit classes can be dramatically more powerful. And approximating partition functions is #P-hard in general (with #P the class of counting problems), so no blanket efficiency can be expected; the question is precisely which solvability notions, parameter regimes, and circuit classes lie on which side of the classical/quantum divide.

Problem Statement

Extend the solvability–simulability correspondence of Van den Nest, Dür, Raussendorf, and Briegel beyond free-fermion-solvable models and beyond the complex parameter regimes. The common objective is to characterize when solvability of a classical spin model — exact or approximate, free-fermion or integrability-based — translates into efficient classical simulation of the associated quantum circuits, or into efficient quantum treatment of the classical model, and thereby to locate the boundary between classically simulable and quantum-hard regimes for circuit families derived from classical spin models. Concretely, the source's outlook lists the following four open challenges as independent sub-problems: each is separately attackable, and a genuine advance resolving any one of them counts as a solution to this task, while the overarching characterization stated above is the motivating objective rather than an additional completion requirement. They are:

(i) Integrability: incorporate Yang–Baxter-equation and Bethe-ansatz solvability into the mapping framework, i.e. construct finite-size, possibly non-translation-invariant circuit families whose efficient classical simulability follows from the integrability of an underlying classical model — resolving how the thermodynamic-limit, restricted-parameter, and high-symmetry character of YBE solutions can be reconciled with the finite, site-dependent circuits of the mapping.

(ii) Physical regime: obtain quantum algorithms that treat classical spin systems with real, positive Boltzmann weights (rather than the negative or complex weights currently required for the local weight matrices to be unitary), on an approximation scale under which the guarantee is nontrivial (not exponentially suppressed), so that a quantum computer can be used to simulate physically relevant classical spin systems.

(iii) Approximate solvability: determine to what extent approximate classical solutions of partition functions — as opposed to exact solvability — can be used within the framework to obtain efficient classical simulations of the corresponding quantum circuits, including whether approximate YBE-based solutions suffice to infer simulability of the associated circuits; such work may also identify where approximation-based simulation provably fails.

(iv) Non-unitary circuits: extend the framework's simulability results to non-unitary circuit families, for example those arising from non-positive Boltzmann weights or describing postselected quantum computation; the source notes that many of its simulability results are not restricted to unitary quantum circuits and that efficient classical simulation of certain non-unitary circuits can be achieved in a similar way.

References

1. M. Van den Nest, W. Dür, R. Raussendorf, H. J. Briegel, 'Quantum algorithms for spin models and simulable gate sets for quantum computation', Physical Review A 80, 052334 (2009). DOI: 10.1103/PhysRevA.80.052334, arXiv:0805.1214. https://arxiv.org/abs/0805.1214
2. L. G. Valiant, 'Quantum Circuits That Can Be Simulated Classically in Polynomial Time', SIAM Journal on Computing 31, 1229 (2002). DOI: 10.1137/S0097539700377025. https://doi.org/10.1137/S0097539700377025
3. I. Arad, Z. Landau, 'Quantum computation and the evaluation of tensor networks', arXiv:0805.0040 (2008). https://arxiv.org/abs/0805.0040
4. 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
5. S. Aaronson, 'Quantum computing, postselection, and probabilistic polynomial-time', Proceedings of the Royal Society A 461, 3473 (2005). DOI: 10.1098/rspa.2005.1546, arXiv:quant-ph/0412187. https://arxiv.org/abs/quant-ph/0412187
6. R. Jozsa, A. Miyake, 'Matchgates and classical simulation of quantum circuits', Proceedings of the Royal Society A 464, 3089 (2008). DOI: 10.1098/rspa.2008.0189, arXiv:0804.4050. https://arxiv.org/abs/0804.4050
7. G. De las Cuevas, W. Dür, M. Van den Nest, M. A. Martin-Delgado, 'Quantum algorithms for classical lattice models', New Journal of Physics 13, 093021 (2011). DOI: 10.1088/1367-2630/13/9/093021, arXiv:1104.2517. https://arxiv.org/abs/1104.2517
8. K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, F. Verstraete, 'Quantum Metropolis Sampling', Nature 471, 87 (2011). DOI: 10.1038/nature09770, arXiv:0911.3635. https://arxiv.org/abs/0911.3635
9. R. D. Somma, D. Nagaj, M. Kieferová, 'Quantum Speedup by Quantum Annealing', Physical Review Letters 109, 050501 (2012). DOI: 10.1103/PhysRevLett.109.050501. https://doi.org/10.1103/PhysRevLett.109.050501
10. A. Matsuo, K. Fujii, N. Imoto, 'Quantum algorithm for an additive approximation of Ising partition functions', Physical Review A 90, 022304 (2014). DOI: 10.1103/PhysRevA.90.022304, arXiv:1405.2749. https://arxiv.org/abs/1405.2749
11. 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, arXiv:1311.2128. https://arxiv.org/abs/1311.2128
12. A. W. Harrow, A. Y. Wei, 'Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions', Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) (2020). DOI: 10.1137/1.9781611975994.12. https://doi.org/10.1137/1.9781611975994.12
13. A. N. Chowdhury, R. D. Somma, Y. Subasi, 'Computing partition functions in the one clean qubit model', Physical Review A 103, 032422 (2021). DOI: 10.1103/PhysRevA.103.032422, arXiv:1910.11842. https://arxiv.org/abs/1910.11842
14. S. Arunachalam, V. Havlicek, G. Nannicini, K. Temme, P. Wocjan, 'Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions', Quantum 6, 789 (2022). DOI: 10.22331/q-2022-09-01-789, arXiv:2009.11270. https://arxiv.org/abs/2009.11270
15. A. Cornelissen, Y. Hamoudi, 'A Sublinear-Time Quantum Algorithm for Approximating Partition Functions', Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA) (2023). DOI: 10.1137/1.9781611977554.ch46, arXiv:2207.08643. https://arxiv.org/abs/2207.08643
16. E. C. Rowell, Z. Wang, 'Localization of Unitary Braid Group Representations', Communications in Mathematical Physics 311, 595 (2012). DOI: 10.1007/s00220-011-1386-7, arXiv:1009.0241. https://arxiv.org/abs/1009.0241
17. G. Alagic, A. Bapat, S. Jordan, 'Classical Simulation of Yang-Baxter Gates', Proceedings of the 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014), Leibniz International Proceedings in Informatics 27, 161 (2014). DOI: 10.4230/LIPIcs.TQC.2014.161, arXiv:1407.1361. https://arxiv.org/abs/1407.1361
18. Y. Miao, E. Vernier, 'Integrable Quantum Circuits from the Star-Triangle Relation', Quantum 7, 1160 (2023). DOI: 10.22331/q-2023-11-03-1160, arXiv:2302.12675. https://arxiv.org/abs/2302.12675
19. B. Barch, D. Lidar, 'Computational complexity and simulability of non-Hermitian quantum dynamics', Physical Review Research 8, 033083 (2026). DOI: 10.1103/lhv6-6t1r, arXiv:2506.03435. https://arxiv.org/abs/2506.03435
20. H. Li, Z. Yao, X. Qiu, 'Quantum Annealing Algorithms for Estimating Ising Partition Functions', Physical Review Letters 136, 100601 (2026). DOI: 10.1103/8gmb-p619, arXiv:2504.21666. https://arxiv.org/abs/2504.21666
21. R. Gargiulo, M. Rizzi, R. Zeier, 'Computing Classical Partition Functions: From Onsager and Kaufman to Quantum Algorithms', Proceedings of Recent Advances in Quantum Computing and Technology (2024). DOI: 10.1145/3665870.3665878. https://doi.org/10.1145/3665870.3665878
22. Z. Feng, Z. Liu, F. Lu, N. Wang, 'Quon Classical Simulation: Unifying Cliffords, Matchgates and Entanglement', arXiv:2505.07804 (2025). https://arxiv.org/abs/2505.07804