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?
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
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=pqN=pqp,qp,qppqq
Se eu olhar para um número , então x compartilha um fator comum com N ou não.xmodNxmodNxxNN
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).xxNNxxNN
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ênciaxxNNmodNmod⁡N
é periódico, quando não compartilham fatores comuns (tente x = 2 , N = 5 ) para vê-lo em primeira mão como:x,Nx,Nx=2x=2N=5N=5
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 )xxNNNN(p−1)(q−1)(p−1)(q−1) .
Por fim, tocando no assunto da teoria de grupos, o comprimento das cadeias repetidas
divide esse número . Então, se você conhece o período de sequências de potências de x(p−1)(q−1)(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 .xNmod5xNmod5(p−1)(q−1)(p−1)(q−1)(p−1)(q−1)(p−1)(q−1)pqpqp,qp,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 .gga1e1+a2e2...a1e1+a2e2...aiaieieipipif^f^f^(pi)=aif^(pi)=ai
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)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).nn2n2n
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.nn2n2n
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.nn
Se conseguirmos encontrar o período muito rapidamente, podemos montar rapidamente uma estimativa para (p−1)(q−1)(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=pqN=pqp,qp,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".