Quantum information and complexity theory

量子信息与复杂性理论

• 批准号: 105393-2013
• 负责人: Cleve, Richard
• 金额: $ 2.62万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634702
• 关键词: 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. One topic is the computational complexity of "non-local games", which are scenarios where two (or more) cooperating players who cannot communicate with each other respond to questions from a verifier. The scenario is particularly interesting when the cooperating players are allowed to possess quantum systems whose joint state is "entangled" (a quantum mechanical analogue of "correlated"), which permits them to coordinate their answers in ways that are impossible with classical information. An interesting problem it to determine the optimal coordination possible. There are classes of these games where the computational complexity of this problem is well-understood, but the general problem is not currently even known to be decidable. The other topic concerns the computational complexity of Hamiltonian evolution: simulating the state that arises if an initial state evolves for a specified time-interval under Schrödinger's equation. This is interesting in the context of simulating physical systems, and also because there are quantum algorithms for combinatorial problems that utilize such simulations. There are interesting open questions about the inherent computational costs arising in these processes. Finally, I speculate that some of the ideas arising in this topic might lead to more efficient Trotter-Suzuki type product formulas.

该提案旨在研究量子信息背景下出现的计算复杂性问题。“计算复杂性”与执行计算的固有计算成本有关。“量子信息”是一个信息模型，它捕捉了物理系统中出现的量子力学行为。在这个模型中考虑计算复杂性是很自然的，在过去的二十年里，这导致了几个显著的结果（比如高效的“量子算法”、新的加密协议、通信复杂性的降低和量子“证明系统”）。该建议的具体重点是以下两个主题。其中一个主题是“非局部游戏”的计算复杂性，即两个（或更多）无法相互通信的合作玩家对验证者提出的问题做出回应的场景。当合作的参与者被允许拥有联合状态为“纠缠”的量子系统（“相关”的量子力学模拟）时，这个场景特别有趣，这允许他们以经典信息不可能的方式协调他们的答案。一个有趣的问题是确定最佳的协调可能。在这类游戏中，我们可以很好地理解这一问题的计算复杂性，但一般问题目前甚至还无法确定。另一个主题涉及哈密顿演化的计算复杂性：在Schrödinger的方程下，模拟初始状态在指定时间间隔内演化所产生的状态。这在模拟物理系统的背景下很有趣，也因为有利用这种模拟的组合问题的量子算法。在这些过程中产生的固有计算成本有一些有趣的开放问题。最后，我推测，在这个主题中产生的一些想法可能会导致更有效的特罗特-铃木类型的产品配方。