10 citations · 11 across the 3 of their papers we have counts for
4 papers
Finding many Collisions via Reusable Quantum Walks
Xavier Bonnetain, André Chailloux, André Schrottenloher +1
Given a random function with domain and codomain , with , a collision of is a pair of distinct inputs with the same image. Collision finding is an…
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
Andris Ambainis, Kaspars Balodis, Jānis Iraids +6
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a d…
Improved Classical and Quantum Algorithms for Subset-Sum
Xavier Bonnetain, Rémi Bricout, André Schrottenloher +1
We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from $\tilde{\mathc…
Quantum Query Complexity of Dyck Languages with Bounded Height
Kamil Khadiev, Yixin Shen
We consider the problem of determining if a sequence of parentheses is well parenthesized, with a depth of at most h. We denote this language as . We study the quantum quer…