Skip to main content
Quantum Computing

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

3
  • 1
    $\begingroup$ I'd just like to mention that Simon's algorithm has been used to attack symmetric cryptography, for instance here. However, contrarily to Shor's algorithm which works offline, only needing the public key, attacks using Simon's algorithm require a quantum access to the encryption function. Great answer otherwise! $\endgroup$ Commented Sep 19, 2022 at 13:07
  • $\begingroup$ @TristanNemoz: Thanks Tristan. I edited my answer accordingly and gave you credit for the correction. Of course, feel free to post your own answer concerning the Simon algorithm. $\endgroup$ Commented Sep 19, 2022 at 15:29
  • 1
    $\begingroup$ "I assume that there is no polynomially complex classical algorithm for factorization"; actually, to demonstrate the best speed up, a better example is using Shor's algorithm to compute discrete logs; there are groups where the best known classical algorithm is exponential; Shor's is (of course) polynomial... $\endgroup$ Commented Sep 20, 2022 at 13:14