Optimization via Quantum Information Combinatorics and Its Applications to Extend Fundamentals of Quantum Information Science and Technology

本研究计画首先从组合最佳化的观点，包括半定规划的观点，探讨广义贝尔不等式的量子非定域性与最大量子破坏。同时，在量子态空间中探讨了量子计算几何，提出了一种计算量子信道容量的新算法。从代数几何结构的角度研究了相关的优化问题，推广的Bell不等式从不同的角度揭示了量子非定域性。这些贝尔不等式被证明是对应于一个特定的三分图的割多面体的刻面不等式。我们推导出一个统一的方法产生这样的贝尔不等式三角消除面的切割多面体的一个完整的图。这些贝尔不等式进行了比较，从理论上和数值上就其强度，揭示量子非局域性。本文首先从最优化的角度研究了广义Bell不等式的最大违背问题，并应用半定规划方法给出了最大违背的界。同时，在计算复杂度上，证明了该问题与2-prover-1-round交互式证明之间新的有趣关系，证明了量子计算几何与经典信息论情形一样具有良好的结构.在量子信息几何空间中，通过冯诺依曼熵及其勒让德变换刻画了关于量子发散的Voronoi图。研究了纯量子态的Voronoi图，并给出了它们之间的关系。这些结构被应用在量子信道容量的计算中，通过应用量子发散的最小包围球算法。该算法可以产生一个几乎最优的解决方案与一些保证的界限。

This research project first investigates quantum nonlocality and maximum quantum violation of generalized Bell inequalities from the viewpoint of combinatorial optimization, including semidefinite programming. Also, quantum computational geometry is explored in the space of quantum states, which leads to a new algorithm to compute the quantum channel capacity. Some related optimization problems are also studied in view of algebraic-geometric structures.Generalized Bell inequalities reveal quantum nonlocality from various standpoints. Those Bell inequalities are shown to correspond to facet inequalities of the cut polytope of a certain tripartite graph. We derive a unified method of generating such Bell inequalities by applying triangular eliminations to facets of the cut polytope of a complete graph. These Bell inequalities are compared theoretically and numerically with respect to its strength to reveal quantum nonlocality. The problem of finding the maximum violation of a generalized Bell inequality is first investigated from the point of view of optimization, and semidefinite programming is applied to derive bounds. Also, new interesting relation is shown between this problem and the 2-prover 1-round interactive proof in computational complexity.Quantum computational geometry is demonstrated to have nice structure as in the classical information-theoretic case. The Voronoi diagram with respect to quantum divergence in the space of quantum information geometry is characterized via the von Neumann entropy and its Legendre transformation. Voronoi diagrams for pure quantum states are also investigated, and relations among these diagrams are shown. These structures are applied in computing the quantum channel capacity by applying the minimum enclosing sphere algorithm for quantum divergence. This algorithm can produce an almost optimum solution with some guaranteed bound.