Алгоритм Шора: что делать после двукратного прочтения результата QFT?
Я спросил, как определить период, глядя на график преобразования Фурье . Кажется, ответ состоит в том, чтобы выполнить преобразование Фурье несколько раз, получив несколько значений, связанных с высокими вероятностями, описанными графиком. Итак, все еще использую ту же картинку, предположим, я прочитал ее дважды и получил значения | 5> и | 11>. Это самые высокие всплески (после первого самого высокого в | 0>). Как мне определить период 12 из 5 и 11? Можете показать пример расчета?
Попытка решения . Читая статью Питера Шора (стр. 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$. Поэтому, хотя я знаю, как вычислить алгоритм непрерывной дроби, я не знаю, что с ним делать. Мне нужно взглянуть на Харди и Райта, главу 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). Первый - это фактический период.
Я мало что знаю о непрерывных дробях, но думаю, что эти приближения очень быстро сходятся к исходной дроби. Поэтому на практике, я думаю, вы бы просто проверили каждый знаменатель в последовательности приблизительных дробей (в данном случае и 12, и 13), поскольку (а) приближенных дробей не должно быть так много и (б) последние шаги Шора алгоритм настолько недорогой.