O que torna os computadores quânticos tão bons em calcular os principais fatores?

Uma das reivindicações comuns sobre computadores quânticos é sua capacidade de "quebrar" a criptografia convencional. Isso ocorre porque a criptografia convencional é baseada em fatores primos, algo que é computacionalmente caro para os computadores convencionais calcularem, mas que é um problema supostamente trivial para um computador quântico.

Que propriedade dos computadores quânticos os torna tão capazes dessa tarefa em que os computadores convencionais falham e como os qubits são aplicados ao problema de cálculo dos fatores primos?

A resposta curta

$\newcommand{\modN}[1]{#1\,\operatorname{mod}\,N}\newcommand{\on}[1]{\operatorname{#1}}$Os computadores quânticos são capazes de executar sub-rotinas de um algoritmo para fatoração, exponencialmente mais rápido que qualquer equivalente clássico conhecido. Isso não significa que os computadores clássicos NÃO PODEM fazê-lo rápido também, mas atualmente não sabemos como os algoritmos clássicos funcionam tão eficientemente quanto os algoritmos quânticos

A resposta longa

Os computadores quânticos são bons em transformações discretas de Fourier. Há muita coisa em jogo aqui que não é capturada apenas por " é paralelo " ou " é rápido ", então vamos entrar no sangue da besta.

O problema de fatoração é o seguinte: Dado um número onde p , q são primos, como você recupera p e q ? Uma abordagem é observar o seguinte:$N = pq$$p,q$$p$$q$

Se eu olhar para um número , então x compartilha um fator comum com N ou não.$\modN{x}$$x$$N$

Se compartilha um fator comum e não é um múltiplo de N , então podemos facilmente perguntar quais são os fatores comuns de x e N (através do algoritmo euclidiano para obter os maiores fatores comuns).$x$$N$$x$$N$

Agora, um fato não tão óbvio: o conjunto de todos os que não compartilham um fator comum com N forma um grupo multiplicativo N mod . O que isso significa? Você pode olhar para a definição de um grupo na Wikipedia aqui . Seja a operação do grupo multiplicação para preencher os detalhes, mas tudo o que realmente importa aqui é a seguinte consequência dessa teoria que é: a sequência$x$$N$$\on{mod} N$

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

é periódico, quando não compartilham fatores comuns (tente x = 2 , N = 5 ) para vê-lo em primeira mão como:$x,N$$x = 2$$N = 5$

$$\newcommand{\mod}[1]{#1\,\operatorname{mod}\,5} \mod1 = 1,\quad \mod4 = 4,\quad \mod8 = 3,\quad \mod{16} = 1.$$

Agora, quantos números naturais menos que N não compartilham nenhum fator comum com N ? Isso é respondido pela função totiente de Euler , é ( p - 1 ) ( q - 1 $x$$N$$N$$(p-1)(q-1)$ .

Por fim, tocando no assunto da teoria de grupos, o comprimento das cadeias repetidas

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

divide esse número . Então, se você conhece o período de sequências de potências de $(p-1)(q-1)$ então você pode começar a adivinhar o que é ( p - 1 ) ( q - 1 ) . Além disso, se você sabe o que ( p - 1 ) ( q - 1 ) é e o que p q é (isso é N, não esqueça!), Então você tem 2 equações com 2 incógnitas, que podem ser resolvidas através da álgebra elementar para: separado p , q .$x \mod N$$(p-1)(q-1)$$(p-1)(q-1)$$pq$$p,q$

Onde os computadores quânticos entram? A descoberta do período. Existe uma operação chamada transformação de Fourier, que assume uma função escrita como uma soma das funções periódicas a 1 e 1 + a 2 e 2 . . . onde um i são números, um e i são funções periódicas período p i e mapeia para uma nova função f tal que f ( P i ) = um i .$g$$a_1 e_1 + a_2 e_2 ...$$a_i$$e_i$$p_i$$\hat{f}$$\hat{f}(p_i) = a_i$

A computação da transformação de Fourier é geralmente introduzida como uma integral, mas quando você deseja aplicá-la a uma matriz de dados (o i- ^ésimo elemento da matriz é ), você pode usar esta ferramenta chamada Transformação Discreta de Fourier, que equivale a multiplicar sua "matriz" como se fosse um vetor, por uma matriz unitária muito grande.$f(I)$

Ênfase na palavra unitário: é uma propriedade realmente arbitrária descrita aqui . Mas o principal argumento é o seguinte:

No mundo da física, todos os operadores obedecem ao mesmo princípio matemático geral: unitariedade .

Então isso significa que não é razoável replicar essa operação da matriz DFT como um operador quântico.

Agora, aqui é onde fica mais profundo um Qubit Array pode representar 2 n possíveis elementos do array (consulte qualquer lugar on-line para obter uma explicação sobre isso ou solte um comentário).$n$$2^n$

Da mesma forma, um operador quântico Qubit pode atuar em todo esse espaço quântico de 2 n e produzir uma resposta que possamos interpretar.$n$$2^n$

Veja este artigo da Wikipedia para mais detalhes.

Se pudermos fazer essa transformação de Fourier em um conjunto de dados exponencialmente grande, usando apenas Qubits, poderemos encontrar o período muito rapidamente.$n$

Se conseguirmos encontrar o período muito rapidamente, podemos montar rapidamente uma estimativa para $(p-1)(q-1)$

Se pudermos fazer isso rápido, dado o nosso conhecimento de , podemos dar uma facada na verificação de p , q .$N=pq$$p,q$

É o que está acontecendo aqui, em um nível muito alto.

O que torna os computadores quânticos bons em fatorar grandes números é sua capacidade de resolver o problema da descoberta de períodos (e um fato matemático que relaciona a descoberta de fatores primários à descoberta de períodos). Isso é basicamente o algoritmo de Shor em poucas palavras. No entanto, ele apenas levanta a questão do que torna os computadores quânticos bons na descoberta de períodos.

No centro da descoberta de períodos está a capacidade de calcular o valor de uma função em todo o seu domínio (ou seja, para cada entrada concebível). Isso é chamado de paralelismo quântico. Isso por si só não é bom o suficiente, mas junto com a interferência (a capacidade de combinar resultados do paralelismo quântico de uma certa maneira), é.

Suponho que essa resposta possa ser um pouco como um cabide de um penhasco: como alguém usa essas habilidades para realmente fatorar? Encontre a resposta na wikipedia no algoritmo de Shor .

Primeiro, o fatoramento pode ser feito em um computador quântico (com uso de portas quânticas 'unitárias') por meio do algoritmo de Shor .

Uma explicação que não requer matemática avançada nem conhecimento avançado de física é esta postagem de blog de Scott Aaronson , intitulada "Shor, eu farei isso".

Um breve resumo de suas idéias é o seguinte:

$\mathbb{R}^2$

$\rho$

Portanto, nossos estranhos relógios quânticos podem nos ajudar a fatorar com eficiência!