中国物理B ›› 2025, Vol. 34 ›› Issue (5): 50201-050201.doi: 10.1088/1674-1056/adbee2

所属专题： SPECIAL TOPIC — Computational programs in complex systems

• •    下一篇

Programming guide for solving constraint satisfaction problems with tensor networks

Xuanzhao Gao(高煊钊)1,2, Xiaofeng Li(李晓锋)1, and Jinguo Liu(刘金国)1,†   

  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
  • 收稿日期:2024-12-30 修回日期:2025-03-01 接受日期:2025-03-11 出版日期:2025-05-15 发布日期:2025-04-18
  • 通讯作者: Jinguo Liu E-mail:jinguoliu@hkust-gz.edu.cn
  • 基金资助:
    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).

Programming guide for solving constraint satisfaction problems with tensor networks

Xuanzhao Gao(高煊钊)1,2, Xiaofeng Li(李晓锋)1, and Jinguo Liu(刘金国)1,†   

  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
  • Received:2024-12-30 Revised:2025-03-01 Accepted:2025-03-11 Online:2025-05-15 Published:2025-04-18
  • Contact: Jinguo Liu E-mail:jinguoliu@hkust-gz.edu.cn
  • Supported by:
    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).

RichHTML

1

PDF (PC)

288

赞

摘要： 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.

关键词: tensor networks, constraint satisfaction problems, problem reductions, Julia

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.

Key words: tensor networks, constraint satisfaction problems, problem reductions, Julia

中图分类号:  (Combinatorics; graph theory)

  • 02.10.Ox
02.10.Xm (Multilinear algebra) 01.50.hv (Computer software and software reviews)