Quantum computation is entering an exciting new period. Small- to medium-scale quantum computers are around the corner, and the biggest upcoming challenges are expected to be algorithmic. The first major challenge is identifying what kinds of computational tasks such computers will be useful for, given that for the foreseeable future, the scale issue will be compounded by minimal or nonexistent error correction. The second challenge is the testing of such devices, as direct simulation by classical computers is all but impossible and running a trace on the quantum program is ruled out by the basic laws of quantum physics.

Providing answers to these questions requires a collaboration between classical theoretical computer science and physics, chemistry, and mathematics. On the quantum algorithms front, there are great challenges in proposals for quantum machine learning and quantum annealing, with connections to classical machine learning, algorithms for low-rank matrix completion, and MCMC algorithms. The most promising algorithmic application for quantum computers in the long run, their "killer app," is expected to be the simulation of quantum systems and quantum chemistry.

On the theoretical computer science end, existing work on testing quantum devices has already led to exciting connections with the theory of interactive proof systems and theoretical cryptography. These connections will evolve into a beautiful and deep theory as the challenges in complexity theory, cryptography, and security raised by interactions with quantum devices are more systematically explored.

This semester-long program brought together researchers from computer science, physics, chemistry, and mathematics to collaborate on formalizing and tackling these questions.