TheoremStatement: 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.

Phase kickback from an XOR oracle

Statement

Let $f : {0, 1}^{n} \to {0, 1}^{m}$ be total, let $s \in {0, 1}^{m}$ , and define the normalized character target

∣ χ_{s} ⟩ = 2^{- m / 2} \sum_{y \in {0, 1}^{m}} (- 1)^{s \cdot y} ∣ y ⟩,

where $s \cdot y$ is the dot product modulo two. Then

O_{f} (∣ x ⟩ ∣ χ_{s} ⟩) = (- 1)^{s \cdot f (x)} ∣ x ⟩ ∣ χ_{s} ⟩ .

For a one-bit output with $s = 1$ , $∣ χ_{s} ⟩ = ∣ - ⟩ = (∣ 0 ⟩ - ∣ 1 ⟩) / \sqrt{2} = H ∣ 1 ⟩$ . Thus the phase action is obtained with one invocation of the declared XOR oracle, with target preparation cost accounted separately.

Facts & Assumptions

Given: The coherent XOR action and ordered bit-string basis. Prove the character-target identity.

[F1]

Coherent XOR function oracle: $O_{f} ∣ x, y ⟩ = ∣ x, y \oplus f (x) ⟩$ .

[F2]

A total Boolean XOR oracle is unitary and involutive: The XOR oracle is a unitary involution for every total Boolean function.

[F3]

Finite registers and their ordered computational bases: The $n$ -qubit register is the ordered tensor product of $n$ copies of $Q_{2}$ , with tuples in lexicographic order and the first wire most significant; the empty register is $C$ .

[F4]

The computational basis is orthonormal: The ordered computational basis of each $Q_{d}$ register is an orthonormal basis for its declared inner product.

[F5]

Big-endian bit-string indices are bijective: For every $n \geq 0$ , the big-endian encoding is a bijection from the length- $n$ bit strings to the $2^{n}$ basis indices.

[F6]

The product basis is orthonormal and tensor dimensions multiply: Ordered product basis vectors form an orthonormal basis of the tensor register.

[F7]

Exact one-qubit gates and rotations: The exact Hadamard matrix is $H : = \frac{X + Z}{\sqrt{2}} = \frac{1}{\sqrt{2}} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ .

Proof

1.1givenF1F3F4F5F6algebra

By [F4]–[F6], the $2^{m}$ target basis vectors are orthonormal and the encoding lists each exactly once; hence $∣ χ_{s} ⟩$ has squared norm $2^{m} 2^{- m} = 1$ . Applying the oracle termwise gives $2^{- m / 2} \sum_{y} (- 1)^{s \cdot y} ∣ x, y \oplus f (x) ⟩$ . Set $z = y \oplus f (x)$ . Then $y = z \oplus f (x)$ and $s \cdot y = s \cdot z \oplus s \cdot f (x)$ , so the sum is $(- 1)^{s \cdot f (x)} ∣ x ⟩ ∣ χ_{s} ⟩$ .

2.1step 1.1F2F3F4F5F6F7algebra∎

By [F3]–[F6], the ordered input basis spans its register, so linearity gives the same phase action on every superposition $\sum_{x} α_{x} ∣ x ⟩$ , with the target factor unchanged. When $m = 1$ and $s = 1$ , multiplying the matrix in [F7] by $∣ 1 ⟩ = (0, 1)^{T}$ gives $H ∣ 1 ⟩ = (∣ 0 ⟩ - ∣ 1 ⟩) / \sqrt{2} = ∣ - ⟩$ . Also $H^{*} H = \frac{1}{2} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}) (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}) = I$ , so this is a unitary target preparation. The unitary character of the oracle is supplied by [F2].

Depends on

Used by

Oracle phase queries and compiled gate costs are distinct Theorem

Dependency tree · two levels

38 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 Preskill, Quantum Computation, Chapter 5: Classical and Quantum Circuits (updated July 2015) (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)