Algoritmo de Shor

Em geral, o algoritmo de estimativa de fase quântica, para qualquer unitário ${\displaystyle U}$ e autoestado ${\displaystyle |\psi \rangle }$ tal que ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$, envia estados de entrada ${\displaystyle |0\rangle |\psi \rangle }$ para estados de saída próximos de ${\displaystyle |\phi \rangle |\psi \rangle }$, onde ${\displaystyle \phi }$ é uma superposição de inteiros próximos a ${\displaystyle 2^{2n}\theta }$. Em outras palavras, ele envia cada autoestado ${\displaystyle |\psi _{j}\rangle }$ de ${\displaystyle U}$ para um estado contendo informações próximas ao autovalor associado. Para os propósitos da determinação de ordem quântica, empregamos esta estratégia usando o unitário definido pela ação:$${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$A ação de ${\displaystyle U}$ em estados ${\displaystyle |k\rangle }$ com ${\displaystyle N\leq k<2^{n}}$ não é crucial para o funcionamento do algoritmo, mas precisa ser incluída para garantir que a transformação geral seja uma porta quântica bem definida. Implementar o circuito para estimativa de fase quântica com ${\displaystyle U}$ requer ser capaz de implementar de forma eficiente as portas ${\displaystyle U^{2^{j}}}$. Isso pode ser alcançado através da exponenciação modular, que é a parte mais lenta do algoritmo.

A porta assim definida satisfaz ${\displaystyle U^{r}=I}$, o que imediatamente implica que seus autovalores são as ${\displaystyle r}$-ésimas raízes da unidade ${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$. Além disso, cada autovalor ${\displaystyle \omega _{r}^{j}}$ tem um autovetor da forma ${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$, e esses autovetores são tais que:$${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle =|1\rangle ,\end{aligned}}}$$ onde a última identidade segue da fórmula da série geométrica, que implica ${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$.

Usar a estimativa de fase quântica em um estado de entrada ${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$ retornaria, então, o inteiro ${\displaystyle 2^{2n}j/r}$ com alta probabilidade. Mais precisamente, o circuito de estimativa de fase quântica envia ${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$ para ${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$ de modo que a distribuição de probabilidade resultante ${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$ tenha pico em torno de ${\displaystyle k=2^{2n}j/r}$, com ${\displaystyle p_{2^{2n}j/r}\geq 4/\pi ^{2}\approx 0.4053}$. Essa probabilidade pode ser feita tão próxima de 1 quanto se queira, usando qubits extras.

Aplicando o raciocínio acima à entrada ${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle }$, a estimativa de fase quântica, portanto, resulta na evolução: $${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes 2n}|\psi _{j}\rangle \to {\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle .}$$ Ao medir o primeiro registrador, agora temos uma probabilidade balanceada de ${\displaystyle 1/r}$ para encontrar cada ${\displaystyle |\phi _{j}\rangle }$, e cada uma delas fornece uma aproximação inteira de ${\displaystyle 2^{2n}j/r}$, a qual pode ser dividida por ${\displaystyle 2^{2n}}$ para se obter uma aproximação decimal para ${\displaystyle j/r}$.

Em seguida, aplicamos o algoritmo de frações contínuas para encontrar inteiros ${\displaystyle b}$ e ${\displaystyle c}$, onde ${\displaystyle b/c}$ fornece a melhor aproximação fracionária para a aproximação medida no circuito, para ${\displaystyle b,c<N}$ com ${\displaystyle b}$ e ${\displaystyle c}$ sendo coprimos. O número de qubits no primeiro registrador, ${\displaystyle 2n}$, que determina a exatidão da aproximação, garante que $${\displaystyle {\frac {b}{c}}={\frac {j}{r}},}$$ desde que a melhor aproximação da superposição de ${\displaystyle |\phi _{j}\rangle }$ tenha sido medida^[2] (o que pode ser tornado arbitrariamente provável usando bits extras e truncando a saída). Contudo, embora ${\displaystyle b}$ e ${\displaystyle c}$ sejam coprimos, pode ser o caso que ${\displaystyle j}$ e ${\displaystyle r}$ não o sejam. Por causa disso, ${\displaystyle b}$ e ${\displaystyle c}$ podem ter perdido alguns fatores que estavam contidos em ${\displaystyle j}$ e ${\displaystyle r}$. Isso pode ser remediado reexecutando a sub-rotina de ordem quântica um número arbitrário de vezes, para produzir uma lista de aproximações em frações: $${\displaystyle {\frac {b_{1}}{c_{1}}},{\frac {b_{2}}{c_{2}}},\ldots ,{\frac {b_{s}}{c_{s}}},}$$ onde ${\displaystyle s}$ é o número de vezes que a sub-rotina foi executada. De cada ${\displaystyle c_{k}}$ podem ter sido removidos fatores diferentes, porque o circuito (provavelmente) terá medido valores distintos possíveis para ${\displaystyle j}$. Para recuperar o verdadeiro valor de ${\displaystyle r}$, podemos calcular o mínimo múltiplo comum (MMC) de cada ${\displaystyle c_{k}}$: $${\displaystyle \operatorname {mmc} (c_{1},c_{2},\ldots ,c_{s}).}$$ O mínimo múltiplo comum será a ordem ${\displaystyle r}$ do inteiro original ${\displaystyle a}$ com alta probabilidade. Na prática, uma única execução da sub-rotina quântica é em geral suficiente caso se utilize um pós-processamento mais avançado.^[21]

A estimativa de fase requer a escolha do tamanho do primeiro registrador para determinar a exatidão do algoritmo, e para a sub-rotina quântica do algoritmo de Shor, ${\displaystyle 2n}$ qubits são suficientes para garantir que a sequência de bits (bitstring) ideal medida na estimativa de fase (isto é, o ${\displaystyle |k\rangle }$ onde ${\textstyle k/2^{2n}}$ é a aproximação mais exata da fase advinda da estimativa de fase) permitirá que o valor real de ${\displaystyle r}$ seja recuperado.

Cada ${\displaystyle |\phi _{j}\rangle }$ antes da medição no algoritmo de Shor representa uma superposição de inteiros aproximando ${\displaystyle 2^{2n}j/r}$. Deixe ${\displaystyle |k\rangle }$ representar o inteiro ideal em ${\displaystyle |\phi _{j}\rangle }$. O teorema a seguir garante que o algoritmo das frações contínuas irá recuperar ${\displaystyle j/r}$ a partir de ${\displaystyle k/2^{2{n}}}$:

^[3] Como ${\displaystyle k}$ é a bitstring ótima da estimativa de fase, ${\displaystyle k/2^{2{n}}}$ tem uma exatidão de ${\displaystyle 2n}$ bits em relação a ${\displaystyle j/r}$. Logo: $${\displaystyle \left\vert {\frac {j}{r}}-{\frac {k}{2^{2n}}}\right\vert \leq {\frac {1}{2^{2{n}+1}}}\leq {\frac {1}{2N^{2}}}\leq {\frac {1}{2r^{2}}}}$$ o que implica que o algoritmo de frações contínuas irá recuperar ${\displaystyle j}$ e ${\displaystyle r}$ (ou eles com o seu máximo divisor comum já extraído).