Tensor networks for $p$-spin models

Abstract

We introduce a tensor network algorithm for the solution of $p$-spin models. We show that bond compression through rank-revealing decompositions performed during the tensor network contraction resolves logical redundancies in the system exactly and is thus lossless, yet leads to qualitative changes in runtime scaling in different regimes of the model. First, we find that bond compression emulates the so-called leaf-removal algorithm, solving the problem efficiently in the "easy" phase. Past a dynamical phase transition, we observe superpolynomial runtimes, reflecting the appearance of a core component. We then develop a graphical method to study the scaling of contraction for a minimal ensemble of core-only instances. We find subexponential scaling, improving on the exponential scaling that occurs without compression. Our results suggest that our tensor network algorithm subsumes the classical leaf removal algorithm and simplifies redundancies in the $p$-spin model through lossless compression, all without explicit knowledge of the problem's structure.

12 pages, 12 figures; Updated results; Corrected typos; Updated to the published version

References in corpus (12)

• Bipartite entanglement and entropic boundary law in lattice spin systems
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Entanglement in the stabilizer formalism
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Tensor Networks contraction and the Belief Propagation algorithm
• Simulated bifurcation for higher-order cost functions
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Simulating quantum circuits using tree tensor networks
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Tensor Networks Meet Neural Networks: A Survey and Future Perspectives
• Do tensor renormalization group methods work for frustrated spin systems?
• One-step replica symmetry breaking in the language of tensor networks

Cited by in corpus (1)

• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices