In the last decade, quantum information theory has proved remarkably useful in quantum gravity. Gauge field/gravity dual models successfully used entanglement entropy to probe the holographic architecture of spacetime; non-perturbative approaches to quantum gravity intended it as a resource to investigate the emergence of classical spacetime geometry out of the hierarchy of correlations of the fundamental quantum system. I will review recent results measuring entanglement entropy in random spin networks, a many-body description of quantum geometry shared by diverse non-perturbative approaches to quantum gravity. Further, in this setting, I will discuss a measure of quantum complexity, whose role in quantum gravity is mostly unexplored.