Quantum information and complexity theory

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

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.