¿Por qué y cómo es una computadora cuántica más rápida que una computadora normal?

Actualmente estoy leyendo un libro (y mucha wikipedia) sobre física cuántica y todavía tengo que entender cómo una computadora cuántica puede ser más rápida que las computadoras que tenemos hoy.

¿Cómo puede una computadora cuántica resolver un problema en tiempo sub-exponencial que una computadora clásica solo puede resolver en tiempo exponencial?

Una computadora cuántica por sí sola no es más rápida. En cambio, tiene un modelo diferente de cálculo . En este modelo, hay algoritmos para ciertos problemas (¡no todos!), Que son asintóticamente más rápidos que los algoritmos clásicos más rápidos posibles (o más rápidos conocidos, para algunos problemas).

Recomiendo leer The Limits of Quantum de Scott Aaronson: es un breve artículo popular que explica exactamente lo que podemos esperar de las computadoras cuánticas.

$2^n$

Es un problema abierto sujeto a la investigación de vanguardia si los algoritmos cuánticos serán alguna vez más rápidos que los algoritmos "clásicos" tanto en el nivel teórico como en el aplicado. en teoría de la complejidad se refleja en la pregunta, por ejemplo, BQP =? P, es decir, si la clase de computación cuántica "P" es equivalente o no a la clase clásica P (tiempo polinómico) y hay muchas otras preguntas abiertas relacionadas.

hay un punto de datos muy intrigante y significativo: el galardonado algoritmo Shors factoriza los números en el tiempo cuántico P, pero aún no se sabe si existe un algoritmo de factorización clásico P-time.

Una nueva dirección en los últimos años es el trabajo en computación cuántica adiabática que es más fácil de implementar / diseñar que otros métodos estándar que involucran el transporte qbit (pero aún así es extremadamente difícil de implementar).

la única computadora (s) cuántica (s) construida hasta la fecha es por sistemas Dwave y actualmente está sujeta a un intenso escrutinio científico y controversia con respecto a sus efectos cuánticos y rendimiento reales; es muy costoso y básicamente no supera a una computadora de escritorio, cuando el código clásico está completamente optimizado (humano / mano). sin embargo, se puede afirmar que ninguna otra entidad de investigación corporativa, gubernamental o universitaria parece estar cerca de su nivel de avance aplicado / técnico / de ingeniería hasta el momento.

el panorama científico es turbio en este momento y algunos expertos / críticos / escépticos científicos, por ejemplo Dyakonov, han creído durante mucho tiempo / argumentan firmemente que las computadoras QM escalables nunca se materializarán debido a dificultades y / o barreras técnicas insuperables.

Tengo una prueba que dice que incluso la potencia cuántica tiene sus límites.

A las computadoras cuánticas les resulta muy difícil incluso llegar a un kilobit de qbits. Pero incluso si solo llegan allí, es bastante poderoso.

16384 qbits harían 128 dimensiones de espacio por 128 pasos de tiempo, búsqueda exhaustiva completa, ¡eso es increíble, 100 pasos de tiempo 100 árbol de probabilidad de dimensión !!! pero no espere más de esa cantidad para Quantum en el futuro cercano.

Un sistema cuántico es un sistema que existe en un estado cuántico (s) con diferentes probabilidades determinadas por restricciones ambientales. Suponiendo que una computadora cuántica contiene todos los estados de un sistema cuántico de n bits, la extracción de uno de estos estados colapsa el sistema en uno de los estados. Esto es similar a una función hash que usa O (1) para buscar un depósito sin iteración. Se necesitan dos cosas, el almacenamiento cuántico de los sistemas de n bits y una función de tipo hash para colapsar el estado que se necesita. Las restricciones desempeñan el papel de diferentes funciones de hash para colapsar el sistema de n bits en el estado deseado.

Piénselo de esta manera: hay problemas que pueden resolverse resolviendo una gran cantidad de sub-casos individuales [ejemplo: factoring por división de prueba]. La resolución de estos problemas lleva mucho tiempo si uno tiene que resolver los casos secundarios uno tras otro. Se pueden resolver mucho más rápido si se puede proporcionar suficiente hardware para resolver todos los casos secundarios en paralelo, pero eso no es práctico porque la cantidad de hardware necesario aumenta con el tamaño del problema. La computación cuántica explota la característica de superposición de estados de la mecánica cuántica para simular el suministro de hardware suficiente, es decir, cada estado en la superposición es 'la máquina' para uno de los sub-casos. Tenga en cuenta que esta simulación no se realiza por software, sino por la naturaleza misma.