4 papers
IQP circuits for 2-Forrelation
Quentin Buzet, André Chailloux
The 2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating and …
Quantum advantage from soft decoders
André Chailloux, Jean-Pierre Tillich
In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work…
The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction
Agathe Blanvillain, André Chailloux, Jean-Pierre Tillich
We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back…
Compressing integer lists with Contextual Arithmetic Trits
Yann Barsamian, André Chailloux
Inverted indexes allow to query large databases without needing to search in the database at each query. An important line of research is to construct the most efficient inverted i…