Алгоритм BHT

В квантовых вычислениях алгоритм Брассара-Хойера-Тапп или алгоритм BHT представляет собой квантовый алгоритм , который решает проблему столкновений . В этой задаче дано n и функция r -к-1. $f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}$ и ему нужно найти два входа, которые f сопоставляются с одним и тем же выходом. Алгоритм BHT делает только $O(n^{1/3})$ запросы к f , что соответствует нижней границе $\Omega (n^{1/3})$ в модели черного ящика . ^[1]^[2]

Алгоритм был открыт Жилем Брассаром , Питером Хойером и Аленом Таппом в 1997 году. ^[3] Он использует алгоритм Гровера , открытый годом ранее.

Алгоритм [ править ]

Интуитивно понятно, что алгоритм сочетает ускорение квадратного корня из парадокса дня рождения с использованием (классической) случайности с ускорением квадратного корня из (квантового) алгоритма Гровера.

Во-первых, н ^1/3 входы для f выбираются случайным образом, и f запрашивается у всех из них. Если между этими входными данными имеется конфликт, мы возвращаем конфликтующую пару входных данных. В противном случае все эти входные данные сопоставляются с различными значениями с помощью f . Затем алгоритм Гровера используется для поиска новых входных данных для f , которые конфликтуют. Поскольку существует n входов для f и n ^1/3 из них могут привести к коллизии с уже запрошенными значениями, алгоритм Гровера может обнаружить коллизию с $O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})$ дополнительные запросы к f . ^[3]

См. также [ править ]

Ссылки [ править ]

^ Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов в малом диапазоне» (PDF) . Теория вычислений . 1 (1): 37–46. дои : 10.4086/toc.2005.v001a003 .
^ Кутин, С. (2005). «Квантовая нижняя граница для задачи столкновения с малым диапазоном» . Теория вычислений . 1 (1): 29–36. дои : 10.4086/toc.2005.v001a002 .
↑ Перейти обратно: Перейти обратно: ^а ^б Брассар, Жиль; Хойер, Питер; Тапп, Ален (1998), «Квантовый алгоритм для проблемы столкновений», в Луккези, Клаудио Л.; Моура, Арнальдо В. (ред.), LATIN '98: Теоретическая информатика, Третий латиноамериканский симпозиум, Кампинас, Бразилия, 20–24 апреля 1998 г., Труды , конспекты лекций по информатике, том. 1380, Springer, стр. 163–169, arXiv : quant-ph/9705002 , doi : 10.1007/BFb0054319 , S2CID 3116149

[1] Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов в малом диапазоне» (PDF) . Теория вычислений . 1 (1): 37–46. дои : 10.4086/toc.2005.v001a003 .

[2] Кутин, С. (2005). «Квантовая нижняя граница для задачи столкновения с малым диапазоном» . Теория вычислений . 1 (1): 29–36. дои : 10.4086/toc.2005.v001a002 .

[:0-3] Перейти обратно: Перейти обратно: ^а ^б Брассар, Жиль; Хойер, Питер; Тапп, Ален (1998), «Квантовый алгоритм для проблемы столкновений», в Луккези, Клаудио Л.; Моура, Арнальдо В. (ред.), LATIN '98: Теоретическая информатика, Третий латиноамериканский симпозиум, Кампинас, Бразилия, 20–24 апреля 1998 г., Труды , конспекты лекций по информатике, том. 1380, Springer, стр. 163–169, arXiv : quant-ph/9705002 , doi : 10.1007/BFb0054319 , S2CID 3116149

[1]

[2]

[3]