Los recursos (tiempo, memoria) necesarios para realizar un cálculo o simulación.El costo computacional se refiere a los recursos—como tiempo, memoria y energía—necesarios para realizar un cálculo o simulación. En física y ciencias de la computación, es una medida crítica de viabilidad: un problema puede ser teóricamente soluble pero prácticamente imposible si el costo crece demasiado rápido con el tamaño. Este concepto es central para entender por qué se necesitan computadoras cuánticas para ciertas tareas, ya que las simulaciones clásicas de sistemas cuánticos a menudo tienen un costo computacional exponencial.
El estudio formal del costo computacional comenzó en la década de 1960 con el trabajo de científicos de la computación como Juris Hartmanis y Richard Stearns, quienes introdujeron las clases de complejidad. La idea de usar el costo computacional para argumentar a favor de las computadoras cuánticas fue popularizada por Feynman a principios de la década de 1980.
El costo computacional se analiza a menudo mediante la teoría de la complejidad, que clasifica los problemas según cómo escalan los recursos requeridos con el tamaño de la entrada. Por ejemplo, un problema que toma tiempo polinómico (como ordenar una lista) se considera tratable, mientras que uno que toma tiempo exponencial (como simular clásicamente un sistema cuántico grande) se vuelve intratable incluso para tamaños moderados. Las computadoras cuánticas buscan reducir este costo para problemas específicos aprovechando la superposición y el entrelazamiento.
El análisis del costo computacional guía el diseño de algoritmos y hardware, desde optimizar simulaciones clásicas en ciencia de materiales hasta determinar qué problemas vale la pena abordar en computadoras cuánticas, como simular la dinámica molecular para el descubrimiento de fármacos.
El famoso 'problema del viajante'—encontrar la ruta más corta a través de muchas ciudades—tiene un costo computacional que crece factorialmente, lo que significa que incluso con todas las computadoras del mundo, sigue siendo irresoluble para solo unos pocos cientos de ciudades.
















