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]
• 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]
• 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]
• Peng et al., Arithmetic circuit tensor networks, multivariable function representation, and high-dimensional integration
  Phys. Rev. Research 5, 013156 (2023) [Crossref]
• Laakkonen et al., Picturing Counting Reductions with the ZH-Calculus
  Electron. Proc. Theor. Comput. Sci. 384, 89 (2023) [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]
• Liu et al., Tropical Tensor Network for Ground States of Spin Glasses
  Phys. Rev. Lett. 126, 090506 (2021) [Crossref]
• Pan et al., Simulation of Quantum Circuits Using the Big-Batch Tensor Network Method
  Phys. Rev. Lett. 128, 030501 (2022) [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]
• Wang et al., Tensor Network Message Passing
  Phys. Rev. Lett. 132, 117401 (2024) [Crossref]
• Klishin et al., Avoidance, adjacency, and association in distributed systems design
  J. Phys. Complex. 2, 025015 (2021) [Crossref]
• Acuaviva et al.,
  , 328 (2023) [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]
• Gray et al., Hyper-optimized tensor network contraction
  Quantum 5, 410 410 (2021) [Crossref]
• Vincent et al., Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
  Quantum 6, 709 709 (2022) [Crossref]
• Liu et al., Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
  SIAM J. Sci. Comput. 45, A1239 (2023) [Crossref]
• Liang et al., Fast Search of the Optimal Contraction Sequence in Tensor Networks
  IEEE J. Sel. Top. Signal Process. 15, 574 (2021) [Crossref]