#11#2 No está demostrado que los ordenadores cuánticos puedan resolver problemas NP en tiempo polinomial.
Lo que sí está bastante claro es que si se puede construir un ordenador cuantico, se podrá factorizar rápido (algoritmo de Shor) y buscar rápido en listas desordenadas (algoritmo de Grover). Pero ninguno de estos dos problemas son np-completos. También se podrán realizar simulaciones sobre procesos cuanticos.
Los problemas que puede resolver un ordenador cuántico son los BQP. En la Wikipedia se puede ver la relación entre P NP y BQP en.wikipedia.org/wiki/BQP
Lo que sí está bastante claro es que si se puede construir un ordenador cuantico, se podrá factorizar rápido (algoritmo de Shor) y buscar rápido en listas desordenadas (algoritmo de Grover). Pero ninguno de estos dos problemas son np-completos. También se podrán realizar simulaciones sobre procesos cuanticos.
Los problemas que puede resolver un ordenador cuántico son los BQP. En la Wikipedia se puede ver la relación entre P NP y BQP
en.wikipedia.org/wiki/BQP