Алгоритм BHT
-
Алгоритм Брассара-Хейера-Таппа (BHT)
- Используется в квантовых вычислениях для решения проблемы коллизий.
- Позволяет найти два входных сигнала с одинаковым выходным значением за O(n^(1/3)) запросов.
- Открыт в 1997 году Жилем Брассаром, Питером Хойером и Аленом Таппом.
-
Принцип работы алгоритма BHT
- Сначала случайным образом выбираются n^(1/3) входных данных и запрашиваются у функции f.
- Если возникает коллизия, возвращается пара входных данных.
- В противном случае все выбранные данные преобразуются функцией f и используются для поиска новой коллизии с помощью алгоритма Гровера.
-
Эффективность алгоритма BHT
- Алгоритм Гровера может обнаружить коллизию за O(n^(1/3)) дополнительных запросов к функции f.
-
Связанные алгоритмы
- Упоминается проблема различимости элементов и алгоритм Гровера.
-
Рекомендации
- Статья не содержит конкретных рекомендаций.