问题标签 [quantum-computing]

我最近一直在网上研究量子计算。

我们会在有生之年看到这些（曾经吗？）（例如，纠错问题对我来说似乎很棘手）。

如果实用的量子计算成为现实，我想知道是否有任何基于 NP 完全问题的公钥密码算法，而不是整数分解或离散对数。

编辑：

请查看 关于量子计算机的 wiki 文章的“计算复杂性理论中的量子计算”部分。 它指出，量子计算机可以回答的问题类别（BQP）被认为比 NP-完全更容易。

编辑2：

“基于 NP 完全”是表达我感兴趣的东西的不好方式。

我想问的是一种公钥加密算法，其属性是任何破解加密的方法也可以用来破解潜在的NP完全问题。这意味着破解加密证明 P=NP。

我经历了一段对量子计算机如何工作以及如果它们变得实用可能有什么好处感兴趣的时期。我知道他们被谈论破解密码。我感兴趣的是通过基本上尝试所有可能的输入（并行）并查看是否达到任何错误状态来使用它们来验证软件。

我知道这有点天方夜谭，但我想知道其他人是否对量子计算机感兴趣，它们是如何工作的，以及它们有什么用处。

补充：只是为了好玩，让我抛出一个迷你教程：

假设你有 N 位内存可以玩。假设您可以使用输入数据加载这些位（或其中一些位）。然后假设您可以对它们执行有限的操作序列（不使用任何额外的内存），将答案留在其中。

要使用量子计算机执行此操作，您只需确保整个计算是可逆的，通过保留一些位来记录您采用的分支，以便您可以撤消它们。如果这样做，那么所有操作都可以写成 N 位上的简单酉矩阵变换。（酉变换是 N 维坐标系中的纯旋转。）因此执行计算包括在位向量上应用一系列纯旋转。

如果你这样做，那么如果 N 位向量在量子计算机中，它可以被初始化为所有 2^N（或更少）可能的输入在“平行宇宙”中同时叠加的状态。然后，如果您进行计算，它会同时进行所有计算。

现在，要查看其中一个输入是否为您提供特定答案，您所要做的就是让它运行到特定状态。如果你停止它并检查状态，它所做的就是随机选择一个宇宙并丢弃所有其余的。因此，Grover 算法让你做的是，在不停止它的情况下，强调具有答案状态的宇宙的概率。然后你向前运行它，然后向后运行，然后向前运行，以此类推进行多次迭代，直到答案宇宙具有非常高的概率。然后如果你检查它，你很有可能看到你想要的答案。

呼...

How soon can I get a quantum computer? Is there any way to build a simple one? How many years out are they for early early adopters?

I'd like to understand from a high level what a QBit is, how many states it can have, and what types of algorithms will work well in this arena.

Although we'll have to wait at least two or three decades until we can see a practical QC, it seems that theoretical studies are improving dramatically (studies using the free QLC language are good examples). However, does that make us expect that big companies and corporations are building (maybe secretly) ‘quantum software’: each seeking to get the leadership in this domain?

不久前我读到量子计算机可以在很短的时间内（我相信只有几分钟）破解当今使用的大多数类型的散列和加密。这怎么可能？我已经尝试阅读有关它的文章，但我迷失在a quantum bit can be 1, 0, or something else. 有人可以解释这与在没有所有花哨数学的情况下用简单的英语破解此类算法有何关系吗？

在物理学中，它是粒子在特定时间点以多个/平行动态状态存在的能力。在计算中，是一个数据位同时等于 1 还是 0，第三个值（如 NULL[unknown]）还是多个值的能力？.. 这种技术如何应用​​到：计算机处理器、编程、安全等等？.. 有没有人建造了一台实用的量子计算机或开发了一种量子编程语言，例如，程序代码是动态变化的或者是自主的？

与普通比特相比，我们可以用量子比特做更多的事情，它们是如何工作的？我前段时间读过它们，看来量子比特不仅可以存储 0 或 1，还可以同时存储 0 和 1。我真的不明白他们是如何工作的。有人可以向我解释一下吗？

它们的优缺点是什么，在量子计算机真正发明之后，它们会对 C 等编程语言产生什么影响？

当一个位（也是一个量子）可以一次取多个值时，我们将如何管理内存？当不止 1 和 0 时，我们如何确定某事物是真还是假？

对于我的 AI 课程，我必须使用 alpha-beta 修剪制作一个量子井字游戏。

我正在考虑表示棋盘状态的最佳方式——我的第一个直觉是使用一种邻域矩阵，即 9x9 矩阵，onM[i,j]是表示移动的整数（tic-tac -toe) 正方形i并被j标记（如果没有这样的连接 -M[i,j]为零）。如果正方形折叠M[i,i]，则不为 0 。i然后，我将创建一个此类矩阵的博弈树，并使用带有 alpha-beta 修剪的经典极小极大。

然而，这种方法似乎相当昂贵——会有一个相对较大的分支因子加上每个节点的基本操作——检查循环并找到 9x9 矩阵的所有等效状态。

我有一种感觉，必须有一个更聪明的解决方案——也许类似于将量子游戏视为一组经典的井字游戏并使用一种广义的极小极大搜索，所以它都会回归到（小）一组经典的井字游戏问题？我看不出这将如何运作。

有没有人有这个（或类似）问题的经验，你能指出我正确的方向吗？

当我们在等待我们的量子计算机时，是否可以编写一个软件模拟？我怀疑答案是否定的，但希望为什么不这样做的原因可以揭开谜团。