A redução no algoritmo de Shor foi descoberta originalmente por Shor?

79

Essa é uma "questão histórica" ​​mais do que uma questão de pesquisa, mas a redução clássica à busca de ordens no algoritmo de Shor para fatoração foi descoberta inicialmente por Peter Shor, ou era conhecida anteriormente? Existe um artigo que descreva a redução que antecede Shor, ou é simplesmente o chamado "resultado folclórico?" Ou foi simplesmente outra inovação no mesmo artigo?

Philip White
fonte

Respostas:

139

Eu tenho que admitir (por mais surpreendente que pareça) que eu não saiba realmente a resposta. Eu mesmo descobri ou redescobri essa redução.

ϕ

Embora eu tenha sugerido a redução dessa pergunta à busca de pedidos, não é difícil, então não ficaria surpreso se houvesse outro artigo descrevendo essa redução que antecede a minha. No entanto, não acho que esse possa ser um "resultado popular" amplamente conhecido. Mesmo se alguém o tivesse descoberto, antes da computação quântica, por que alguém se importaria em reduzir o fatorial à questão da busca de pedidos (comprovadamente exponencial em um computador clássico)?

NN

Peter Shor
fonte
92
Hmm, eu não tenho certeza se isso é autoritário suficiente
chbaker0
5
@mebob: Cria um bom ceticismo post SE = P
Mehrdad
26
Então ... Shor não tem certeza?
precisa saber é o seguinte
1
Na verdade, seu pdf original em papel de 1994 contém a frase “Há uma redução aleatória de fatoração para a ordem de um elemento [23]”, onde [23] é novamente uma referência ao pdf de Miller 1976 . No entanto, uma rápida olhada neste artigo não me permitiu encontrar a redução correspondente, mas a redução para φ.
Frédéric Grosshans
2
@ Frédéric Grosshans: Na verdade, acho bastante provável que Andrew Odlyzko tenha apontado essa referência para mim.
Peter Shor
55

A redução aleatória da fatoração para a busca de ordens (mod N) era muito conhecida pelas pessoas que trabalhavam em algoritmos de teoria dos números no final dos anos 70 e início dos anos 80. De fato, aparece em um artigo de Heather Woll, Reduções entre problemas teóricos dos números, Information and Computation 72 (1987) 167-179 , e Eric Bach e eu sabíamos disso antes disso.

φ(N)

Jeffrey Shallit
fonte
14
k,nfk(n)
14
Eu suspeitava que você tivesse um modelo de computação muito mais restrito em mente. Mas - como tenho certeza de que você sabe - o problema específico do mod N de busca de pedidos é bem diferente. Então, de fato, é bastante plausível que as pessoas pensassem na redução desse problema específico de e para o fatorial.
Jeffrey Shallit
Heather Woll cita [1] como fonte para a redução da fatoração para a busca de pedidos, mas nem a biblioteca de engenharia de Princeton nem o departamento de Ciência da Computação de Princeton têm uma cópia. (Eu estaria interessado em encontrar um, aliás) [1] LONGO. D. (1981) "Equivalência aleatória de fatoração e computação de ordens", Relatório Técnico 284, Universidade de Princeton, Departamento de Engenharia Elétrica e Ciência da Computação, abril.
Frédéric Grosshans
2
Eu tenho uma cópia e posso enviar para você se você me enviar seu endereço de e-mail.
precisa saber é o seguinte