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.

A total Boolean XOR oracle is unitary and involutive

Statement

For every total Boolean function $f : {0, 1}^{n} \to {0, 1}^{m}$ , including noninjective functions, the coherent XOR oracle $O_{f} ∣ x, y ⟩ = ∣ x, y \oplus f (x) ⟩$ is unitary and satisfies $O_{f}^{2} = I$ . Hence $O_{f}^{- 1} = O_{f}$ .

Facts & Assumptions

Given: The basis action in Coherent XOR function oracle on the finite ordered computational basis. Prove involutivity and unitarity without assuming $f$ injective.

[F1]

Coherent XOR function oracle: $O_{f} ∣ x, y ⟩ = ∣ x, y \oplus f (x) ⟩$ for every ordered input and target string.

[F2]

Big-endian encoding of ordered bit strings: The big-endian index is ${enc}_{n} (x) = \sum_{k < n} x_{k} 2^{n - 1 - k}$ , and the word $x$ occupies the basis slot numbered by that index.

[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; for $n = 0$ it is $C$ with basis ${1}$ .

[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$ , ${enc}_{n}$ is a bijection from ${0, 1}^{n}$ to ${0, \dots, 2^{n} - 1}$ .

[F6]

The product basis is orthonormal and tensor dimensions multiply: The lexicographically ordered elementary tensors of the factor bases form an orthonormal basis of the tensor register.

Proof

1.1givenF1algebra

Apply $O_{f}$ twice to a basis vector. The first application gives $∣ x, y \oplus f (x) ⟩$ ; the second gives $∣ x, (y \oplus f (x)) \oplus f (x) ⟩ = ∣ x, y ⟩$ because every bit added modulo two twice is zero. The input $x$ is preserved throughout, so injectivity of $f$ is not needed.

2.1F1F2F3F4F5F6step 1.1algebra∎

By [F2]–[F6], the input and target strings label the entire finite orthonormal product basis in the declared order. Step 1.1 shows that the oracle map is a permutation of this basis, so its matrix has orthonormal columns and satisfies $O_{f}^{†} O_{f} = I$ . Therefore it is unitary, and Step 1.1 gives its inverse as itself.

Depends on

Used by

Reversible modular multiplication by a unit Algorithm
Simon promise decision by sampled rank Algorithm
Promise query instance and oracle family Definition
Quantum query algorithm Definition
Simon injectivity decision promise with XOR-oracle access Definition
Standard bit-flip query convention Definition
Bounded-error parity query lower bound Theorem
Correctness of the reversible modular multiplier Theorem
Oracle phase queries and compiled gate costs are distinct Theorem
Phase kickback from an XOR oracle Theorem
Promise-preserving reduction composes with a query solver Theorem
Sparse Hamiltonian no-fast-forwarding Theorem

Cited to discharge well-definedness by Coherent XOR function oracle.

Dependency tree · two levels

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