Computing solution space properties of combinatorial optimization problems via generic tensor networks. (English) Zbl 1527.90189
Summary: We introduce a unified framework to compute the solution space properties of a broad class of combinatorial optimization problems. These properties include finding one of the optimum solutions, counting the number of solutions of a given size, and enumeration and sampling of solutions of a given size. Using the independent set problem as an example, we show how all these solution space properties can be computed in the unified approach of generic tensor networks. We demonstrate the versatility of this computational tool by applying it to several examples, including computing the entropy constant for hardcore lattice gases, studying the overlap gap properties, and analyzing the performance of quantum and classical algorithms for finding maximum independent sets.
MSC:
| 90C27 | Combinatorial optimization |
| 05C31 | Graph polynomials |
| 14N10 | Enumerative problems (combinatorial problems) in algebraic geometry |
Keywords:
generic tensor network; solution space property; independent set; combinatorial optimizationSoftware:
CUDAnative.jl; PRMLT; Julia; TropicalGEMM.jl; CUDA.jl; NumPy; GitHub; GenericTensorNetworks; Algorithm 457References:
| [1] | Generic Tensor Networks, https://github.com/QuEraComputing/GenericTensorNetworks.jl. |
| [2] | Tropical GEMM, https://github.com/TensorBFS/TropicalGEMM.jl. |
| [3] | Alikhani, S. and Peng, Y.-H., Introduction to Domination Polynomial of a Graph, https://arxiv.org/abs/0905.2251, 2009. · Zbl 1324.05138 |
| [4] | Altshuler, B., Krovi, H., and Roland, J., Anderson localization makes adiabatic quantum optimization fail, Proc. Natl. Acad. Sci. USA, 107 (2010), pp. 12446-12450, doi:10.1073/pnas.1002116107. · Zbl 1205.81056 |
| [5] | Baxter, R. J., Enting, I. G., and Tsang, S. K., Hard-square lattice gas, J. Stat. Phys., 22 (1980), pp. 465-489, doi:10.1007/BF01012867. |
| [6] | Besard, T., Foket, C., and De Sutter, B., Effective extensible programming: Unleashing Julia on GPUs, IEEE Trans. Parallel Distr. Syst., 30 (2018), pp. 827-841, doi:10.1109/TPDS.2018.2872064. |
| [7] | Bezanson, J., Karpinski, S., Shah, V. B., and Edelman, A., Julia: A Fast Dynamic Language for Technical Computing, https://arxiv.org/abs/1209.5145, 2012. · Zbl 1356.68030 |
| [8] | Biamonte, J. and Bergholm, V., Tensor Networks in a Nutshell, https://arxiv.org/abs/1708.00006, 2017. |
| [9] | Biamonte, J. D., Morton, J., and Turner, J., Tensor network contractions for #SAT, J. Stat. Phys., 160 (2015), pp. 1389-1404, doi:10.1007/s10955-015-1276-z. · Zbl 1341.68053 |
| [10] | Bishop, C. M., Pattern Recognition and Machine Learning, Springer, New York, 2006, https://link.springer.com/gp/book/9780387310732. · Zbl 1107.68072 |
| [11] | Bousquet-Mélou, M., Linusson, S., and Nevo, E., On the independence complex of square grids, J. Algebraic Combin., 27 (2008), pp. 423-450, doi:10.1007/s10801-007-0096-x. · Zbl 1202.05095 |
| [12] | Bron, C. and Kerbosch, J., Algorithm 457: Finding all cliques of an undirected graph, Commun. ACM, 16 (1973), pp. 575-577, doi:10.1145/362342.362367. · Zbl 0261.68018 |
| [13] | Butenko, S. and Pardalos, P. M., Maximum Independent Set and Related Problems, with Applications, Ph.D. thesis, University of Florida, 2003, https://ufdc.ufl.edu/UFE0001011/00001. |
| [14] | Butera, P. and Pernici, M., Sums of Permanental Minors Using Grassmann Algebra, https://arxiv.org/abs/1406.5337, 2014. |
| [15] | Cichocki, A., Era of Big Data Processing: A New Approach via Tensor Networks and Tensor Decompositions, https://arxiv.org/abs/1403.2048, 2014. |
| [16] | Cirac, J. I., Pérez-García, D., Schuch, N., and Verstraete, F., Matrix product states and projected entangled pair states: Concepts, symmetries, theorems, Rev. Modern Phys., 93 (2021), doi:10.1103/revmodphys.93.045003. |
| [17] | Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. Comput., 85 (1990), pp. 12-75, doi:10.1016/0890-5401(90)90043-H. · Zbl 0722.03008 |
| [18] | Dyre, J. C., Simple liquids’ quasiuniversality and the hard-sphere paradigm, J. Phys. Condensed Matter, 28 (2016), 323001, doi:10.1088/0953-8984/28/32/323001. |
| [19] | Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., Luo, X.-Z., Nash, B., Gao, X., Barak, B., Farhi, E., Sachdev, S., Gemelke, N., Zhou, L., Choi, S., Pichler, H., Wang, S.-T., Greiner, M., Vuletić, V., and Lukin, M. D., Quantum optimization of maximum independent set using Rydberg atom arrays, Science, 376 (2022), pp. 1209-1215, doi:10.1126/science.abo6587. |
| [20] | Eppstein, D., Löffler, M., and Strash, D., Listing all maximal cliques in sparse graphs in near-optimal time, in Algorithms and Computation, Cheong, O., Chwa, K.-Y., and Park, K., eds., Springer, Berlin, 2010, pp. 403-414, doi:10.1007/978-3-642-17517-6_36. · Zbl 1311.05187 |
| [21] | Fernandes, H. C. M., Arenzon, J. J., and Levin, Y., Monte Carlo simulations of two-dimensional hard core lattice gases, J. Chem. Phys., 126 (2007), 114508, doi:10.1063/1.2539141. |
| [22] | Ferrin, G. M., Independence Polynomials, https://scholarcommons.sc.edu/etd/2609/, 2014 |
| [23] | Fomin, F. V. and Kaski, P., Exact exponential algorithms, Commun. ACM, 56 (2013), pp. 80-88, doi:10.1145/2428556.2428575. |
| [24] | Gamarnik, D., The overlap gap property: A topological barrier to optimizing over random structures, Proc. Natl. Acad. Sci. USA, 118 (2021), doi:10.1073/pnas.2108492118. |
| [25] | Gamarnik, D. and Jagannath, A., The Overlap Gap Property and Approximate Message Passing Algorithms for \(p\)-Spin Models, https://arxiv.org/abs/1911.06943, 2019. · Zbl 1470.60277 |
| [26] | Gamarnik, D. and Sudan, M., Limits of Local Algorithms over Sparse Random Graphs, https://arxiv.org/abs/1304.1831, 2013. · Zbl 1365.05277 |
| [27] | Garey, M. R. and Johnson, D. S., The rectilinear steiner tree problem is \(NP\)-complete, SIAM J. Appl. Math., 32 (1977), pp. 826-834, doi:10.1137/0132071. · Zbl 0396.05009 |
| [28] | Gaspers, S., Kratsch, D., and Liedloff, M., On independent sets and bicliques in graphs, Algorithmica, 62 (2012), pp. 637-658, doi:10.1007/s00453-010-9474-1. · Zbl 1239.05101 |
| [29] | Golub, G. H. and Van Loan, C. F., Matrix Computations, Vol. 3, Johns Hopkins University Press, Baltimore, 2013, doi:10.2307/3621013. · Zbl 1268.65037 |
| [30] | Goodman, J., Semiring parsing, Comput. Linguist., 25 (1999), pp. 573-606, https://aclanthology.org/J99-4004.pdf. |
| [31] | Gray, J. and Kourtis, S., Hyper-optimized tensor network contraction, Quantum, 5 (2021), 410, doi:10.22331/q-2021-03-15-410. |
| [32] | Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., Fernández del Río, J., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E., Array programming with NumPy, Nature, 585 (2020), pp. 357-362, doi:10.1038/s41586-020-2649-2. |
| [33] | Harvey, N. J., Srivastava, P., and Vondrák, J., Computing the independence polynomial: From the tree threshold down to the roots, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, , SIAM, Philadelphia, 2018, pp. 1557-1576, doi:10.1137/1.9781611975031.102. · Zbl 1403.68351 |
| [34] | Hastad, J., Clique is hard to approximate within \(n^{1-\epsilon }\), in Proceedings of the 37th Conference on Foundations of Computer Science, , IEEE, 1996, pp. 627-636, doi:10.1007/BF02392825. |
| [35] | Johnson, D. S., Yannakakis, M., and Papadimitriou, C. H., On generating all maximal independent sets, Inform. Process. Lett., 27 (1988), pp. 119-123, doi:10.1016/0020-0190(88)90065-8. · Zbl 0654.68086 |
| [36] | Kalachev, G., Panteleev, P., and Yung, M.-H., Multi-Tensor Contraction for XEB Verification of Quantum Circuits, https://arxiv.org/abs/2108.05665, 2021. |
| [37] | Kerr, L. R., The Effect of Algebraic Structure on the Computational Complexity of Matrix Multiplication, Tech. report, Cornell University, 1970, https://ecommons.cornell.edu/handle/1813/5934. |
| [38] | Kourtis, S., Chamon, C., Mucciolo, E., and Ruckenstein, A., Fast counting with tensor networks, SciPost Phys., 7 (2019), doi:10.21468/scipostphys.7.5.060. |
| [39] | Lee, T.-D. and Yang, C.-N., Statistical theory of equations of state and phase transitions. II. Lattice gas and ising model, Phys. Rev., 87 (1952), 410, doi:10.1103/PhysRev.87.410. · Zbl 0048.43401 |
| [40] | Levit, V. E. and Mandrescu, E., The Independence Polynomial of a Graph at −1, https://arxiv.org/abs/0904.4819, 2009. · Zbl 1194.05062 |
| [41] | Liu, J.-G., Wang, L., and Zhang, P., Tropical tensor network for ground states of spin glasses, Phys. Rev. Lett., 126 (2021), doi:10.1103/physrevlett.126.090506. |
| [42] | Maclagan, D. and Sturmfels, B., Introduction to Tropical Geometry, , AMS, Providence, RI, 2015, http://www.cs.technion.ac.il/∼janos/COURSES/238900-13/Tropical/MaclaganSturmfels.pdf. · Zbl 1321.14048 |
| [43] | Manne, F. and Sharmin, S., Efficient counting of maximal independent sets in sparse graphs, in International Symposium on Experimental Algorithms, , Springer, New York, 2013, pp. 103-114, doi:10.1007/978-3-642-38527-8_11. |
| [44] | Markov, I. L. and Shi, Y., Simulating quantum computation by contracting tensor networks, SIAM J. Comput., 38 (2008), pp. 963-981, doi:10.1137/050644756. · Zbl 1165.81017 |
| [45] | Moore, C. and Mertens, S., The nature of computation, Oxford University Press, Oxford, UK, 2011, doi:10.1093/acprof:oso/9780199233212.001.0001. · Zbl 1237.68004 |
| [46] | Orús, R., A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Ann. Phys., 349 (2014), pp. 117-158, doi:10.1016/j.aop.2014.06.013. · Zbl 1343.81003 |
| [47] | Oseledets, I. V., Tensor-train decomposition, SIAM J. Sci. Comput., 33 (2011), pp. 2295-2317, doi:10.1137/090752286. · Zbl 1232.15018 |
| [48] | Pan, F. and Zhang, P., Simulating the Sycamore Quantum Supremacy Circuits, https://arxiv.org/abs/2103.03074, 2021. |
| [49] | Pearce, P. A. and Seaton, K. A., A classical theory of hard squares, J. Stat. Phys., 53 (1988), pp. 1061-1072, doi:10.1007/BF01023857. |
| [50] | Pichler, H., Wang, S.-T., Zhou, L., Choi, S., and Lukin, M. D., Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays, https://arxiv.org/abs/1808.10816, 2018. |
| [51] | Rahman, M. and Virág, B., Local algorithms for independent sets are half-optimal, Ann. Probab., 45 (2017), doi:10.1214/16-aop1094. · Zbl 1377.60049 |
| [52] | Schönhage, A. and Strassen, V., Schnelle multiplikation grosser zahlen, Computing, 7 (1971), pp. 281-292, doi:10.1007/BF02242355. · Zbl 0223.68007 |
| [53] | Shitov, Y., The complexity of tropical matrix factorization, Adv. Math., 254 (2014), pp. 138-156, doi:10.1016/j.aim.2013.12.013. · Zbl 1359.68112 |
| [54] | Stepanov, A. A. and Rose, D. E., From Mathematics to Generic Programming, Pearson Education, 2014, https://www.fm2gp.com/. |
| [55] | Wu, Q. and Hao, J.-K., A review on algorithms for maximum clique problems, European J. Oper. Res., 242 (2015), pp. 693-709, doi:10.1016/j.ejor.2014.09.064. · Zbl 1341.05241 |
| [56] | Xu, Y.-Z., Yeung, C. H., Zhou, H.-J., and Saad, D., Entropy inflection and invisible low-energy states: Defensive alliance example, Phys. Rev. Lett., 121 (2018), doi:10.1103/physrevlett.121.210602. |
| [57] | Yang, C.-N. and Lee, T.-D., Statistical theory of equations of state and phase transitions. I. Theory of condensation, Phys. Rev., 87 (1952), pp. 404-409, doi:10.1103/PhysRev.87.404. · Zbl 0048.43305 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
