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.
The controlled input-consistency circuit realizes the exact reflection
Statement
Assume the distinguished vector in the input decomposition is unit, as required by Controlled input-consistency reflection from a bit query. For every promised input x, that circuit realizes the control-first block operator where projects onto the start vector and all query states whose response equals x_i. The controlled operation uses the plus-on-range sign, including on the distinguished start state.
The displayed consistency sum is an orthogonal projection. For arbitrary control/data superpositions, the supplied circuit restores its scratch qubit to zero, including the start mode protected by a scratch during both unconditional calls; no controlled unknown-oracle call is required.
Facts & Assumptions
Given: The finite controlled consistency-reflection circuit and its projection Π_x.
Finite Boolean query problem and error model for adversary bounds: each promised input x supplies the bit x_i at each address i.
Standard bit-flip query convention: the XOR oracle toggles a response bit by x_i and is an involution.
Clean and dirty ancillas: a clean scratch qubit is initialized to |0⟩ and must be returned to |0⟩.
Projector Reflections Are Hermitian Unitary Involutions: R_Π=2Π-I is the unitary reflection acting +1 on ran Π and −1 on ker Π.
Finite registers and their ordered computational bases: the d-level register is C^d with its standard coordinate pairing and ordered standard basis. The mode/address/response/work decomposition is supplied by the input of Controlled input-consistency reflection from a bit query.
Proof
Let H=span{|start⟩}⊕(C^N⊗K⊗C²). The algorithm input requires |start⟩ to be unit and orthogonal to every query mode; hence |start⟩⟨start| is the orthogonal projection onto its span. It also labels the standard address basis by |i⟩=e_{i−1}, i∈[N]. Under the standard coordinate pairing in [F25], ⟨e_j,e_k⟩=Σ_rδ_{rj}δ_{rk}=δ_{jk}, so these address vectors and the response basis vectors are orthonormal. Therefore the query summands |i⟩⟨i|⊗I_K⊗|x_i⟩⟨x_i| are mutually orthogonal projections and are orthogonal to the start projection. Thus Π_x is an orthogonal projection.
Append a clean scratch bit u=0. In query mode, call O_x at address i to write u=x_i. In start mode route the oracle address to a fixed i_0∈[N] and apply H to u so the target is |+⟩; since X^{x_{i_0}}|+⟩=|+⟩, the unconditional oracle call leaves start unchanged. Apply a fixed phase −1 exactly when c=1, the mode is a query state, and z≠u; apply +1 on the start mode and when c=0. On query basis states this phase is +1 exactly when z=x_i, and −1 otherwise.
Call O_x again at the same address to reset u to 0 in query mode, using O_x²=I from [F22]. In start mode the second call again fixes |+⟩, and the final controlled H returns u to |0⟩. For c=1 the induced operator on H is 2Π_x-I; for c=0 it is I. Thus this fixed circuit realizes controlled R_{Π_x} with the plus-on-range sign specified in [F24], without a controlled unknown-oracle call. By linearity the same control/data action holds for arbitrary superpositions with the scratch returned clean.
Depends on
- Controlled input-consistency reflection from a bit query
- Orthogonal-Projector Reflection and Access Contract
- Projector Reflections Are Hermitian Unitary Involutions
- Standard bit-flip query convention
- Query-address projectors for bit-oracle algorithms
- Finite Boolean query problem and error model for adversary bounds
- Clean and dirty ancillas
- Dirac Notation Conversion
- Quantum query algorithm
- Finite registers and their ordered computational bases
Used by
- Bounded-error evaluation from a dual adversary certificate Algorithm
- Controlled consistency reflection uses two bit queries Theorem
- Dual reflection evaluator has bounded-error correctness Theorem
Cited to discharge well-definedness by Controlled input-consistency reflection from a bit query.
Dependency tree · two levels
46 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 (17 April 2025) (standard reference, not scraped)
- Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)