Si el problema de señal del Fermio es un problema NP-hard como parece demostrado por este trabajo, es posible tomar un problema NP-hard, convertirlo en un problema de evolución equivalente estado fermiónicos, preparar físicamente el sistema, que evolucionan, promedio sobre muchas ¿experimentos y esperar el resultado para converger a la solución del problema original?
Respuesta
¿Demasiados anuncios?
user1559834
Puntos
103
Scott Aarson da ejemplos de los problemas que podría parecerse a la habilitación de un procedimiento de reducción, pero no en el papel de 'NP-completo de los Problemas y de la Realidad Física'.
Puede NP-completos, los problemas pueden resolverse de manera eficiente en el universo físico? I encuesta de propuestas incluyendo las burbujas de jabón, el plegamiento de la proteína, la computación cuántica cuántica asesoramiento, cuántica adiabática los algoritmos, la mecánica cuántica no-linealidades, variables ocultas, relativista de la dilatación del tiempo, analógica de la computación, (...)
En los enfoques clásicos:
(...) Hay otros métodos propuestos para la solución de NP-completo los problemas que involucran a la relajación un mínimo de estado de energía, tales como el giro de las gafas y el plegamiento de la proteína . Todos estos métodos están sujetos a las mismas trampas de local optima y potencialmente largos tiempos de relajación.
En la computación cuántica:
(...) En otras palabras, no hay ninguna "fuerza bruta" algoritmo cuántico para resolver problemas del tipo NP-completo los problemas en el polinomio de tiempo, así como no hay fuerza bruta clásico algoritmo.
