DefinitionDefinition: AI-adaptedProof: Not applicablePipeline-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.

EQP on promise problems in the QC14 model

Definition

A promise problem $Π = (Y, N)$ belongs to $E Q P$ in the QC14 model if there is a full-list uniform family $(C_{n})_{n \geq 0}$ and a polynomial-time total acceptance predicate $A_{n}$ as in Finite quantum promise-computation model, Full-list uniform quantum circuit family, and Quantum acceptance probability for a finite promise computation, using the exact gate and cost conventions of Circuit-family and computation cost model and Clifford+T gate library and exact matrices, such that

$p_{C_{∣ x ∣}} (x) = 1 (x \in Y), p_{C_{∣ x ∣}} (x) = 0 (x \in N) .$

No condition is imposed on $x \notin Y \cup N$ (Promise problem). The finite output law is normalized by The partial-output acceptance law is a finite probability law.

Depends on

Used by

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

Dependency tree · two levels

38 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, Section IV.1 (standard reference, not scraped)