Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization

Abstract

Constrained combinatorial optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In some heuristic solvers, these are typically addressed by introducing certain Lagrange multipliers in the cost function, by relaxing them in some way, or worse yet, by generating many samples and only keeping valid ones, which leads to very expensive and inefficient searches. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric tensor networks (TNs) and leverage their applicability as quantum-inspired generative models to assist in the search of solutions to combinatorial optimization problems. This allows us to exploit the generalization capabilities of TN generative models while constraining them so that they only output valid samples. Our constrained TN generative model efficiently captures the constraints by reducing number of parameters and computational costs. We find that at tasks with constraints given by arbitrary equalities, symmetric Matrix Product States outperform their standard unconstrained counterparts at finding novel and better solutions to combinatorial optimization problems.

arXiv commentv2. Improved version: restructured the paper; corrected complexity analysis and put more details of the encoding algorithm; added new, and improved some existing figures for clarity; added a few extra refs. v3. Shortened captions, added new table with outline of algorithm

References in corpus (40)

• The density-matrix renormalization group in the age of matrix product states
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• A Quantum Approximate Optimization Algorithm
• Entanglement renormalization
• Area laws in quantum systems: mutual information and correlations
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Tensor networks for complex quantum systems
• Perspectives of quantum annealing: Methods and implementations
• From density-matrix renormalization group to matrix product states
• A generative modeling approach for benchmarking and training shallow quantum circuits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Tensor network states and algorithms in the presence of a global U(1) symmetry
• Machine Learning Topological States
• Tensor network decompositions in the presence of a global symmetry
• Recurrent Neural Network Wave Functions
• Unsupervised Generative Modeling Using Matrix Product States
• On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Symmetries and many-body excited states with neural-network quantum states
• Solving Gapped Hamiltonians Locally
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Exploiting symmetry in variational quantum machine learning
• A Tutorial on Formulating and Using QUBO Models
• Group-Invariant Quantum Machine Learning
• Perfect Sampling with Unitary Tensor Networks
• Tensor network states and algorithms in the presence of a global SU(2) symmetry
• Variational Neural Annealing
• Neural network representation of tensor network and chiral states
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Matrix product decomposition and classical simulation of quantum dynamics in the presence of a symmetry
• Tropical Tensor Network for Ground States of Spin Glasses
• Expressive Power and Approximation Errors of Restricted Boltzmann Machines
• U(1) symmetric recurrent neural networks for quantum state reconstruction
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Representation Theory for Geometric Quantum Machine Learning
• Probabilistic Modeling with Matrix Product States
• Modeling Sequences with Quantum States: A Look Under the Hood
• Anomaly Detection with Tensor Networks
• Generalization and Overfitting in Matrix Product State Machine Learning Architectures
• Gauge Equivariant Neural Networks for 2+1D U(1) Gauge Theory Simulations in Hamiltonian Formulation

Cited by in corpus (10)

• Does provable absence of barren plateaus imply classical simulability?
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models
• Tensor networks for interpretable and efficient quantum-inspired machine learning
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Privacy-preserving machine learning with tensor networks
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints
• TensorKrowch: Smooth integration of tensor networks in machine learning
• Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Variational matrix product states for combinatorial optimization