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.
A BQP promise pair with unrestricted off-promise inputs
Example
Let and as subsets of . They are disjoint, and every other binary word is off the promise. For each , let be the gate-free identity circuit with the first input wire as its one-bit output. For , let have one zero-initialized auxiliary wire as output. Use one total predicate that accepts exactly when is the one-bit word and the measured output is .
Facts & Assumptions
Given: The promise pair and the BQP thresholds in BQP for promise problems in the fixed QC14 model.
BQP for promise problems in the fixed QC14 model: only YES inputs require acceptance at least and NO inputs require acceptance at most ; off-promise inputs have no constraint.
Promise problem: a promise problem is a pair of disjoint subsets of , and either answer is allowed outside their union.
Full-list uniform quantum circuit family: a family description records input and total wire counts, a finite gate list, and an ordered output tuple; the full-list generator receives unary input .
Verification
The pair is a promise problem because and are disjoint singletons of distinct one-bit words, as required by [F2]. For , use input count , total wire count , gate count zero, and output tuple . For , use input count zero, total wire count one, gate count zero, and output tuple , whose wire is initialized to zero. These are valid descriptions under [F3]. One fixed one-tape generator writes the two unary counts by repeated sweeps over the input marks and then appends the constant gate-count and output fields; at most transitions suffice. The total predicate is exactly when is the one-bit word and , and otherwise, so it is deterministic and polynomial time.
On the YES input , the identity circuit leaves the measured output in , so acceptance is . On the NO input , it leaves the measured output in , so acceptance is . Every other string is outside , where [F1] imposes no condition. Hence this promise problem is in BQP in the stated model.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
13 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
- John Watrous, Quantum Computational Complexity, Sections II.2 and IV.1 (standard reference, not scraped)
- Ronald de Wolf, Quantum Computing: Lecture Notes, Chapter 13, Section 13.2 (standard reference, not scraped)