It's complex in a physicist's sense of the word: the equations are hopelessly complicated to solve even in very simple cases. This means it's hard to build intuition or describe in simple terms.
Quantum chromodynamics is actually pretty similar to Maxwell's equations of electromagnetism. The big difference is that unlike photos, gluons interact with each other. This means goodbye to linear equations and simple planewave solutions. One can't even solve the equations in empty space, and only recently have supercomputers become powerful enough to make good, quantitative predictions about things like the proton mass.
I wonder if it is inherently complex in an information-theory framework, or that we simply haven’t yet found its “natural” basis under which its description is most succinct?
Yeah it's a great question. I don't know the answer, but I suspect the people who study it strongly suspect that it is highly complex in this sense. Otherwise they would be looking for simpler representations instead of running massive simulations.
To your question, I think there is an elegant answer actually; most composite particles in QCD are unstable. They're either made out of equal parts matter and antimatter (like pions) or they're heavier than the proton, in which case they can decay into one (or more) protons (or antiprotons). If any of the internal complexities of the proton made it distinguishable from other protons, they wouldn't both be protons, and one could decay into the other. Quantum mechanics also helps to keep things simple by forcing the various properties of bound states to be quantized; there isn't a version of a proton where e.g. one of the quarks has a little more energy, similar to how the energies atomic orbitals are quantized.
A key property of QCD is that unlike electrodynamics, the forces between interacting objects increase with distance (quark confinement). This is what breaks the usual style of expansions used to simplify problems. It's hard to overstate how important this is.
One of the implications is that there are many interactions where most possible Feynman diagrams contribute non-negligibly. The advances in theory arguably have much more to do with improvements in techniques and the applied math used, such as in lattice QCD and Dean Lee's group for instance.
Quantum chromodynamics is actually pretty similar to Maxwell's equations of electromagnetism. The big difference is that unlike photos, gluons interact with each other. This means goodbye to linear equations and simple planewave solutions. One can't even solve the equations in empty space, and only recently have supercomputers become powerful enough to make good, quantitative predictions about things like the proton mass.