4501
правка
Квантовый алгоритм для решения задачи поиска коллизий: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм для решения задачи поиска коллизий (посмотреть исходный код)
Версия от 20:35, 13 января 2023
, 13 января 2023→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
== Основные результаты == | == Основные результаты == | ||
Представленный здесь алгоритм находит коллизии в произвольной функции F типа «r к 1», выполнив всего O( | Представленный здесь алгоритм находит коллизии в произвольной функции F типа «r к 1», выполнив всего <math>O(\sqrt[3]{N/r})</math> ожидаемых оценок F. Алгоритм использует функцию как «черный ящик», то есть единственное, что требуется алгоритму – это способность оценить функцию. В предположении, что функция задается черным ящиком, алгоритм является оптимальным [1] и более эффективным, чем наилучший ''возможный'' классический алгоритм, имеющий сложность в запросах <math>\Omega(\sqrt{N/r})</math>. Этот результат точно сформулирован в следующей теореме и следствии. | ||
Теорема 1. Пусть дана функция типа «r к 1» F: X | '''Теорема 1. Пусть дана функция типа «r к 1» <math>F: X \to Y, r \ge 2</math>, и целое число <math>1 \le k \le N = |X|</math>. Алгоритм Collision(F, k) возвращает коллизию после ожидаемого числа <math>O(k + \sqrt{N/(rk)})</math> оценок F с использованием <math>\Theta(k)</math> ячеек памяти. В частности, при <math>k = \sqrt[3]{N/r}</math> алгоритм Collision(F, k) использует <math>O(\sqrt[3]{N/r})</math> ожидаемых оценок и <math>\Theta(\sqrt[3]{N/r})</math> ячеек памяти.''' | ||