Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTensor network method for reversible classical computation
70
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
We introduce tensor network contraction algorithms for counting satisfying assignments of constraint satisfaction problems (#CSPs). We represent each arbitrary #CSP formula as a tensor network, whose full contraction yields the number of satisfying assignments of that formula, and use graph theoretical methods to determine favorable orders of contraction. We employ our heuristics for the solution of #P-hard counting boolean satisfiability (#SAT) problems, namely monotone #1-in-3SAT and #Cubic-Vertex-Cover, and find that they outperform state-of-the-art solvers by a significant margin.
Mappings of classical computation onto statistical mechanics models have led to remarkable successes in addressing some complex computational problems. However, such mappings display thermodynamic phase transitions that may prevent reaching solution even for easy problems known to be solvable in polynomial time. Here we map universal reversible classical computations onto a planar vertex model that exhibits no bulk classical thermodynamic phase transition, independent of the computational circuit. Within our approach the solution of the computation is encoded in the ground state of the vertex model and its complexity is reflected in the dynamics of the relaxation of the system to its ground state. We use thermal annealing with and without learning to explore typical computational problems. We also construct a mapping of the vertex model into the Chimera architecture of the D-Wave machine, initiating an approach to reversible classical computation based on state-of-the-art implementations of quantum annealing.
The classical Heisenberg model in two spatial dimensions constitutes one of the most paradigmatic spin models, taking an important role in statistical and condensed matter physics to understand magnetism. Still, despite its paradigmatic character and the widely accepted ban of a (continuous) spontaneous symmetry breaking, controversies remain whether the model exhibits a phase transition at finite temperature. Importantly, the model can be interpreted as a lattice discretization of the $O(3)$ non-linear sigma model in $1+1$ dimensions, one of the simplest quantum field theories encompassing crucial features of celebrated higher-dimensional ones (like quantum chromodynamics in $3+1$ dimensions), namely the phenomenon of asymptotic freedom. This should also exclude finite-temperature transitions, but lattice effects might play a significant role in correcting the mainstream picture. In this work, we make use of state-of-the-art tensor network approaches, representing the classical partition function in the thermodynamic limit over a large range of temperatures, to comprehensively explore the correlation structure for Gibbs states. By implementing an $SU(2)$ symmetry in our two-dimensional tensor network contraction scheme, we are able to handle very large effective bond dimensions of the environment up to $chi_E^text{eff} sim 1500$, a feature that is crucial in detecting phase transitions. With decreasing temperatures, we find a rapidly diverging correlation length, whose behaviour is apparently compatible with the two main contradictory hypotheses known in the literature, namely a finite-$T$ transition and asymptotic freedom, though with a slight preference for the second.
We generalize a tensor-network algorithm to study thermodynamic properties of self-similar spin lattices constructed on a square-lattice frame with two types of couplings, $J_{1}^{}$ and $J_{2}^{}$, chosen to transform a regular square lattice ($J_{1}^{} = J_{2}^{}$) onto a fractal lattice if decreasing $J_{2}^{}$ to zero (the fractal fully reconstructs when $J_{2}^{} = 0$). We modified the Higher-Order Tensor Renormalization Group (HOTRG) algorithm for this purpose. Single-site measurements are performed by means of so-called impurity tensors. So far, only a single local tensor and uniform extension-contraction relations have been considered in HOTRG. We introduce ten independent local tensors, each being extended and contracted by fifteen different recursion relations. We applied the Ising model to the $J_{1}^{}-J_{2}^{}$ planar fractal whose Hausdorff dimension at $J_{2}^{} = 0$ is $d^{(H)} = ln 12 / ln 4 approx 1.792$. The generalized tensor-network algorithm is applicable to a wide range of fractal patterns and is suitable for models without translational invariance.
We define a class of tensor network states for spin systems where the individual tensors are functionals of fields. The construction is based on the path integral representation of correlators of operators in quantum field theory. These tensor network states are infinite dimension
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
