We propose an extensive analysis of Simon's algorithm, and we show that it requires little more than $n$ queries to succeed in most cases. We performed the first concrete cost analysis for the exact variant of Simon's algorithm and the offline Simon's algorithm, and show that they require respectively at most $3n$ queries and little more than $n+k$ queries. We also found that for parameter sizes of cryptographic relevance, it is possible to truncate the output of the periodic function to a dozen of bits without any impact on the number of queries, which saves qubits in reversible implementations of Simon's algorithm.
Category / Keywords: foundations / Simon's algorithm, quantum cryptanalysis, query complexity Date: received 23 Jul 2020, last revised 25 Oct 2020 Contact author: xbonnetain at uwaterloo ca Available format(s): PDF | BibTeX Citation Version: 20201025:222516 (All versions of this report) Short URL: ia.cr/2020/919