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.
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.
Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process’s complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n -qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state in our model, via a complexity-constrained process, is quantified by the state’s . The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the . The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer’s ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy. In a random circuit—a simple model for quantum chaotic dynamics—the complexity entropy transitions from zero to its maximal value around the time corresponding to the observer’s computational-power limit. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a , which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of , as quantified by .
An exact operational selector specifies which candidate maps are nonnegative on declared preparation and effect resources. This paper studies finite-count calibration of that resource-dependent question for a qubit apparatus with an inert qubit reference, an arbitrary complex physical preparation, and an arbitrary physical binary detector, relative to a trusted common calibration frame. Two preparation-stabilizer settings and six separable detector probes control the statistic of the affine family (1 − θ)id + θT, 0 ≤ θ ≤ 1, uniformly over all compatible state–effect pairs. The explicit radius is 3h + √(2s), where h is a simultaneous detector calibration width and s is a one-sided bound on Bell infidelity. It yields simultaneous inner and outer confidence sets for a one-parameter slice of the declared safe-map class. A fixed allocation of 200,000 trials per calibration setting, totaling 1,600,000 calibration trials, gives false-implication probability at most 0.005 and transpose-exclusion power at least 0.996 at the specified physical alternative. The calibration confidence budgets are 0.001 for preparation and 0.004 for the detector. This exclusion calculation uses no target stream; the acquired calibration circuits can use identity wiring. Coverage and prospective power remain separate statements. The acquisition contract uses fixed-length iid Bernoulli streams with their stated physical means and permits coupling between whole streams. The numerical example sets external-reference systematic errors to zero, and its trial budget excludes establishing reference trust and accuracy. If the preparation and detector references are not linked, the paper constructs two physical identity-wired apparatus worlds with identical complete record laws under the specified independent acquisition construction but different safety conclusions on the fixed target cone pair. A secondary nearest-center theorem supplies unconditional error control for the joint event of a wrong and nonabstaining candidate label under an additional finite-context target-law contract. Its nonidentity candidates are not completely positive maps, and their ideal probabilities lie below the nominal detector’s ordinary positive-output floor. That target law is an explicit model assumption; the label theorem is not a conditional-correctness or posterior statement. The results are analytic and prospective. The number of settings and trial allocations are sufficient constructions, with no empirical success-rate, minimality, optimal sample-complexity, or general certified count-to-feasibility implementation claim. The scope is one declared qubit apparatus, target preparation ray and binary effect cone, and affine map slice. The common complex operator description, trusted reference relationship and physical calibration probability law are assumptions. Exact finite checks and an assessed supporting Lean subset accompany the manuscript. That subset covers 326 audited named declarations: 240 theorems and 86 definition/type interfaces. Analytic binomial coverage, concentration and acquisition bridges, independent-product-law construction and normalization, and the complete noisy-power chain remain outside the accepted Lean subset. That subset does not establish a certified numerical feasibility evaluator, a complete physical two-sector implementation, or an ordinary-channel realization. AI assistance and the dated review/correction provenance are disclosed in the manuscript and companion records. No experimental dataset, external human peer review, or end-to-end formal verification is claimed.
Quantum circuit complexity is a fundamental concept whose importance permeates quantum information, computation, many-body physics and high-energy physics. While extensively studied in closed systems, its characterization and behaviors in the widely important setting where the system is embedded within a larger one -- encompassing measurement-assisted state preparation -- lack systematic understanding. We introduce the notion of embedded complexity that characterizes the complexity of projected states and measurement operators in this general setting incorporating auxiliary systems and measurements. For random circuits and certain strongly interacting time-independent Hamiltonian dynamics, we show that the embedded complexity is lower-bounded by the circuit volume -- the total number of gates acting on both the subsystem and its complement. This strengthens the complexity linear growth theorems, enriches the understanding of deep thermalization, and indicates that measurement-assisted methods generically cannot yield significant advantages in state preparation cost, contrary to expectations. We further demonstrate a spacetime conversion of certain circuit models that concentrates circuit volume onto a subsystem, and showcase applications for random circuit sampling and shadow tomography. Our theory establishes a unified framework for space and time aspects of quantum circuit complexity, yielding profound new insights and applications across quantum information and physics.
Quantum circuit complexity quantifies the minimal number of gates needed to realize a unitary transformation and plays a central role in quantum computation. In this work, we investigate the complexity of quantum circuits through coherence and imaginarity resources. We establish a lower bound on the circuit cost by the Tsallis relative α entropy of cohering power, which is shown to be tighter than the one presented by Bu et al.[\textit{Communications in Mathematical Physics} 405, no. 7 (2024):161] under restrictive conditions. As a consequence, we obtain the relationships between the circuit cost and the coherence generating power via probabilistic average in terms of skew information/relative entropy, and present explicit bounds of the circuit cost for typical quantum gates. Moreover, we derive lower bounds on the circuit cost via the imaginaring power of the circuit, induced by the Tsallis relative α entropy and relative entropy. We demonstrate that imaginarity can yield nontrivial constraints on the circuit cost even when coherence-based lower bounds are zero (e.g., for the T gate), which implies that imaginarity may provide advantages under certain circumstances compared with coherence. Our results may help better understand the connections between quantum resources and circuit complexity.
Loss can restore the vacuum entropy bound without erasing non-Gaussian structure. This paper determines when an entropy statement justifies a coherent-state approximation, when non-Gaussian structure survives optical loss, and what mode and source-request budgets are needed to use that structure. The results give quantum-optics researchers separate criteria for entropy recovery, state approximation, Gaussian concentration and conversion to a specified output. Version 1.5 — revised 10 October 2026. The 96-page PDF contains the main article, Methods, Supplementary Information and references. This revision connects the exact loss boundary to a mode-uniform near-equality certificate, finite-data validation, a conversion-cost lower bound for the same thermally repaired source, and an exact equal-entropy comparison of sources with different conversion-cost exponents. The central figures are updated accordingly. 1. Near-vacuum states can have an unbounded entropy deficit Write νm for the m-mode vacuum and define Δα,m(ρ)=Hα(Wνm)−Hα(Wρ), using natural logarithms; H1 is Shannon entropy. Positive deficit means entropy below vacuum. We construct physical Wigner-positive states satisfying, simultaneously, Em=Tr(Nmρm)→0,21∥ρm−νm∥1→0,dFm(ρm)→0,Δ1,m(ρm)→+∞. Here Fm is the trace-norm-closed convex hull of Gaussian states and dFm uses half the trace norm. Thus proximity to the entire Gaussian model does not control Wigner entropy uniformly in mode number. Independent weak modes amplify a one-mode entropy effect while their total excitation vanishes. For the same sequence, half loss instead gives −Em≤Δ1,m(L1/2⊗mρm)≤0, so the entropy difference from vacuum tends to zero. 2. The exact pure-loss recovery boundary For Wigner-positive inputs, intensity transmissivity η and any fixed positive total input-energy budget E, the sharp threshold is ηc(α)={1/2,α/2,0<α≤1,1<α<2. With Pm,E={ρ:Wρ≥0,Tr(Nmρ)≤E}, supm≥1supρ∈Pm,EΔα,m(Lη⊗mρ)={0,+∞,η≤ηc(α),η>ηc(α). The recovery statement includes the boundary itself and is independent of mode number. Half loss also restores vacuum majorization for arbitrary density operators. For α≥2, established Wigner-norm bounds give the vacuum entropy bound at every transmissivity for Wigner-positive outputs. These statements distinguish a universal guarantee from the earlier sign crossing that a particular source may exhibit. 3. Near equality gives a certificate for the entire input For an arbitrary input ρ, define the half-loss output Shannon excess s(ρ)=h(WL1/2⊗mρ)−m(1+lnπ)≥0. The half-loss identity identifies this quantity with the input's total Wehrl entropy excess. Applying mode-uniform Wehrl stability yields infa∥ρ−∣a⟩⟨a∣∥12≤ln264s(ρ). The bound controls the full input state, with no energy or photon-support restriction. One coherent reference then controls every subsequent quantum channel and every unconditional measurement event. In particular, an event-probability error at most ϵ is guaranteed by s≤(ln2)ϵ2/16. Conversely, a surviving output Gaussian-hull gap enforces s(ρ)≥16ln2dFm(L1/2⊗mρ)2. Recovery of the inequality and proximity to equality therefore support different physical inferences: the former permits residual non-Gaussian structure, while the latter certifies a coherent-state approximation. 4. Surviving structure has mode and conversion costs A thermally repaired vacuum–three-photon source with per-mode occupation c/m has total input energy tending to 3c. Along the recovery boundary, its attenuated state obeys liminfm→∞dFm(ρm,ηc)≥cηc3exp{−c[1−(1−ηc)3]}>0. At half transmission this lower bound is g(c)=(c/8)e−7c/8. Starting from one complete block, Gaussian processing requires Θ(m) output modes to retain any fixed positive gap below this bound at success probability at least a fixed p0>0. Gaussian ancillary states, adaptive Gaussian measurements, feedback, discarding and postselection are included. A distinct task requests fresh independent blocks of this same half-loss source to produce the one-mode target τ∗=(18∣0⟩⟨0∣+6∣1⟩⟨1∣+∣2⟩⟨2∣)/25 within half trace distance 10−6. Let Cm be the infimum of expected complete-block requests divided by success probability, including all failed requests. For fixed 0<c≤1, every achieving Gaussian protocol obeys the asymptotic lower bound logCm≥1281(m/c)1/3−logm−O(1). This is a source-request lower bound; the optimal achievable cost for this source remains undetermined. The proof evaluates a curvature-controlled input certificate for the actual thermally repaired state and applies the Gaussian conversion theorem of the companion paper cited below. 5. Exactly equal entropy does not fix conversion cost For two separate two-mode quartic source families, their mixture probabilities can be adjusted so that their half-loss Shannon entropies are exactly equal. Under a common target, tolerance and failure-inclusive accounting, the inherited matching conversion laws become h(WωA)=h(WωB)=2(1+lnπ)+s,logCA(s)=Θ(s−1/3),logCB(s)=Θ(s−1/2). The target tolerance is held fixed in these asymptotics. The delivered energies after entropy matching satisfy EA,EB∼s/2. At exactly equal energy, the two excesses instead share si(E)=2E−(35/8)E2+O(E3) and differ by sA(E)−sB(E)=15E3+O(E4). Entropy alone therefore cannot select the cheaper source for a fixed output task. 6. Finite data and finite mode budgets Under a declared displaced-input photon-tail bound Tr[N1N>Kσa]≤τK, trusted half loss and all-mode on/off detection with efficiency at least ξmin, the click probability q gives s(σ)≤AKq+τK,AK=1−(1−ξmin/2)KK. A one-sided binomial bound turns this into an entropy confidence certificate. An explicit undisplaced four-photon-cutoff example uses K=4, τK=0, ξ=0.8 and N=3,517,336 independent validation blocks, accepting at most 41 clicks, to certify unconditional event error at most 0.05 with false-acceptance probability at most 0.001 and missed acceptance at most 0.001 on the stated low-click alternative class. All vacuum results count; training, calibration and source heralding are separate costs. When coherent-state approximation alone is the task, the same click measurement supplies a stronger direct fidelity test. The paper also gives all-input finite-budget exclusions above the loss-recovery line. For example, at E=1, α=1.9, η=0.9505 and m=105, the certified bound Δα<0.06942 rules out a target deficit of 0.1 nat. A separate finite single-mode preparation model predicts positive Shannon deficit near η=0.97, negative deficit near η=0.85, and a Gaussian-hull witness above 4.4×10−3 at half transmission, with explicit preparation, measurement-error and raw-trial budgets in the PDF. 7. Dimensional scales, a strict entropy floor and ORCS Near order two, put α=2−δ and L=ln(1/δ). For the maximum deficit Dm,E at fixed total energy, Dm,E(2−δ)=Θm,E(δ/L)for fixed m,Th(δ,E)=ΘE,h(L/δ), where Th is the first mode number allowing a fixed positive deficit h. Beyond a sufficiently large fixed multiple of L/δ, Dm,E(2−δ)=ΘE(mδ). The manuscript separates proved sufficient fronts from necessary exit bounds; the sharp first-crossing coefficient remains open. At every fixed mode number, an energy-unrestricted strict Shannon floor also holds: h(Wρ)≥mln(2π)+εm with εm>0 for all Wigner-positive states. The ordering-resolved coherence spectrum (ORCS) supplies an exact single-mode loss coordinate. With Cr,k denoting the ordering-weighted norm of photon-number-difference block k, Cr,k(Lηρ)=CTη(r),k(ρ),Tη(r)=1−η1−r. For vacuum–n-photon coherence and 1<α<2, C1−α/2(Lη∣n⟩⟨0∣)=(α2η)n. This formula exposes the high-order coherence mechanism at the loss threshold; the universal recovery result is proved through the full nonlinear Wigner-norm inequality. Related papers and history The counterexample paper Wigner entropy below vacuum: physical counterexamples and stability limits expands arXiv:2609.13312v1, submitted on 10 September 2026. This stability paper develops the dimensional, loss-dependent and operational consequences. Its state-approximation and conversion interfaces use the companion results From phase-space entropy to coherent-state error: mode-uniform Rényi–Wehrl stability and Phase records control the conversion cost of non-Gaussian light. The mode-retention comparison connects to Limits to Gaussian concentration of non-Gaussian light.
This paper explores the application of quantum information entropy to the theory of computational complexity. We posit that quantum information entropy can serve as a novel metric for quantifying the complexity of quantum algorithms and their associated resource requirements. The core argument is that traditional measures of computational complexity, such as circuit depth or quantum gate count, often fail to fully capture the inherent challenges posed by quantum systems. By leveraging entropy, we aim to provide a more nuanced and potentially more accurate assessment of the difficulty of quantum computations. This work introduces a framework for analyzing quantum algorithms through the lens of information entropy, exploring relationships between algorithmic complexity, entropy generation, and the resources needed to execute these algorithms. Specifically, we examine how entropy can be used to characterize the 'quantumness' of an algorithm and its impact on the overall computational cost. The ultimate goal is to develop a more robust and predictive model for quantum computation, leading to improved algorithm design and resource allocation. ---