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

量子信息组合优化及其在扩展量子信息科学与技术基础方面的应用

基本信息

批准号：
17300001
负责人：
IMAI Hiroshi
金额：
$ 10.53万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

项目摘要

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.

该研究项目首先从组合优化（包括半定规划）的角度研究量子非定域性和广义贝尔不等式的最大量子违反。此外，在量子态空间中探索了量子计算几何，从而产生了一种计算量子通道容量的新算法。一些相关的优化问题也从代数几何结构的角度进行了研究。广义贝尔不等式从不同的角度揭示了量子非定域性。这些贝尔不等式与某个三方图的切割多胞形的面不等式相对应。我们通过对完整图的切割多面体的面应用三角消除来导出生成此类贝尔不等式的统一方法。从理论上和数值上比较这些贝尔不等式揭示量子非定域性的强度。首先从优化的角度研究了寻找广义贝尔不等式的最大违反的问题，并应用半定规划来导出边界。此外，在计算复杂性方面，该问题与 2-prover 1-round 交互证明之间显示了新的有趣关系。量子计算几何被证明具有与经典信息论情况一样良好的结构。关于量子信息几何空间中的量子发散的 Voronoi 图通过冯诺依曼熵及其勒让德变换来表征。还研究了纯量子态的 Voronoi 图，并显示了这些图之间的关系。这些结构通过应用量子发散的最小包围球算法来计算量子信道容量。该算法可以产生具有一定保证界限的几乎最优解。