问Deutsch-Jozsa算法
EN

Stack Overflow用户

提问于 2011-08-20 19:50:37

回答 1查看 596关注 0票数 1

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

发布于 2011-08-20 19:59:21

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

，Deutsch-Jozsa量子算法生成的答案总是正确的，只需对f进行一次评估。

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

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/7131569

复制

相似问题

问Deutsch-Jozsa算法EN