Quantum codes achieving approximate quantum error correction (AQEC) are useful, often fundamentally important, from both practical and physical perspectives but lack a systematic understanding. In this work, 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) critical threshold then any state in the code subspace must obey certain circuit complexity lower bounds, which identify nontrivial “phases” of codes. Our theory of AQEC provides a versatile framework for understanding the quantum complexity and order of many-body quantum systems. In addition to showcasing applications to a wide variety of AQEC codes arising from diverse contexts spanning computer science and physics, we also demonstrated how our theory offers new physical insights through the lens of both gapped and gapless systems. Specifically, it enables a long-sought rigorous understanding of the gap between strict definitions of gapped topological order and the widely-used long-range entanglement and topological entanglement entropy (TEE) signatures, as well as a discussion of how AQEC codes exhibiting physically significant power-law-error behavior emerge at low energies of conformal field theory (CFT), potentially advancing the understanding of quantum gravity through holography. 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. [Ref: arXiv:2310.04710, in press at Nature Physics]