Approximate computing offers pathways to increased energy efficiency in computational settings where perfect accuracy is not required. In this work, we explore fundamental links between approximation, information loss, and limiting energy efficiency of computation. We distinguish physical and semantic aspects of approximation in digital computation, and show how the physical aspects — whether of deterministic or non-deterministic origin — can be quantified at a fundamental physical level in physical-information-theoretic measures that directly link loss of input information to energy dissipation. We then present a fundamental energy efficiency bound that explicitly incorporates these measures, and illustrate its evaluation in simple examples involving approximate adders.