DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-generated

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.

Coherent XOR function oracle

Definition

Let $n, m \geq 0$ and let $f : {0, 1}^{n} \to {0, 1}^{m}$ be a total Boolean function on ordered bit strings. Its coherent XOR oracle is the linear extension of

O_{f} ∣ x, y ⟩ = ∣ x, y \oplus f (x) ⟩

on the ordered input and target computational basis, where XOR is componentwise. The declared access contract states how many invocations count as queries and whether a controlled invocation is supplied. A query to this declared black box is counted separately from elementary gate size, depth, and width.

If $f$ is supplied instead by an explicit Boolean circuit, implementing $O_{f}$ means compiling that circuit and paying its reversible elementary-gate and workspace costs; the function description alone is not a free query. For this XOR oracle, its inverse is the same map, as proved in A total Boolean XOR oracle is unitary and involutive ↗. Controlled access remains a separate capability unless the contract explicitly provides it.

Depends on

Used by

Complete-graph continuous-time search Algorithm
Costed coherent evaluation of cyclic group powers Algorithm
One finite abelian hidden-subgroup Fourier sample Algorithm
One-query Bernstein–Vazirani algorithm Algorithm
One-query Deutsch algorithm Algorithm
One-query Deutsch–Jozsa algorithm Algorithm
Power-of-two dihedral hidden-subgroup sieve Algorithm
Reversible modular multiplication by a unit Algorithm
Simon promise decision by sampled rank Algorithm
Szegedy-walk marked-set detection Algorithm
One oracle query can require many ordinary gates Counterexample
Childs–Kothari–Somma sparse QLSP oracle model Definition
Element-distinctness Johnson walk and value access Definition
Finite abelian hidden-shift promise Definition
Finite abelian hidden-subgroup promise and output encoding Definition
Finite cyclic discrete-logarithm problem and costed encoding Definition
Promise query instance and oracle family Definition
Quantum convex membership and weak-separation model Definition
Quantum query algorithm Definition
Simon injectivity decision promise with XOR-oracle access Definition
Sparse Hamiltonian row and value oracles Definition
Sparse SDP matrix access and computational model Definition
Standard bit-flip query convention Definition
Clean sparse-state preparation from sorted XOR locations Lemma
Coherent Johnson row access with stored values Lemma
Discarding the hiding register yields a coset-state mixture Lemma
Fourier sample from a generalized-dihedral reflection coset state Lemma
A total Boolean XOR oracle is unitary and involutive Theorem
Bounded-error parity query lower bound Theorem
Correctness of the reversible modular multiplier Theorem
Element-distinctness gate cost in the QRAM model Theorem
Finite abelian hidden-subgroup query and circuit costs Theorem
Hidden shift as generalized-dihedral hidden subgroup Theorem
Kuperberg dihedral hidden-subgroup scope and resource claim Theorem
Oracle phase queries and compiled gate costs are distinct Theorem
Phase kickback from an XOR oracle Theorem
Sparse Hamiltonian no-fast-forwarding Theorem

Dependency tree · two levels

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