Fast counting with tensor networks

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.

v2: added results for monotone #1-in-3SAT; published version

References in corpus (10)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Tensor renormalization group approach to 2D classical lattice models
• Accurate determination of tensor network state of quantum lattice models in two dimensions
• A Knowledge Compilation Map
• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• Entanglement renormalization and topological order
• Renormalization of tensor networks using graph independent local truncations
• Exact entanglement renormalization for string-net models
• Constraint satisfaction problems with isolated solutions are hard
• Evaluating the Jones polynomial with tensor networks

Cited by in corpus (29)

• Hyper-optimized tensor network contraction
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Tropical Tensor Network for Ground States of Spin Glasses
• Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Gauging tensor networks with belief propagation
• The computational power of random quantum circuits in arbitrary geometries
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Tensor networks for quantum computing
• Opening the Black Box Inside Grover's Algorithm
• Tensor Network Rewriting Strategies for Satisfiability and Counting
• The minimal canonical form of a tensor network
• Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound
• Protocols for classically training quantum generative models on probability distributions
• Sampling diverse near-optimal solutions via algorithmic quantum annealing
• Méthodes de calcul avec réseaux de tenseurs en physique (Basic tensor network computations in physics)
• The resource theory of tensor networks
• Picturing Counting Reductions with the ZH-Calculus
• Avoidance, Adjacency, and Association in Distributed Systems Design
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints
• SuperGrad: a differentiable simulator for superconducting processors
• 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
• Variational matrix product states for combinatorial optimization
• The product structure of MPS-under-permutations
• Counting with the quantum alternating operator ansatz
• End-to-End Quantum Algorithms for the Jones Polynomial