Programming guide for solving constraint satisfaction problems with tensor networks
Xuanzhao Gao(高煊钊)1,2, Xiaofeng Li(李晓锋)1, and Jinguo Liu(刘金国)1,†
1 Hong Kong University of Science and Technology (Guangzhou), Guangzhou 511453, China; 2 Hong Kong University of Science and Technology, Hong Kong SAR, China
Abstract Constraint satisfaction problems (CSPs) are a class of problems that are ubiquitous in science and engineering. They feature a collection of constraints specified over subsets of variables. A CSP can be solved either directly or by reducing it to other problems. This paper introduces the Julia ecosystem for solving and analyzing CSPs with a focus on the programming practices. We introduce some important CSPs and show how these problems are reduced to each other. We also show how to transform CSPs into tensor networks, how to optimize the tensor network contraction orders, and how to extract the solution space properties by contracting the tensor networks with generic element types. Examples are given, which include computing the entropy constant, analyzing the overlap gap property, and the reduction between CSPs.
Fund: This work is partially funded by the National Key R&D Program of China (Grant No. 2024YFE0102500), the National Natural Science Foundation of China (Grant No. 12404568), the Guangzhou Municipal Science and Technology Project (Grant No. 2023A03J00904), the Quantum Science Center of Guangdong-Hong Kong-Macao Greater Bay Area, China and the Undergraduate Research Project from HKUST (Guangzhou).
Corresponding Authors:
Jinguo Liu
E-mail: jinguoliu@hkust-gz.edu.cn
Cite this article:
Xuanzhao Gao(高煊钊), Xiaofeng Li(李晓锋), and Jinguo Liu(刘金国) Programming guide for solving constraint satisfaction problems with tensor networks 2025 Chin. Phys. B 34 050201
[1] Clark B N, Colbourn C J and Johnson D S 1991 Annals of Discrete Mathematics 48 165 [2] Ding C H, He X, Zha H, Gu M and Simon H D 2001 Proceedings 2001 IEEE international conference on data mining (IEEE) pp. 107-114 [3] Crescenzi P, Kann V and Halldórsson M 1995 A Compendium of NP Optimization Problems [4] Chvatal V 1979 Mathematics of Operations Research 4 233 [5] Jensen T R and Toft B 2011 Graph Coloring Problems (John Wiley & Sons) [6] Malaguti E and Toth P 2010 International Transactions in Operational Research 17 1 [7] Biere A, Heule M and van Maaren H 2009 Handbook of Satisfiability Vol. 185 (IOS press) [8] Schaefer T J 1978 Proceedings of the tenth annual ACM symposium on Theory of computing pp. 216-226 [9] Moore C and Mertens S 2011 The Nature of Computation (Oxford University Press) [10] Butenko S and Pardalos P M 2003 Maximum Independent Set and Related Problems, with Applications PhD thesis (University of Florida) [11] Wu Q and Hao J K 2015 European Journal of Operational Research 242 693 [12] Hastad J 1996 Proceedings of 37th Conference on Foundations of Computer Science (IEEE) pp. 627-636 [13] Mézard M, Parisi G, Sourlas N, Toulouse G and Virasoro M 1984 Journal de Physique 45 843 [14] Gamarnik D 2021 Proc. Natl. Acad. Sci. USA 118 e2108492118 [15] Cain M, Chattopadhyay S, Liu J G, Samajdar R, Pichler H and Lukin M D 2023 arXiv:2306.13123 [16] Ebadi S, Keesling A, Cain M, Wang T T, Levine H, Bluvstein D, Semeghini G, Omran A, Liu J G, Samajdar R, et al. 2022 Science 376 1209 [17] Mohseni N, McMahon P L and Byrnes T 2022 Nature Reviews Physics 4 363 [18] Lucas A 2014 Frontiers in Physics 2 5 [19] Ushijima-Mwesigwa H, Negre C F A and Mniszewski S M 2017 arXiv:1705.03082 [20] Pichler H, Wang S t, Zhou L, Choi S and Lukin M D 2018 Science 376 6598 [21] Nguyen M T, Liu J G, Wurtz J, Lukin M D, Wang S T and Pichler H 2023 PRX Quantum 4 010316 [22] Bezanson J, Karpinski S, Shah V B and Edelman A 2012 arXiv:1209.5145 [23] Bezanson J 2015 Why is Julia fast? Can it be faster? (JuliaCon India) [24] Liu J G, Wang L and Zhang P 2021 Phys. Rev. Lett. 126 090506 [25] Liu J G, Gao X, Cain M, LukinMD andWang S T 2023 SIAM Journal on Scientific Computing 45 A1239 [26] Fishman M, White S and Stoudenmire E 2022 SciPost Physics Codebases [27] Luo X Z, Liu J G, Zhang P and Wang L 2020 Quantum 4 341 [28] Lubin M, Dowson O, Dias Garcia J, Huchette J, Legat B and Vielma J P 2023 Mathematical Programming Computation 15 581 [29] Rackauckas C and Nie Q 2017 Journal of Open Research Software 5 15 [30] Besard T, Foket C and Sutter B D 2017 arXiv:1712.03112 [31] Glover F, Kochenberger G and Du Y 2018 arXiv:1811.11538 [32] Qiu X, Zoller P and Li X 2020 PRX Quantum 1 020311 [33] Scott A D and Sokal A D 2005 J. Stat. Phys. 118 1151 [34] Tarjan R E and Trojanowski A E 1977 SIAM Journal on Computing 6 537 [35] Xiao M and Nagamochi H 2013 Theoretical Computer Science 469 92 [36] Karp R M 2010 Reducibility Among Combinatorial Problems (Springer) [37] Chaitin G J 1982 ACM Sigplan Notices 17 98 [38] Stojmenovic I, Seddigh M and Zunic J 2002 IEEE Transactions on Parallel and Distributed Systems 13 14 [39] Lovász L and Plummer M D 2009 Matching Theory Vol. 367 (American Mathematical Soc.) [40] Edmonds J 1965 Canadian Journal of Mathematics 17 449 [41] Valiant L G 1979 SIAM Journal on Computing 8 410 [42] Baumgartner P et al. 2002 AI in the new Millenium, Morgan Kaufmann, Seattle [43] Biere A, Heule M, van Maaren H and Walsh T 2009 Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications pp. 131- 153 [44] Montgomery P L 1994 CWI Quarterly 7 337 [45] MumtazMand Ping L 2019 Journal of Discrete Mathematical Sciences and Cryptography 22 9 [46] Markov I L and Shi Y 2008 SIAM Journal on Computing 38 963 [47] Gray J and Kourtis S 2021 Quantum 5 410 [48] Roa-Villescas M, Gao X, Stuijk S, Corporaal H and Liu J G 2024 Phys. Rev. Res. 6 033261 [49] Lawson C L, Hanson R J, Kincaid D R and Krogh F T 1979 ACM Transactions on Mathematical Software (TOMS) 5 308 [50] Lukas Devos Maarten Van Damme J H and Contributors 2023 arXiv:2406.07052 [51] Liu J G, Wurtz J, Nguyen M T, Lukin M D, Pichler H and Wang S T 2024 unpublished [52] Kalachev G, Panteleev P and Yung M H 2021 arXiv:2108.05665 [53] Schlag S, Heuer T, Gottesbüren L, Akhremtsev Y, Schulz C and Sanders P 2023 ACM Journal of Experimental Algorithmics 27 1 [54] Bouchitté V and Todinca I 2001 SIAM Journal on Computing 31 212 [55] Ferrin G M 2014 https://scholarcommons.sc.edu/etd/2609/ [56] Farrell E J 1979 Journal of Combinatorial Theory, Series B 27 75 [57] Read R C 1968 Journal of Combinatorial Theory 4 52 [58] Baxter R J, Enting I G and Tsang S K 1980 J. Stat. Phys. 22 465 [59] Pearce P A and Seaton K A 1988 J. Stat. Phys. 53 1061 [60] Fomin F V and Kaski P 2013 Communications of the ACM 56 80 [61] Gao X Z, Wang Y J, Zhang P and Liu J G 2024 arXiv:2412.07685 [62] Lamm S, Sanders P, Schulz C, Strash D and Werneck R F 2017 J. Heuristics 23 207
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
