TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Flagged Gibbs trace estimation: errors, probability floors and charged access

Statement

Let $d \geq 1$ , $0 < θ \leq 1 / 4$ , and let a frozen finite Hermitian matrix $G$ satisfy $1 \leq λ_{\min} (G) \leq 2$ and a supplied finite norm bound. Let $A = A^{*}$ with $∥ A ∥ \leq 1$ , $Z = tr (e^{- G})$ , $ρ_{G} = e^{- G} / Z$ , and $F_{A} = \frac{1}{2} \sqrt{I + A / 2}$ . Choose $0 < e \leq \min (1 / 2, θ / (100000 d))$ and the common normalizations $B_{G}^{+} = B_{A}^{+} = 1 + e / 8$ . Supply finite successful blocks approximating $e^{- G / 2} / B_{G}^{+}$ and $F_{A} / B_{A}^{+}$ in operator norm within $e$ . The baseline observable block approximates $I / (2 B_{A}^{+})$ within $e$ , using the same normalizations. Supply their unitary circuits, inverses, controlled versions, and the reference preparation $∣ Φ_{d} ⟩ = d^{- 1 / 2} \sum_{k = 1}^{d} ∣ k, k ⟩$ at declared cost $C_{Φ}$ .

Let $V_{A}$ prepare the reference and apply the Gibbs block followed by the observable block on its first factor, with distinct work registers; success means both work registers zero. Define $V_{0}$ with the baseline observable block. Supply a rational $c_{r e l}$ satisfying $θ / 72 < c_{r e l} \leq θ / 36$ and rational failure budgets in $(0, 1)$ . Apply Relative estimation of a promised coherent success probability separately to their actual probabilities $q_{A}, q_{0}$ , with floor $1 / (1024 d)$ and relative tolerance $c_{r e l}$ . Form $2 ({\hat{q}}_{A} / {\hat{q}}_{0} - 1)$ , allowing additive rounding error at most $θ / 4$ , and clip to $[- 1, 1]$ . On the joint relative-estimation good event, the result estimates $tr (A ρ_{G})$ within $θ$ .

The ideal probabilities satisfy $p_{0} \geq 1 / (64 d)$ and $p_{A} \geq 1 / (128 d)$ ; the actual probabilities both exceed $1 / (1024 d)$ . ShiftMin's measured parameters must be frozen once per MMW round before making an indexed trace sampler. A finite coherent implementation retains every internal history and provides an inverse of its entire circuit, without an inverse of a normalized postselected Gibbs state.

With primitive cost $Q_{f l a g}$ for each complete preparation, inverse or controlled preparation, including reference preparation inside each call, the number of primitive accesses is $\tilde{O} (\sqrt{d} / θ)$ with confidence logarithms. Thus their charged cost is $\tilde{O} ((\sqrt{d} / θ) Q_{f l a g})$ . Controlled reflections, all AE/QFT operations and coherent arithmetic, comparisons, divisions, rounding and history work are additional charged quantum operations unless included in the declared primitive cost. This query bound alone implies no matching total quantum-gate bound; that stronger profile requires efficient implementations of every such operation and its precision budget.

Facts & Assumptions

Given: The matrices, spectral promises, precision, common normalization, finite block-error bounds, reference circuit, controlled access, inverse access and declared costs in the Statement. The supplied reference is exact; if its state has error $e_{Φ}$ , add $e_{Φ}$ to each successful-vector error below and tighten the numerical budgets accordingly.

[F1]

Flagged trace ratio returns a Gibbs-state observable mean gives the maximally entangled trace identity and the ideal Gibbs observable ratio by finite trace cyclicity.

[F2]

Certified finite smooth Fourier approximation and LCU normalization supplies finite Fourier/LCU blocks with certified normalization $1 + e / 8$ for the exponential and observable square root after their declared synthesis errors are allocated. Its remarks give their analytic coefficient budgets; the operator error required here includes every implementation contribution.

[F3]

Relative estimation of a promised coherent success probability and Relative probability estimation with a charged finite cap apply to a finite unitary with supplied controlled sampler, inverse and reflection access and a promised positive probability floor. They return rational relative estimates with the stated confidence, a finite padded cap and the declared sampler query cost. Their retained exact-cyclotomic mode has its charged finite comparison cost; the supplied efficient-grid mode uses polynomial-in-logarithmic-scale reversible rounding. Every other arithmetic cost remains charged.

