Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs

Ryan L. Mann and Michael J. Bremner

Centre for Quantum Computation and Communication Technology, Centre for Quantum Software and Information, Faculty of Engineering & Information Technology, University of Technology Sydney, NSW 2007, Australia

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.

► BibTeX data

► References

[1] 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.
https:/​/​doi.org/​10.1088/​1367-2630/​13/​9/​093021
arXiv:1104.2517

[2] 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.
https:/​/​doi.org/​10.1017/​s0305004100068936

[3] L. A. Goldberg and H. Guo, Computational Complexity 26, 765 (2017), arXiv:1409.5627.
https:/​/​doi.org/​10.1007/​s00037-017-0162-2
arXiv:1409.5627

[4] K. Fujii and T. Morimae, New Journal of Physics 19, 033003 (2017), arXiv:1311.2128.
https:/​/​doi.org/​10.1088/​1367-2630/​aa5fdb
arXiv:1311.2128

[5] X. Gao, S.-T. Wang, and L.-M. Duan, Physical Review Letters 118, 040502 (2017), arXiv:1607.04947.
https:/​/​doi.org/​10.1103/​physrevlett.118.040502
arXiv:1607.04947

[6] 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.
https:/​/​doi.org/​10.1038/​s41567-018-0124-x
arXiv:1608.00263

[7] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Physical Review X 8, 021010 (2018), arXiv:1703.00466.
https:/​/​doi.org/​10.1103/​physrevx.8.021010
arXiv:1703.00466

[8] A. Barvinok, Theory of Computing 11, 339 (2015), arXiv:1405.1974.
https:/​/​doi.org/​10.4086/​toc.2015.v011a013
arXiv:1405.1974

[9] A. Barvinok, Foundations of Computational Mathematics 16, 329 (2016a), arXiv:1405.1303.
https:/​/​doi.org/​10.1007/​s10208-014-9243-7
arXiv:1405.1303

[10] A. Barvinok, Combinatorics and complexity of partition functions, Vol. 274 (Springer, 2016).
https:/​/​doi.org/​10.1007/​978-3-319-51829-9

[11] V. Patel and G. Regts, SIAM Journal on Computing 46, 1893 (2017), arXiv:1607.01167.
https:/​/​doi.org/​10.1137/​16m1101003
arXiv:1607.01167

[12] C. Borgs, J. Chayes, J. Kahn, and L. Lovász, Random Structures & Algorithms 42, 1 (2013), arXiv:1002.0115.
https:/​/​doi.org/​10.1002/​rsa.20414
arXiv:1002.0115

[13] A. Barvinok and P. Soberón, Combinatorica 37, 633 (2017), arXiv:1406.1771.
https:/​/​doi.org/​10.1007/​s00493-016-3357-2
arXiv:1406.1771

[14] A. D. Sokal et al., Surveys in Combinatorics 327, 173 (2005), arXiv:math/​0503607.
https:/​/​doi.org/​10.1017/​cbo9780511734885.009
arXiv:math/0503607

[15] J. Liu, A. Sinclair, and P. Srivastava, Journal of Statistical Physics 174, 287 (2019), arXiv:1704.06493.
https:/​/​doi.org/​10.1109/​focs.2017.95
arXiv:1704.06493

[16] T.-D. Lee and C.-N. Yang, Physical Review 87, 410 (1952).
https:/​/​doi.org/​10.1103/​physrev.87.410

[17] H. Peters and G. Regts, arXiv e-prints (2018), arXiv:1810.01699.
arXiv:1810.01699

[18] A. Sinclair, P. Srivastava, and M. Thurley, Journal of Statistical Physics 155, 666 (2014), arXiv:1107.2368.
https:/​/​doi.org/​10.1007/​s10955-014-0947-5
arXiv:1107.2368

[19] A. Sly and N. Sun, in 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (IEEE, 2012) pp. 361-369, arXiv:1203.2602.
https:/​/​doi.org/​10.1109/​focs.2012.56
arXiv:1203.2602

[20] A. Galanis, D. Štefankovič, and E. Vigoda, Combinatorics, Probability and Computing 25, 500 (2016), arXiv:1203.2226.
https:/​/​doi.org/​10.1017/​s0963548315000401
arXiv:1203.2226

[21] J. Liu, A. Sinclair, and P. Srivastava, arXiv e-prints (2018), arXiv:1807.06577.
arXiv:1807.06577

[22] S. Iblisdir, M. Cirio, O. Boada, and G. Brennen, Annals of Physics 340, 205 (2014), arXiv:1208.3918.
https:/​/​doi.org/​10.1016/​j.aop.2013.11.001
arXiv:1208.3918

[23] 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.
https:/​/​doi.org/​10.1098/​rspa.2008.0443
arXiv:0809.0847

[24] D. Shepherd, arXiv e-prints (2010), arXiv:1005.1744.
arXiv:1005.1744

[25] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Physical Review Letters 117, 080501 (2016), arXiv:1504.07999.
https:/​/​doi.org/​10.1103/​physrevlett.117.080501
arXiv:1504.07999

[26] 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.
https:/​/​doi.org/​10.1098/​rspa.2010.0301
arXiv:1005.1407

[27] 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.
https:/​/​doi.org/​10.1109/​focs.2018.00012
arXiv:1711.09457

[28] P. Hell and J. Nešetřil, Graphs and homomorphisms (Oxford University Press, 2004).
https:/​/​doi.org/​10.1093/​acprof:oso/​9780198528173.001.0001

[29] P. Hell and J. Nešetřil, Journal of Combinatorial Theory, Series B 48, 92 (1990).
https:/​/​doi.org/​10.1016/​0095-8956(90)90132-j

[30] M. Dyer and C. Greenhill, Random Structures and Algorithms 17, 260 (2000).
https:/​/​doi.org/​10.1002/​1098-2418(200010/​12)17:3/​4<260::AID-RSA5>3.0.CO;2-W

[31] A. Bulatov and M. Grohe, Theoretical Computer Science 348, 148 (2005).
https:/​/​doi.org/​10.1016/​j.tcs.2005.09.011

[32] L. A. Goldberg, M. Grohe, M. Jerrum, and M. Thurley, SIAM Journal on Computing 39, 3336 (2010), arXiv:0804.1932.
https:/​/​doi.org/​10.1137/​090757496
arXiv:0804.1932

[33] J.-Y. Cai, X. Chen, and P. Lu, in International Colloquium on Automata, Languages, and Programming (Springer, 2010) pp. 275-286, arXiv:0903.4728.
https:/​/​doi.org/​10.1007/​978-3-642-14165-2_24
arXiv:0903.4728

[34] M. Jerrum and A. Sinclair, SIAM Journal on Computing 22, 1087 (1993).
https:/​/​doi.org/​10.1137/​0222066

[35] I. L. Markov and Y. Shi, SIAM Journal on Computing 38, 963 (2008), arXiv:quant-ph/​0511069.
https:/​/​doi.org/​10.1137/​050644756
arXiv:quant-ph/0511069

[36] D. Weitz, in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (ACM, 2006) pp. 140-149.
https:/​/​doi.org/​10.1145/​1132516.1132538

[37] A. Sly, in 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS) (IEEE, 2010) pp. 287-296, arXiv:1005.5584.
https:/​/​doi.org/​10.1109/​focs.2010.34
arXiv:1005.5584

Cited by

[1] Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava, "Fisher zeros and correlation decay in the Ising model", arXiv:1807.06577.

The above citations are from SAO/NASA ADS (last updated 2019-07-16 19:33:19). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-07-16 19:33:18).