ExampleConstruction: AI-generatedVerification: AI-adaptedPipeline-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.

A one-query exact algorithm on a two-point OR promise

Example

For $N = 2$ , let $D = {00, 11}$ and let $f = {O R}_{2} ∣_{D}$ , so $f (00) = 0$ and $f (11) = 1$ . There is a one-query local bit-query algorithm with acceptance probability $p (x_{0}, x_{1}) = \frac{x_{0} + x_{1}}{2} .$

Facts & Assumptions

Given: The two-bit local query model, one-hot addresses $e_{0} = 10, e_{1} = 01$ , and the two-point promise $D$ .

[F1]

Oracle-only bit-query algorithm: the root state is all zero, fixed unitaries may prepare a superposition of addresses, one XOR query acts on that address register, and acceptance is a fixed subset of terminal outputs, with probabilities given by the finite output law summing over unmeasured basis labels.

[F2]

Standard bit-flip query convention: a query at address $e_{i}$ toggles the target by $x_{i}$ .

[F3]

Clifford+T gate library and exact matrices: $H = \frac{1}{\sqrt{2}} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ and CNOT maps $∣ a, b ⟩$ to $∣ a, b \oplus a ⟩$ .

[F4]

The Pauli matrices: $X = (\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array})$ in the ordered basis $(∣ 0 ⟩, ∣ 1 ⟩)$ .

[F5]

Acceptance polynomials and approximate degree on Boolean domains: exact approximate degree on $D$ is the least total degree of a real polynomial agreeing with $f$ at every point in $D$ .

[F6]

Local bounded-error bit-query complexity: $Q_{0}^{b i t} (f; D)$ is the minimum worst-branch number of oracle queries among algorithms exact on $D$ .

[F7]

Polynomial rings in finitely many commuting indeterminates by iteration and Monomials, coefficients, degree in each variable and total degree in $F [x_{1}, \dots, x_{n}]$ : coordinate variables and their finite real linear combinations are multivariate polynomials, with the displayed linear polynomial having degree one.

Verification

1.1givenF1F3F4construct

The matrices in [F3] and [F4] satisfy $H^{*} H = I$ and $X^{*} X = I$ by direct multiplication; the CNOT action in [F3] permutes the four computational-basis vectors, so it is unitary. Starting at $∣ 00, 0 ⟩$ , apply $X$ to the second address bit, then $H$ to the first and CNOT from the first to the second. The basis actions in [F3]–[F4] give $\frac{1}{\sqrt{2}} (∣ 01, 0 ⟩ + ∣ 10, 0 ⟩) = \frac{1}{\sqrt{2}} (∣ e_{1}, 0 ⟩ + ∣ e_{0}, 0 ⟩)$ . These are fixed input-independent unitaries permitted by [F1].

2.1step 1.1F1F2algebra

One oracle call and [F2] transform this to $\frac{1}{\sqrt{2}} (∣ e_{1}, x_{1} ⟩ + ∣ e_{0}, x_{0} ⟩)$ . Measuring the target and accepting exactly when it is $1$ has probability $\frac{1}{2} ∣ x_{1} ∣^{2} + \frac{1}{2} ∣ x_{0} ∣^{2} = (x_{0} + x_{1}) / 2$ , because the orthogonal address basis states have no cross terms and each $x_{i}$ is a bit. This gives the stated acceptance polynomial.

3.1givenstep 2.1F5F6F7algebra∎

On $00$ the acceptance probability is $0 = f (00)$ , and on $11$ it is $1 = f (11)$ , so the algorithm is exact on $D$ with one query. The polynomial $p$ has total degree one by [F7]. No constant polynomial can be exact on $D$ because a constant has the same value at $00$ and $11$ , while $f$ differs there. Thus ${\overset{}{\deg}}_{0} (f; D) = 1$ by [F5], and the one-query construction verifies $Q_{0}^{b i t} (f; D) \leq 1$ by [F6].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

35 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

Andrew M. Childs, Lecture Notes on Quantum Algorithms (2025), §21.3 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (arXiv:1907.09415), §11.2 (standard reference, not scraped)