Todos los algoritmos cuánticos que he visto hasta ahora requieren un ordenador cuántico completo como el de Turing, al menos hasta donde yo sé. ¿Existe algún algoritmo cuántico que sólo requiera un autómata finito cuántico ? Si es así, ¿cómo se compara su complejidad asintótica con las versiones clásicas de esos algoritmos?
Respuesta
¿Demasiados anuncios?
Esto es realmente un problema abierto. Incluso para la clase de problemas en los que se sabe que los ordenadores cuánticos son rápidos -y el algoritmo de Shor en particular- no hay ninguna prueba "contundente" de que los ordenadores clásicos deban ser lentos en ellos. (Para que quede claro: no creo que ningún informático serio espere que la factorización esté en P pero no hay ninguna prueba formal de que no lo sea).
No me queda claro qué quieres decir con "máquina de estado finito". El algoritmo de Shor requiere un ordenador cuántico universal, pero cualquier implementación debe tener registros finitos y su tamaño determinará el tamaño de los enteros que pueden factorizar.
Por lo que veo, lo que preguntas es si hay dispositivos cuánticos especiales que proporcionen mejoras en la velocidad cuántica, en comparación con los mejores algoritmos clásicos, para un problema concreto. Si ese es el caso, puede que quieras mirar las implementaciones de computación cuántica óptica lineal del problema de muestreo de bosones, que está exactamente en esa clase. Algunos lugares donde buscar son
La complejidad computacional de la óptica lineal. S Aaronson y A Arkhipov. Actas del 43º simposio anual de la ACM sobre teoría de la computación (STOC '11), pp. 333-342 . Documento completo (96 páginas) en arXiv:1011.3245 [quant-ph].
Para una referencia más comprensible, intente esta entrada del blog por Aaronson.
