DefinitionDefinition: Literature-sourcedProof: AI-generatedPipeline-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.

Bernstein–Vazirani no-offset promise

Definition

Let $n \geq 1$ . The Bernstein–Vazirani no-offset promise consists of the total functions

f_{a} : {0, 1}^{n} \to {0, 1}, f_{a} (x) : = a \cdot x,

for an unknown secret $a \in {0, 1}^{n}$ , using Binary dot product as parity. The task is to output $a$ . This version has no additive offset: the oracle is exactly $f_{a}$ , not $x \mapsto a \cdot x \oplus b$ .

Facts & Assumptions

Given: $n \geq 1$ and a secret $a \in {0, 1}^{n}$ .

[F1]

QA task and promise domain: a search task requires a witness in the declared relation on each promised input.

[F2]

Promise query instance and oracle family: a query function is total on every address string in its domain.

[F3]

Binary dot product as parity: $a \cdot x = ⨁_{i < n} (a_{i} \land x_{i})$ .

Verification

1.1givenF2F3algebra

For every $x \in {0, 1}^{n}$ , [F3] is a finite XOR of bits, hence defines one bit; therefore $f_{a}$ is a total Boolean function and satisfies the query-instance requirement [F2].

2.1givenF1F3step 1.1constructalgebra∎

For each coordinate $i < n$ , let $e_{i}$ be the string with a single $1$ at position $i$ . Then $f_{a} (e_{i}) = a_{i}$ by [F3]. If $f_{a} = f_{b}$ , evaluation at every $e_{i}$ gives $a_{i} = b_{i}$ , so $a = b$ . Thus the secret is uniquely determined by the function table.

Depends on

Used by

Dependency tree · two levels

16 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, arXiv:1907.09415v6 (2026-08-27) (standard reference, not scraped)
John Preskill, Quantum Information, Chapter 6: Quantum Algorithms (updated November 2020) (standard reference, not scraped)