  We establish rigorous connections between quantum circuit complexity and
approximate quantum error correction (AQEC) properties, covering both
all-to-all and geometric scenarios including lattice systems. To this end, we
introduce a type of code parameter that we call subsystem variance, which is
closely related to the optimal AQEC precision. Our key finding is that if the
subsystem variance is below an $O(k/n)$ threshold then any state in the code
subspace must obey certain circuit complexity lower bounds, which identify
nontrivial ``phases'' of codes. Based on our results, we propose $O(k/n)$ as a
boundary between subspaces that should and should not count as AQEC codes. This
theory of AQEC provides a versatile framework for understanding the quantum
complexity and order of many-body quantum systems, offering new insights for
wide-ranging physical scenarios, in particular topological order and critical
quantum systems which are of outstanding importance in many-body and high
energy physics. We observe from various different perspectives that roughly
$O(1/n)$ represents a common, physically significant ``scaling threshold'' of
subsystem variance for features associated with nontrivial quantum order.
