Quantum information and complexity theory

量子信息与复杂性理论

• 批准号: 105393-2013
• 负责人: Cleve, Richard
• 金额: $ 2.62万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=521917
• 关键词: Quantum; information; complexity; theory

The proposal is to investigate computational complexity issues that arise in the context of quantum information. "Computational complexity" is concerned with the inherent computational costs of performing computations. "Quantum information" is a model of information that captures the quantum mechanical behavior that arises in physical systems. It is natural to consider computational complexity in this model and this has resulted in several remarkable results during the past two decades (such as efficient "quantum algorithms", novel cryptographic protocols, reductions in communication complexity, and quantum "proof systems"). The specific focus of the proposal is on the following two topics.

该提案旨在研究量子信息背景下出现的计算复杂性问题。“计算复杂性”与执行计算的固有计算成本有关。“量子信息”是一种信息模型，它捕捉物理系统中出现的量子力学行为。在这个模型中考虑计算复杂性是很自然的，这在过去的二十年中导致了一些显着的结果（如有效的“量子算法”，新的密码协议，降低通信复杂性，量子“证明系统”）。该提案的具体重点是以下两个专题。