Velocidade do algoritmo de Shor

8

Sou um estudioso de ciência da computação e estou sendo solicitado a escrever um artigo que envolva fatoração de número inteiro. Como resultado, estou tendo que analisar o algoritmo de Shor em computadores quânticos.

Para os outros algoritmos, consegui encontrar equações específicas para calcular o número de instruções do algoritmo para um determinado tamanho de entrada (a partir do qual pude calcular o tempo necessário para calcular em uma máquina com uma velocidade especificada). No entanto, para o algoritmo de Shor, o máximo que posso encontrar é a sua complexidade: O( (log N)^3 ).

Existe alguma maneira de encontrar sua velocidade / complexidade real na Notação Big-O? Caso contrário, há alguém que possa me dizer o que eu quero ou como encontrá-lo?

Morgan Patch
fonte

Respostas:

23

A melhor estimativa que conheço pode ser encontrada em Redes eficientes para fatoração quântica , por David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni e John Preskill, que fornece72(registroN)3.

Dito isto, uma comparação direta do número de etapas em um computador quântico versus número de etapas em um computador clássico é problemática por várias razões. Primeiro, como diz a resposta da DW, o número de etapas depende da arquitetura exata do computador quântico, que não teremos até que um seja construído. Segundo, o tempo necessário para uma única etapa em um computador quântico provavelmente será um pouco mais lento que um único passo em um computador clássico. 1 Novamente, não saberemos quanto mais lento até que existam computadores quânticos.

1 Se fosse mais rápido, você poderia usar a mesma arquitetura para construir um computador clássico que fosse pelo menos tão rápido e provavelmente mais rápido porque, para um computador clássico, você não precisa se preocupar em manter a coerência quântica.

Peter Shor
fonte
20
Uma pergunta sobre o algoritmo de Shor, respondida pelo próprio Peter Shor. Arrumado.
precisa saber é o seguinte
2
Provavelmente, existem estimativas melhores até agora, na verdade.
Peter Shor
4

O que você está pedindo não existe, por boas razões.

Hoje não existe computador que possa executar o algoritmo de Shor. Para executar o algoritmo de Shor, você precisa de um computador quântico, que ainda não existe. Portanto, você não deve esperar estimativas precisas de sua velocidade ou tempo de execução, pois isso dependerá dos detalhes do computador em que o algoritmo está sendo executado - e não podemos conhecê-los até que construamos com êxito um .

DW
fonte