机构名称：
¥ 1.0
稍加思考就会发现，经典的 2 n / 2 + 1 次查询（即指数级多）是必要且充分的，可以在最坏情况下确定性地解决问题。充分性是显而易见的（为什么？）。对于必要性，假设我们有一个确定性的经典算法，该算法声称在任何情况下都可以确定地解决这个问题，对于任何满足承诺的 f，同时进行 K ≤ 2 n / 2 次查询。在这里，查询的选择甚至可能以任何方式自适应地取决于先前查询的结果。一个狡猾的对手（具有函数 f ）可以迫使该算法失败，如下所示（从而显示必要性）：当算法应用于他时，他实际上还没有先验地选择他的函数 f ，而只是对所有查询回答 0。最后，他的函数在 K 个输入上固定下来，但如果 K ≤ 2 n / 2，他仍然可以自由地完成他的函数的定义，使其为常数或平衡，并使其与算法得出的任何结论相矛盾。类似地，对于任何概率经典算法，其最终输出仍然需要确定性地正确（尽管在此过程中可以使用概率选择），算法的每个概率分支必须本身确定性地工作，并且上述论点适用于它们，再次表明查询的数量（在任何概率分支上）必须至少为 2 n / 2 + 1。
1 Deutsch-Jozsa（DJ）算法
主要关键词
相关文件推荐
