Quantifying the complexity of quantum states that possess intrinsic structure, such as symmetry or encoding, in a fair manner constitutes a core challenge in the benchmarking of quantum technologies. This paper introduces the Reference-Contingent Complexity (RCC), an information-theoretic measure calibrated by the available quantum operations. The core idea is to leverage the quantum relative entropy to quantify the deviation of a quantum state from its "structured vacuum"-namely, the maximum entropy state within its constrained subspace-thereby only pricing the process of creating non-trivial information. Our central result is a key theorem that rigorously proves the RCC serves as a lower bound for the complexity of any universal quantum circuit. This lower bound is comprised of a linear dominant term, a universal logarithmic correction, and a precise physical correction term that accounts for non-uniformity in the spectral distribution. Crucially, we establish a set of operational protocols, grounded in tasks like quantum hypothesis testing, which make this theoretical lower bound experimentally "auditable." This work provides a "ruler" for quantum technology that is structure-fair and enables cross-platform comparison, thereby establishing a strictly verifiable constraint between the computational cost of the process and the structured information of the final state.