Advanced Geometric Algorithms Based on Discrete Analysis of Information-Geometric Structures with Applications

信息对象，如Web图，量子信息和知识，表示为几何空间中的流形与坐标自然引入其相关的数值。信息几何学研究这种空间的几何结构，而对于空间中的离散算法的研究却很少。该项目首先研究信息几何（包括量子信息几何）的离散几何结构，然后开发在空间中工作的有效算法。利用毒理想及其Grobner基等计算代数工具，研究了多面体复形的壳性、定向性和Web链接图结构等拓扑性质，并利用图的离散结构和空间信息熵，发展了Web结构的信息压缩技术.针对真实的空间中的可实现性问题，对有向矩阵进行了单纯复形壳的拓扑扩展，并在量子信息几何中设计了离散优化算法，如量子态关于量子发散的Voronoi图，量子态的最小包围球，以及量子通信信道的Holevo容量计算等.作为显著的结果之一，我们首次证明了4信号1量子比特量子信道的存在。量子纠缠和它们的等级结构也从几何的观点进行了研究。有了这些结果，从离散几何学研究量子信息的新方法已被证明是一个有前途的领域。

Information objects such as Web graphs, quantum information, and knowledge are represented by manifolds in geometric spaces with coordinates naturally introduced by their associated numerical values. Information geometry investigates geometric structures of such spaces., while there have been little research on discrete algorithms working in the spaces. This project first investigates discrete geometric structures of information geometry, including quantum information geometry, and then develops efficient algorithms working in the space. Some topological properties such as shelling/orientation of polyhedral complexes and Web link graph structures are also investigated together with computational algebraic tools such as toxic ideals and their Grobner bases.Concerning Web structures, information compression techniques are developed by using discrete structure of the graph with regard to information entropy in the space. Topological extensions of shellings of a simplicial complex are made for oriented matroics, with connection to the realizability issue in real space.Discrete optimization algorithms have been devised in quantum information geometry, such as the Voronoi diagram of quantum states with respect to quantum divergence, minimum enclosing sphere of quantum states in connection with computing the Holevo capacity of a quantum communication channel. As one of remarkable results, we show the existence of a 4-signal 1-qubit quantum channel for the first time. Quantum entanglements and their hierarchical structures are also studied from the geometric viewpoint. With these results such new approaches to quantum information from discrete geometry have been shown to be a promising field.