¿Existe un algoritmo cuántico de NC para calcular GCD?

14

A partir de los comentarios sobre una de mis preguntas sobre MathOverflow, tengo la sensación de que la pregunta sobre que GCD está en vs. es similar a la pregunta sobre la Factorización de enteros en vs. .NCPPNP

¿Hay algo así como un algoritmo "quantum " para GCD ya que existe un algoritmo de tiempo polinómico cuántico ( ) para la factorización de enteros?B Q PNCBQPAG

Pregunta relacionada: complejidad del máximo divisor común (mcd)

cc.complexity-theory quantum-computing dc.parallel-comp nt.number-theory comp-number-theory T ....
fuente
55
cuando realiza una publicación cruzada, es mejor volver a escribir la pregunta.
Alessandro Cosentino

Respuestas:

14

En primer lugar, hay una definición formal de "Quantum-NC", ver QNC en el zoológico.

De hecho, GCD es un buen candidato para un problema que podría demostrarse que está en QNC, pero no se sabe que esté en Carolina del Norte. Sin embargo, encontrar un algoritmo QNC para GCD sigue siendo un problema abierto.

El sentimiento por el cual se cree que esto es cierto proviene del hecho de que la Transformación Cuántica de Fourier se puede hacer en QNC.

Referencia: sección de conclusión de "R. Cleve y J. Watrous, circuitos paralelos rápidos para la transformada cuántica de Fourier", arXiv: quant-ph / 0006004

Alessandro Cosentino
fuente
66
Sería bueno si puedes explicar la relación entre la transformada cuántica de Fourier y el MCD.
Kaveh
Estoy de acuerdo con Kaveh. Sería bueno proporcionar la relación.
T ....
2
No creo que haya una relación directa. Lo que quise decir es que sospechamos que QNC es más poderoso que NC, porque podemos hacer QFT en QNC. Entonces preguntamos si hay algún problema más natural que también está en QNC, y uno de los problemas naturales más simples que no sabemos cómo hacer en Carolina del Norte es el MCD. En algún momento sospeché que existe una relación entre los dos problemas que provienen del hecho de que QFT y GCD se usan como subrutinas en el algoritmo de búsqueda de períodos, pero no pude hacer esto formal. Quizás otros usuarios puedan iluminarnos más.
Alessandro Cosentino
Hola Alessandro: ¿Sabes si Polynomial GCD está en Carolina del Norte?
T ....
1
@Arul: sí, lo es. Ver von zur Gathen, Algoritmos paralelos para problemas algebraicos. dx.doi.org/10.1145/800061.808728
Alessandro Cosentino