자연계열 3번

[3.1] $\displaystyle N$개의 데이터가 있을 때 $\displaystyle k$번째 검색에서 원하는 자료를 찾으려면, 첫 번째 검색부터 $\displaystyle k-1$번째 검색까지 원하는 자료가 나오지 않아야 한다. 첫 번째에서 검색에 실패할 확률 $\displaystyle q_1=1-\frac1N=\frac{N-1}N$이며 첫 번째에 이어 두 번째 검색에서도 원하는 데이터를 얻지 못할 확률은$\displaystyle q_2=q_1\times\left(1-\frac1{N-1}\right)=\frac{N-1}N\times\frac{N-2}{N-1}=\frac{N-2}N$이다.이와 같이 연속해서 $\displaystyle k-1$번째까지 원하는 데이터를 얻지 못할 확률은 다음과 같다.$\displaystyle q_{k-1}=q_{k-2}\times\left(1-\frac1{N-(k-2)}\right)=\left(\frac{N-1}N\right)\left(\frac{N-2}{N-1}\right)\left(\frac{N-3}{N-2}\right)\cdots\left(\frac{N-(k-1)}{N-(k-2)}\right)=\frac{N-(k-1)}N$이를 이용하여 $\displaystyle k$번째에 데이터를 찾을 확률은 확률의 곱셈정리를 통하여 다음과 같이 구한다.$\displaystyle p_k=q_{k-1}\times\frac1{N-(k-1)}=\left(\frac{N-(k-1)}N\right)\left(\frac1{N-(k-1)}\right)=\frac1N$검색 완료까지의 횟수에 대한 기댓값은 $\displaystyle \sum_{k=1}^Nk\times p_k=\sum_{k=1}^Nk\times\frac1N=\frac{N(N+1)}2\times\frac1N=\frac{N+1}2$이다.

[3.2] 제시문 (다)에서 $\displaystyle N=4$일 때, 선분 OS와 $\displaystyle x$축 사이의 각도 $\displaystyle \theta$는 $\displaystyle \sin\theta=\frac12$을 만족하므로 $\displaystyle \theta=\frac\pi6$이다. 따라서 점 S의 좌표 $\displaystyle (\cos\theta,\sin\theta)=\left(\frac{\sqrt3}2,\frac12\right)$이다. $\displaystyle G_{\mathrm S}$연산을 처음 수행할 때, 점 $\displaystyle \mathrm Q_0$의 위치는 점 S와 같으므로 점 $\displaystyle \mathrm Q_0$를 $\displaystyle x$축 대칭이동 시킨 점 $\displaystyle \mathrm Q_1$의 좌표는 $\displaystyle \left(\frac{\sqrt3}2,-\frac12\right)$이다. 점 $\displaystyle \mathrm Q_2$와 점 $\displaystyle \mathrm Q_1$은 선분 OS에 대하여 대칭이므로 제시문 (가)를 활용하여 $\displaystyle \overrightarrow{\mathrm{OQ}_2}=2(\overrightarrow{\mathrm{OS}}\cdot\overrightarrow{\mathrm{OQ}_1})\overrightarrow{\mathrm{OS}}-\overrightarrow{\mathrm{OQ}_1}$을 얻는다.이를 이용하여 점 $\displaystyle \mathrm Q_2$의 좌표를 구하기 위해 $\displaystyle \overrightarrow{\mathrm{OS}}=\left(\frac{\sqrt3}2,\frac12\right)$ 및 $\displaystyle \overrightarrow{\mathrm{OQ}_1}=\left(\frac{\sqrt3}2,-\frac12\right)$를 넣어주면 $\displaystyle \overrightarrow{\mathrm{OQ}_2}=(0,1)$임을 알 수 있다. 점 $\displaystyle \mathrm A_1$의 좌표는 점 $\displaystyle \mathrm Q_2$의 좌표와 같으므로 $\displaystyle \mathrm A_1$의 좌표는 $\displaystyle (0,1)$이다.따라서 확률 $\displaystyle p_1=(\overrightarrow{\mathrm{OA}_1}\cdot\overrightarrow{e_2})^2=1$이다.

[3.3] 선분 $\displaystyle \mathrm{OQ}_0$과 $\displaystyle x$축 사이의 각도를 $\displaystyle \gamma$라고 하자. 점 $\displaystyle \mathrm Q_1$은 $\displaystyle \mathrm Q_0$을 $\displaystyle x$축에 대칭시킨 점이므로 선분 $\displaystyle \mathrm{OQ}_1$과 $\displaystyle x$축 사이의 각도 역시 $\displaystyle \gamma$이다. 따라서 선분 OS와 선분 $\displaystyle \mathrm{OQ}_1$이 이루는 각도 $\displaystyle \angle\mathrm{SOQ}_1=\theta+\gamma$이다.점 $\displaystyle \mathrm Q_2$와 $\displaystyle \mathrm Q_1$은 선분 OS에 대해 대칭이므로 $\displaystyle \angle\mathrm{SOQ}_2=\angle\mathrm{SOQ}_1=\theta+\gamma$이다. 따라서 선분 $\displaystyle \mathrm{OQ}_2$와 $\displaystyle x$축 사이의 각도는 $\displaystyle \angle\mathrm{SOQ}_2+\theta=2\theta+\gamma$이다. 선분 $\displaystyle \mathrm{OQ}_0$과 $\displaystyle x$축 사이의 각도가 $\displaystyle \gamma$이므로 선분 $\displaystyle \mathrm{OQ}_0$과 선분 $\displaystyle \mathrm{OQ}_2$가 이루는 각도 $\displaystyle \alpha$는 $\displaystyle (2\theta+\gamma)-\gamma=2\theta$이다.처음으로 $\displaystyle G_{\mathrm S}$연산을 하는 경우는 점 $\displaystyle \mathrm Q_0$을 S로 놓기 때문에 선분 $\displaystyle \mathrm{OA}_1$이 선분 OS에 대해 $\displaystyle 2\theta$만큼 시계 반대방향으로 회전하게 된다. 이와 같이 $\displaystyle G_{\mathrm S}$연산을 $\displaystyle n$번 연속적으로 실행한 후에는 선분 $\displaystyle \mathrm{OA}_n$은 선분 OS에 대해 $\displaystyle (2\theta)\times n$만큼 시계 반대방향으로 회전하게 된다. 선분 OS와 $\displaystyle x$축 사이의 각도가 $\displaystyle \theta$이므로 선분 $\displaystyle \mathrm{OA}_n$과 $\displaystyle x$축과의 각도는 $\displaystyle (2\theta)\times n+\theta=(2n+1)\theta$가 된다.

[3.4] 데이터를 찾을 확률이 최대인 지점은 점 $\displaystyle \mathrm A_n$이 $\displaystyle y$축에 가장 가깝게 되는 곳이다. 즉 선분 $\displaystyle \mathrm{OA}_n$과 $\displaystyle x$축과의 각도 $\displaystyle (2n+1)\theta$가 $\displaystyle \frac\pi2$에 최대한 가까워야 된다. $\displaystyle N=2^{13}$일 때 $\displaystyle \sin\theta=\frac1{\sqrt{2^{13}}}$이다. 문제의 조건에서 $\displaystyle \theta=0.01$이므로 $\displaystyle (2n+1)\theta=(2n+1)\times0.01\approx\frac\pi2=\frac{3.14}2$를 만족하는 $\displaystyle n$을 구하면 $\displaystyle n=78$이다. 따라서, 양자컴퓨터가 $\displaystyle G_{\mathrm S}$연산을 $\displaystyle 78$번 반복한 후 탐색이 종료된다.