论文标题
重新审视的“量子至高无上”：经典物理系统中原始Deutsch-Jozsa问题的低复杂性，确定性解决方案
"Quantum supremacy" revisited: Low-complexity, deterministic solutions of the original Deutsch-Jozsa problem in classical physical systems
论文作者
论文摘要
原始的Deutsch-Jozsa（ODJ）问题是针对尺寸N的Oracle（在此处实现为数据库），根据他们的主张，在经典Turing计算机上对问题的确定性解决方案需要O（n）计算复杂性。他们制作了著名的Deutsch-Jozsa量子算法，该算法在经典计算机上提供了指数加速，即量子计算机中解决方案的复杂性。在本文中，问题是在基于瞬时噪声的逻辑处理器上实现的。结果表明，与量子算法类似，ODJ问题可以通过O [log（n）]复杂性确定性解决。这意味着，通过将真正随机的硬币添加到经典的图灵机中，并且使用这种经典的物理算法也可以加快Deutsch-Jozsa问题的确定性解决方案，与量子算法类似。然后，人们意识到，即使没有噪声/随机硬币，也可以通过更简单的方式使用相同的数据库和Deutsch-Jozsa问题的解决方案来实现。与基于噪声的逻辑相比，该新系统中唯一丢失的功能是能够在整个数据库上进行通用并行逻辑操作。由于ODJ问题不需要后一个功能，因此可以得出结论，即使没有随机硬币，也可以在具有O [log（n）]复杂性的经典计算机上解决该问题。因此，虽然ODJ算法在历史上是量子计算机发展中的重要一步，但不足以证明量子至上。请注意，稍后提出的简化了Deutsch-Jozsa问题，在该领域更受欢迎，但是与本文无关。
The original Deutsch-Jozsa (oDJ) problem is for an oracle (realized here as a database) of size N, where, according to their claim, the deterministic solution of the problem on a classical Turing computer requires O(N) computational complexity. They produced the famous Deutsch-Jozsa quantum algorithm that offered an exponential speedup over the classical computer, namely O[log(N)] complexity for the solution in a quantum computer. In this paper, the problem is implemented on an instantaneous noise-based logic processor. It is shown that, similarly to the quantum algorithm, the oDJ problem can deterministically be solved with O[log(N)] complexity. The implication is that by adding a truly random coin to a classical Turing machine and using this classical-physical algorithm can also speed up the deterministic solution of the Deutsch-Jozsa problem exponentially, similarly to the quantum algorithm. Then it is realized that the same database and the solution of the Deutsch-Jozsa problem can also be realized by using an identical algorithmic structure in a simpler way, even without noise/random coin. The only lost function in this new system, as compared to noise-based logic, is the ability to do generic parallel logic operations over the whole database. As the latter feature is not needed for the oDJ problem, it is concluded that the problem can be solved on a classical computer with O[log(N)] complexity even without a random coin. Therefore, while the oDJ algorithm is historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also simplified Deutsch-Jozsa problem proposed later, which is more popular in the field, however it is irrelevant for the present paper.
