Какие интересные всплески на этом графике после QFT (стр. 241) программирования квантовых компьютеров?
Я читаю " Программирование квантовых компьютеров", пытаясь понять алгоритм Шора. Я узнал там, что мы готовим состояние$|x^i \bmod N\rangle$, затем примените QFT к этому состоянию. QFT изменяет амплитуды от однородной суперпозиции до больших амплитуд, равномерно разделенных периодом$x^i \bmod N$. Например, вот график амплитуд после применения QFT с$N = 35$. Это на странице 241.
В книге написано 12 шипов, расположенных на равном расстоянии друг от друга. Я вижу гораздо больше, чем 12 шипов, равномерно расположенных. Должен ли я считать только самые высокие и останавливаться, когда я насчитал 12? Но разве это не субъективно? Как мне понять, что это действительно 12, просто взглянув на этот график, не зная правильного ответа? (Другими словами, как мне получить из этого 12?)
Ответы
Глядя на графики, которые вы воспроизвели, левый график показывает оценку $2^x\bmod 35$ для $x\in\{0,\dots 63\}$ а правый график иллюстрирует амплитуду дискретного преобразования Фурье для $\hat{x}\in\{0,\dots 63\}$. Комментарий о «12 равномерно расположенных пиках» указывает на то, что локальные максимумы правого графа повторяются каждые$64/12=5.33$ значения.
Вы правы, у вас нет доступа к $\hat{x}$ таким образом, чтобы вы могли наблюдать эту периодичность в $\hat{x}$немедленно; однако, что вы делаете имеете доступ к способу выборки$\hat{x}_i$ для нескольких $i$ способом, который возвращается $\hat{x}_i$ с вероятностью, равной (квадрату) высоты соответствующего $\hat{x}_i$.
Например, если вы запустите модульное возведение в степень (левый график), а затем QFT (правый график) и выберите первый регистр, вы, вероятно, получите такое значение, как $0$ с большей вероятностью, чем $5$, с большей вероятностью, чем $32$, с большей вероятностью, чем $11$, с большей вероятностью, чем $6$, так далее.
Из этих соответствующих выборок $\hat{x}_i$, вы можете запустить классические части (часть непрерывной дроби) алгоритма Шора, чтобы сделать вывод, что действительно было 12 равномерно распределенных пиков в $\hat{x}$, давая вам период $12$ в $2^x\bmod 35$. Я забываю о многих деталях, но дело в том, что вы используете образцы из своего QFT в качестве входных данных для этой классической части.