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

Ryan L. Mann; Michael J. Bremner

doi:10.22331/q-2019-07-11-162

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

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

Published:	2019-07-11, volume 3, page 162
Eprint:	arXiv:1806.11282v2
Doi:	https://doi.org/10.22331/q-2019-07-11-162
Citation:	Quantum 3, 162 (2019).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

Featured image: Computational complexity of approximating the Ising model partition function on graphs of maximum degree at most $\Delta$ with temperature parameter $\omega$.

► BibTeX data

@article{Mann2019approximation,
  doi = {10.22331/q-2019-07-11-162},
  url = {https://doi.org/10.22331/q-2019-07-11-162},
  title = {Approximation {A}lgorithms for {C}omplex-{V}alued {I}sing {M}odels on {B}ounded {D}egree {G}raphs},
  author = {Mann, Ryan L. and Bremner, Michael J.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {162},
  month = jul,
  year = {2019}
}

► 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] Sergey Bravyi, David Gosset, and Ramis Movassagh, "Classical algorithms for quantum mean values", Nature Physics 17 3, 337 (2021).

[2] 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).

[3] Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava, "Fisher zeros and correlation decay in the Ising model", Journal of Mathematical Physics 60 10, 103304 (2019).

[4] Ryan L. Mann and Tyler Helmuth, "Efficient algorithms for approximating quantum partition functions", Journal of Mathematical Physics 62 2, 022201 (2021).

[5] 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).

[6] Sergey Bravyi, David Gosset, and Ramis Movassagh, "Classical algorithms for quantum mean values", arXiv:1909.11485, (2019).

[7] Aram Harrow, Saeed Mehraban, and Mehdi Soleimanifar, "Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems", arXiv:1910.09071, (2019).

[8] Tyler Helmuth and Ryan L. Mann, "Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature", arXiv:2201.06533, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-03-31 01:31:25) and SAO/NASA ADS (last updated successfully 2023-03-31 01:31:26). 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.