DefinitionDefinition: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass

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.

Deutsch constant-versus-balanced promise

Definition

Let $f : {0, 1} \to {0, 1}$ be the total Boolean function of a Promise query instance and oracle family. Encode $f$ by its hidden length-two truth table $z = f (0) f (1) \in {0, 1}^{2}$ , whose associated oracle function is $f_{z} = f$ . The Deutsch promise is the decision task with YES set $Y = {00, 11}$ and NO set $N = {01, 10}$ . The required output is $0$ on $Y$ (constant, $f (0) = f (1)$ ) and $1$ on $N$ (balanced, $f (0) \neq f (1)$ ). All four Boolean functions on one bit are promised. The truth table labels the hidden instance; the query interface supplies oracle access to $f$ .

Facts & Assumptions

Given: A total function $f : {0, 1} \to {0, 1}$ .

[F1]

QA task and promise domain: a decision task consists of disjoint YES and NO subsets of the encoded inputs; no answer is required outside their union.

[F2]

Promise query instance and oracle family: each promised instance supplies a total function on its entire address domain.

Verification

1.1givenF1F2algebra

Writing the two function values in order gives exactly the four strings $00, 01, 10, 11$ . By the Definition, $00$ and $11$ are in $Y$ , while $01$ and $10$ are in $N$ . These two sets are disjoint and cover all four possible tables, so the promised output is well-defined.

2.1givenF2step 1.1algebra∎

The totality in [F2] makes both evaluations $f (0)$ and $f (1)$ available. Equality gives the constant case and inequality gives the balanced case by the two disjoint rows of the table in step 1.1.

Depends on

Used by

One-query Deutsch algorithm Algorithm
Deutsch, Deutsch–Jozsa and Bernstein–Vazirani examples Example
Deutsch algorithm is exact Theorem
One classical query cannot solve Deutsch exactly Theorem

Dependency tree · two levels

12 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)