La existencia de algoritmos que solo una computadora cuántica puede resolver es un tema de disputa. Antes de revisar la web, mi respuesta habría sido una computadora clásica que satisficiera la integridad de Turing utilizando bits, la arquitectura von Neumann y las puertas clásicas (AND, OR, NOR, XOR, etc.) pueden emular una computadora cuántica y ejecutar sus algoritmos. El problema es solo cuánto tiempo lleva una solución de este tipo. Una revisión rápida de la web reveló una contra opinión opuesta:
[quant-ph / 0111063v2] Una reformulación del décimo problema de Hilbert a través de la Mecánica Cuántica (artículo de TT Kieu) “Un algoritmo cuántico para el décimo problema de Hilbert, que es equivalente al problema de detención de Turing y se sabe que es matemáticamente no computable, es propuso dónde se emplean variables cuánticas continuas y evolución adiabática cuántica. Si este algoritmo pudiera implementarse físicamente, tanto como sea válido en principio, es decir, si cierto hamiltoniano y su estado fundamental pueden construirse físicamente de acuerdo con la propuesta, computabilidad cuántica superaría la computabilidad clásica como lo delimita la tesis de la Iglesia-Turing. Por lo tanto, se argumenta que la computabilidad, y con ella los límites de las Matemáticas, debe determinarse no solo por las Matemáticas en sí sino también por los Principios Físicos “.
y su refutación : https://arxiv.org/ftp/quant-ph/p… ¿Puede la computación cuántica resolver problemas clásicos insolubles? por Andrew Hodges de Oxford. “TD Kieu ha afirmado que un procedimiento de computación cuántica puede resolver un problema clásico insoluble. El trabajo reciente de WD Smith ha demostrado que la afirmación matemática central de Kieu no puede sostenerse. Aquí, se hace una crítica más general de la propuesta de Kieu y se hacen algunas sugerencias sobre la tesis de la Iglesia-Turing “.
- ¿Por qué no se puede probar experimentalmente la interpretación de von Neumann-Wigner de la física cuántica de que la conciencia hace colapsar la función de onda?
- ¿Qué nos dice la acción espeluznante a distancia sobre la naturaleza del universo?
- ¿Cuál es la relación entre la serie Taylor y los diagramas de Feynman?
- ¿Cómo difiere el átomo de hidrógeno relativista del átomo de hidrógeno no relativista?
- ¿Se puede decidir la verdad del enredo de una vez por todas, utilizando el experimento que propongo a continuación?
A medida que se formula la pregunta: cualquier algoritmo se puede emular en una computadora cuántica. El algoritmo se ejecutará. A menos que Google no nos haya dicho algo, su Quantum Computing Playground es una computadora clásica. Sin embargo, no todos los algoritmos se detienen. Problema de detención Esto puede suceder si la computadora es cuántica o clásica. Otros algoritmos necesitan tiempos de ejecución exponencialmente más largos para completarse. NP (complejidad) A menos que se aplique algún límite superior arbitrario en el tiempo de ejecución, el factor tiempo es irrelevante en cuanto a si el algoritmo se puede calcular.
