Jakie są interesujące skoki na tym wykresie QFT po QFT (strona 241) programowania komputerów kwantowych?
Czytam Programming Quantum Computers, próbując zrozumieć algorytm Shora. Dowiedziałem się tam, że przygotowujemy stan$|x^i \bmod N\rangle$, a następnie zastosuj QFT do tego stanu. QFT zmienia amplitudy z jednorodnej superpozycji na duże amplitudy równomiernie rozmieszczone w okresie$x^i \bmod N$. Na przykład, oto wykres amplitud po zastosowaniu QFT z$N = 35$. To jest na stronie 241.

Książka mówi, że istnieje 12 kolców równomiernie rozmieszczonych. Widzę dużo więcej niż 12 kolców rozmieszczonych równomiernie. Czy mam policzyć tylko te najwyższe i przestać, gdy policzę 12? Ale czy nie jest to subiektywne? Jak mógłbym dowiedzieć się, że liczba to naprawdę 12, patrząc tylko na ten wykres, nie znając prawidłowej odpowiedzi? (Innymi słowy, jak mam z tego uzyskać 12?)
Odpowiedzi
Patrząc na odtworzone wykresy, lewy wykres przedstawia ocenę $2^x\bmod 35$ dla $x\in\{0,\dots 63\}$ podczas gdy prawy wykres ilustruje amplitudę dyskretnej transformaty Fouriera dla $\hat{x}\in\{0,\dots 63\}$. Komentarz, że istnieje „12 równomiernie rozmieszczonych wartości szczytowych” wskazuje, że lokalne maksima prawego wykresu powtarzają się co$64/12=5.33$ wartości.
Masz rację, nie masz dostępu do $\hat{x}$ w sposób, który pozwala obserwować tę okresowość w $\hat{x}$natychmiast; Jednak to, co zrobić mają dostęp do jest sposobem na próbce$\hat{x}_i$ dla wielu $i$ w sposób, który powraca $\hat{x}_i$ z prawdopodobieństwem określonym przez (kwadrat) wysokości odpowiedniego $\hat{x}_i$.
Na przykład, jeśli miałbyś uruchomić modułowe potęgowanie (lewy wykres), a następnie QFT (prawy wykres) i próbkować pierwszy rejestr, prawdopodobnie otrzymasz wartość taką jak $0$ z większym prawdopodobieństwem niż $5$, z większym prawdopodobieństwem niż $32$, z większym prawdopodobieństwem niż $11$, z większym prawdopodobieństwem niż $6$itp.
Z tych odpowiednich pobrań próbek $\hat{x}_i$, możesz uruchomić klasyczne części (część ciągłego ułamka) algorytmu Shora, aby wywnioskować, że rzeczywiście było 12 równomiernie rozmieszczonych skoków w $\hat{x}$, dając ci okres $12$ w $2^x\bmod 35$. Jest wiele szczegółów, o których zapominam, ale chodzi o to, że używasz próbek z QFT jako danych wejściowych do tej klasycznej części.