Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass
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 f:{0,1}a→{0,1} be total. Starting a target qubit in ∣0⟩, apply X and then H, and make one standard bit query. Since HX∣0⟩=∣−⟩, phase kickback implements Pf 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.

[F1]

Standard bit-flip query convention: one query applies ∣x⟩∣y⟩↦∣x⟩∣y⊕f(x)⟩.

[F2]

Binary phase-query convention: Pf∣x⟩=(−1)f(x)∣x⟩.

[F3]

Phase kickback from the standard bit query: a target in ∣−⟩ converts one standard query to the phase query and returns unchanged.

[F4]

Exact one-qubit gates and rotations: X∣0⟩=∣1⟩ and H∣1⟩=(∣0⟩−∣1⟩)/2.

[F5]

Finite circuit resource accounting: the declared gate count counts each X and H occurrence once, separately from black-box calls.

[F6]

Nonoracle quantum gate cost: query calls and gates outside those calls are separate resource coordinates, and the latter count preparation gates.

[A1]

For the explicit preparation from ∣0⟩ and its two-gate count, the selected nonoracle operation model has a finite gate alphabet containing and permitting X and H 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 ∣0⟩ and its gate count.

Proof

1.1givenF4A1algebra

From [F4], after the first gate the target is X∣0⟩=∣1⟩, and after the second it is H∣1⟩=∣−⟩. The chronological order is therefore HX∣0⟩, not XH∣0⟩.

2.1step 1.1F1F2F3

Apply the standard query once. The phase-kickback theorem [F3], using the query action [F1] and the target established in step 1.1, gives Pf on the address and returns the target to ∣−⟩. By [F2] this address action is exactly the defined phase query.

3.1step 1.1F1F5F6A1∎

The preparation has one X and one H, 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

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