In classical cryptography, it has long been known that the existence of one-way functions is the minimum assumption. However, in quantum cryptography, where quantum computation and communication are possible, several recent studies have shown that it is not necessarily the case. This workshop will explore foundations of quantum cryptography without one-way functions to answer the ultimate open problem, "What is the most fundamental assumption in quantum cryptography?"

Speakers: Tomoyuki Morimae (Kyoto University), Prabhanjan Ananth (UC Santa Barbara), Andrea Coladangelo (University of Washington), James Bartusek (UC Berkeley), and Jiahui Liu (University of Texas at Austin)

Event description forthcoming. This is a joint workshop with CIQC. For more information, visit: https://ciqc.berkeley.edu/ciqc-colloquium

Quantum Gibbs sampling is a family of quantum algorithms for simulating many-body physics in thermal equilibrium, which can be understood as the quantum analog of classical Markov chain Monte Carlo algorithms. We plan to cover quantum algorithms for sampling Gibbs states, techniques for proving mixing times, and obstructions to fast mixing. The goal is to introduce the basic concepts and techniques to newcomers and build towards an open-ended discussion.

Recent developments in quantum algorithms, particularly the 2021 discovery of an apparent exponential quantum speedup for the SIS-infinity problem by filtering, and the 2024 discovery of an apparent exponential quantum speedup for the optimal polynomial intersection problem by decoded quantum interferometry, provide new motivation for the quantum decoding problem. Here, one is given a codeword from a classical error correcting code, which has been subjected to a coherent superposition of symbol-flip errors, and one wishes to recover the original codeword using an efficient quantum circuit. In this workshop we will survey the current state of the art in quantum decoding, present open problems in quantum decoding motivated by algorithmic applications, and then work on these problems together.

In classical cryptography, it has long been known that the existence of one-way functions is the minimum assumption. However, in quantum cryptography, where quantum computation and communication are possible, several recent studies have shown that it is not necessarily the case. This workshop will explore foundations of quantum cryptography without one-way functions to answer the ultimate open problem, "What is the most fundamental assumption in quantum cryptography?"

Speakers: Tomoyuki Morimae (Kyoto University), Prabhanjan Ananth (UC Santa Barbara), Andrea Coladangelo (University of Washington), James Bartusek (UC Berkeley), and Jiahui Liu (University of Texas at Austin)

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

Event description forthcoming. This is a joint workshop with CIQC. For more information, visit: https://ciqc.berkeley.edu/ciqc-colloquium

Quantum Gibbs sampling is a family of quantum algorithms for simulating many-body physics in thermal equilibrium, which can be understood as the quantum analog of classical Markov chain Monte Carlo algorithms. We plan to cover quantum algorithms for sampling Gibbs states, techniques for proving mixing times, and obstructions to fast mixing. The goal is to introduce the basic concepts and techniques to newcomers and build towards an open-ended discussion.

Recent developments in quantum algorithms, particularly the 2021 discovery of an apparent exponential quantum speedup for the SIS-infinity problem by filtering, and the 2024 discovery of an apparent exponential quantum speedup for the optimal polynomial intersection problem by decoded quantum interferometry, provide new motivation for the quantum decoding problem. Here, one is given a codeword from a classical error correcting code, which has been subjected to a coherent superposition of symbol-flip errors, and one wishes to recover the original codeword using an efficient quantum circuit. In this workshop we will survey the current state of the art in quantum decoding, present open problems in quantum decoding motivated by algorithmic applications, and then work on these problems together.