[gunfighthacksaw]

Quantum computers are good at solving the hidden subgroup problem, which generalizes RSA and Diffie Hellman.

The reason they do well in this area is that you can implement a Fourier transform with exponentially fewer quantum logic gates than classical logic gates.

Post quantum involves implementing a cryptosystem which can not be reduced to a hidden subgroup problem, but I’m still not sure if this is sufficient (QIP might solve other classes of problems easily)

[ssfrr]

Do you have a good reference on the relationship between quantum computers and Fourier transforms? I’m a DSP researcher by day and this is the first time I’ve heard about this, so my interest is piqued.

[olliej]

There is an excruciating amount of papers, but at least it has a sensible name: you can google “quantum Fourier transform” and go down the rabbit hole of suffering from there :D