4 ms·
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 c
by gunfighthacksaw 5y ago
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 5y agoDo 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 5y agoThere 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