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

Question

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

Answer 1

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

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

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