Welcome to TQC 2025, the 20th TQC Conference!

The New Frontier in Low-Overhead Fault-Tolerant Quantum Computation

Fault-tolerant quantum computation (FTQC) is essential for unlocking the full potential of quantum computation, enabling the accurate simulation of noiseless quantum mechanics in our inherently noisy world. Conventionally, FTQC requires overheads that grow polylogarithmically in both the number of qubits and the computational runtime. However, a series of our recent works challenges this conventional understanding by introducing new protocols and analyses that substantially reduce these overheads. These developments open the door to the new frontier in low-overhead FTQC, offering improved scaling in space and time across a broad range of fault-tolerant protocols. In this talk, I will present an overview of our key contributions, highlight their conceptual foundations, and discuss their implications for the future design of scalable quantum computers.

Quantum algorithms for codes and lattices based on Regev's reduction
(joint work with Jean-Pierre Tillich)

In recent years, Regev’s reduction has been used as a quantum algorithmic tool to provide quantum advantage for variants of the decoding problem. Chen, Liu, and Zhandry (Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering, EUROCRYPT 2022) presented a novel quantum algorithm for SIS_infty in a parameter regime unachievable by classical computers. While this regime is far from the one used in post-quantum cryptography, the algorithm already demonstrates how to leverage Regev's reduction for quantum advantage. Following this line of work, a new quantum algorithm called Decoded Quantum Interferometry has been proposed by Jordan et al., which is capable of solving several optimization problems in quantum polynomial time. In particular, they study the Optimal Polynomial Interpolation (OPI) problem, which can be viewed as a decoding problem on Reed–Solomon codes.

In this talk, I will present an overview of this family of quantum algorithms as well as some of our contributions. I will first briefly introduce the main ideas from our paper The Quantum Decoding Problem (Chailloux and Tillich, TQC 2024), where we conduct an extensive study of the decoding problem when errors are in quantum superposition, and show how this can be applied using Regev's reduction. Then, I will present in more detail our work Quantum Advantage from Soft Decoders (Chailloux and Tillich, STOC 2025). In this work, we provide natural and compelling decoding problems for which we believe a quantum advantage exists. Our proof techniques involve the use of a soft decoder for Reed–Solomon codes—namely, the decoding algorithm from Koetter and Vardy. To make this decoder compatible with the setting of Regev’s reduction, we present a novel, generic reduction from a syndrome decoding problem to a coset sampling problem. This yields a powerful and easy-to-use theorem that generalizes previous work and is of independent interest. We also present an extensive study of OPI using the Koetter and Vardy algorithm.

Post-quantum security of lattice-based cryptosystems

Classical number-theoretic cryptosystems (such as RSA and ElGamal) are not secure against adversaries equipped with fully-fledged quantum computers. Given the progress in quantum computing over the past two decades, there is a possibility of practical attacks on these traditional cryptosystems in the near future. For long-term security, we turn to post-quantum cryptosystems, which can be implemented on today’s computers and are conjectured to be secure even against quantum attacks.

In this talk, I will discuss the post-quantum security of lattice-based cryptosystems, which is the most prominent candidates for post-quantum cryptography. We will explore recent classical and quantum attacks, and I will also talk about recent work on establishing fine-grained security guarantees for lattice-based schemes.