We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3SAT, or #P-complete, such as #2SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms.We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3SAT, or #P-complete, such as #2SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms.

arXiv:2004.06455Electronic Proceedings in Theoretical Computer ScienceSep 6, 202115 citations

Iterative tensor network transformations for element-wise evaluation of elementary and filtering functions

Xiao Wang, Tomohiro Hashizume, Pia Siegl +1 more

Tensor networks are powerful formats for compressing large-scale data. However, their application to general data processing has been limited by the difficulty of performing nonlinear operations. Here, we introduce iterative tensor network transformations (ITNTs), a general algorithmic framework for the element-wise evaluation of elementary and nonlinear filtering functions on data encoded as tensor trains (TTs), a class of tensor networks. Our approach operates entirely in the compressed domain, enabling efficient computation on exponentially large datasets while maintaining a controlled computational cost. We demonstrate its power in two key areas: (I) evaluating highly nonlinear elementary and filtering functions on a 3D reactive flow field, enabling high-fidelity reaction rate computation and region filtering, and (II) finding extrema in complex optimization problems, such as solving Max-SAT instances on spaces up to $2^{70}$ configurations. These results establish ITNT as a foundational tool that provides tensor network methods with the capability for general-purpose data science and large-scale optimization.Tensor networks are powerful formats for compressing large-scale data. However, their application to general data processing has been limited by the difficulty of performing nonlinear operations. Here, we introduce iterative tensor network transformations (ITNTs), a general algorithmic framework for the element-wise evaluation of elementary and nonlinear filtering functions on data encoded as tensor trains (TTs), a class of tensor networks. Our approach operates entirely in the compressed domain, enabling efficient computation on exponentially large datasets while maintaining a controlled computational cost. We demonstrate its power in two key areas: (I) evaluating highly nonlinear elementary and filtering functions on a 3D reactive flow field, enabling high-fidelity reaction rate computation and region filtering, and (II) finding extrema in complex optimization problems, such as solving Max-SAT instances on spaces up to $2^{70}$ configurations. These results establish ITNT as a foundational tool that provides tensor network methods with the capability for general-purpose data science and large-scale optimization.

cs.LGCross-listedarXiv:2608.17135Aug 19, 20260 citations

Nonuniversal entanglement level statistics in projection-driven quantum circuits and glassy dynamics in classical computation circuits

Lei Zhang

