Pipeline-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.

Uniform Circuit Families, Promise Problems, and Complexity — Examples

1 · Prerequisites

2 · Summary

The worked promise pair makes the off-domain convention concrete: a circuit family must satisfy the two acceptance bounds on the declared YES and NO sets, while inputs outside their union carry no acceptance requirement.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

A BQP promise pair with unrestricted off-promise inputs

Example

Let $Y = {0}$ and $N = {1}$ as subsets of ${0, 1}^{*}$ . They are disjoint, and every other binary word is off the promise. For each $n \geq 1$ , let $C_{n}$ be the gate-free identity circuit with the first input wire as its one-bit output. For $n = 0$ , let $C_{0}$ have one zero-initialized auxiliary wire as output. Use one total predicate that accepts exactly when $x$ is the one-bit word $0$ and the measured output is $0$ .

Facts & Assumptions

Given: The promise pair and the BQP thresholds in BQP for promise problems in the fixed QC14 model.

[F1]

BQP for promise problems in the fixed QC14 model: only YES inputs require acceptance at least $2 / 3$ and NO inputs require acceptance at most $1 / 3$ ; off-promise inputs have no constraint.

[F2]

Promise problem: a promise problem is a pair of disjoint subsets of ${0, 1}^{*}$ , and either answer is allowed outside their union.

[F3]

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 $1^{n}$ .

Verification

1.1givenF2F3construct

The pair is a promise problem because $Y$ and $N$ are disjoint singletons of distinct one-bit words, as required by [F2]. For $n \geq 1$ , use input count $n$ , total wire count $m = n$ , gate count zero, and output tuple $(0)$ . For $n = 0$ , use input count zero, total wire count one, gate count zero, and output tuple $(0)$ , 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 $n$ input marks and then appends the constant gate-count and output fields; at most $O ((n + 1)^{2})$ transitions suffice. The total predicate is $1$ exactly when $x$ is the one-bit word $0$ and $z = 0$ , and $0$ otherwise, so it is deterministic and polynomial time.

2.1step 1.1F1algebra∎

On the YES input $x = 0$ , the identity circuit leaves the measured output in $∣ 0 ⟩$ , so acceptance is $1 \geq 2 / 3$ . On the NO input $x = 1$ , it leaves the measured output in $∣ 1 ⟩$ , so acceptance is $0 \leq 1 / 3$ . Every other string is outside $Y \cup N$ , where [F1] imposes no condition. Hence this promise problem is in BQP in the stated model.