Fast counting with tensor networks
arXiv:1805.00475 · doi:10.21468/SciPostPhys.7.5.060
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.
arXiv commentv2: added results for monotone #1-in-3SAT; published version
References in corpus (30)
- Community structure in social and biological networks
- Community detection in graphs
- Area laws for the entanglement entropy - a review
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
- SATzilla: Portfolio-based Algorithm Selection for SAT
- Tensor renormalization group approach to 2D classical lattice models
- Classical simulation of quantum many-body systems with a tree tensor network
- Accurate determination of tensor network state of quantum lattice models in two dimensions
- Simulating quantum computation by contracting tensor networks
- Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
- Coarse-graining renormalization by higher-order singular value decomposition
- A Knowledge Compilation Map
- Tensor Network Renormalization
- Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
- Entanglement renormalization and topological order
- Loop optimization for tensor network renormalization
- Renormalization of tensor networks using graph independent local truncations
- Algorithms for tensor network renormalization
- Exact entanglement renormalization for string-net models
- Renormalization group flows of Hamiltonians using tensor networks
- Constraint satisfaction problems with isolated solutions are hard
- Implementing Efficient All Solutions SAT Solvers
- The Phase Diagram of 1-in-3 Satisfiability Problem
- Tensor Network Contractions for #SAT
- Tensor network algorithm by coarse-graining tensor renormalization on finite periodic lattices
- Algebraically contractible topological tensor network states
- Tensor network method for reversible classical computation
- 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 -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