Алгоритм Дойча-Йоже

Question

Когда я читал о квантовых алгоритмах, я столкнулся с алгоритмом Дойча-Йоссы, и я увидел, что если мы хотим решить эту проблему с помощью неквантового алгоритма, наш алгоритм будет иметь экспоненциальную временную сложность. Теперь я хочу знать, какова временная сложность алгоритма Дойча-Йосса как квантового алгоритма на квантовых компьютерах?

Answer 1

Согласно Википедии сложность квантового алгоритма постоянна:

Квантовый алгоритм Дойча-Йозсы дает ответ, который всегда верен с одной оценкой f.

Сам алгоритм представляет собой всего лишь некоторые вычисления квантовых состояний без каких-либо итераций /... поэтому сложность равна O (1).