This workshop will bring together researchers from academia and industry to study the capabilities of existing and upcoming quantum computers. Topics will include protocols for characterizing quantum noise, as well as tailoring fault-tolerance protocols to more concrete noise models. The other theme will be proofs of quantumness and other near-term algorithms suitable for such computers, as well as algorithms for scalable fault-tolerant quantum computers.

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

Sergio Boixo (Google), Kostyantyn Kechedzhi (Google)

Quantum computers hold the promise of executing tasks beyond the capability of classical computers. Noise competes with coherent evolution and destroys long-range correlations, making it an outstanding challenge to fully leverage the computation power of near-term quantum processors. We report Random Circuit Sampling (RCS) experiments where we identify  distinct phases driven by the interplay between quantum dynamics and noise. Using cross-entropy benchmarking, we observe phase boundaries which can define the computational complexity of noisy quantum evolution.

This reunion workshop is for long-term participants in the program "Quantum Algorithms, Complexity, and Fault Tolerance," held in the spring 2024 semester. It will provide an opportunity to meet old and new friends. Moreover, we hope that it will give everyone a chance to reflect on the progress made during the semester and since, and sketch which directions the field should go in the future. In an effort to keep things informal and to encourage open discussion, none of the activities will be recorded. Participation in the workshop is by invitation only. 

Sample Schedule (see schedule tab for more detail)

9:00-9:30 AM Check-in refreshments

9:30-10:00 AM Talk 1

10:30-11:00 AM AM Break

11:00-12:00 AM Talk 2

12:00-2:00 PM Lunch

2:00-3:00 PM Talk 3

3:00-3:30 PM PM Break

3:30-4:30 PM Talk 4

4:30-5:30 PM Reception (Day 1 only)

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.

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

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)

There has been a burst of recent progress on quantum error-correcting codes, across the physics, computer science, and math communities. This workshop will bring together researchers from all these communities to share recent progress and exchange ideas. Particular topics covered will include constructions of quantum LDPC codes and new algorithms for quantum codes. 

This is a joint workshop between the Error-Correcting Codes: Theory and Practice program and the Quantum Algorithms, Complexity, and Fault Tolerance program.

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.

This workshop will bring together researchers from academia and industry to study the capabilities of existing and upcoming quantum computers. Topics will include protocols for characterizing quantum noise, as well as tailoring fault-tolerance protocols to more concrete noise models. The other theme will be proofs of quantumness and other near-term algorithms suitable for such computers, as well as algorithms for scalable fault-tolerant quantum computers.

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

Adam Bouland (Stanford University)

Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. Inspired by recent work of Gheorghiu and Hoban, we define the notion of "pseudoentanglement", a property exhibited by ensembles of efficiently constructible quantum states which are indistinguishable from quantum states with maximal entanglement.

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