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,
Here has the bounded-failure, no-wrong-definite-answer convention of ZQP on promise problems with bounded failure, and uses the exact 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.
Promise problem: PromiseP has one deterministic polynomial-time machine correct on and , with no condition off the promise.
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.
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.
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.
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.
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 on each promised side.
BQP for promise problems in the fixed QC14 model: BQP requires acceptance probability at least on YES and at most on NO, with the same full-list QC14 model.
The partial-output acceptance law is a finite probability law: the finite output strings of the witnessed computation have a normalized probability law.
Proof
Let and choose its deterministic polynomial-time decider from [F1]. The Boolean circuit family of [F2] computes ; [F3] gives a polynomial-time full-list generator, and [F4] compiles each list into a QC14 family whose one-bit target is exactly when accepts. The two polynomial-time stages compose to one fixed deterministic multitape generator on input : 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 . Convert 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 steps, each track uses at most cells; a constant number of sweeps across this interval simulates each transition, so the one-tape time is . Write the generated circuit description on an output track starting at cell ; 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 the acceptance probability is , and for every it is , so .
If , take its witnessing family and define when its acceptance predicate accepts and 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 .
If , keep its full-list family and define the BQP acceptance predicate to accept exactly when . On this event has probability at least . On it has probability zero, since a wrong definite YES label is forbidden. By [F8] these event probabilities are normalized, and [F7] gives .
Depends on
- Promise problem
- EQP on promise problems in the QC14 model
- ZQP on promise problems with bounded failure
- BQP for promise problems in the fixed QC14 model
- The partial-output acceptance law is a finite probability law
- Polynomial-time computations have logspace-uniform circuit families
- Indexed uniform circuits convert to polynomial-time full lists
- Boolean circuits compile exactly into the QC14 gate alphabet
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
- Ronald de Wolf, Quantum Computing: Lecture Notes, Chapter 13, Section 13.2 (standard reference, not scraped)
- John Watrous, Quantum Computational Complexity, Sections IV.1–IV.3 (standard reference, not scraped)