En un nuevo paper de Andreas de Vries[1], parece ser que el algoritmo que plantea es capaz de realizar una búsqueda en una base de datos desordenada en un órden O(log n). Esto implica que NP está dentro de BQP, o sea: los problemas NP completos son resolubles en tiempo polinomial en una computadora cuántica.
Si esto es correcto, este nuevo algoritmo hace obsoleto el algoritmo de Grover y es, junto al algoritmo de Shor, uno de los más importantes algoritmos cuánticos.
Aún debo leerlo más "sesudamente", luego comentaré mis impresiones.
Update: Estaba leyendo el paper y encontré hasta ahora un error en la ecuación (9) donde dice que C²=C-I, esto no es cierto, pero igualmente, antes de terminar de leerlo encontré este post en el Weblog de Dave Bacon que ya lo estudió a fondo y encontró otros errores más. El paper fue enviado a la Physical Review D, así que será cuestión de tiempo de esperar a que lo refereen y de Vries corrija los errores, asimismo creo que la afirmación de que NP C BQP no se podrá demostrar a partir de este algoritmo.
Update++: En palabras del mismo Andreas, el problema más severo en su paper está en el Ejemplo 5, en el cual dice que su algoritmo es más rápido que el de Grover, y esto no es cierto, ya que para el caso especial de N=4 (el que él analiza) el algoritmo de Grover requiere una sóla consulta al oráculo, no 2 como dice él, y en ese caso su algoritmo se comporta exactamente igual, por lo tanto el algoritmo de Grover sigue siendo "óptimo".
[1] A. de Vries, Fast quantum search algorithms by qubit comparisons exploiting global phase interference, arXiv:quant-ph/0506137.
Blog sobre computación cuántica y fundamentos de las ciencias de la computación. En general cubrimos los temas de investigación a los que nosotros nos dedicamos, los cuales comenzaron siendo computación cuántica, y con el tiempo van evolucionando, cambiando, agregando nuevas áreas, etc.
0 comments:
Publicar un comentario