TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Reversing a circuit implements its inverse

Statement

Let $C$ be a finite measurement-free unitary circuit. Assume that for every gate occurrence its adjoint is a legal gate occurrence on the same ordered wires and that the operation model explicitly grants each inverse call, as required by Inverse Unitary Access. Reverse the chronological layer order and, within each layer, reverse its gate list while replacing each gate by its adjoint. The resulting circuit $C^{- 1}$ has $U_{C^{- 1}} = U_{C}^{†} = U_{C}^{- 1} .$ It has the same number of gate occurrences as $C$ ; inverse calls retain their separately declared access cost.

Facts & Assumptions

Given: A finite layered unitary circuit $C$ and explicit inverse access to every gate occurrence.

[F1]

Denotational semantics of a finite layered circuit: if the chronological layer maps are $U_{L_{1}}, \dots, U_{L_{d}}$ , then $U_{C} = U_{L_{d}} \dots U_{L_{1}}$ .

[F2]

Inverse Unitary Access: inverse access supplies $U^{†} = U^{- 1}$ as an explicitly declared operation, with its own charge.

[F3]

Finite circuit resource accounting: size is the number of gate occurrences; controlled and inverse calls require explicitly granted access and separately recorded charges; inverse charges remain separate from controlled forward charges.

[F4]

Adjoints satisfy $(S + T)^{*} = S^{*} + T^{*}$ , $(λ T)^{*} = \overline{λ} T^{*}$ , $(S T)^{*} = T^{*} S^{*}$ , and $T^{* *} = T$ : $(S T)^{†} = T^{†} S^{†}$ for compatible finite-dimensional maps.

[F5]

A local gate has a unique global wire embedding: the full-register embedding of a local unitary is uniquely determined by its action on the named ordered wires and identity action on every other wire.

Proof

1.1givenF1F4algebra

Enumerate one layer as $L_{t} = (g_{1}, \dots, g_{s})$ . By [F1] its denotation is ${\tilde{U}}_{g_{s}} \dots {\tilde{U}}_{g_{1}}$ , so [F4] gives its adjoint ${\tilde{U}}_{g_{1}}^{†} \dots {\tilde{U}}_{g_{s}}^{†}$ .

2.1givenstep 1.1F1F2F3F5algebra

For each occurrence, its global embedding $T = {\tilde{U}}_{g_{j}}$ is unitary by [F1]. The inverse $T^{- 1} = T^{†}$ acts on each ordered product basis vector by applying $U_{g_{j}}^{- 1} = U_{g_{j}}^{†}$ to the selected factors and leaving every complement factor fixed: applying $T$ to that result returns the original vector. The legal local-adjoint embedding has the same action, so uniqueness in [F5] identifies it with $T^{†}$ . The assumed legal inverse occurrence and [F2] provide this call. There is one inverse occurrence per original gate, so the size is unchanged by [F3].

2.2givenF1F2F4step 1.1algebra

By [F1], the whole circuit is $U_{L_{d}} \dots U_{L_{1}}$ . Repeated use of [F4] yields $U_{C}^{†} = U_{L_{1}}^{†} \dots U_{L_{d}}^{†}$ , which acts by executing the inverse of $L_{d}$ first and the inverse of $L_{1}$ last. Since each layer is unitary, $U_{C}^{†} U_{C} = U_{C} U_{C}^{†} = I$ , so $U_{C}^{†} = U_{C}^{- 1}$ and it is the denotation of the reversed circuit.

3.1F1F3algebra∎

If $d = 0$ , both circuits are empty and denote the identity; the occurrence count is zero on both sides by [F3].

Depends on

Used by

Compute-copy-uncompute restores clean workspace Theorem

Dependency tree · two levels

17 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)
John Preskill, Quantum Computation, Chapter 5: Classical and Quantum Circuits (standard reference, not scraped)