Model Checking Matrix Product States against Linear Chain Logic
Ming Xu, Yihao Chen, Ji Guan · 2026
Read Model Checking Matrix Product States against Linear Chain Logic by Ming Xu, Yihao Chen, Ji Guan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14356.txt.
Introduction
Ming Xu, Yihao Chen and Ji Guan bring model checking, systematic checks against stated requirements, to matrix product states. These tensor-network forms describe one-dimensional quantum ground states. They propose Linear Chain Logic, a spatial logic for properties of periodic state families as system size grows, such as nontriviality on rings. Each periodic state induces a completely positive map on its virtual space, so inner products can be computed without brute-force expansion. Approximate checking then verifies nontrivial cases and detects large-size patterns on test families.
Catalog record
| CREATOR | Ming Xu, Yihao Chen, Ji Guan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75428 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14356
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Model Checking Matrix Product States against Linear Chain Logic Ming Xu, Yihao Chen, Ji Guan Abstract Matrix product states (MPS) are a standard tensor-network representation for ground states of one-dimensional quantum many-body systems, and they underpin widely used simulation tools such as DMRG. However, while quantum model checking has been developed mainly for quantum programs and communication protocols (with properties expressed along a time axis), there is still no comparable framework for systematically verifying spatial and size-dependent properties of physical many-body states, where the key parameter is the system size. This paper takes a step toward bridging the gap. We propose Linear Chain Logic (LCL), a spatial logic designed to specify physically meaningful properties of periodic MPS families as the system size grows, such as nontriviality on rings and large-size asymptotic patterns. Our approach builds on a simple but powerful connection: every periodic MPS naturally induces a completely positive map (a quantum operation) on its virtual space, so many quantitative features of the MPS can be analysed through the repeated application of the operation. Using this perspective, we derive an effective procedure to compute the inner products of an MPS at a given size and to support richer LCL specifications, without relying on brute-force state expansion. We then develop approximate model-checking algorithms that combine sound bounding with asymptotic structural analysis, enabling scalable reasoning about large system sizes. Experiments on representative MPS families illustrate that our method can automatically verify nontriviality and detect asymptotic spatial regimes in a way that complements traditional numerical techniques. 1 Introduction Model checking is a cornerstone of formal verification: given a system model and a specification , it decides whether the former satisfies the latter [ 11 , 4 ] . Driven by quantum software stacks and quantum networks, model checking has been extended to quantum settings and become an effective tool for validating quantum programs and communication protocols [ 40 , 41 ] . As in the classical case, success hinges on two ingredients: i) a precise model of system evolution, and ii) a property language with an executable checking procedure. Where quantum model checking has been most successful. Most existing frameworks target temporal verification tasks that arise naturally in computation and communication: program steps, rounds, and time slots. A representative model is the quantum Markov chain (QMC), which generalises classical Markov chains by replacing stochastic transitions with completely positive maps (quantum operations) [ 38 ] . This paradigm underlies verification across quantum control [ 28 ] , quantum information theory [ 18 ] , quantum programming [ 42 ] , and quantum communication protocols [ 40 , 41 ] . A growing verification frontier: state families indexed by size. Many important quantum systems are not naturally described as a time-evolving protocol, but as a family of states parameterised by a size parameter (e. g., the number of sites N in a one-dimensional (1D) chain) [ 44 ] . The viewpoint is central in quantum simulation and device-level validation, where the goal is to prepare and certify target states and their properties as the system scales. From a verification perspective, the core challenge is therefore spatial and asymptotic : properties may stabilize only beyond a threshold, recur periodically, or change regime as N grows. It calls for a model-checking perspective that reasons over the index N , rather than over time. Recent work at the interface of automata/regular languages and quantum state representations further suggests that formal-methods structure can fruitfully organise many-body state classes and their properties [ 15 ] . MPS as a scalable system model. For 1D local quantum systems, the matrix product state (MPS) is a standard compact representation, which underpins numerical methods such as DMRG [ 37 ] . From a verification perspective, the key point is that many physically relevant 1D ground states admit such compact descriptions: for gapped local Hamiltonians, entanglement satisfies an entanglement area law [ 23 ] , which implies approximability by MPS with a bond dimension that grows only with the desired accuracy (and model parameters), rather than exponentially with the chain length [ 3 ] . Thus, MPS provides a natural system model for scalable, size-indexed reasoning about state families \{|\psi_{N}\rangle\}_{N\geq 1} generated by a fixed set of matrices \{A_{k}\}_{k=1}^{d} (to be formalised in Section 2 ): |\psi_{N}\rangle=\sum_{k_{1},\ldots,k_{N}=1}^{d}\mathrm{tr}(A_{k_{1}}\cdots A_{k_{N}})\;|k_{1}\rangle\otimes\cdots\otimes|k_{N}\rangle. (1) The gap: model checking for spatial, quantitative properties of MPS families. Despite substantial progress on temporal logics and QMC-style models, systematic verification of spatial properties of MPS families remains largely unexplored. Yet these properties are exactly what one needs to study and validate quantum many-body behavior: Is the periodic MPS nontrivial for all sufficiently large size parameter N ? Do key observables eventually lie in a prescribed range? Do behaviors become ultimately periodic or converge to a limiting regime? Answering such questions requires: i) a logic whose semantics ranges over the size parameter N , and ii) algorithms that exploit the algebraic structure of the MPS tensors. Our approach. To fill this gap, we propose a spatial logic, Linear Chain Logic (LCL), and approximate model-checking algorithms for periodic MPS. The key technical bridge is that a fixed MPS tensor family \{A_{k}\} induces a completely positive (CP) map \mathcal{E}(X)=\sum_{k}A_{k}XA_{k}^{\dagger} on the bond space (the space of A_{k} ), together with the (Liouville) matrix representation M_{\mathcal{E}}=\sum_{k}A_{k}^{*}\otimes A_{k} . The transfer-operator view turns many MPS quantities into trace expressions of matrix powers. Particularly, \|\psi_{N}\|^{2}=\mathrm{tr}(M_{\mathcal{E}}^{\,N}) , so fundamental questions are reduced to reasoning about the scalar sequence \{\mathrm{tr}(M_{\mathcal{E}}^{\,N})\}_{N\geq 1} . Furthermore, structural results for irreducible CP maps constrain the peripheral spectrum to be cyclic (roots of unity), yielding eventual periodic regimes that our algorithms can exploit without requiring an explicit full-spectrum computation. Logic and algorithms. LCL is LTL-like in syntax, but interpreted over the size index N . Value expressions \Gamma(N) are extracted from the MPS contractions, interval predicates \in\mathcal{I} give the ranges, atomic formulas combine them as \Gamma(N)\in\mathcal{I} , and general formulas admit Boolean connectives and spatial operators such as “eventually” and “infinitely often” along N . Our approximate model-checking pipeline: i) computes sound bounds for \Gamma(N) using the transfer-operator structure, ii) derives semilinear over-/under-approximations of the set of sizes satisfying each atomic formula, and iii) propagates these approximations bottom-up to decide the input formula. In sum, this paper makes three main contributions: 1. Specification — We introduce the linear chain logic (LCL) to express size-indexed, spatial properties of periodic MPS families in many-body systems. 2. Technique — We develop the transfer-operator-based model checking, leveraging CP-map view, irreducible decomposition, and peripheral cyclicity to compute semilinear over-/under-approximations efficiently. 3. Validation — We evaluate the checker on representative MPS families and quantitative properties, demonstrating scalable certification of nontriviality and detection of asymptotic spatial regimes. 1.1 Related work (1) Chain logic vs. temporal logics: Classical model checking is tightly coupled with temporal logics, where the system is observed along a time axis. Linear-time logics such as LTL specify properties over single executions, while branching-time logics such as CTL/CTL ∗ quantify over computation trees and enable richer path quantification (e. g., reachability) [ 10 , 4 ] . The logics and their model-checking pipelines are now standard for software/hardware verification. Our setting differs in what the “axis” ranges over: rather than time