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

Three classical samples solve Deutsch–Jozsa with bounded error

Statement

For n≥2, the finite probability experiment that samples three distinct addresses uniformly without replacement and outputs constant exactly when all three replies agree has success probability at least 3/4 on every Deutsch–Jozsa input. In the finite fair-bit classical query model, sampling three independent uniform addresses with replacement and using the same output rule also succeeds with probability at least 3/4, using exactly 3n random bits and three value queries. For n=1, querying both addresses solves the promise exactly with two queries. Thus the deterministic exact lower bound is not a bounded-error exponential separation.

Facts & Assumptions

Given: n≥2, N=2n≥4, and a total Boolean function promised constant or exactly balanced; consider both the uniform without-replacement experiment and the independent with-replacement algorithm.

[F1]

Deutsch–Jozsa promise: a balanced function has N/2 addresses of each output value.

[F2]

Classical query algorithm: randomized addresses may be chosen from the random tape, and query cost counts each returned function value once.

[F3]

Finite probability spaces, outcome weights, events, and event probabilities: the uniform law on a finite set assigns each outcome reciprocal cardinality and event probability by finite summation.

[F4]

The cardinality ∣A∣ of a finite set: the address and ordered-triple sample sets have their finite cardinalities.

Proof

1.1givenF1F3F4algebra

For a constant function, all three replies agree, so the procedure outputs constant correctly with probability one. For a balanced function write m=N/2. The ordered sample space has N(N−1)(N−2) triples. If m=2, no three distinct samples can have the same reply, so the error probability is zero. If m≥3, the error event consists of an ordered triple all drawn from the zero class or all from the one class; its probability is 2m(m−1)(m−2)(2m)(2m−1)(2m−2)=m−22(2m−1)=N−44(N−1). This is at most 1/4, since N−4≤N−1.

2.1givenF1F2step 1.1algebra∎

The without-replacement experiment has success at least 3/4 by step 1.1. For an implementation in the finite fair-bit model, take three independent blocks of n fair bits as addresses, allowing repetitions. On a balanced input the three replies are independent fair bits, so they all agree with probability 2(1/2)3=1/4; on a constant input they always agree. Thus this algorithm uses exactly 3n random bits and three value queries and has success at least 3/4. When n=1, the domain has two addresses and querying both returns the full truth table, which classifies exactly. The claim concerns bounded-error upper cost and leaves the deterministic exact lower bound as a separate query measure.

Depends on

Used by

Dependency tree · two levels

19 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