Tensor Network Contractions for #SAT

Abstract

The computational cost of counting the number of solutions satisfying a Boolean formula, which is a problem instance of #SAT, has proven subtle to quantify. Even when finding individual satisfying solutions is computationally easy (e.g. 2-SAT, which is in P), determining the number of solutions is #P-hard. Recently, computational methods simulating quantum systems experienced advancements due to the development of tensor network algorithms and associated quantum physics-inspired techniques. By these methods, we give an algorithm using an axiomatic tensor contraction language for n-variable #SAT instances with complexity $O((g+cd{)}^{O(1)}{2}^c)$ where $c$ is the number of COPY-tensors, $g$ is the number of gates, and $d$ is the maximal degree of any COPY-tensor. Thus, counting problems can be solved efficiently when their tensor network expression has at most $O(\log c)$ COPY-tensors and polynomial fan-out. This framework also admits an intuitive proof of a variant of the Tovey conjecture (the r,1-SAT instance of the Dubois-Tovey theorem). This study increases the theory, expressiveness and application of tensor based algorithmic tools and provides an alternative insight on these problems which have a long history in statistical physics and computer science.

16 pages, 8 diagrams

References in corpus (13)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Novel schemes for measurement-based quantum computation
• Entanglement renormalization, scale invariance, and quantum criticality
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Matrix product operators and states: NP-hardness and undecidability
• Ground State Spin Logic
• Entanglement and tensor network states
• Dynamical simulations of classical stochastic systems using matrix product states
• Solving search problems by strongly simulating quantum circuits
• A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth
• Renyi entropies as a measure of the complexity of counting problems
• Tensor network non-zero testing
• Tensor networks for frustrated systems: emergence of order from simplex entanglement

Cited by in corpus (29)

• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Lecture Notes of Tensor Network Contractions
• Variational Quantum Eigensolver with Fewer Qubits
• Tensor Networks in a Nutshell
• The Presence and Absence of Barren Plateaus in Tensor-network Based Machine Learning
• Tropical Tensor Network for Ground States of Spin Glasses
• Probabilistic Nonunitary Gate in Imaginary Time Evolution
• Fast counting with tensor networks
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Gauging tensor networks with belief propagation
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Lectures on Quantum Tensor Networks
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
• Charged String Tensor Networks
• Sampling diverse near-optimal solutions via algorithmic quantum annealing
• Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
• Tensor network method for reversible classical computation
• Entanglement Scaling in Quantum Advantage Benchmarks
• A Complete Set of Invariants for LU-Equivalence of Density Operators
• Avoidance, Adjacency, and Association in Distributed Systems Design
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints
• Tensor network non-zero testing
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Tensor networks for $p$-spin models
• Quick design of feasible tensor networks for constrained combinatorial optimization
• The product structure of MPS-under-permutations
• Variational matrix product states for combinatorial optimization