Quantum computation has forced a dramatic change in our beliefs about the foundations of computer science, the security of cryptosystems, and the nature of quantum systems. This award focuses on several fundamental algorithmic questions that arise out of this viewpoint. The first is the design of new quantum algorithms. The challenge here is that the major paradigm for the design of quantum algorithms - the hidden subgroup framework - has recently been shown to have severe limitations in its applicability. The center will explore several approaches, including a new framework for the design of quantum algorithms via the quantum approximation of tensor networks, as well as recent work on the use of quantum algorithms for discovering hidden nonlinear structures.
Establishing the limits of quantum algorithms is equally important to the possibility of designing efficient classical cryptosystems that are immune to quantum cryptanalysis. Such "post-quantum" cryptosystems could have an enormous practical impact well before the first working quantum computer is ever built. For this to happen it is necessary to better understand the quantum hardness of concrete classical cryptosystems such as the lattice-based cryptosystems or the McEliese cryptosystem. A different approach would involve designing novel cryptosystems whose security is based on already established quantum hardness results in the hidden subgroup framework.
The center would also study fundamental questions in quantum complexity theory, including the complexity of quantum interactive proof systems. Arguably the most important challenge is proving the quantum analog of the celebrated PCP theorem. This would have wide implications including quantum hardness of inapproximability results, improved fault-tolerance results for adiabatic quantum computing, as well as implications for theoretical condensed matter physics. Another fundamental question is the power of multi-prover quantum interactive proof systems. Resolving whether or not this complexity class is NEXP as in the celebrated classical result MIP = NEXP, is expected to provide important insights into the nature of quantum entanglement.
