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

信息对象，如Web图形、量子信息和知识，由几何空间中的流形表示，其相关的数值自然引入坐标。信息几何研究的是这类空间的几何结构，而在这类空间中工作的离散算法的研究却很少。这个项目首先研究了信息几何的离散几何结构，包括量子信息几何，然后开发了在空间中工作的高效算法。结合计算代数工具，如毒性理想及其Grobner基，研究了多面体复合体的一些拓扑性质，如多面体复合体和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.