BHT 알고리즘

양자 컴퓨팅에서 브라자드-호이어-타파 알고리즘 또는 BHT 알고리즘은 충돌 문제를 해결하는 양자 알고리즘이다.이 문제에서는 n과 r-to-1 $함수{\displaystyle }$ f${\displaystyle }$:${\displaystyle }${ ${\displaystyle 1}$,${\displaystyle }$… , ${\displaystyle n}$ ${\displaystyle \}}$→${\displaystyle }${ 1${\displaystyle }$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle n}$ ${\displaystyle \}}$ ${\displaystyle f:\,\1,\ldots,n\}\rightarrow \{1,\ldots,n\}}}}}$이(가) 주어지며$$, f가 동일한 출력에 매핑되는 두 개의 입력을 찾아야 한다.BHT 알고리즘은 블랙박스 모델에서$$ $\Omega {\displaystyle \mathrm{}({}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$/ 3${\displaystyle {}^{}}$)의 하한$($n ${\displaystyle {1\mathrm{}}^{}}$/ 3${\displaystyle {}^{}}$)과 일치하는 $(n$ / ${\displaystyle {3\mathrm{}}^{}}$$)${\$displaystyle \Oomega(n^{1/3})$ 쿼리만$$ f로 만든다.^[1][2]null

이 알고리즘은 1997년 길레스 브래서드, 피터 호이어, 알랭 태프에 의해 발견되었다.^[3]전년도에 발견된 그로버 알고리즘을 사용한다.null

알고리즘.

직관적으로 이 알고리즘은 생일 역설(클래식)의 무작위성을 이용한 제곱근 속도 상승과 그로버(퀀텀) 알고리즘의 제곱근 속도 상승을 결합한다.null

첫째, f에 대한 n개의^1/3 입력을 임의로 선택하고 그 모든 입력에서 f를 쿼리한다.만약 이러한 입력들 사이에 충돌이 있다면, 우리는 충돌 쌍의 입력들을 반환한다.그렇지 않으면 이 모든 입력은 f로 구별되는 값에 매핑된다.그리고 그로버의 알고리즘은 충돌하는 f에 대한 새로운 입력을 찾는데 사용된다.f에 대한 입력과 n에^1/3 대한 입력은 이미 조회된 값과 충돌을 일으키므로 그로버 알고리즘은 $O{\displaystyle (\sqrt{\frac{{n\mathrm{}}^{}}{}}}$ 1${\displaystyle \sqrt{\frac{{}^{}}{}}}$/ 3${\displaystyle \sqrt{\frac{{}^{}}{}}}$)${\displaystyle }$= ${\displaystyle O({}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$/ $){\displaystyle O\좌({\sqrt {\n}{n^{n/3}}}}\right)$와의 충돌을 찾을 수 있다.$O(n^{1/3})$ 추가$$ 쿼리를 f에 추가하십시오.null

참고 항목

• 요소 고유성 문제

참조