Det er interessant å sammenligne [[Simons algoritme]] med [[Kvante-kollisjonsøk]]: Klassisk er disse problemene ekvivalente, i den forstand at optimal strategi og kjøretid er den samme, men kvantisk er det en *eksponentiell* forskjell mellom de to. Dette kommer fundamentalt av den ekstra strukturen i dette problemet: I begge tilfeller kan funksjonene være 2-til-1, men i dette tilfellet er *alle* verdiene skiftet med den samme verdien $s$, som tillater kvantealgoritmen å hente den ut langt mer direkte. Dette er kanskje det tydeligste eksempelet på hva [[Scott Aaronson]] spør om i [How Much Structure Is Needed for Huge Quantum Speedups?](https://arxiv.org/pdf/2209.06930.pdf). [Andrew Childs sier](https://youtu.be/M0e5gkf7QSQ?t=865) (edited for clarity): > In this collision problem, we somehow don't have enough structure to get a fast quantum algorithm. In the case of Simon's problem, which a quantum computer can use to be a lot faster. Of course, that additional structure could in principle be exploited by a classical algorithm as well, but it turns out that it's not structure that is useful for a classical algorithm. So, what we would like to understand in general is: When does this happen? What are the problems for which we have fast quantum algorithms but not fast classical algorithms? And digging down a little bit more, what are the structures that enable exponential quantum speedup? What are the kinds of problem where we can really take advantage of this high-dimensional interference? Også relatert er den litt eldre og mer tekniske artikkelen til [[Scott Aaronson]] og [[Andris Ambainis]], [The Need for Structure in Quantum Speedups](https://arxiv.org/abs/0911.0996).