量子计算 快速傅里叶算法笔记

So the problem we need to solve is that of multiplying polynomials fast. Doing it the regular convolution way takes quadratic time -O(n2). This is OK for small n but won't do for large n. So what do we do? Here is a sketch of what needs to be done -the Discrete Fourier Transform: Take two polynomials A(x)= a0+ a1x + a2x2+ … + anxnand B(x) = b0+ b1x + b2x2+ … + bmxm