Welcome to TQC 2025, the 20th TQC Conference!

Composing Quantum Algorithms

Composition is something we take for granted in classical algorithms design, and in particular, we take it as a basic axiom that composing ``efficient'' algorithms should result in an ``efficient'' algorithm -- even using this intuition to justify our definition of ``efficient.'' Composing quantum algorithms is a much more subtle affair than composing classical algorithms. It has long been known that zero-error quantum algorithms do not compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In fact, in the bounded-error setting, quantum algorithms can even avoid the log factor needed in composing bounded-error randomized algorithms that comes from amplifying the success probability via majority voting. This latter point hints at a fundamental difference between quantum and classical computing, and has recently been used to make progress on the complexity theoretic question of QMA vs. QMA1. In this talk, I will try to give some intuition for how composing quantum algorithms is different from the classical case, and what we might learn from this difference about the power of quantum computing in general.

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.