충돌 문제

r-to-1 충돌 문제는 복잡성 이론, 양자 컴퓨팅, 계산 수학에서 중요한 이론적 문제다.The collision problem most often refers to the 2-to-1 version:^[1] given ${\displaystyle n}$ even and a function ${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}$, we are promised that f is either 1-to-1 or 2-to-1.모든 $i{\displaystyle \in \{}$ ${\displaystyle 1}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle n}$ ${\displaystyle \}}$ ${\displaystyle i\in \{1,\ldots,n\}$에 $대해$ f${\displaystyle }$($){\displaystyle f(i)}$의 값에 대해서만 쿼리를 할 수 있다$.$그러면 문제는 f가 1 대 1인지 2 대 1인지 확실하게 판단하기 위해 얼마나 많은 그런 질의를 해야 하는지 묻는다.

고전적 해법

결정론적

2대1 버전을 결정적으로 해결하려면 $\frac{\mathrm{n}}{}$ $2$+ 1 ${\textstyle${\$frac{n}{2}}+1}$쿼리가$$ 필요하며, 일반적으로 r-to-1 함수와 1대1 함수를 구분하려면 $\frac{n}{}$ r$$+ $1$ ${\textstyle {\frac{n}{r}}}}+1}$쿼리가$$ 필요하다.

이것은 비둘기 구멍 원리의 간단한 적용이다: 만약 함수가 r-to-1이라면, $\frac{n}{}$ r$$+ $1$ ${\textstyle${\$frac{n}{r$}{r$}+1}$쿼리$$ 후에 우리는 충돌을 발견했을 것이다.기능이 1 대 1이면 충돌은 존재하지 않는다.따라서 $n\frac{}{}$ $\frac{r}{}$+ $1$ ${\textstyle {\frac{n}{r}+1}$쿼리로$$ 충분하다.운이 없는 경우 첫 ${\displaystyle 번째}$ $n{\displaystyle }$/ r ${\displaystyle n/r}$ 쿼리는$$ 고유한 답변을 반환할 수 있으므로 $\frac{n}{}$ r$$+ $1$ ${\textstyle {\frac{n}{r}}+1}$쿼리도$$ 필요하다.

무작위화

무작위성을 허용하면 문제가 더 쉬워진다.생일 역설로 우리가 임의로 (간결한) 쿼리를 선택하면 높은 확률로 $\theta {\displaystyle \mathrm{}}$($){\displaystyle \Theta ({\sqrt{n}})$ 쿼리$$ 후 고정된 2대 1 함수에서 충돌을 발견할 수 있다.

양자 해법

Grover의 알고리즘을 사용하는 BHT $알고리즘$은${\displaystyle {}^{}}$(${\displaystyle {n\mathrm{}}^{}}$1${\displaystyle {}^{}}$/ ${\displaystyle {3\mathrm{}}^{}}$ $){\displaystyle O(n^{1/$3$$}) 쿼리를 f(으)로 만들어 이 문제를 최적으로 해결한다.

참조