Shor의 알고리즘 : QFT의 결과를 두 번 읽은 후 어떻게해야합니까?
나는 푸리에 변환 플롯을보고 기간을 식별하는 방법에 대해 물었다 . 대답은 그래프에 설명 된 높은 확률과 관련된 여러 값을 가져 오는 푸리에 변환을 여러 번 실행하는 것 같습니다. 그래도 같은 그림을 사용하고 있는데 두 번 읽고 | 5>와 | 11> 값을 얻었다 고 가정합니다. 이것은 가장 높은 스파이크입니다 (| 0>에서 처음 가장 높은 값 이후). 5와 11 중 12의 기간을 어떻게 알 수 있습니까? 계산의 예를 보여줄 수 있습니까?
시도 된 솔루션 입니다. Peter Shor의 논문 (320 페이지)을 읽으면서$q$ 이다 $q=64$여기 우리의 예에서. 쇼어는 우리가 분수를 얻을 수 있다고 말한다$d/r$ 가장 낮은 용어 (여기서 $r = 12$ 여기) 반올림하여 $c/q$ 분모가보다 작은 가장 가까운 분수로 $n=35$여기. 우리의 가능$c$ 여기 있습니다 $5$ 과 $11$.
시도해 봅시다. QFT 후 우리는$c = 5$ 그리고 우리는 $q = 64$. 그래서 우리는$5/64 = 0.078125$ 분모가 다음보다 작은 가장 가까운 분수로 반올림하고 싶습니다. $35$. 에 대한$5/64$, 나는 연속 분수를 찾습니다 $[0,12,1,4]$. (나는$5/64 = 1/(12 + 1/(1 + 1/4))$, 맞습니다.) 이제이 연속 분수 (목록 형식)에서 다음과 같은 분수 시퀀스를 얻습니다. $1/4, 5/4, 64/5, 5/64$. (내가 무엇을하는지 잘 모르겠습니다.) 아마도$5$불운입니까? 하지만 아니요,$11$ 또한 생산할 것이다 $11/64$. 따라서 연속 분수 알고리즘을 계산하는 방법을 알고 있지만 어떻게해야할지 모르겠습니다. Hardy와 Wright의 X 장을 봐야 겠어요.
답변
이것은 위키 백과의 5 단계 알고리즘의 연속 부분입니다. 당신이 측정 한 것은$y$ 그런 $\frac{yr}{Q}\approx c$, 어디 $c$ 알 수없는 정수입니다. $r$ 숨겨진 기간 (이 경우 12) $Q=64$QFT의 크기입니다. 이것은$\frac{y}{Q}\approx \frac{c}{r}$. 에 대한$y=5$, 우리는 $\frac{5}{64}\approx \frac{1}{12}$, 그리고 $y=11$, 우리는 $\frac{11}{64}\approx \frac{2}{12}$. 이것이 측정 된 값과 기간 사이의 관계입니다.
하지만 실제로 그 값에서 기간을 어떻게 찾을 수 있습니까? $c$ 또는 $r$)? 연속 분수로. 숫자에 대한 연속 분수$x$ 재귀 적으로 정의됩니다. $a_0=x$, 다음 $b_n=\lfloor a_n\rfloor$, 및 $a_n=\frac{1}{a_{n-1}-b_{n-1}}$. 이 문제에 적용$x=\frac{5}{64}$, 우리는
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
이로부터 근사치를 재구성 할 수 있으며 이러한 근사치의 분모가 기간이 될 것입니다. 연속 분수에 대한 위키피디아 페이지 는 일련의 근사 분수를 얻는다고 설명합니다.$\frac{h_n}{k_n}$, 여기서 우리는 분자를 설정합니다. $h_n=b_nh_{n-1}+h_{n-2}$ 및 분모 $k_n=b_nk_{n-1}+k_{n-2}$, 초기 값 포함 $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, 및 $k_{-2}=1$. 이것은 두 가지 시퀀스를 제공합니다.
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
세 개의 근사 분수를 제공합니다. $\frac{1}{12}$, $\frac{1}{13}$, 및 $\frac{5}{64}$. 마지막 것은 우리가 시작한 것이고 64가 너무 커서 쓸모가 없습니다 (결국 기간은 35보다 작아야합니다). 첫 번째는 실제 기간입니다.
연속 분수에 대해서는 잘 모르지만 이러한 근사값이 원래 분수로 매우 빠르게 수렴한다고 생각합니다. 따라서 실제로는 (a) 근사 분수가 그렇게 많지 않아야하고 (b) Shor의 마지막 단계가 있기 때문에 근사 분수 (이 경우 12와 13 모두)에서 각 분모를 확인하면됩니다. 알고리즘은 너무 저렴합니다.