量子科技中心_量科网

将任意图的顶点嵌入到树中同时最小化某种重叠度量，是计算机科学和物理学应用中的一个重要问题。在这项工作中，该研究团队考虑了将n个顶点的图G的顶点双射地嵌入到n叶有根二叉树B的叶子中的问题。这种嵌入的拥塞由删除B的任何顶点获得的两个分量的割集的最大大小给出。拥塞cng(G)定义为任何嵌入获得的最小拥塞。该研究团队表明λ₂(G)·2n/9 ≤ cng(G) ≤ λₙ(G)·2n/9，其中0=λ₁(G) ≤ ⋯ ≤ λₙ(G)是G的拉普拉斯特征值。该研究团队还提供了一种通过分层谱聚类原始图给出的收缩启发式算法，数值上发现该方法能有效找到稀疏图的低拥塞嵌入。该研究团队数值比较了不同具有规则结构图族（超立方体和格子）、随机图以及量子电路张量网络表示的拥塞界。研究结果意味着张量网络收缩内存复杂度的下界和上界，基于底层图结构。