Proof

Given: The data and finite-circuit access above.

1.1givenF1algebra

On disjoint initially zero work registers, projection of both flags after the sequential blocks gives the product of their successful compressions: the second block does not act on the first work register, so a nonzero first-work component cannot contribute to joint success. For any matrix $M$ , direct expansion of the orthonormal reference labels gives $∥ (M \otimes I) Φ_{d} ∥^{2} = tr (M^{*} M) / d$ . Using $F_{A}^{2} = (I + A / 2) / 4$ , trace cyclicity and the common normalizations therefore yields $p_{0} = Z / [4 d (B_{G}^{+})^{2} (B_{A}^{+})^{2}]$ and $p_{A} = p_{0} [1 + \frac{1}{2} tr (A ρ_{G})]$ . No commutation of $A$ with $G$ is needed. Thus $x = p_{A} / p_{0} \in [1 / 2, 3 / 2]$ . The cancellation depends on the baseline being $I / (2 B_{A}^{+})$ , with the same $B_{A}^{+}$ as the numerator.

1.2givenF2constructalgebra

Condition on one good ShiftMin measurement for the MMW round. Freeze its energy shift, the resulting matrix $G$ , its norm bound, all Fourier cutoffs and coefficient encodings, normalizations and synthesis parameters before constructing indexed TraceMean. Shifting the energy by a scalar multiple of the identity changes no normalized Gibbs density matrix. Every indexed $A_{i}$ and the separate scalar $C$ estimate use this same frozen Gibbs block. The scalar estimate may be measured once before defining the geometric oracle's region. Repeating or measuring ShiftMin inside an indexed sampler is not justified by the present construction. The Fourier theorem [F2] supplies the finite analytic blocks conditional on these frozen parameters and declared implementation errors.

1.3givenF3constructalgebra

To implement finite adaptive RelProb coherently, copy each would-be measured computational-basis outcome to a fresh retained history register, perform all subsequent arithmetic reversibly and condition further operations on that history. Pad stopped branches by identities to the supplied finite worst-case cap. Fresh repetition workspaces and retained coin registers reproduce independent repetitions. Orthogonal history labels prevent distinct classical branches from interfering, so measuring the final estimate gives the classical procedure's distribution. Retain every AE/QPE target, stop flag, rounded value, comparison bit, arithmetic scratch and coin; reversing the entire padded circuit gives its inverse. Controlled versions require the supplied controlled access or controlled explicit gates and their charged costs. No normalized postselected-state inverse occurs. In this implementation every arithmetic, exact algebraic comparison, division and rounding operation is coherent quantum work, not free classical preprocessing.

2.1givenstep 1.1algebra

At least one eigenvalue of $G$ is at most two, so $Z \geq \exp (- 2) > 1 / 8$ . For an elementary numerical bound, the exponential series through degree three sums to $8 / 3$ and its remaining tail is at most $(1 / 24) \sum_{j \geq 0} 5^{- j} = 5 / 96$ , giving $\exp (1) \leq 87 / 32 < 11 / 4$ , hence $\exp (2) < 121 / 16 < 8$ . Since $e \leq 1 / 2$ , $(B_{G}^{+})^{2} (B_{A}^{+})^{2} \leq (17 / 16)^{4} < 2$ . Step 1.1 gives $p_{0} \geq 1 / (64 d)$ and $p_{A} \geq p_{0} / 2 \geq 1 / (128 d)$ . The ideal block operators are contractions because $G ⪰ I$ , $∥ A ∥ \leq 1$ and their normalizations exceed one.

3.1givenstep 2.1algebra

Write ideal blocks as $D, C$ and their actual successful compressions as $D + E_{D}, C + E_{C}$ , with both error norms at most $e$ . Then $∥ (C + E_{C}) (D + E_{D}) - C D ∥ \leq ∥ E_{C} D + C E_{D} + E_{C} E_{D} ∥ \leq 2 e + e^{2}$ . The same holds for the baseline. Consequently each actual successful vector differs from its ideal vector by at most $2 e + e^{2} \leq (5 / 2) e$ . Since the ideal vector has norm at most one, its probability differs by at most $2 (5 e / 2) + (5 e / 2)^{2} \leq 15 e$ . Thus, putting $Δ = 15 e$ , $∣ q_{s} - p_{s} ∣ \leq Δ$ for $s = A, 0$ . The errors compare ideal blocks against the actual finite circuits whose probabilities are estimated, rather than being ignored at each estimator invocation.

