RealFeedApp Для нечетного k≥5 получен нижний предел Ω_k(N^{1-2/(k-1)})
Исследователи установили точную оценку классической сложности задачи для четного k и нижнюю границу для нечетного k. Для четного k доказана сложность Θ(N^(1-2/k)), а для нечетного k — Ω(N^(1-2/(k-1))).
#quantum computing#complexity theory#cyclic forrelation#query complexity
