主题：【原创】科普--量子计算机到底是什么 -- bnugirl

傅立叶变换 Fourier transformation 是啥呢 就是把一个方程转化为它的频率方程 举个例子吧 sin(x) 它的周期是2*pi 频率是1/(2*pi) 在Fourier domain里 它就变成了delta(f+-1/(2*pi)) 它只在+-1/(2*pi)这两点上有定义 在其他地方都是0

量子算法 也是聪明地用了量子傅立叶变换

再说这个Shor's factorization algorithm 它用了一个数学定理 如果要分解一个整数N 任选一个小于它的整数 x 取n=0,1,2, ..., N 作x^n mod N 得到的结果是一个周期为r的周期性序列 x^(r/2) + 1或者 x^(r/2)-1 和N的最大公约数 就是N的一个因子 利用这个定理 就把这个factorization问题转化成了算周期或者频率的问题 用傅立叶变换 可以很容易地得到周期

for example, pick N=15, x=2

n=0,1,2,3,...15

x^n mod N=1,2,4,8,1,2,4,8,....

r=4 x^(r/2)+1=5 x^(r/2)-1=3 5 and 3 are factors of N=15.

那为什么只有量子计算机能用这个定理 传统计算机不能用这个定理呢 因为只有量子计算机可以同时对2^n个状态作运算 传统计算机只能一个一个作 所以只有量子计算机可以利用这个定理 快速地解决factorization问题