问题标签 [computer-science]

量子算法有用吗？

有没有人成功地将量子算法用于任何用途？

我正在查看我的理论计算机科学课程的教学大纲，并在上下文无关语法的标题中列出了“闭包属性”。我翻阅了关于这个主题的教科书，发现很少。目前它所拥有的东西有点超出我的想象（我还没有上过这门课程），但我了解一点。

我想知道上下文无关语法中的闭包概念是否与函数式编程中的闭包概念相同或相关。据我所知，它谈到了结合语法和解决重叠问题。书中的部分有很多部分我还不明白，所以我不确定这些想法是否相同。

（更多背景信息：我正在给教授写一封电子邮件，询问是否可以将课程从 Perl 切换到 Ruby 或 Python。如果这些概念相关，那可能是我们应该使用 Ruby 而不是 Perl 的另一个原因。）

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

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

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

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

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

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

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

呼...

我一直在这里和那里阅读有关使用“蚁群”模型作为优化各种类型算法的启发式方法的内容。但是，我还没有找到一篇文章或书籍以介绍性的方式讨论蚁群优化，甚至是非常详细的讨论。谁能指出我可以了解更多关于这个想法的一些资源？

我正在实施一个尽可能接近正式定义的 DFA 作为学习练习（和博客材料）

我计划使用一个 java.util.Set ，其中定义中涉及一个集合。

该定义涉及一组元组来定义合法的状态转换：(state,symbol) -> nextState。

我有一个带有成员 state、symbol 和 nextState 的 Transition 类。我已经实现了 equals() 和 hashCode() 来指示如果两个转换在状态和符号上匹配，则它们是相等的。然后我有一个 java.util.Set 的 Transition 实例。

在我的处理算法中，当我读取下一个符号时，我拥有当前状态。我预计使用这两个构建一个 Transition 对象，从 Set 中提取匹配的 Transition，然后它会告诉我下一个状态，我可以迭代。

但是 - 我看不到任何提取 java.util.Set 成员以供进一步使用的方法。我可以删除（对象 o），但这只是返回布尔值。

我究竟做错了什么？

哪些语言或平台影响了 .NET 1.0 团队从一开始就内置了属性的概念？这是面向方面的事情吗？序列化？或者是其他东西？当时我还在 VB6 领域，从未使用过任何 1.0 之前的 .NET 版本。

我已经阅读了“什么是图灵完备”和维基百科页面，但我对正式证明的兴趣不如对图灵完备的实际意义感兴趣。

我实际上想要决定的是我刚刚设计的玩具语言是否可以用作通用语言。我知道如果我可以用它编写图灵机，我可以证明它是。但在我相当确定成功之前，我不想进行那个练习。

是否有最小的功能集，没有图灵完备性是不可能的？是否有一组功能几乎可以保证完整性？

（我的猜测是条件分支和可读/可写的内存存储将使我大部分时间到达那里）

编辑：

我想我已经说“图灵完成”了。我试图以合理的信心猜测具有特定功能集的新发明语言（或者具有特定指令集的 VM）将能够计算任何值得计算的东西。我知道证明你可以用它构建图灵机是一种方法，但不是唯一的方法。

我希望的是一套指导方针，例如：“如果它可以做 X、Y 和 Z，它可能可以做任何事情”。

我的理解是哈希码和校验和是相似的东西 - 一个数值，为数据块计算，相对唯一。

即两个数据块产生相同数字散列/校验和值的概率足够低，以至于可以忽略应用程序的目的。

那么我们是否对同一事物有两个词，或者哈希码和校验和之间是否存在重要区别？

通过“理论计算机科学主题”，我指的是诸如常规语言与非常规语言、抽引引理和语法之类的东西。

我熟悉有限自动机和正则表达式在现实世界中的应用，但是诸如此类的其他主题给我带来了更多问题，因为我没有看到任何现实世界的应用。

我没有计算机科学背景，对 CS 的全部内容只有初步的了解。但是，我想知道，过去五年中最重要的 CS 进步是什么？

为了让您了解我是多么的无知，我无法说出这些进步中的任何一个。但是，请不要让我知道所有血腥的细节。

我不是在寻找有关 CS 的教育或有关 CS 历史的故事。就这个问题而言，只有过去五年才重要！:-)