TheoremStatement: AI-adaptedProof: 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.

Deutsch algorithm is exact

Statement

For either promised one-bit function $f$ , the final measurement of One-query Deutsch algorithm outputs $0$ with probability one when $f$ is constant and $1$ with probability one when $f$ is balanced. In the algorithm's declared exact $X, H$ gate model, it uses exactly one oracle query and one $X$ and three $H$ gates, totaling four one-qubit gates. The terminal measurement is a separate resource.

Facts & Assumptions

Given: A total Boolean function on one address bit satisfying the Deutsch promise.

[F1]

One-query Deutsch algorithm: the circuit prepares $∣ + ⟩_{A} ∣ - ⟩_{T}$ , invokes $U_{f}$ once, then applies $H$ to $A$ and measures $A$ .

[F2]

Deutsch constant-versus-balanced promise: constant means $f (0) = f (1)$ and balanced means $f (0) \neq f (1)$ .

[F3]

One standard query implements one phase query: with a one-bit target $∣ - ⟩$ , the XOR query applies phase $(- 1)^{f (x)}$ to each address basis state and leaves the target unchanged.

[F4]

Exact one-qubit gates and rotations: $H ∣ 0 ⟩ = (∣ 0 ⟩ + ∣ 1 ⟩) / \sqrt{2}$ and $H ∣ 1 ⟩ = (∣ 0 ⟩ - ∣ 1 ⟩) / \sqrt{2}$ .

[F5]

Normalized output law for finite quantum query branches: at the terminal measured leaf, output weights are the sums of the diagonal state weights over unmeasured basis strings and form a normalized finite probability law.

[F6]

A unit-vector outer product is a density operator: if $u$ is a unit vector, $∣ u ⟩ ⟨ u ∣$ is a density operator, with root pairing linear in the first argument.

[F7]

Ordered tensor registers, their inner product, and wire permutations: the product basis retains the address-then-target order and its inner product is the product of factor inner products.

[F8]

Nonoracle quantum gate cost: each declared nonoracle gate occurrence, including preparation, is counted once; oracle calls and terminal measurement are separate resources under the algorithm's gate model.

Proof

1.1givenF1F3F4algebra

By [F1], the address is initially $∣ + ⟩ = 2^{- 1 / 2} \sum_{x \in {0, 1}} ∣ x ⟩$ and the target is $∣ - ⟩$ . By [F3], after the query and final address Hadamard, the output amplitude at $y \in {0, 1}$ is $α_{y} = \frac{1}{2} \sum_{x \in {0, 1}} (- 1)^{f (x) + x y} .$ The target remains the same unit vector [F3].

2.1givenF2step 1.1algebra

For $y = 0$ , $α_{0} = ((- 1)^{f (0)} + (- 1)^{f (1)}) / 2$ ; for $y = 1$ , $α_{1} = ((- 1)^{f (0)} - (- 1)^{f (1)}) / 2$ . If $f (0) = f (1)$ , these are respectively $\pm 1$ and $0$ ; if they differ, they are $0$ and $\pm 1$ , by [F2].

3.1F3F5F6F7step 2.1algebra

In each case the address amplitudes have squared moduli $1$ at the correct output and $0$ at the other. Since the terminal state is the product of that address vector and the unit target $∣ - ⟩$ , [F5] and [F7] sum the target's two squared coordinate moduli to one and give exactly the same address output law. Thus the measured output is correct with probability one.

4.1F1F8algebra∎

The procedure [F1] contains one oracle invocation. Its target preparation has one $X$ and one $H$ , and its address has $1$ Hadamard gates before and $1$ after the query. Thus [F8] gives exactly one query and one $X$ and three $H$ gates, totaling four one-qubit gates; the terminal measurement is counted separately.

Depends on

Used by

Deutsch, Deutsch–Jozsa and Bernstein–Vazirani examples Example

Dependency tree · two levels

66 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 (2026-08-27) (standard reference, not scraped)
John Preskill, Quantum Information, Chapter 6: Quantum Algorithms (updated November 2020) (standard reference, not scraped)