Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-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.

General adversary spectral lower bound for quantum queries

Statement

For every finite Boolean query problem and 0≤ε<1/2, Qϵ(f)≥(12−ϵ(1−ϵ))Adv⁡±(f). In particular, at ε=1/3 the coefficient is 1/2−2/3>0.

Facts & Assumptions

Given: A finite Boolean query problem and a standard XOR algorithm in its ordinary oracle-only model with worst-case error at most ε.

[F1]

Adversary progress at initial and bounded-error final states: for an admissible real symmetric Γ and a real unit principal eigenvector, an ordinary oracle-only algorithm with per-input error at most ε has |W_0|=||Γ|| and |W_T|≤2√(ε(1−ε))||Γ||.

[F2]

One oracle call changes adversary progress by at most filtered spectral norm: in the ordinary oracle-only unitary normal form, each XOR query changes W by at most 2 max_i||Γ∘Δ_i||.

[F3]

Finite Boolean query problem and error model for adversary bounds: Qϵ(f) is the least worst-case number of standard XOR calls among algorithms correct with probability at least 1−ϵ on every promised input.

[F4]

Quantum query complexity: the query-cost coordinate is the worst-case number of designated oracle calls, excluding nonoracle gates.

[F5]

General adversary matrix and spectral bound: admissible Γ is nonzero, real symmetric and zero on equal-output pairs. Its denominator is positive, and Adv± is the attained maximum of the norm ratio for nonconstant f.

[F6]

Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely: a finite normal complex endomorphism has an orthonormal eigenbasis.

[F7]

Unitary normal form for finite bit-query algorithms without extra queries: an ordinary oracle-only algorithm with at most T standard XOR queries on each branch has the same output law in unitary normal form with exactly T unconditional queries and an input-independent initial state.

Proof

1.1givenF1F2F3F4F6F7algebra

Fix a nonconstant f and an algorithm with per-input error at most ε, as in the parameterized definition [F3]. If its worst-case query count is T, apply [F7] to obtain the same output probabilities in unitary normal form with T queries. For any admissible real symmetric Γ, [F6] applied to its complexification gives an eigenvalue of modulus ||Γ||; the eigenvalue is real, and real or imaginary part of a corresponding eigenvector is a nonzero real eigenvector, so choose a real unit principal eigenvector α. Put D_Γ=max_i||Γ∘Δ_i||. Between queries the algorithm's input-independent unitaries preserve all pairwise inner products, so they do not change W. For T queries, [F2] and the triangle inequality give |W_T−W_0|≤2T D_Γ.

2.1givenF1F5step 1.1algebra

By [F1], ||Γ||=|W_0|≤|W_T|+|W_T−W_0|≤(2√(ε(1−ε)))||Γ||+2T D_Γ. Since ε<1/2 and D_Γ>0 by [F5], rearrangement yields T≥(1/2−√(ε(1−ε)))||Γ||/D_Γ.

3.1givenF3F4F5step 2.1∎

The inequality holds for every admissible Γ. Taking the attained maximum ratio from [F5] gives Q_ε(f)≥(1/2−√(ε(1−ε)))Adv±(f). For constant f the empty algorithm is exact and both sides are zero.

Depends on

Used by

Dependency tree · two levels

34 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