¿Sería posible simular un ordenador cuántico en un ordenador normal? Estaba pensando en algo así como tener un montón de GPU ejecutando un conjunto de partículas cuánticas entrelazadas y luego producir los resultados. ¿Sería esto factible o se necesitaría toda la vida del universo para ejecutar los problemas?
Respuesta
¿Demasiados anuncios?
Sin duda es posible simular un ordenador cuántico en uno clásico, pero como usted señala la verdadera cuestión es si puede hacerse de forma eficiente.
Los cálculos que realiza un ordenador cuántico son no matemáticas de fantasía: todo es álgebra lineal en términos de evolución unitaria y medida proyectiva de un sistema cuántico de dimensión finita. Sin embargo, si tiene $n$ qubits la dimensión del espacio de estados aumenta como $2^n$ de modo que muy pronto se tienen matrices inmanejablemente grandes, e incluso los algoritmos algebraicos lineales eficientes (en términos del tamaño de la matriz) se convierten en algoritmos de escala exponencial.
Hay una serie de algoritmos de computación cuántica conocidos que pueden simularse eficientemente con un ordenador clásico (tomemos por ejemplo el Teorema de Gottesman-Knill ) y se está investigando qué cálculos pueden simularse así y cuáles no. Si (como parece ser el caso) la factorización no puede realizarse eficientemente en un ordenador clásico, entonces el algoritmo de Shor es un ejemplo de esto último.
