Optimal Merging in Quantum K-XOR and K-Sum Algorithms

Explore quantum algorithms for solving k-xor and k-sum problems in this conference talk presented at Eurocrypt 2020. Delve into the Generalized Birthday Problem and its applications, examining Wagner's algorithm and known quantum complexities. Learn about classical merging as a sampling procedure and depth-first traversal of Wagner's tree. Discover quantum merging techniques, including a 4-xor example and the re-optimization of the tree structure. Investigate the general strategy for merging 4 lists with a single solution, comparing Schroeppel and Shamir's 4-list method to quantum approaches. Analyze time complexities and gain insights into the transition from classical to quantum algorithms in this field.

Intro
Outline
Generalized Birthday Problem(s)
Applications
Wagner's algorithm in a single slide
An example with k = 4
Known quantum complexities
Previous exponents (with QAQM)
Quantum search
Classical merging as a sampling procedure
Depth-first traversal of Wagner's tree
Quantum merging
4-xor example
We have to re-optimize the tree
General strategy
Merging 4 lists with a single solution
Schroeppel and Shamir's 4-list method
From classical to quantum
Time complexity of this example
General comparison
Conclusion