The resources (time, memory) required to perform a computation or simulation.Computational cost refers to the resources—such as time, memory, and energy—required to perform a computation or simulation. In physics and computer science, it is a critical measure of feasibility: a problem may be theoretically solvable but practically impossible if the cost grows too quickly with size. This concept is central to understanding why quantum computers are needed for certain tasks, as classical simulations of quantum systems often have exponential computational cost.
The formal study of computational cost began in the 1960s with the work of computer scientists like Juris Hartmanis and Richard Stearns, who introduced complexity classes. The idea of using computational cost to argue for quantum computers was popularized by Feynman in the early 1980s.
Computational cost is often analyzed using complexity theory, which classifies problems by how the required resources scale with input size. For example, a problem that takes polynomial time (like sorting a list) is considered tractable, while one that takes exponential time (like simulating a large quantum system classically) becomes intractable for even moderate sizes. Quantum computers aim to reduce this cost for specific problems by exploiting superposition and entanglement.
Computational cost analysis guides the design of algorithms and hardware, from optimizing classical simulations in materials science to determining which problems are worth pursuing on quantum computers, such as simulating molecular dynamics for drug discovery.
The famous 'traveling salesman problem'—finding the shortest route through many cities—has a computational cost that grows factorially, meaning even with all the world's computers, it remains unsolvable for just a few hundred cities.
















