Fantásticamente lento es un poco exagerado. Cualquier algoritmo clásico puede implementarse en un circuito cuántico trivialmente, excluyendo todos los estados de superposición para qubits. También se puede demostrar que una máquina de Turing irreversible (una con una matriz de transición no invertible) puede ser simulada por una máquina de Turing reversible con un aumento polinómico (cuadrático) en los recursos, por lo que la codificación de un circuito irreversible en uno reversible debe ser “eficiente” (vea este documento de CH Bennett, o tal vez este documento mucho más antiguo es más fácil de leer).
Pero tengo la sensación de que no estabas haciendo una declaración precisa, y tal vez tu pregunta fue realmente, “¿por qué nuestros algoritmos cuánticos no son tan buenos? La respuesta es aburrida. En principio, no hay razón para que nuestros algoritmos sean malos, pero por alguna razón no hemos encontrado mejores. A pesar de los avances interesantes, como el algoritmo de factorización de números enteros de Shor, todavía estamos en la oscuridad sobre cómo “explotar cuántica” en general (si incluso puede definir con precisión lo que eso significa, podría ganar un buen premio o medalla).
Podemos considerar la aceleración dada por la búsqueda de Grover por un momento. La complejidad es relativa a una llamada de función de caja negra, por lo que si configura el problema para que un algoritmo cuántico y clásico llame a esta cosa de tipo subrutina de caja negra, la versión clásica toma el cuadrado del número de llamadas que toma el algoritmo cuántico. Sin embargo, no se han encontrado implementaciones prácticas de la función de caja negra que preserven esta aceleración sobre todos los demás algoritmos de búsqueda clásicos, e incluso podría tener una reacción mentalmente violenta a esta idea que al principio parece que está barriendo las cosas debajo de la alfombra (ciertamente lo hice ) Supongo que esto es “malo”, pero hasta ahora (la relativización) es lo más avanzado, principalmente porque sin la relativización los problemas son simplemente irresolubles. Por otro lado, el problema de Simon estaba en un lugar similar hasta Peter Shor (ambos son casos especiales de un problema más general), por lo que al menos en un caso valió la pena ser un poco optimista.
- La singularidad tecnológica: ¿cuánto poder informático se necesitaría para ejecutar una simulación de antepasados para todos los que alguna vez existieron en la Tierra?
- ¿Dónde existe la mecánica cuántica en la vida real?
- ¿Alguien puede proporcionar una explicación simple pero detallada de la computación cuántica?
- ¿Qué puede hacer una computadora cuántica de 8 bits mejor que una clásica?
- ¿La computación cuántica es solo un concepto o tiene aplicaciones prácticas que se pueden aplicar en la tecnología ahora?
