Quantum complexity measures the difficulty of obtaining a given state starting from a typically unentangled state. In this work, we show that complexity, when defined through the minimization of a Riemannian cost functional over the manifold of Gaussian states, provides the same information as quantum fidelity and is therefore capable of detecting quantum phase transitions. However, it does not offer a more refined analysis than entanglement entropy for a given state. We conclude that incorporating a notion of spatial locality into the computation of complexity is essential to uncover new physics beyond what is accessible through entanglement entropy and fidelity.