Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints

Abstract

In this study, we introduce a novel family of tensor networks, termed constrained matrix product states (MPS), designed to incorporate exactly arbitrary discrete linear constraints, including inequalities, into sparse block structures. These tensor networks are particularly tailored for modeling distributions with support strictly over the feasible space, offering benefits such as reducing the search space in optimization problems, alleviating overfitting, improving training efficiency, and decreasing model size. Central to our approach is the concept of a quantum region, an extension of quantum numbers traditionally used in U(1) symmetric tensor networks, adapted to capture any linear constraint, including the unconstrained scenario. We further develop a novel canonical form for these new MPS, which allow for the merging and factorization of tensor blocks according to quantum region fusion rules and permit optimal truncation schemes. Utilizing this canonical form, we apply an unsupervised training strategy to optimize arbitrary objective functions subject to discrete linear constraints. Our method's efficacy is demonstrated by solving the quadratic knapsack problem, achieving superior performance compared to a leading nonlinear integer programming solver. Additionally, we analyze the complexity and scalability of our approach, demonstrating its potential in addressing complex constrained combinatorial optimization problems.

References in corpus (25)

• The density-matrix renormalization group in the age of matrix product states
• An Area Law for One Dimensional Quantum Systems
• The ITensor Software Library for Tensor Network Calculations
• Classical simulation of quantum many-body systems with a tree tensor network
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Tensor network states and algorithms in the presence of a global U(1) symmetry
• Non-abelian symmetries in tensor networks: a quantum symmetry space approach
• Unsupervised Generative Modeling Using Matrix Product States
• Solving Gapped Hamiltonians Locally
• The Tensor Networks Anthology: Simulation techniques for many-body quantum lattice systems
• Perfect Sampling with Unitary Tensor Networks
• Tensor network states and algorithms in the presence of a global SU(2) symmetry
• Machine Learning by Unitary Tensor Network of Hierarchical Tree Structure
• Learning Relevant Features of Data with Multi-scale Tensor Networks
• Supervised Learning with Projected Entangled Pair States
• Tropical Tensor Network for Ground States of Spin Glasses
• Tensor Network Contractions for #SAT
• Fast counting with tensor networks
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• A quantum-inspired tensor network method for constrained combinatorial optimization problems
• Anomaly Detection with Tensor Networks
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Privacy-preserving machine learning with tensor networks
• Renyi entropies as a measure of the complexity of counting problems
• Constructive TT-representation of the tensors given as index interaction functions with applications

Cited by in corpus (2)

• Tensor Network Estimation of Distribution Algorithms
• Variational matrix product states for combinatorial optimization