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.