aiqbench analysis
This paper establishes a rigorous, auditable lower bound for quantum circuit complexity by introducing the Reference-Contingent Complexity (RCC) framework, which accounts for entropy removal costs often ignored in standard resource accounting. By proving that specific information gaps relative to a structured vacuum serve as universal cost floors, the authors provide verifiable certificates for state preparation without needing to reconstruct generation histories. This work advances fundamental quantum information theory by defining structural fairness and quantifying the intrinsic physical burden of generating quantum states under varying reference frames.
Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound
arXiv:2509.18205v4 Announce Type: replace 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.
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.
119 pages. Substantially expanded treatment of the physical model and axiomatic foundations, with more detailed proofs; main results unchanged. Companion code: this https URL
Quantum Physics (quant-ph); Information Theory (cs.IT)
arXiv:2509.18205 [quant-ph]
(or arXiv:2509.18205v4 [quant-ph] for this version)
Full text under the publisher's open licence · 243 words
