博文
量子计算对传统计算机理论的影响
精选
||
P!=NP 对物理的影响： 第三， 量子计算对传统计算机理论的影响
在量子计算机的概念提出来后，它对计算机理论有什么影响呢？
第一个观点是只要是上层的东西就不用管，因为你用高级语言编程的时候根本可以不考虑底层结构；
另一方的观点是由于量子计算是不同的概念，很多东西都必须改变，包括一些算法。
第一种观点并没有错，我们知道量子力学可以退化成经典力学，所以量子计算机肯定可以做经典计算机的事情，不过这不是我们要的重点，我们要的是经典计算机不能做的事情。
7）那何为量子计算机？
计算机说一千道一万，最根本就是比特（bit）以及对它的操作，比特有两种状态，0或者1。在经典力学的世界里，要么是0，要么是1。但是在量子力学的世界里，有可能既是0又是1的状态，这就是态叠加原理。而这样的比特就是（Q-bit）。
这个到底有什么用处呢？想像一下，比如你计算一个函数对所有可能输入的值，原先有两种可能输入，0或者1，所以你要计算2次。现在你可以制造一个0和1的叠加态，把它输入，你一次就可以得出结果了。当然细究起来还有一些细节问题，比如得到叠加态的输出后你怎么读出来，你要测量。量子力学的测量会让系统塌缩到它的本征态，所以一次测量你只能得到一个输出，哪怎么办？不过跳过这些细节，你大体可以明白，量子计算机本质上是基于态叠加原理的，天生的并行计算机。一个比较简单的例子是Deutsch问题及其Deutsch Jozsa算法。
有兴趣可以看下面wiki的解释：
http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm
8）量子计算机对计算机复杂性理论的影响
回想一下，P和NP问题的定义中有多项式时间算法，显然这个是对于计算机而言，如果改成量子计算机，拿情况就不一样了。
比如说，大数的质因数分解这样问题，现在只有指数时间算法（对经典计算机而言）。如果有了量子计算机，用多项式时间算法就可以做到，这就是有名的Shor算法。
有兴趣可以看wiki：
http://en.wikipedia.org/wiki/Shor%27s_algorithm
所以对于量子计算机，P和NP问题就完全不一样了。对于经典计算机，我们下面的结论（如果P！＝NP的话）。图来自于网络。
注：NP－complete是指那些本身是NP问题，同时又是NP-hard问题的问题，何谓NP-hard问题，指那些最难的问题，任何NP问题可以用多项式时间约化成它，NP-hard本身不一定是NP问题。
考虑了量子计算机后，复杂性问题变成下面（图来自于网络），
简单说，BQP，QMA分别是P，NP在量子计算机上的推广。BQP指可以用量子计算机在多项式时间解决的问题，由于量子力学可以退化到经典力学，所以经典计算机可以做的量子计算机肯定也能，所以P是BQP的子集。QMA是指用量子计算机可以在多项式时间验证给定答案是不是正确答案的问题，同样NP是QMA的子集。当然有一些经典计算机的NP问题现在对于量子计算机成了P问题（就是BQP），所以NP和BQP有一定的交集。
这篇是物理理论对计算机复杂性的影响，反过来，复杂性问题对物理理论有何帮助呢？
https://blog.sciencenet.cn/blog-210983-366220.html
上一篇：P!=NP 的八卦传闻
下一篇：数学家让某些物理学家的诺贝尔梦破灭了
在量子计算机的概念提出来后，它对计算机理论有什么影响呢？
第一个观点是只要是上层的东西就不用管，因为你用高级语言编程的时候根本可以不考虑底层结构；
另一方的观点是由于量子计算是不同的概念，很多东西都必须改变，包括一些算法。
第一种观点并没有错，我们知道量子力学可以退化成经典力学，所以量子计算机肯定可以做经典计算机的事情，不过这不是我们要的重点，我们要的是经典计算机不能做的事情。
7）那何为量子计算机？
计算机说一千道一万，最根本就是比特（bit）以及对它的操作，比特有两种状态，0或者1。在经典力学的世界里，要么是0，要么是1。但是在量子力学的世界里，有可能既是0又是1的状态，这就是态叠加原理。而这样的比特就是（Q-bit）。
这个到底有什么用处呢？想像一下，比如你计算一个函数对所有可能输入的值，原先有两种可能输入，0或者1，所以你要计算2次。现在你可以制造一个0和1的叠加态，把它输入，你一次就可以得出结果了。当然细究起来还有一些细节问题，比如得到叠加态的输出后你怎么读出来，你要测量。量子力学的测量会让系统塌缩到它的本征态，所以一次测量你只能得到一个输出，哪怎么办？不过跳过这些细节，你大体可以明白，量子计算机本质上是基于态叠加原理的，天生的并行计算机。一个比较简单的例子是Deutsch问题及其Deutsch Jozsa算法。
有兴趣可以看下面wiki的解释：
http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm
8）量子计算机对计算机复杂性理论的影响
回想一下，P和NP问题的定义中有多项式时间算法，显然这个是对于计算机而言，如果改成量子计算机，拿情况就不一样了。
比如说，大数的质因数分解这样问题，现在只有指数时间算法（对经典计算机而言）。如果有了量子计算机，用多项式时间算法就可以做到，这就是有名的Shor算法。
有兴趣可以看wiki：
http://en.wikipedia.org/wiki/Shor%27s_algorithm
所以对于量子计算机，P和NP问题就完全不一样了。对于经典计算机，我们下面的结论（如果P！＝NP的话）。图来自于网络。
注：NP－complete是指那些本身是NP问题，同时又是NP-hard问题的问题，何谓NP-hard问题，指那些最难的问题，任何NP问题可以用多项式时间约化成它，NP-hard本身不一定是NP问题。
考虑了量子计算机后，复杂性问题变成下面（图来自于网络），
简单说，BQP，QMA分别是P，NP在量子计算机上的推广。BQP指可以用量子计算机在多项式时间解决的问题，由于量子力学可以退化到经典力学，所以经典计算机可以做的量子计算机肯定也能，所以P是BQP的子集。QMA是指用量子计算机可以在多项式时间验证给定答案是不是正确答案的问题，同样NP是QMA的子集。当然有一些经典计算机的NP问题现在对于量子计算机成了P问题（就是BQP），所以NP和BQP有一定的交集。
这篇是物理理论对计算机复杂性的影响，反过来，复杂性问题对物理理论有何帮助呢？
https://blog.sciencenet.cn/blog-210983-366220.html
上一篇：P!=NP 的八卦传闻
下一篇：数学家让某些物理学家的诺贝尔梦破灭了
