In recent years, intriguing connections between classical cryptography and quantum computing have emerged. Quantum algorithms have been crucial in developing leading cryptographic assumptions, such as learning with errors, and concepts such as no-signaling have been used to build classical cryptographic protocols. In the last couple of years, a series of papers revealed another surprising, entirely different facet of this relationship: it was shown that classical cryptography could be used to address fundamental questions in quantum computing, such as whether quantum computers can be classically verified, or whether uniquely quantum properties, such as the inherent randomness in quantum computations, can be classically controlled. This project seeks to explore the ways in which classical cryptography can be used to harness the power of quantum computers. The interface between quantum computing and classical cryptography is largely unexplored, and the results mentioned above only hint at the potential impact of this field. This impact could span several areas, including both theoretical and experimental physics, complexity theory and of course cryptography and quantum computing. A major step in realizing this impact is to recruit both students and more senior researchers to the area. It will take significant effort to make quantum computing more approachable to computer scientists, and the investigator seeks to focus on making progress towards this goal, through education, mentoring and interdisciplinary collaboration.
The investigator will build on recent work which has shown that classical cryptography can be used to verify quantum computations, both generally and in more restricted settings. The properties of these protocols are not yet fully understood, and one objective of this project is to gain a better understanding of the extent to which cryptographic techniques can be used to characterize quantum machines. While the work on verification clearly shows that classical cryptography is useful in testing quantum devices, the connection between cryptography and quantum computing seems to have many more facets, as demonstrated by recent work which shows that cryptography can be used as a means of employing quantum computers for useful tasks. To do so, classical cryptography is used to leverage quantum properties, such as the inherent randomness generated in quantum computations. The second aspect of this project focuses on further exploration of this connection: can new, classically impossible primitives be built by combining uniquely quantum properties and classical cryptography? The study of these two general directions will yield insight into the power and limitations of quantum computers.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
