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.
One standard query implements one phase query
Statement
Let be total. Starting a target qubit in , apply and then , and make one standard bit query. Since , phase kickback implements on the address and returns the target to . This conversion uses one query plus exactly two nonoracle one-qubit gates; the target preparation is explicit and assumes no preprepared state or generic amplitude loading.
Facts & Assumptions
Given: The zero-initialized target, the standard bit query, and the exact one-qubit gate matrices in the ordered computational basis.
Standard bit-flip query convention: one query applies .
Phase kickback from the standard bit query: a target in converts one standard query to the phase query and returns unchanged.
Finite circuit resource accounting: the declared gate count counts each and occurrence once, separately from black-box calls.
Nonoracle quantum gate cost: query calls and gates outside those calls are separate resource coordinates, and the latter count preparation gates.
For the explicit preparation from and its two-gate count, the selected nonoracle operation model has a finite gate alphabet containing and permitting and as callable gates, each occurrence is counted once, and the standard query is charged separately as one oracle call.
The phase identity in [F3] for an already prepared target does not require [A1]; [A1] is needed only for the displayed preparation from and its gate count.
Proof
From [F4], after the first gate the target is , and after the second it is . The chronological order is therefore , not .
Apply the standard query once. The phase-kickback theorem [F3], using the query action [F1] and the target established in step 1.1, gives on the address and returns the target to . By [F2] this address action is exactly the defined phase query.
The preparation has one and one , hence two nonoracle gates by [F5]–[F6], and the oracle is invoked once by [F1]. These counts are separate; the construction makes no generic state-preparation call.
Depends on
Used by
- BBHT search when the marked count is unknown Algorithm
- Known-count Grover search by exact integer maximization Algorithm
- One Grover iterate in the standard bit-query model Algorithm
- One-query Bernstein–Vazirani algorithm Algorithm
- One-query Deutsch algorithm Algorithm
- One-query Deutsch–Jozsa algorithm Algorithm
- Finite marked-item search and its bit oracle Definition
- Bernstein–Vazirani algorithm returns the secret exactly Theorem
- Deutsch algorithm is exact Theorem
- Deutsch–Jozsa algorithm is exact Theorem
- Exact success probability after an integer number of Grover iterates Theorem
- One Grover iterate uses one standard bit query Theorem
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
- Ronald de Wolf, Quantum Computing: Lecture Notes (arXiv:1907.09415v6) (standard reference, not scraped)
- Andrew M. Childs, Lecture Notes on Quantum Algorithms (17 April 2025) (standard reference, not scraped)