We study the problem of approximating the Ising model partition function with complex parameters on bounded degree graphs. We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. Furthermore, we prove that for this class of Ising models the partition function does not vanish. Our algorithm is based on an approach due to Barvinok for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts for efficiently computing the leading coefficients of graph polynomials on bounded degree graphs. Finally, we show how our algorithm can be extended to approximate certain output probability amplitudes of quantum circuits.
 G. De las Cuevas, W. Dür, M. Van den Nest, and M. A. Martin-Delgado, New Journal of Physics 13, 093021 (2011), arXiv:1104.2517.
 F. Jaeger, D. L. Vertigan, and D. J. Welsh, in Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 108 (Cambridge Univ Press, 1990) pp. 35–53.
 X. Gao, S.-T. Wang, and L.-M. Duan, Physical Review Letters 118, 040502 (2017), arXiv:1607.04947.
 S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics 14, 595 (2018), arXiv:1608.00263.
 D. Shepherd and M. J. Bremner, Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 465, 1413 (2009), arXiv:0809.0847.
 M. J. Bremner, A. Montanaro, and D. J. Shepherd, Physical Review Letters 117, 080501 (2016), arXiv:1504.07999.
 M. J. Bremner, R. Jozsa, and D. J. Shepherd, in Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences (The Royal Society, 2010) p. rspa20100301, arXiv:1005.1407.
 L. Eldar and S. Mehraban, in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2018) pp. 23–34, arXiv:1711.09457.
 P. Hell and J. Nešetřil, Graphs and homomorphisms (Oxford University Press, 2004).
 M. Dyer and C. Greenhill, Random Structures and Algorithms 17, 260 (2000).
 J.-Y. Cai, X. Chen, and P. Lu, in International Colloquium on Automata, Languages, and Programming (Springer, 2010) pp. 275–286, arXiv:0903.4728.
 Sergey Bravyi, David Gosset, and Ramis Movassagh, "Classical algorithms for quantum mean values", Nature Physics 17 3, 337 (2021).
 Andreas Galanis, Leslie A. Goldberg, and Andres Herrera-Poyatos, "The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs", SIAM Journal on Discrete Mathematics 36 3, 2159 (2022).
 Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava, "Fisher zeros and correlation decay in the Ising model", Journal of Mathematical Physics 60 10, 103304 (2019).
 Ryan L. Mann and Tyler Helmuth, "Efficient algorithms for approximating quantum partition functions", Journal of Mathematical Physics 62 2, 022201 (2021).
 Pjotr Buys, Andreas Galanis, Viresh Patel, and Guus Regts, "Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs", Forum of Mathematics, Sigma 10, e7 (2022).
The above citations are from Crossref's cited-by service (last updated successfully 2023-09-28 07:45:23) and SAO/NASA ADS (last updated successfully 2023-09-28 07:45:24). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.