Tensor network method for reversible classical computation
arXiv:1708.08932 · doi:10.1103/PhysRevE.97.033303
Abstract
We develop a tensor network technique that can solve universal reversible classical computational problems, formulated as vertex models on a square lattice [Nat. Commun. 8, 15303 (2017)]. By encoding the truth table of each vertex constraint in a tensor, the total number of solutions compatible with partial inputs/outputs at the boundary can be represented as the full contraction of a tensor network. We introduce an iterative compression-decimation (ICD) scheme that performs this contraction efficiently. The ICD algorithm first propagates local constraints to longer ranges via repeated contraction-decomposition sweeps over all lattice bonds, thus achieving compression on a given length scale. It then decimates the lattice via coarse-graining tensor contractions. Repeated iterations of these two steps gradually collapse the tensor network and ultimately yield the exact tensor trace for large systems, without the need for manual control of tensor dimensions. Our protocol allows us to obtain the exact number of solutions for computations where a naive enumeration would take astronomically long times.
arXiv commentUpdated version with more careful discussions on the distribution of bond dimensions over random instances, as well as distinguishing between average versus typical behavior. 13.5 pages, 13 figures
References in corpus (31)
- The density-matrix renormalization group
- Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
- Quantum Networks for Elementary Arithmetic Operations
- Tensor renormalization group approach to 2D classical lattice models
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Accurate determination of tensor network state of quantum lattice models in two dimensions
- Coarse-graining renormalization by higher-order singular value decomposition
- Gapless spin-liquid ground state in the kagome antiferromagnet
- Tensor Network Renormalization
- Algorithms for entanglement renormalization
- Tensor-entanglement renormalization group approach to 2D quantum systems
- Era of Big Data Processing: A New Approach via Tensor Networks and Tensor Decompositions
- First order phase transition in the Quantum Adiabatic Algorithm
- Loop optimization for tensor network renormalization
- Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
- Tensor Networks in a Nutshell
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Algorithms for tensor network renormalization
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Training A Quantum Optimizer
- Renormalization group flows of Hamiltonians using tensor networks
- Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
- Tensor Network Contractions for #SAT
- Tensor network algorithm by coarse-graining tensor renormalization on finite periodic lattices
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Entanglement renormalization for disordered systems
- Virtual Parallel Computing and a Search Algorithm using Matrix Product States
- Tensor Network Methods for Invariant Theory
- Quantum Vertex Model for Reversible Classical Computing
- Renyi entropies as a measure of the complexity of counting problems