Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound

Abstract

Quantum circuit complexity is often used to characterize the physical cost of state preparation, but its physical meaning depends on the reference and counting rules; the entropy-removal costs of operations such as reset may be left out of resource accounting. We propose the principle of structural fairness and develop the Reference-Contingent Complexity (RCC) framework, jointly specifying the reference, generation capabilities, and atomic costs. We construct a model family that can approximate arbitrary finite-dimensional pure and mixed states. Within an admissible model fixed in advance, we prove a rigorous lower bound on universal optimal quantum circuit complexity. The target state's smooth one-shot information gap relative to the unbiased structured vacuum (the maximum-entropy state on the reference support) has an entropy-spectrum structure. Calibrated by the atomic control bandwidth and with finite-description corrections included, this gap sets a common cost floor for every admissible successful path. Predeclared final-state measurements and their finite-sample statistics thus yield independently verifiable one-sided complexity lower-bound certificates without reconstructing the generation history. Finally, exact structural allocation relations under changes of observation window and reference motivate a conjecture on the reference covariance of entropy and complexity: a reference can shift the complexity zero point, but cannot remove the burden of generating structure at no cost.

arXiv comment119 pages. Substantially expanded treatment of the physical model and axiomatic foundations, with more detailed proofs; main results unchanged. Companion code: https://github.com/yeruciwenrou-dotcom/rcc-refcert