量子计算的误区

量子计算不是并行计算

并行计算是通过把多个不相关的计算分散在不同的处理进行的计算方式，而量子计算跟并行计算 并不是这样的模型。量子计算比传统计算机的优势也不在于并行能力，而是量子比特和纠缠特性。

量子计算机不是经典计算机的超集

量子计算机可以计算的问题与经典计算机几乎是相同的。

不过在有些问题上，比如分解质因数、模特卡罗模拟，比传统计算机有不同级别的加速。 一般认为，分解质因数是指数级提速，模特卡罗是平方级别提速。

模拟器 和 真机。

逻辑比特和物理比特

一般说的某个量子算法需要100个比特，是逻辑比特。

物理比特则是承载计算的元器件：比如光子、原子等等

但是物理比特有噪声，一个逻辑比特需要通常 100 到 10000 个物理比特进行模拟。

量子计算机不会通过穷举破解你的密码

网上盛传的量子计算机破解密码的说法大部分都是很有问题的。

• 原理上错了
• 时间尺度上错了

Shor’s algorithm 不是穷举算法，该算法需要至少 1000 逻辑比特破解一个RSA 128密码。 那就意味着 100000 （十万） 到 1000000 （一百万）物理特比。

目前(2021)最有前景的机器有希望拥有127个比特。未来10年，不会出现支持该算法的量子计算机。

经典计算机计算过程

[00] -> 加法器（与门+或非门） -> [00]
[01] -> 加法器（与门+或非门） -> [01]
[10] -> 加法器（与门+或非门） -> [01]
[11] -> 加法器（与门+或非门） -> [11]

量子比特

\[|q\rangle := \alpha[0,1]^T + \beta[1, 0]^T = [\alpha, \beta]^T\]

\[|0\rangle := [0, 1]^T\]

\[|1\rangle := [1, 0]^T\]

\[\alpha^2+\beta^2=1\]

量子比特的观测

\[|q\rangle := \alpha[0,1]^T + \beta[1, 0]^T = [\alpha, \beta]^T\]

观测结果： \(\alpha^2\)概率是 \(|0\rangle\), \(\beta^2\) 概率是 \(|1\rangle\)

两个量子比特

\[|00\rangle,|01\rangle,|10\rangle,|11\rangle\]

纠缠态

\[|q\rangle = 1/\sqrt{2}(|00\rangle + |11\rangle)\]

观测结果只可能是： \[|00\rangle,|11\rangle\]

量子门

如何进行量子计算？

1. 初始化多个量子比特
2. 对问题进行编码
3. 构造量子门电路，改变量子比特编码的概率分布
4. 反复执行量子电路
5. 结果取样

那些问题具有优势？

• 模拟自然过程
• 线性方程求解
• 组合优化
• 蒙特拉罗