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

本课题首先从组合优化的角度研究广义贝尔不等式的量子非局域性和最大量子违逆，包括半定规划。在量子态空间中探索了量子计算几何，提出了一种计算量子信道容量的新算法。针对代数-几何结构，研究了一些相关的优化问题。广义贝尔不等式从不同的角度揭示了量子的非定域性。这些贝尔不等式对应于某三方图的切多面体的面不等式。通过对完全图的切多面体的切面进行三角消去，得到了生成此类贝尔不等式的统一方法。从理论上和数值上比较了这些贝尔不等式揭示量子非定域性的强度。首先从最优化的角度研究了一类广义贝尔不等式的最大违和问题，并利用半定规划的方法推导了该不等式的界。同时，在计算复杂度方面，给出了该问题与2个证明者1轮交互证明之间新的有趣关系。量子计算几何与经典信息论的情况一样，具有良好的结构。通过冯诺依曼熵及其勒让德变换表征了量子信息几何空间中关于量子散度的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.