量子比特如何工作以及它们的优缺点是什么？它们对编程语言有什么影响？

Question

使用量子比比普通比特更能做些什么,它们如何工作？我前一段时间了解他们,似乎量子比特可以同时不只是0或1,而且还0和1存储.我真的不明白它们是如何工作的.有人可以向我解释一下吗？

他们有什么利弊,他们将对像C编程语言有什么影响之后,量子计算机实际上是谁发明的？

当一点(也是一个量子)可以同时获取多个值时,我们如何管理内存？当超过1和0时,我们如何确定某些事物是真还是假？

Answer 1

通过转换问题,可以使用某种量子处理器来解决通过"经典"代码解决的任何"经典"(一旦技术被广泛使用将被称为)问题.例如,要进行数据库搜索,而不是使用基于索引的搜索/二进制搜索,或者对未排序的数据库进行线性搜索,可以使用Grover的算法.此外,为了从前一张海报提到的BQP问题中退一步,NP可以通过Grover的算法(搜索每个可能的解决方案的时间加速)大大加快在时间上运行的经典"解决方案"的问题.随着Shor算法的出现,RSA密码术也变得更加不安全因为它将大数分解成它们的主要因子(RSA所处的铰链)在对数时间内可解.

编辑:Shor的算法实际上在O((log N)^ 3)中运行,这是多项式 - 对数时间.

这种事情的结论是,由于量子算法的性质(将某些函数应用于量子态),预先存在的编程语言如C将无法在量子计算机上使用,除非有人发明了一种映射方法量子门等等到逻辑门(编辑:这已经在这里得到了很大的解决),在这种情况下我们得到的是一个非常非常快的逻辑处理器,当使用像C这样的语言.

PS:我确信最终会有量子计算的OpenGL绑定:P

Answer 2

如果我们能够制造出一台可用的量子计算机（仍然是一个悬而未决的问题），那么它就可以有效地解决（我们认为）经典计算机无法有效解决的某些算法问题。这些是复杂性类BQP中的问题，但不是P中的问题。一大问题是整数分解。正如 Will A 提到的，如果你能快速分解巨大的整数，你就能破解许多现代密码。

问题是，没有人确切知道 BQP 是否真的比 P “更大”——量子计算机可能可以快速完成任何事情，经典计算机也可以。

我们也不知道 BQP 是否和 NP 一样大——例如，没有人找到在量子计算机上解决旅行商问题的有效方法。这是对量子计算机的常见误解。他们可能能够快速解决 NP 完全问题，但也可能不能。没人知道。

http://scottaaronson.com/blog/?p=208好好阅读这个主题（博客的其余部分也是如此）。