4.1F3step 1.1step 2.1step 3.1algebra

The actual floor follows from $q_{s} \geq 1 / (128 d) - 15 θ / (100000 d) > 1 / (1024 d)$ , so [F3] applies to both calls. Put $κ = Δ / p_{0} \leq 960 d e \leq θ / 100 \leq 1 / 400$ . Cross multiplication and $x \leq 3 / 2$ give $∣ q_{A} / q_{0} - x ∣ \leq (Δ + x Δ) / (p_{0} - Δ) \leq (5 κ / 2) / (1 - κ) \leq 3 κ \leq 3 θ / 100$ . In particular $q_{A} / q_{0} < 2$ .

5.1F3step 4.1algebra

On both relative-estimation good events, $c_{r e l} \leq θ / 36 \leq 1 / 144$ , so $∣ {\hat{q}}_{s} - q_{s} ∣ \leq c_{r e l} q_{s}$ and ${\hat{q}}_{0} > 0$ . Therefore $∣ {\hat{q}}_{A} / {\hat{q}}_{0} - q_{A} / q_{0} ∣ \leq (q_{A} / q_{0}) 2 c_{r e l} / (1 - c_{r e l}) \leq 5 c_{r e l} \leq 5 θ / 36$ . Combining this with step 4.1, the unrounded trace estimate has error at most $2 (3 θ / 100 + 5 θ / 36) < θ / 2$ . Rational division and final rounding with error at most $θ / 4$ leave error below $θ$ . Clipping cannot increase distance from the true trace in $[- 1, 1]$ . The denominator cannot vanish on this good event.

6.1givenstep 4.1step 5.1step 1.3algebra

The floors and caps are uniform in the basis index. Thus step 4.1 and step 5.1 apply conditionally to each index with the allocated good-output probability. They do not assert that every supported label is good. A robust-minimum consumer needs its separate operator-norm cleaning and whole-circuit hybrid theorem; uniform marginal trace accuracy alone does not imply those hypotheses.

7.1givenF3step 1.2step 1.3step 6.1algebra

If finite implementations further approximate the declared access unitaries, let the padded circuit have at most $L$ such slots. Allocate operator error $ζ \leq δ_{h y b} / (4 L)$ per slot, or nonuniform errors summing to at most $δ_{h y b} / 4$ . Telescoping the product of unitaries bounds final vector error by the error sum, and measurement total variation by at most twice that sum, hence at most $δ_{h y b} / 2$ . Inverse errors have the same norm, and controlled errors obey the same bound when their operator estimates hold uniformly over the controlled index blocks. Apply any coherent robust-minimum consumer's stronger operator-cleaning and global hybrid budget separately. A union bound combines the two relative-estimation failure budgets, scalar/shift failures and these implementation budgets; independence is unnecessary.

8.1F2F3step 5.1step 1.3step 7.1algebra∎

The floor $1 / (1024 d)$ and rational tolerance $θ / 72 < c_{r e l} \leq θ / 36$ in [F3] give $\tilde{O} (\sqrt{d} / θ)$ sampler-plus-inverse accesses for each probability, including its finite cap and confidence logarithms. Two calls preserve this order. Each complete flag preparation, inverse or controlled preparation costs its supplied $Q_{f l a g}$ , including reference preparation of cost $C_{Φ}$ inside each invocation, both finite blocks, flag handling and scratch. Add controlled input/success reflections and control phases where not included. All AE/QFT gates and the reversible arithmetic, algebraic comparisons, divisions, rounding, history storage and precision synthesis in step 1.3 and step 7.1 are charged quantum gates and work. [F3] retains a finite but potentially expensive exact-cyclotomic mode, and also supplies efficient-grid rounding with polynomial-in-logarithmic-scale reversible resources. Use the actual selected mode and charge every other arithmetic operation; mere finiteness does not establish polylogarithmic gate complexity. A source-like total gate profile therefore remains conditional on efficient implementations of every charged primitive, including sparse access and memory if used. The access bound and step 5.1 establish the theorem without any such unproved efficiency inference.

Depends on

Used by

Dependency tree · two levels

23 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

van Apeldoorn et al., Quantum SDP-solvers: Better upper and lower bounds, Sections 2.2–2.3 (standard reference, not scraped)