Tight Bounds for Simon's Algorithm.
Xavier Bonnetain · IACR Cryptology ePrint Archive · 2020
Simon’s algorithm is the first example of a quantum algorithm exponentially faster than any classical algorithm, and has many applications in cryptanalysis. While these quantum attacks are often extremely efficient, they are generally missing some precise cost estimate. This article aims at resolving this issue by computing precise query costs for the different use cases of Simon’s algorithm in cryptanalysis.