Квантовый алгоритм для решения задачи поиска коллизий: различия между версиями

'''Следствие 2'''. Существует квантовый алгоритм, способный найти коллизию в произвольной функции <math>F: X \to Y</math> для любого <math>r \ge 2</math>, используя объем памяти S и ожидаемое число O(T) оценок F для каждого <math>1 \le S \le T</math> при условии <math>S T^2 \ge |F(X)|</math>, где F(X) обозначает образ F.

Алгоритм использует в качестве процедуры версию алгоритма поиска Гровера. Если дана функция H с размером области n и цель y, алгоритм Grover(H, y) возвращает x, такой, что H(x) = y, за ожидаемое число <math>O(\sqrt{n})</math> оценок H.

'''Collision (F, k)'''