Todo lo que puede calcular un ordenador cuántico se puede calcular mediante un ordenador (clásico), basta simularlo. Se acaba de publicar un problema con oráculo que se puede resolver de forma eficiente en un ordenador cuántico, está en la clase BQP, pero que no se puede resolver de forma eficiente en un ordenador (clásico), incluso bajo la hipótesis P=NP. Por supuesto, bajo la hipótesis de que P≠NP ya sabíamos que los ordenadores cuánticos son más eficientes, pues hay problemas en BQP que no están en P.
Comentarios
Habla de complejidad algorítmica, que es un campo que estudiamos los informáticos (no los telecos, aunque todavía haya cientos de ofertas para ellos porque no se sabe muy bien la diferencia en muchas empresas
Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2n-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.
Un problema de decisión C es NP-completo si:
C está contenido en el conjunto NP, y
Todo problema de NP es reducible a C en tiempo polinomial.
Se puede demostrar que C es NP demostrando que un candidato a solución de C puede ser verificado en tiempo polinómico.
Una transformación polinómica de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y sólo si la respuesta a l lo es.
Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.
Por otro lado:
En teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a ¼.
Dicho de otra forma, existe un algoritmo cuántico cuya cota superior en tiempo es polinómica para resolver ese problema, tal que la probabilidad de obtener una respuesta equivocada es menor de 25%.
El nivel de error de ¼ es arbitrario, cualquier valor real k tal que 0 < k < ½ podría ser utilizado sin cambiar el conjunto BQP. La idea es que si la probabilidad de error es pequeña, la ejecución del algoritmo un número suficiente de veces lleva a una probabilidad exponencialmente pequeña de que la mayoría de las ejecuciones sean erróneas.
La computación cuántica ha despertado interés debido a que problemas que se supone no pertenecen a P pertenecen a la clase BQP. Actualmente solo se han clasificado tres de esos problemas:
Factorización entera ( algoritmo de Shor)
Logaritmo discreto
Simulación de sistemas cuánticos (Computador cuántico universal)
No me he enterado de una mierda, pero si alguien es capaz de comprenderlo parece interesante
#1 Esto de lo cuántico fluctúa, más bien, entre el NPI y el FU.
#1 Intel malo, cuánticos con problemas, el proximo pc, me vuelvo al spectrum. Load "" intro.
#4 y ojo, que no había ni que escribirlo entero
El articulo es interesante, pero demasiado orientado para los que nos dedicamos a este campo.
Básicamente este articulo habla de la resolución de algoritmos con complejidad en tiempo polinómico, los cuales son costosos en tiempo (valga la redundancia) para una máquina clásica.
En este caso parece ser que se ha podido demostrar formalmente la resolución de un problema de clase BQPO y su aplicación eficiente en computación cuantica. Si no recuerdo mal la clase BQP esta en igualdad jerarquicamente con el NP, problemas que en computación clásica son mayormente insufribles.
#3 me lo has quitao de la boca
#3 Creo que muchos agradeceremos una explicación en cristiano.
Y dice el Villatoro que escribe en su blog para practicar el arte de hacer fácil lo difícil
Pues que se quite la boina y se arremangue porque no parece ser lo suyo.
#6 en ingeniería, la clase que se explicaba lo de problemas np era tan jodido de entender que parecía que debieras ir bajo efectos de psicotrópicos para lograr algo de entendimiento.
#6 .. se limita a resumir un paper de un tema puntero para hacerlo accesible a gente que no sea del campo,, el blog de Villatoro no se dirige a los que dejaron los libros en educación secundaria, para ellos hay otros blog más accesibles máscaditos e imprecisos.
Ademas del tema de los ordenadores cuánticos y el problema P NP ya lo ha explicado anteriomente bastantes veces, otra cosa es que yo pueda entender lo mínimamente.
Soy experto en ordenadores cuánticos
Creo que esta vez me he columpiado...