SciPost Physics

SciPost Phys. 7, 060 (2019) · published 12 November 2019

• doi: 10.21468/SciPostPhys.7.5.060
• pdf
• BiBTeX
• RIS
• Submissions/Reports
• 

Abstract

We introduce tensor network contraction algorithms for counting satisfying assignments of constraint satisfaction problems (#CSPs). We represent each arbitrary #CSP formula as a tensor network, whose full contraction yields the number of satisfying assignments of that formula, and use graph theoretical methods to determine favorable orders of contraction. We employ our heuristics for the solution of #P-hard counting boolean satisfiability (#SAT) problems, namely monotone #1-in-3SAT and #Cubic-Vertex-Cover, and find that they outperform state-of-the-art solvers by a significant margin.

• Mohseni et al., Sampling diverse near-optimal solutions via algorithmic quantum annealing
  Phys. Rev. E 108, 065303 (2023) [Crossref]
• Wu et al., Counting the number of solutions in satisfiability problems with tensor-network message passing
  Phys. Rev. E 110, 034126 (2024) [Crossref]
• Pan et al., Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
  Phys. Rev. Lett. 125, 060503 (2020) [Crossref]
• Dudek et al.,
  12333, 211 (2020) [Crossref]
• Laakkonen et al., Picturing Counting Reductions with the ZH-Calculus
  Electron. Proc. Theor. Comput. Sci. 384, 89 (2023) [Crossref]
• Stoudenmire et al., Opening the Black Box inside Grover’s Algorithm
  Phys. Rev. X 14, 041029 (2024) [Crossref]
• Rams et al., Approximate optimization, sampling, and spin-glass droplet discovery with tensor networks
  Phys. Rev. E 104, 025308 (2021) [Crossref]
• Gray et al., Hyperoptimized Approximate Contraction of Tensor Networks with Arbitrary Geometry
  Phys. Rev. X 14, 011009 (2024) [Crossref]
• Pan et al., Simulation of Quantum Circuits Using the Big-Batch Tensor Network Method
  Phys. Rev. Lett. 128, 030501 (2022) [Crossref]
• Pan et al., Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs
  ACM Transactions on Quantum Computing, 3696465 (2024) [Crossref]
• Lanthier et al., Tensor networks for p-spin models
  Front. Phys. 12, 1431810 (2024) [Crossref]
• Wang et al., Tensor Network Message Passing
  Phys. Rev. Lett. 132, 117401 (2024) [Crossref]
• Acuaviva et al.,
  , 328 (2023) [Crossref]
• Gray et al., Hyper-optimized tensor network contraction
  Quantum 5, 410 410 (2021) [Crossref]
• Liu et al., Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
  SIAM J. Sci. Comput. 45, A1239 (2023) [Crossref]
• Lee et al.,
  , 3095 (2024) [Crossref]
• Liang et al., Fast Search of the Optimal Contraction Sequence in Tensor Networks
  IEEE J. Sel. Top. Signal Process. 15, 574 (2021) [Crossref]
• de Beaudrap et al., Tensor Network Rewriting Strategies for Satisfiability and Counting
  Electron. Proc. Theor. Comput. Sci. 340, 46 (2021) [Crossref]
• Wahl et al., Simulating Quantum Circuits Using Efficient Tensor Network Contraction Algorithms with Subexponential Upper Bound
  Phys. Rev. Lett. 131, 180601 (2023) [Crossref]
• Peng et al., Arithmetic circuit tensor networks, multivariable function representation, and high-dimensional integration
  Phys. Rev. Research 5, 013156 (2023) [Crossref]
• Liu et al., Tropical Tensor Network for Ground States of Spin Glasses
  Phys. Rev. Lett. 126, 090506 (2021) [Crossref]
• Klishin et al., When does entropy promote local organization?
  Soft Matter 16, 6523 (2020) [Crossref]
• Tindall et al., Gauging tensor networks with belief propagation
  SciPost Phys. 15, 222 (2023) [Crossref]
• Klishin et al., Avoidance, adjacency, and association in distributed systems design
  J. Phys. Complex. 2, 025015 (2021) [Crossref]
• Kasture et al., Protocols for classically training quantum generative models on probability distributions
  Phys. Rev. A 108, 042406 (2023) [Crossref]
• Baker et al., Méthodes de calcul avec réseaux de tenseurs en physique
  Can. J. Phys. 99, 207 (2021) [Crossref]
• Ibrahim et al.,
  , 1 (2022) [Crossref]
• Vincent et al., Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
  Quantum 6, 709 709 (2022) [Crossref]