Quantum information and 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.