Алгоритм BHT

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

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

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

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

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

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

Проблема отличимости элементов

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

^ Ambainis, A. (2005). "Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым диапазоном" (PDF) . Теория вычислений . 1 (1): 37–46. DOI : 10.4086 / toc.2005.v001a003 .
^ Кутин, С. (2005). «Квантовая нижняя граница для проблемы столкновений с малым радиусом действия» . Теория вычислений . 1 (1): 29–36. DOI : 10.4086 / toc.2005.v001a002 .
^ Брассар, Жиль; Хойер, Питер; Тэпп, Ален (1997). «Квантовый алгоритм для проблемы столкновения» . Конспект лекций по информатике : 163–169. arXiv : квант-ph / 9705002 . DOI : 10.1007 / BFb0054319 .

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

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

[3] Брассар, Жиль; Хойер, Питер; Тэпп, Ален (1997). «Квантовый алгоритм для проблемы столкновения» . Конспект лекций по информатике : 163–169. arXiv : квант-ph / 9705002 . DOI : 10.1007 / BFb0054319 .

[1]