by Sandy Irani
This is a particularly exciting time in the field of quantum information and computation, as advances in quantum computers are happening at a striking pace. The most significant recent milestone was the announcement by Google last fall that its 53-qubit quantum computer was able to perform a computational task that we believe even the most powerful classical computer cannot complete in a reasonable amount of time — a feat known as quantum supremacy. These developments have placed the field of quantum computation in the spotlight, as we seek to answer fundamental questions about what these devices will be capable of when they can be built on a large scale. Quantum computers are inherently noisy, so measuring, characterizing, and ultimately correcting the noise generated by these devices is of the utmost importance. In the meantime, researchers are actively working on how to harness the power of the smaller, faultier versions that are being developed now.
The origins of quantum computing date back to the 1980s, when Richard Feynman and others noticed that the ability of classical computers to simulate quantum systems is inherently limited, due to the exponential number of parameters required to fully describe a quantum state. Feynman reasoned that in order for a computer to simulate a quantum system, the computer itself should exploit the properties of quantum mechanics in how it stores and manipulates information. While potential applications in physics and chemistry remain the most likely “killer apps” for quantum computers, researchers have branched out to develop quantum algorithms that could potentially offer speedups for a much broader array of computational problems in diverse application areas.
The Simons Institute’s Spring 2020 program on The Quantum Wave in Computing brought together researchers working in physics, chemistry, mathematics, and computer science to advance our understanding of these new and still mysterious computational devices. The program was scheduled alongside the Simons program on lattices to take advantage of the growing synergy between these two areas. The connection is actually based on the possibility that quantum computers can't solve certain problems related to lattices. Since a large-scale, fault-tolerant quantum computer will be able to break most of the cryptosystems in use today, cryptographers are working to develop new cryptographic schemes based on the hardness of lattice problems. Interestingly, this conjectured limitation also enables protocols to test that quantum computers are performing correctly. These timely connections were the focus of the workshop on Quantum Cryptanalysis of Post-Quantum Cryptography, organized jointly by both programs.
The Quantum Wave program featured four additional workshops. The first was a boot camp designed to bring participants up to speed on recent developments on key program themes.
The second workshop, on Quantum Algorithms, explored, among other topics, the interplay between machine learning and quantum algorithms, including quantum algorithms for problems in machine learning, quantum-inspired classical algorithms for machine learning, and machine learning techniques for hybrid quantum-classical algorithms. Another main theme of the workshop was quantum simulation for physics and chemistry, spanning the spectrum from algorithms for full-scale, fault-tolerant quantum computers to promising methods for quantum chemistry on near-term devices.
Over the course of March 2020, the circumstances for the Quantum Wave program and the rest of the world changed dramatically as we were all called to shelter in place to prevent the spread of the coronavirus. This of course was a source of concern, as the success of the Simons Institute is built on the understanding that new scientific ideas are best catalyzed by bringing researchers together in the same place. Indeed, it has been the chance interactions during informal teas and the clusters of researchers around whiteboards in the open workspaces that have led to so many exciting new developments at Simons. Nonetheless, the community has shown remarkable resilience in coming together electronically. Afternoon teas took place over videoconference, research projects that began during the first part of the program were carried out in small groups remotely, and the remaining two workshops took place over Zoom, with an adjusted schedule to accommodate speakers from around the world. To cite some early data: the first remote workshop was extremely well attended, with 315 participants from 29 countries on the Zoom videoconference alone and over 3,000 live and on-demand views on YouTube within the first couple of days.
The third workshop, on Quantum Protocols, explored two very different themes with the hope that more connections would emerge between the two. The first, very practical, theme was how to devise tests to benchmark and validate the performance of real-world quantum computers. The second broad theme was more theoretical and explored how a limited classical computer can test multiple quantum devices that cannot communicate with each other, even if those quantum devices are extremely powerful. This breakthrough result has important connections to computational complexity theory and mathematics.
The final workshop, on Quantum Devices, focused on the state of the art in the experimental realization of quantum computers. The workshop explored further developments in quantum supremacy experiments in order to bolster the claim that quantum computers are fundamentally more powerful than their classical counterparts. The more challenging the task that a quantum computer can perform, the more convincing it will be that classical computers cannot match their capabilities. The workshop also explored the prospects for running algorithms for quantum simulations on quantum computers in the near future.
It would have been hard to imagine even several years ago the dramatic advances that have recently taken place in the field of quantum computation. The Simons program on the Quantum Wave in Computing will no doubt help inspire many of the exciting advances that lie ahead.
- Letter from the Director, June 2020
- Computational and Statistical Tools to Control a Pandemic | Theoretically Speaking
- Berkeley in the 80s: Manuel Blum
- Simons Institute Polylogues: Algorithms and Race
- Differential Privacy: Issues for Policymakers
- From the Inside: Lattices: Algorithms, Complexity, and Cryptography
- Research Vignette: Generalization and Interpolation
- Research Vignette: The Many Dimensions of High-Dimensional Expanders
- Cooks, in Theory