Quantum-Classical Correlation Games and New Analyses of Discrete-Continuous Optimization and Computational Complexity

量子经典相关博弈以及离散连续优化和计算复杂性的新分析

• 批准号: 20300002
• 负责人: IMAI Hiroshi
• 金额: $ 12.15万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20300002/
• 关键词: 量子コンピュータ; 量子計算; アルゴリズム; 量子情報; 離散数学; 量子エレクトロニクス; 計算機システム

Quantum Computing overcomes the barriers of current classical computers through computational power via quantum effects. This research focuses on quantum correlation as such effects. We analyze quantum correlation in a unified way as follows : (1) revealing discrete aspects of quantum correlation by the theory of cut polytopes in combinatorial optimization, (2) investigating maximum quantum violations by continuous optimization, and (3) analyzing quantum correlation by multi-prover interactive proof in computational complexity theory. Furthermore, problems in new quantum computational models and quantum information are explored through discrete and continuous geometric structures.

量子计算通过量子效应的计算能力克服了当前经典计算机的障碍。本研究的重点是量子相关效应。我们对量子相关性进行了统一的分析：(1)利用组合优化中的切多体理论揭示量子相关性的离散性，(2)利用连续优化研究最大量子违反，(3)利用计算复杂性理论中的多证明者交互证明分析量子相关性。此外，通过离散和连续几何结构探索了新的量子计算模型和量子信息中的问题。

项目成果

Solvability of Sliding Atoms Puzzle on a Lattice

格子上滑动原子难题的可解性

• 发表时间: 2008
• 期刊: Proceedings of the 8th Asian Conference on Quantum Information Science Vol.1
• 作者: A.Inoko;N.Kakiuchi;M.Yoshimitsu;S.Q.Cai;M.Mikage;N. Fu and H. Imai
• 通讯作者: N. Fu and H. Imai

Revisiting Hyperbolic Voronoi Diagrams from Theoretical, Applied and Generalized Viewpoints

• DOI: 10.1109/isvd.2010.13
• 发表时间: 2010-06
• 期刊: 2010 International Symposium on Voronoi Diagrams in Science and Engineering
• 作者: T. Tanuma;H. Imai;Sonoko Moriyama

Analyzing Geometric Realizability Problems by Semidefinite Programming.

通过半定规划分析几何可实现性问题。

• 发表时间: 2008
• 期刊: Proceedings of the Kyoto RIMS Workshop on Computational Geometry and Discrete Mathematics
• 作者: H.Miyata;S.Moriyama;H.Imai
• 通讯作者: H.Imai

Large scale matroid enumeration and analysis of orientation

大规模拟阵枚举与方向分析

• 发表时间: 2008
• 期刊: Proceedings of the Kyoto RIMS Workshop on Computational Geometry and Discrete Mathematics Vol.1
• 作者: Y. Matsumoto;S. Moriayma;H. Imai and D. Bremner
• 通讯作者: H. Imai and D. Bremner

幾何から量子そしてその先

从几何到量子及其他

• 发表时间: 2011
• 作者: Sigunga D.O.;Hoshino M.;Onyango J.C.;Asanuma S. and Kimura M.;今井浩
• 通讯作者: 今井浩