Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)
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.

PromiseP is contained in EQP, EQP in ZQP, and ZQP in BQP

Statement

In the QC14 promise-problem model,

PromiseP⊆EQP⊆ZQP⊆BQP.

Here ZQP has the bounded-failure, no-wrong-definite-answer convention of ZQP on promise problems with bounded failure, and BQP uses the exact 2/3,1/3 thresholds of BQP for promise problems in the fixed QC14 model.

Facts & Assumptions

Given: A binary-string promise pair and the class definitions and suppliers below. Prove each containment for the stated QC14 gate alphabet and full-list uniformity.

[F1]

Promise problem: PromiseP has one deterministic polynomial-time machine correct on Y and N, with no condition off the promise.

[F2]

Polynomial-time computations have logspace-uniform circuit families: every fixed deterministic polynomial-time machine has a polynomial-size logspace-uniform Boolean circuit family computing its answer.

[F3]

Indexed uniform circuits convert to polynomial-time full lists: a logspace indexed Boolean family can be emitted as a complete self-delimiting list by a deterministic polynomial-time generator.

[F4]

Boolean circuits compile exactly into the QC14 gate alphabet: each such Boolean circuit has an exact QC14 reversible embedding, with a polynomial-time full-list compiler.

[F5]

EQP on promise problems in the QC14 model: EQP requires acceptance probability one on YES and zero on NO for a full-list QC14 family.

[F6]

ZQP on promise problems with bounded failure: ZQP has a polynomial-time label decoder, no wrong definite answer, and correct definite answer probability at least 2/3 on each promised side.

[F7]

BQP for promise problems in the fixed QC14 model: BQP requires acceptance probability at least 2/3 on YES and at most 1/3 on NO, with the same full-list QC14 model.

[F8]

The partial-output acceptance law is a finite probability law: the finite output strings of the witnessed computation have a normalized probability law.

Proof

1.1givenF1F2F3F4F5construct

Let Π=(Y,N)∈PromiseP and choose its deterministic polynomial-time decider M from [F1]. The Boolean circuit family of [F2] computes M; [F3] gives a polynomial-time full-list generator, and [F4] compiles each list into a QC14 family whose one-bit target is 1 exactly when M accepts. The two polynomial-time stages compose to one fixed deterministic multitape generator G on input 1n: it emits the Boolean list and compiles that list to the complete QC14 description. Its intermediate list length and total running time are polynomial in n. Convert G to one tape by storing the finitely many simulated tape contents in aligned tracks of a finite product alphabet, with one head marker per tape. During a computation of at most P(n) steps, each track uses at most n+P(n)+O(1) cells; a constant number of sweeps across this interval simulates each transition, so the one-tape time is O(P(n)(n+P(n))). Write the generated circuit description on an output track starting at cell 0; at halt, a cleanup sweep replaces each product symbol by its output-track component, leaving the exact binary description followed by blanks on the final tape. This is one fixed deterministic one-tape polynomial-time generator as required by [F5]. Use the target bit as the acceptance predicate. For every x∈Y the acceptance probability is 1, and for every x∈N it is 0, so Π∈EQP.

1.2F5F6construct

If Π∈EQP, take its witnessing family and define Dn(x,z)=YES when its acceptance predicate accepts and Dn(x,z)=NO otherwise. This is a total polynomial-time decoder. The exact probabilities in [F5] make the wrong definite label have probability zero and the correct definite label have probability one on each promised side; therefore the same family witnesses Π∈ZQP.

2.1givenF6F7F8step 1.2algebra∎

If Π∈ZQP, keep its full-list family and define the BQP acceptance predicate to accept exactly when Dn(x,z)=YES. On Y this event has probability at least 2/3. On N it has probability zero, since a wrong definite YES label is forbidden. By [F8] these event probabilities are normalized, and [F7] gives Π∈BQP.

Depends on

Used by

Nothing in the library uses this result yet.

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