This Spring at the Simons Institute

by Prasad Raghavendra

This spring, the Simons Institute is hosting programs on lattices and on quantum computation, two fields with strong interactions between them that are both entering an exciting new period. It has been an intense and packed semester with two boot camps, three workshops in each program, and a joint workshop between the two. Although we recently moved our activities online due to the coronavirus closures, research progress and community life continue.

Quantum computers seem closer to reality than they have ever been. There is genuine excitement at the opportunities they will bring. It is clear, however, that the big challenges that lie ahead are not purely technological, but algorithmic as well. First, we need to identify computational tasks that can be carried out on these noisy quantum computing devices but are out of reach for classical computational devices. Second, we must develop algorithms and protocols for testing these quantum devices, as direct simulation by classical computers is all but impossible.

On the algorithmic front, the most promising application for quantum computers would be the simulation of quantum systems and quantum chemistry. There have also been proposals for quantum algorithms for machine learning and quantum annealing, but several challenges remain on this end.

The past couple of years have seen major breakthroughs on the quantum complexity front. New protocols have been designed for classical verification of quantum computations and generating certifiably random bits. In a recent breakthrough, interactive proofs with entangled provers have been shown to be astronomically more powerful than classical proof systems in that they can be used to certify that a Turing machine halts to a polynomially bounded verifier. Not only is this a major advance in quantum proof systems, but it has led to resolution of long-standing open questions such as the Connes embedding problem.

The program The Quantum Wave in Computing, organized by Andrew Childs, Ignacio Cirac, Umesh Vazirani, and Thomas Vidick, comes at this opportune moment. Leading experts on these topics from computer science, physics, chemistry, and mathematics are participating in this program.

The concurrent program on Lattices: Algorithms, Complexity, and Cryptography is organized by Vinod Vaikuntanathan, Daniele Micciancio, Oded Regev, and Hoeteck Wee, along with Simons Institute Director Shafi Goldwasser.

As a fundamental link between number theory and geometry, integer lattices have been extensively studied since the 18th century. In computer science, lattices rose to prominence through their tremendous impact on the theory and practice of cryptography. On the one hand, lattices and algorithms on lattices serve as potent tools for breaking cryptosystems. At the same time, lattices yield new ways to realize basic cryptographic primitives such as one-way functions and public-key encryption schemes with a clean theoretical framework of worst-case to average-case reductions to back them. More recently, they have been successfully applied to construct powerful and game-changing cryptographic constructs such as fully homomorphic encryption. Finally, lattice-based cryptosystems are generating a tremendous amount of interest as a result of their apparent resistance to quantum attacks.

Despite this promise, widespread use of lattice cryptography at Internet scale requires major advances in our understanding of the hardness of the lattice problems that underlie the security of these cryptosystems. Progress on the underlying fundamental open questions is only possible with a concerted effort by researchers from diverse areas, including (algebraic) number theory, (quantum) algorithms, optimization, cryptography, and coding theory. Researchers drawn from all these communities are participating in an intense program this semester. Starting with a boot camp, the program includes four workshops that cover all algorithmic aspects of lattices and lattice-based cryptographic constructions (including the joint workshop with the quantum program).

Over the summer, the Institute will host a cluster on Interpretable Machine Learning. The scheduled program on Computational Innovation and Data-Driven Biology has been postponed due to coronavirus pandemic.

The cluster on Interpretable Machine Learning is organized by Shai Ben-David, Zachary Lipton, Ruth Urner, and Bin Yu, and will explore theoretical and philosophical foundations around how to interpret machine learning models. With machine learning models increasingly making decisions that directly impact individuals, it is critical that their results be interpretable in order to make them amenable to regulation and transparently fair. This cluster will bring together experts in theoretical computer science, machine learning, statistics, causal inference, and fairness to systematically tackle the issue of interpretability.

 

 

 

Related articles

Related stories

,