Pipeline-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.

✓ 1 result · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Reversible Arithmetic and Oracle Conversion — Examples

1 · Prerequisites

2 · Summary

The companion computes a one-bit phase query and a two-bit reversible dot product explicitly. It compares clean uncomputation with a circuit that leaves address-dependent garbage, then checks how a constant phase changes when its call is controlled. Each example includes the resulting basis-state calculation and its measurement consequence.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

Oracle conversion and uncomputation examples

Example

For the one-bit function $f (x) = x$ , compute the standard XOR query with a clean work bit, copy its value to the target, and uncompute the work. On input address $∣ + ⟩$ , target $∣ - ⟩$ , and work $∣ 0 ⟩$ , the address becomes $∣ - ⟩$ and the work returns to zero; a final Hadamard on the address yields outcome $1$ with certainty. For the two-bit dot product, take $a = 11$ , $x = 10$ , and target $z = 0$ . The reversible Toffoli circuit outputs target $1$ and resets its work bit. If the one-bit circuit omits its final uncomputation, residual address-dependent work makes the same final address measurement uniform instead of deterministic. Finally, a constant-one phase query has no standalone measurement effect, but its controlled call changes a control $∣ + ⟩$ to $∣ - ⟩$ .

Facts & Assumptions

Given: The explicit one-bit and two-bit inputs above and the stated ordered registers. The operation model's declared finite nonoracle gate alphabet contains and permits CNOT, Toffoli and $H$ as callable gates, with each occurrence counted once; any explicitly supplied standard or controlled phase-oracle call is charged separately from those gate occurrences.

[F1]

Standard bit-flip query convention: the standard query is the basis action $∣ x ⟩ ∣ y ⟩ \mapsto ∣ x ⟩ ∣ y \oplus f (x) ⟩$ .

[F2]

Binary phase-query convention: a Boolean phase query acts by $P_{f} ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ .

[F3]

Phase kickback from the standard bit query: a standard query with target $∣ - ⟩$ applies $P_{f}$ to the address and returns the target unchanged.

[F4]

Binary dot product as parity: $a \cdot x$ is the XOR of coordinatewise conjunctions.

[F5]

Reversible binary dot-product query: the reversible circuit accumulates the products into a clean work bit, copies the parity to the target, and reverses the Toffolis.

[F6]

Reversible binary dot product: correctness and exact cost: the circuit realizes that map with $2 n$ Toffoli gates, one CNOT, and clean work.

[F7]

Clean and dirty ancillas: clean work begins at zero and must return exactly to zero; an uncomputed work register is not clean.

[F8]

Toffoli and Fredkin gates: Toffoli toggles its target by the conjunction of its two controls.

[F9]

CNOT and Control-Target Order: CNOT toggles its target by its control and leaves the control unchanged.

[F10]

Exact one-qubit gates and rotations: $H = 2^{- 1 / 2} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ in the ordered basis $∣ 0 ⟩, ∣ 1 ⟩$ .

[F11]

Finite registers and their ordered computational bases: the displayed wire order specifies the tensor-factor order and computational-basis labels.

[F12]

A constant phase query is invisible alone and relative under control: constant phase is unobservable standalone and, under explicit controlled access, is a relative phase with a distinguishing control measurement.

[F13]

Finite circuit resource accounting: elementary gate occurrences and explicitly supplied oracle calls are separate resource coordinates.

Verification

1.1givenF1F7F9F11algebra

Let the one-bit address be $x$ and the target be $y$ . The first CNOT from $x$ to clean work $r$ maps $∣ x ⟩ ∣ 0 ⟩_{r}$ to $∣ x ⟩ ∣ x ⟩_{r}$ by [F9]. Copying $r$ to $y$ changes $y$ to $y \oplus x$ . The final CNOT from $x$ to $r$ restores $r$ to $x \oplus x = 0$ and leaves $x, y \oplus x$ unchanged. Thus the three-CNOT circuit is exactly the standard query for $f (x) = x$ with clean work.

1.2givenF4F5F6F8F9algebra

For $a = 11$ and $x = 10$ , the two coordinate products are $1 \land 1 = 1$ and $1 \land 0 = 0$ , so $a \cdot x = 1 \oplus 0 = 1$ by [F4]. In the forward Toffoli loop of [F5], the first gate changes $r : 0 \to 1$ and the second leaves it at $1$ ; CNOT changes $z : 0 \to 1$ . In reverse, the second Toffoli leaves $r$ unchanged and the first changes $r : 1 \to 0$ by [F8]. Thus the output is $∣ 11 ⟩ ∣ 10 ⟩ ∣ 1 ⟩ ∣ 0 ⟩_{r}$ , consistent with [F6].

2.1step 1.1F3F7F10algebra

Starting with address $∣ + ⟩$ , target $∣ - ⟩$ , and clean work $∣ 0 ⟩_{r}$ , step 1.1 applies the standard query. By [F3] the output is $∣ - ⟩_{x} ∣ - ⟩_{y} ∣ 0 ⟩_{r}$ . Multiplying the matrix in [F10] gives $H ∣ 0 ⟩ = ∣ + ⟩$ and $H ∣ 1 ⟩ = ∣ - ⟩$ , hence $H ∣ - ⟩ = ∣ 1 ⟩$ . The final address measurement therefore returns $1$ with probability one.

2.2step 1.1F7F9F10F11algebra

Omit only the final CNOT from $x$ to $r$ in step 1.1. After compute and copy, the input $∣ + ⟩_{x} ∣ - ⟩_{y} ∣ 0 ⟩_{r}$ becomes, in the same register order $x, y, r$ ,

\frac{∣ 0 ⟩_{x} ∣ - ⟩_{y} ∣ 0 ⟩_{r} - ∣ 1 ⟩_{x} ∣ - ⟩_{y} ∣ 1 ⟩_{r}}{\sqrt{2}} .

Applying $H$ to the address gives

\frac{∣ 0 ⟩_{x} ∣ - ⟩_{y} ∣ - ⟩_{r} + ∣ 1 ⟩_{x} ∣ - ⟩_{y} ∣ + ⟩_{r}}{\sqrt{2}} .

Because $∣ + ⟩_{r}$ and $∣ - ⟩_{r}$ are orthogonal unit vectors, address outcomes $0$ and $1$ each have probability $1 / 2$ . The residual work value is correlated with the address, violating the clean-ancilla contract [F7] and destroying the intended deterministic interference.

3.1givenF2F10F12F13algebra∎

For the constant function $f (x) = 1$ , [F2] gives $P_{f} = - I$ , a standalone global scalar; [F12] therefore gives no standalone measurement distinction from $I$ . Under the explicit controlled call, the control output is $∣ + ⟩$ for the identity case and $∣ - ⟩$ for the constant-one case by [F12]. Matrix multiplication using [F10] gives $H ∣ + ⟩ = ∣ 0 ⟩$ and $H ∣ - ⟩ = ∣ 1 ⟩$ , so a computational-basis measurement distinguishes them with certainty.