论文标题
部分可观测时空混沌系统的无模型预测
The Complexity of Contracting Planar Tensor Network
论文作者
论文摘要
在许多研究领域（例如量子计算和机器学习）中，张量网络一直是一个重要的概念和技术。我们研究了两个特殊图形结构上收缩张量网络的指数复杂性：平面图和有限元图。 我们证明，任何有限元图都有$ O（d \ sqrt {\ max \ {δ，d \} n}）$ size gende spairator。此外，我们开发了$ 2^{o（d \ sqrt {\ max \ {δ，d \} n}）} $ time算法，以收缩张量网络，该网络由$ n $ boolean张贴器组成，由$ n $ boolean启动器组成，其基础图是与$δ$相比，与$ d $ d $ d $ decource的台面相比$ 2^{o（\ sqrt {Δn}）} $ time算法\ cite {fastcounting}用于平面布尔张量张量网络收缩。 我们使用两种方法通过将高维张量转移到低维张量来加速指数算法。 我们为任何布尔的对称张量$ k $添加了$ O（k）$尺寸的平面小工具，该小工具仅由尺寸不超过$ 5 $的布尔张量组成。 另一种方法是根据其\ emph {cp {cp分解} \ cite {tensor-rank}将任何张量分解为一系列向量（单函数）。 我们还证明，在计数\ emph {指数时间假设}（\ #eth）保留下，用于收缩张量网络的子指数时间下限。
Tensor networks have been an important concept and technique in many research areas, such as quantum computation and machine learning. We study the exponential complexity of contracting tensor networks on two special graph structures: planar graphs and finite element graphs. We prove that any finite element graph has a $O(d\sqrt{\max\{Δ,d\}N})$ size edge separator. Furthermore, we develop a $2^{O(d\sqrt{\max\{Δ,d\}N})}$ time algorithm to contracting a tensor network consisting of $N$ Boolean tensors, whose underlying graph is a finite element graph with maximum degree $Δ$ and has no face with more than $d$ boundary edges in the planar skeleton, based on the $2^{O(\sqrt{ΔN})}$ time algorithm \cite{fastcounting} for planar Boolean tensor network contractions. We use two methods to accelerate the exponential algorithms by transferring high-dimensional tensors to low-dimensional tensors. We put up a $O(k)$ size planar gadget for any Boolean symmetric tensor of dimension $k$, where the gadget only consists of Boolean tensors with dimension no more than $5$. Another method is decomposing any tensor into a series of vectors (unary functions), according to its \emph{CP decomposition} \cite{tensor-rank}. We also prove the sub-exponential time lower bound for contracting tensor networks under the counting \emph{Exponential Time Hypothesis} (\#ETH) holds.
