A Matrix Product State Representation of Boolean Functions

2025/05/03 by Umut Eren Usturali, Usturali, Umut Eren, Claudio Chamon +5
Computer Science · Mathematics · Physics and Astronomy · #Computational Physics (physics.comp-ph) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum many-body systems #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2505.01930

openalex publication_date 2025/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a novel normal form representation of Boolean functions in terms of products of binary matrices, hereafter referred to as the Binary Matrix Product (BMP) representation. BMPs are analogous to the Tensor-Trains (TT) and Matrix Product States (MPS) used, respectively, in applied mathematics and in quantum many-body physics to accelerate computations that are usually inaccessible by more traditional approaches. BMPs turn out to be closely related to Binary Decision Diagrams (BDDs), a powerful compressed representation of Boolean functions invented in the late 80s by Bryant that has found a broad range of applications in many areas of computer science and engineering. We present a direct and natural translation of BMPs into Binary Decision Diagrams (BDDs), and derive an elementary set of operations used to manipulate and combine BMPs that are analogous to those introduced by Bryant for BDDs. Both BDDs and BMPs are practical tools when the complexity of these representations, as measured by the maximum bond dimension of a BMP (or the accumulated bond dimension across the BMP matrix train) and the number of nodes of a BDD, remains polynomial in the number of bits, n. In both cases, controlling the complexity hinges on optimizing the order of the Boolean variables. BMPs offer the advantage that their construction and manipulation rely on simple linear algebra -- a compelling feature that can facilitate the development of open-source libraries that are both more flexible and easier to use than those currently available for BDDs. An initial implementation of a BMP library is available on GitHub, with the expectation that the close conceptual connection to TT and MPS techniques will motivate further development of BMP methods by researchers in these fields, potentially enabling novel applications to classical and quantum computing.

Citations

• Quantized tensor networks for solving the Vlasov-Maxwell equations
• Numerical solution of the incompressible Navier-Stokes equations for chemical mixers via quantum-inspired Tensor Train Finite Element Method
• TTOpt: A Maximum Volume Quantized Tensor Train-based Optimization and its Application to Reinforcement Learning
• Quantum Computational Advantage via 60-Qubit 24-Cycle Random Circuit Sampling
• A Tensor Network based Decision Diagram for Representation of Quantum Circuits
• Convolutional Tensor-Train LSTM for Spatio-temporal Learning
• Generalized Tensor Models for Recurrent Neural Networks
• A low-rank projector-splitting integrator for the Vlasov--Poisson\n equation
• Multigrid methods combined with low-rank approximation for tensor\n structured Markov chains
• 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
• Graph-Based Algorithms for Boolean Function Manipulation

Related

• Representation Theorem for Matrix Product States
• Computing the Boolean product of two n× n Boolean matrices using O(n²) mechanical operation
• Low-rank tensor decompositions of quantum circuits
• SeeMPS: A Python-based Matrix Product State and Tensor Train Library
• Shortcut Matrix Product States and its applications