Algoritmo de Shor: o que fazer depois de ler o resultado do QFT duas vezes?
Eu perguntei sobre como identificar o período olhando para um gráfico de transformação de Fourier . A resposta parece ser executar a transformada de Fourier várias vezes, obtendo vários valores associados às altas probabilidades descritas pelo gráfico. Portanto, ainda usando a mesma imagem, suponha que eu a leia duas vezes e obtenha os valores | 5> e | 11>. Esses são os picos mais altos (após o primeiro mais alto em | 0>.) Como eu descobriria o período 12 de 5 e 11? Você pode mostrar um exemplo do cálculo?
Uma tentativa de solução . Lendo o artigo de Peter Shor (na página 320), descobrimos que seu$q$ é $q=64$aqui em nosso exemplo. Shor está dizendo que podemos obter uma fração$d/r$ em termos mais baixos (onde $r = 12$ aqui) por arredondamento $c/q$ para a fração mais próxima com um denominador menor que $n=35$aqui. Nosso possivel$c$ aqui está $5$ e $11$.
Vamos tentar isso. Após o QFT, temos$c = 5$ e nós temos $q = 64$. Então nós temos$5/64 = 0.078125$ e queremos arredondar para a fração mais próxima com um denominador menor que $35$. Para$5/64$, Eu acho a fração contínua $[0,12,1,4]$. (Eu verifiquei isso$5/64 = 1/(12 + 1/(1 + 1/4))$, então está correto.) Agora, dessa fração contínua (em forma de lista), obtenho a seguinte sequência de frações: $1/4, 5/4, 64/5, 5/64$. (Não tenho certeza do que estou fazendo.) Talvez$5$dá azar? Mas, não, tentando a mesma coisa com$11$ também irá produzir $11/64$. Portanto, embora eu saiba como calcular o algoritmo de fração contínua, não sei o que fazer com ele. Vou ter que olhar para Hardy e Wright, Capítulo X.
Respostas
Esta é a parte contínua da fração do algoritmo, etapa 5 na Wikipedia. O que você mediu é$y$ de tal modo que $\frac{yr}{Q}\approx c$, Onde $c$ é algum inteiro desconhecido, $r$ é o período oculto (neste caso 12), e $Q=64$é o tamanho do QFT. Isso significa que$\frac{y}{Q}\approx \frac{c}{r}$. Para$y=5$, temos $\frac{5}{64}\approx \frac{1}{12}$, e para $y=11$, temos $\frac{11}{64}\approx \frac{2}{12}$. Então essa é a relação entre os valores medidos e o período.
Como podemos realmente encontrar o período a partir desses valores, embora (uma vez que não sabemos $c$ ou $r$)? Com frações contínuas. Uma fração contínua para um número$x$ é definido recursivamente, com $a_0=x$, então com $b_n=\lfloor a_n\rfloor$, e $a_n=\frac{1}{a_{n-1}-b_{n-1}}$. Aplicado a este problema com$x=\frac{5}{64}$, temos
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
A partir disso, podemos reconstruir as aproximações, e o denominador dessas aproximações provavelmente será o período. A página da Wikipedia sobre frações contínuas explica que temos uma série de frações aproximadas$\frac{h_n}{k_n}$, onde definimos um numerador $h_n=b_nh_{n-1}+h_{n-2}$ e denominador $k_n=b_nk_{n-1}+k_{n-2}$, com valores iniciais $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, e $k_{-2}=1$. Isso dá duas sequências:
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
que dá três frações aproximadas: $\frac{1}{12}$, $\frac{1}{13}$, e $\frac{5}{64}$. O último é o que começamos e é inútil porque 64 é muito grande (afinal, o período deve ser menor que 35). O primeiro é o período real.
Não sei muito sobre frações contínuas, mas acho que essas aproximações convergem muito rapidamente para a fração original. Então, na prática, eu acho que você apenas verificaria cada denominador na sequência de frações aproximadas (neste caso, 12 e 13) já que (a) não deve haver tantas frações aproximadas, e (b) as etapas finais de Shor's algoritmo são tão baratos.