Source-linked AI summary
Tensor Networks in a Nutshell
Jacob Biamonte, Ville Bergholm
TL;DR
Tensor networks provide compact representations and graphical reasoning tools for quantum states and related structures, but their broader use requires understanding their notation and contractions. This tutorial introduces the graphical language, matrix product states, and tensor-contraction approaches to counting problems. It presents efficient MPS representations, an approximation error scaling as O(ξ), Boolean-SAT solution counting, and Penrose’s counting of proper 3-edge-colorings for planar 3-regular graphs.
Problem
As quantum-state descriptions grow computationally unmanageable with system size, the paper explains tensor-network representations as a less data-intensive alternative.
Method
The tutorial develops tensor diagrams, introduces MPS construction through recursive SVD, and formulates counting problems as tensor contractions.
Results
The paper shows that bounded-size MPS representations require information scaling linearly with n, while tensor contractions count SAT solutions and planar 3-regular graph 3-edge-colorings.
Takeaways & Limitations
Tensor contractions adapt quantum-system simulation tools to computer-science counting problems and provide efficient descriptions for some tensor networks.
Takeaways & Limitations
The graph-coloring contraction returns the number of proper colorings only for planar 3-regular graphs, while the MPS factorization has a canonical choice only under open boundary conditions up to spectral degeneracies.
Abstract
from arXiv · showhide
Tensor network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states, and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits, channels, protocols, open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions, the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae, whereas the second is Penrose's tensor contraction algorithm, returning the number of $3$-edge-colorings of $3$-regular planar graphs.
1. QUANTUM LEGOS
Tensor networks are collections of contracted tensors used across quantum information, physics, mathematics, and computer science. They offer graphical reasoning and efficient approximations for certain quantum states.
- Tensors generalize multilinear maps, while tensor networks are collections of tensors connected by contractions.
- Tensor network methods are used in quantum information science, condensed matter physics, mathematics, and computer science.
- Their graphical language supports intuitive reasoning about tensor networks and connects them to quantum circuits.
- Certain quantum systems can be simulated more efficiently and studied in greater detail using tensor network algorithms.
- These methods approximate complicated quantum states with regular tensor networks, functioning as lossy compression that preserves important properties.
- The tutorial assumes basic knowledge of quantum theory, linear algebra, and tensors, while allowing readers to proceed informally.
tensors and tensor products.
The tutorial begins with abstract index notation and explains its connection to Dirac notation used in quantum computing.
- The paper first presents tensors using abstract index notation, then connects that notation to Dirac notation.
2. FROM TENSORS TO NETWORKS
Tensor diagrams represent tensors as shapes with indexed wires, and connecting wires performs contractions. Examples link this language to linear algebra, entanglement, and quantum circuits.
- Tensor diagrams depict tensors as labelled shapes whose open arms and legs represent upper and lower indices.
- Disconnected tensors are combined with tensor products, while wires may cross or tensors may move without changing wire endpoints.
- Connecting tensor legs with wires contracts the corresponding indices by summing over them.
- A tensor network is fully contracted when no tensors have open arms or legs, yielding a scalar.
- The examples use tensor networks to express determinants, entanglement invariants, concurrence, and quantum circuits.
- Quantum circuits are restricted tensor networks whose wires represent subsystem Hilbert spaces and whose attached tensors represent quantum gates.
3. BENDING AND CROSSING WIRES
Bending and crossing wires provide diagrammatic operations for changing tensor index arrangements, tracing systems, and representing quantum transformations. These operations connect tensor diagrams to swaps, entanglement, and adjoints.
- Cups and caps bend tensor legs to raise or lower indices, while the identity tensor supports index contraction.
- Crossing wires represents the SWAP operation, which exchanges subsystem order and is self-inverse.
- Trace joins a tensor’s output wires to corresponding inputs, whereas partial trace contracts only selected pairs.
- The partial trace of a bipartite state can be represented using cups, caps, and SWAPs.
- The epsilon tensor is related to SWAP and antisymmetrization through tensor contractions.
- For n-dimensional spaces, epsilon tensors and antisymmetrizers encode permutation signatures and vanish when antisymmetrizing more indices than the dimension.
- Map-state duality interprets bipartite vectors and linear maps as equivalent diagrammatic forms, including transposition around cups or caps.
- The dagger operation reverses tensor-network structure and combines transposition with complex conjugation.
4. DIAGRAMMATIC SVD
The section presents the SVD diagrammatically, shows its Schmidt-decomposition corollary, and explains why singular-value truncation enables controlled low-rank approximation.
- Singular value decomposition: The SVD factors a tensor into two unitary tensors and a diagonal tensor containing its singular values.Grouping tensor legs extends the construction from matrices to tensors of order two or higher.
- Tensor-network relevance: The SVD underlies efficient tensor-network representations by repeatedly combining it with low-rank approximations for physically relevant low-entanglement states.This procedure retains a small portion of the Hilbert space while approximating the full state.
- Low-rank approximation: Trimming the smallest singular values produces the optimal rank-r approximation under any unitarily invariant matrix norm.The Eckart-Young-Mirsky theorem identifies this truncation as the best approximation among approximations of the same or lesser rank.
- Schmidt decomposition: Applying wire bending to the SVD converts a bipartite state into its Schmidt decomposition, with singular values becoming Schmidt coefficients.For normalized states, these coefficients determine the bipartite entanglement topology.
- Applications: Schmidt coefficients also support tensor-network analyses of concurrence and purification, including density-matrix interpretations of their squared values.The examples show how unitary factors can cancel or disappear in entanglement-related contractions.
5. MATRIX PRODUCT STATES
Matrix product states represent quantum states as tensor chains or rings, using repeated SVDs and truncation to obtain compact approximations. Their efficiency depends on bounded internal dimensions and controlled entanglement across partitions.
- MPS structure: Matrix product states represent quantum states as linear chains or rings of tensors, with open or periodic boundary conditions.Any quantum state admits an exact MPS representation, while certain 1D gapped systems can be approximated efficiently.
- Efficiency: If local matrices are at most χ by χ, the representation size scales as ndχ^2 and therefore grows only linearly in n for bounded matrix size.Here d is the dimension of each subsystem.
- Construction: A recursive sequence of SVDs across successive bipartitions converts a state tensor into the one-dimensional MPS form.The factorization traverses the tensor from one end, after which tensors are grouped into the standard representation.
- Approximation: For general n-qubit states, exact MPS bond dimensions can still grow exponentially, so practical algorithms truncate singular values or retain at most χ values.The resulting Schmidt rank across an MPS cut is at most χ.
- Approximation error: The truncation error in the analyzed approximation scales at most as O(ξ), while the error in the inner product is quadratic after normalization.The linear bound is stated for the approximation error, whereas the normalized inner-product comparison yields a quadratic error.
- Entanglement: Tensor-network partitions bound entanglement entropy through the total cut-wire dimension, with H0(ρA) ≤χ and H1(ρA) ≤log χ.These area-law quantities connect bounded bond dimension with controlled entanglement across partitions.
6. COUNTING BY TENSOR CONTRACTION
The section connects tensor contractions with counting and computational complexity. Fully contracted tensor diagrams can encode counts, including Boolean-function solutions and graph-coloring problems.
- Tensor-network counting: Counting problems can be represented in the tensor-network language by evaluating fully contracted diagrams.The contraction returns a scalar encoding the count being computed.
- Counting versus search: Counting asks for all solutions to a search problem rather than locating or checking one specified solution.The phone-book analogy distinguishes searching for one entry from counting every entry satisfying a property.
- Complexity: Search problems are generally associated with NP, while counting versions of NP-complete problems are #P-complete.The section frames counting complexity separately from the difficulty of verifying an individual solution.
- Applications: Penrose showed that tensor contraction can solve certain graph-coloring problems, and the tutorial also uses contractions to count Boolean-function inputs producing output 1.These two applications are presented as connections between tensor networks and combinatorial counting.
1. Counting Boolean Formula Solutions
The paper represents Boolean functions as tensor networks and uses contractions to isolate satisfying inputs and count them. This connects tensor-network techniques with Boolean formula counting, including #P-complete general instances.
- Boolean tensors: A Boolean function maps an n-bit input string to one binary digit and can be represented by a Boolean tensor network.The network is determined from the classical logic-gate description of the function.
- Boolean states: Contracting the function tensor with |1⟩ produces an unnormalized Boolean state supported only on inputs satisfying f(x).The support therefore consists of assignments for which f(x)=1.
- Counting by contraction: The squared two-norm of |f⟩ equals the number of satisfying assignments for a SAT instance.For Boolean states, the squared two-norm equals the one-norm because f(x)∈{0,1}.
- Complexity: General Boolean-formula counting is #P-complete, distinguishing counting solutions from merely deciding satisfiability.The condition ⟨f|f⟩>0 indicates that at least one satisfying assignment exists.
- Broader use: Tensor-network formulations allow quantum-system and circuit-simulation tools to be applied to counting problems in computer science.The paper reports efficient tensor-network descriptions for a wide class of contractable counting networks.
2. Counting Graph Colorings
Penrose’s contraction replaces vertices of a planar 3-regular graph with epsilon tensors and edges with wires, yielding the number of proper 3-edge-colorings. Planarity is essential because nonzero contraction terms must all have positive sign.
- Problem setup: The problem asks for proper three-edge-colorings of a 3-regular planar graph, with distinct colors on edges incident to each node.The construction uses the order-3 epsilon tensor.
- Penrose contraction: Theorem 23 states that replacing each node by an order-3 epsilon tensor and each edge by a wire gives the coloring count after contraction.This is Penrose’s tensor contraction algorithm for planar 3-regular graphs.
- Example: A two-node example has 6 distinct edge colorings, illustrating the contraction’s direct enumeration of allowed assignments.The example is explicitly described as having six colorings.
- Mechanism: The contraction sums all index assignments, interpreting the three index values as edge colors and eliminating assignments with repeated colors at a vertex.Only proper local color assignments contribute nonzero terms.
- Scope condition: Planarity guarantees that every nonzero term contributes +1; for nonplanar graphs, signs can cancel, as in K3,3, which has 12 colorings but zero contraction.Thus the contraction need not equal the coloring count outside the planar setting.
7. FRONTIERS IN TENSOR NETWORKS
Tensor networks remain an active research area spanning quantum mechanics, mathematics, computer science, and connections to quantum gravity. The tutorial highlights established structures while pointing to ongoing developments and incomplete coverage.
- Active research: Tensor network research continues to produce new results and ideas, with applications across quantum mechanics, mathematics, and computer science.The reference list is explicitly described as incomplete but intended as a starting place for further study.
- Tutorial scope: The tutorial covers elementary tensor-network language, matrix product states, and contraction-based applications to Boolean solutions and planar graph colorings.These are presented as three sample applications within a broader active field.
- Major methods: Common structures and algorithms include MPS, DMRG, MPO, Tensor Trains, TTN, MERA, PEPS, CPS, and TEBD.These methods constitute prominent tensor-network approaches used in quantum mechanics.
- Research directions: Reviews commonly map lattice problems to tensor networks to study strongly correlated systems.The paper encourages readers to consult several reviews for further study.
- Quantum gravity connections: MERA can represent ground states of certain many-body models at critical points and has been connected with tensor-network versions of the AdS/MERA correspondence.The cited discussion describes networks realizing discrete anti-de Sitter space.
Appendix A: Tensors and Tensor Products
The appendix defines tensors through tensor products of primal and dual vector spaces, then explains contractions, multilinear-map interpretations, and abstract index notation. It also introduces simple tensors and diagrammatic composition.
- Tensor products: The tensor product of vectors is bilinear and can be expressed in standard coordinates using the Kronecker product.For inner-product spaces, the tensor-product space inherits an inner product from its constituent spaces.
- Definitions: A tensor is an element of a tensor product of finitely many vector spaces over a common scalar field.An order-(p,q) tensor contains p primal-space factors and q dual-space factors.
- Representation and notation: Every tensor is a linear combination of simple tensors, although most tensors cannot themselves be written as one tensor product of factors.Abstract index notation records tensor order rather than basis components, with repeated upper-lower indices summed.
- Contraction: Contracting matching primal and dual indices sums over the repeated index and lowers tensor order by (1,1).The contraction uses the natural pairing between a vector space and its dual.
- Multilinear maps: An order-(p,q) tensor can be reinterpreted as a multilinear map from vectors to vectors, or equivalently as a map between dual-vector spaces.Vector spaces can be moved across the map arrow by taking their duals.