algorithm - Deutsch-Jozsa 算法

Question

当我阅读量子算法时，我遇到了 Deutsch-Jozsa 算法，我发现如果我们想在非量子算法中解决这个问题，我们的算法将具有指数时间复杂度。现在我想知道Deutsch-Jozsa算法作为量子计算机上的量子算法的时间复杂度是多少？

Answer 1

根据维基百科，量子算法的复杂性是恒定的：

Deutsch-Jozsa 量子算法通过对f的一次评估产生一个始终正确的答案。

该算法本身只是对量子态的一些计算，没有任何迭代/......所以复杂度是O(1)。