Existe um algoritmo NC quântico para calcular o GCD?

14

A partir dos comentários de uma das minhas perguntas no MathOverflow, sinto que a pergunta sobre o GCD estar em vs. é semelhante à pergunta sobre a Fatoração Inteira em vs. .NCPPNP

Existe algo como um algoritmo "quantum " para GCD, pois existe um algoritmo de tempo polinomial quântico ( ) para fatoração inteira?NCBQP

Pergunta relacionada: complexidade do maior divisor comum (MDC)

cc.complexity-theory quantum-computing dc.parallel-comp nt.number-theory comp-number-theory T ....
fonte
5
quando você faz uma postagem cruzada, é melhor escrever a pergunta novamente.
Alessandro Cosentino 31/03

Respostas:

14

Primeiro de tudo, existe uma definição formal de "NC quântico", veja QNC no zoológico.

O GCD é de fato um bom candidato para um problema que pode ser mostrado no QNC, mas não se sabe que ele esteja no NC. No entanto, encontrar um algoritmo QNC para o GCD ainda é um problema em aberto.

A sensação de que isso é verdade vem do fato de que a Transformada quântica de Fourier pode ser realizada no QNC.

Referência: seção de conclusão de "R. Cleve e J. Watrous, circuitos paralelos rápidos para a transformada quântica de Fourier", arXiv: quant-ph / 0006004

Alessandro Cosentino
fonte
6
Seria bom se você pudesse explicar a relação entre a transformada quântica de Fourier e a GCD.
Kaveh
Eu concordo com Kaveh. Seria bom fornecer a relação.
T ....
2
Eu não acho que exista uma relação direta. O que eu quis dizer é que suspeitamos que o QNC seja mais poderoso que o NC, porque podemos fazer QFT no QNC. Por isso, perguntamos se também existe algum problema mais natural no QNC, e um dos problemas naturais mais simples que não sabemos como fazer no NC é o GCD. Em algum momento, eu suspeitava que existe uma relação entre os dois problemas advindos do fato de o QFT e o GCD serem usados ​​como sub-rotinas no algoritmo de busca de período, mas não consegui formalizar isso. Talvez outros usuários possam nos esclarecer mais.
Alessandro Cosentino
Oi Alessandro: Você sabe se o Polynomial GCD está na Carolina do Norte?
T ....
1
@Arul: sim, é. Veja von zur Gathen, Algoritmos paralelos para problemas algébricos. Dx.doi.org/10.1145/800061.808728
Alessandro Cosentino