In this thesis, I describe research results on three topics : (i) a phase transition in the area-law regime of quantum circuits driven by projection measurements; (ii) ultra slow dynamics in two dimensional spin circuits; and (iii) tensor network methods applied to boolean satisfiability problems. (i) Nonuniversal entanglement level statistics in projection-driven quantum circuits; Non-thermalized closed quantum many-body systems have drawn considerable attention, due to their relevance to experimentally controllable quantum systems. In the first part of the thesis, we study the level-spacing statistics in the entanglement spectrum of output states of random universal quantum circuits where, at each time step, qubits are subject to a finite probability of projection onto states of the computational basis. We encounter two phase transitions with increasing projection rate: The first is the volume-to-area law transition observed in quantum circuits with projective measurements; The second separates the pure Poisson level statistics phase at large projective measurement rates from a regime of residual level repulsion in the entanglement spectrum within the area-law phase, characterized by non-universal level spacing statistics that interpolates between the Wigner-Dyson and Poisson distributions. The same behavior is observed in both circuits of random two-qubit unitaries and circuits of universal gates, including the set implemented by Google in its Sycamore circuits. (ii) Ultra-slow dynamics in a translationally invariant spin model for multiplication and factorization; Slow relaxation of glassy systems in the absence of disorder remains one of the most intriguing problems in condensed matter physics. In the second part of the thesis we investigate slow relaxation in a classical model of short-range interacting Ising spins on a translationally invariant two-dimensional lattice that mimics a reversible circuit that, depending on the choice of boundary conditions, either multiplies or factorizes integers. We prove that, for open boundary conditions, the model exhibits no finite-temperature phase transition. Yet we find that it displays glassy dynamics with astronomically slow relaxation times, numerically consistent with a double exponential dependence on the inverse temperature. The slowness of the dynamics arises due to errors that occur during thermal annealing that cost little energy but flip an extensive number of spins. We argue that the energy barrier that needs to be overcome in order to heal such defects scales linearly with the correlation length, which diverges exponentially with inverse temperature, thus yielding the double exponential behavior of the relaxation time. (iii) Reversible circuit embedding on tensor networks for Boolean satisfiability; Finally, in the third part of the thesis we present an embedding of Boolean satisfiability (SAT) problems on a two-dimensional tensor network. The embedding uses reversible circuits encoded into the tensor network whose trace counts the number of solutions of the satisfiability problem. We specifically present the formulation of #2SAT, #3SAT, and #3XORSAT formulas into planar tensor networks. We use a compression-decimation algorithm introduced by us to propagate constraints in the network before coarse-graining the boundary tensors. Iterations of these two steps gradually collapse the network while slowing down the growth of bond dimensions. For the case of #3XORSAT, we show numerically that this procedure recognizes, at least partially, the simplicity of XOR constraints for which it achieves subexponential time to solution. For a #P-complete subset of #2SAT we find that our algorithm scales with size in the same way as state-of-the-art #SAT counters, albeit with a larger prefactor. We find that the compression step performs less efficiently for #3SAT than for #2SAT.In this thesis, I describe research results on three topics : (i) a phase transition in the area-law regime of quantum circuits driven by projection measurements; (ii) ultra slow dynamics in two dimensional spin circuits; and (iii) tensor network methods applied to boolean satisfiability problems. (i) Nonuniversal entanglement level statistics in projection-driven quantum circuits; Non-thermalized closed quantum many-body systems have drawn considerable attention, due to their relevance to experimentally controllable quantum systems. In the first part of the thesis, we study the level-spacing statistics in the entanglement spectrum of output states of random universal quantum circuits where, at each time step, qubits are subject to a finite probability of projection onto states of the computational basis. We encounter two phase transitions with increasing projection rate: The first is the volume-to-area law transition observed in quantum circuits with projective measurements; The second separates the pure Poisson level statistics phase at large projective measurement rates from a regime of residual level repulsion in the entanglement spectrum within the area-law phase, characterized by non-universal level spacing statistics that interpolates between the Wigner-Dyson and Poisson distributions. The same behavior is observed in both circuits of random two-qubit unitaries and circuits of universal gates, including the set implemented by Google in its Sycamore circuits. (ii) Ultra-slow dynamics in a translationally invariant spin model for multiplication and factorization; Slow relaxation of glassy systems in the absence of disorder remains one of the most intriguing problems in condensed matter physics. In the second part of the thesis we investigate slow relaxation in a classical model of short-range interacting Ising spins on a translationally invariant two-dimensional lattice that mimics a reversible circuit that, depending on the choice of boundary conditions, either multiplies or factorizes integers. We prove that, for open boundary conditions, the model exhibits no finite-temperature phase transition. Yet we find that it displays glassy dynamics with astronomically slow relaxation times, numerically consistent with a double exponential dependence on the inverse temperature. The slowness of the dynamics arises due to errors that occur during thermal annealing that cost little energy but flip an extensive number of spins. We argue that the energy barrier that needs to be overcome in order to heal such defects scales linearly with the correlation length, which diverges exponentially with inverse temperature, thus yielding the double exponential behavior of the relaxation time. (iii) Reversible circuit embedding on tensor networks for Boolean satisfiability; Finally, in the third part of the thesis we present an embedding of Boolean satisfiability (SAT) problems on a two-dimensional tensor network. The embedding uses reversible circuits encoded into the tensor network whose trace counts the number of solutions of the satisfiability problem. We specifically present the formulation of #2SAT, #3SAT, and #3XORSAT formulas into planar tensor networks. We use a compression-decimation algorithm introduced by us to propagate constraints in the network before coarse-graining the boundary tensors. Iterations of these two steps gradually collapse the network while slowing down the growth of bond dimensions. For the case of #3XORSAT, we show numerically that this procedure recognizes, at least partially, the simplicity of XOR constraints for which it achieves subexponential time to solution. For a #P-complete subset of #2SAT we find that our algorithm scales with size in the same way as state-of-the-art #SAT counters, albeit with a larger prefactor. We find that the compression step performs less efficiently for #3SAT than for #2SAT.

Jan 1, 20210 citations

2^{70}

configurations. These results establish ITNT as a foundational tool that provides tensor network methods with the capability for general-purpose data science and large-scale optimization.