3

量子アルゴリズムについて読んでいたとき、Deutsch-Jozsa アルゴリズムに直面しました。その問題を非量子アルゴリズムで解決しようとすると、アルゴリズムの時間の複雑さが指数関数的になることがわかりました。今、量子コンピューターの量子アルゴリズムとしての Deutsch-Jozsa アルゴリズムの時間計算量を知りたいですか?

4

1 に答える 1

4

ウィキペディアによると、量子アルゴリズムの複雑さは一定です。

Deutsch-Jozsa 量子アルゴリズムは、fの 1 回の評価で常に正しい答えを生成します。

アルゴリズム自体は、反復なしの量子状態に関するいくつかの計算です/...したがって、複雑さはO(1)です。

于 2011-08-20T11:59:21.033 に答える