LemmaStatement: 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.

Exact Central Controlled-Z Absorption at a QSD Node

Statement

Let $k \geq 1$ , let the first of $k + 1$ wires be the target, and let $L = diag (L_{0}, L_{1})$ and $R = diag (R_{0}, R_{1})$ be generic block-diagonal unitaries in that target's basis. Let $M$ be a multiplexed $R_{y}$ on that target, selected by the other $k$ wires. The exact matrix $L M R$ can be represented by four generic $k$ -qubit slots, two multiplexed $R_{z}$ factors and a central network with only $2^{k} - 1$ controlled- $Z$ gates and arbitrary one-qubit rotations. Each controlled- $Z$ costs one CNOT. Thus one CNOT is saved relative to demultiplexing $L, R$ and using a full $2^{k}$ -CNOT central rotation. The exact rewritten factors add no workspace, preserve scalar phases, and keep every non-target wire a select wire within the central network.

Facts & Assumptions

Given: The target-first ordered basis, $k \geq 1$ , and $L, M, R$ as stated.

[F1]

Gray-Code Synthesis of a Multiplexed Axis Rotation supplies the cyclic Gray masks and Walsh angles for $M$ .

[F2]

One-Qubit Euler Decomposition gives the QC7 matrix $R_{y} (t) = (\begin{array}{cc} \cos (t / 2) & - \sin (t / 2) \\ \sin (t / 2) & \cos (t / 2) \end{array})$ .

[F3]

Demultiplexing a Two-Block Unitary factors each generic two-block unitary into two smaller unitaries and a diagonal two-block factor.

[F4]

CNOT and Control-Target Order supplies the exact controlled- $X$ matrix; Denotational semantics of a finite layered circuit puts later chronological gates to the left.

[F5]

Finite circuit resource accounting counts declared CNOT occurrences and all wires.

Proof

1.1givenF1F2F4algebra

Direct multiplication of [F2] gives $Z R_{y} (t) Z = R_{y} (- t)$ , with $Z = diag (1, - 1)$ . In the cyclic Gray construction [F1], replace each select-to-target controlled- $X$ by select-to-target controlled- $Z$ . On select word $x$ , the parity accumulated at mask $p_{j}$ is now $Z^{p_{j} \cdot x}$ , so conjugation changes the $j$ th rotation angle to $(- 1)^{p_{j} \cdot x} β_{j}$ . The same Walsh inversion proves the final target angle is $θ_{x}$ , and the final Gray edge restores the accumulated $Z$ exponent to zero. Thus this network equals $M$ exactly and contains $2^{k}$ controlled- $Z$ gates. All select bits are unchanged.

2.1step 1.1F4algebra

Let its final chronological controlled- $Z$ use select wire $r$ , and put $Z_{r}$ for $Z$ on that select wire and identity on the other $k - 1$ select wires. In target-first block order this last gate is $E_{r} = diag (I_{2^{k}}, Z_{r})$ . If $T$ is the chronological network with this last gate deleted, [F4] gives the exact identities $M = E_{r} T$ and $L M R = (L E_{r}) T R = diag (L_{0}, L_{1} Z_{r}) T diag (R_{0}, R_{1})$ . Both $L_{0}$ and $L_{1} Z_{r}$ remain arbitrary $k$ -qubit unitaries. This is a block multiplication identity and does not commute $E_{r}$ through $L$ .

3.1step 2.1F2F3algebra

Apply [F3] separately to $L E_{r}$ and $R$ . These two generic block-diagonal factors still produce four arbitrary $k$ -qubit slots and two diagonal two-block factors. A diagonal factor $diag (D, D^{*})$ is a multiplexed $R_{z}$ on the first wire: if $D_{x x} = e^{i α_{x}}$ , its two target entries are $e^{i α_{x}}, e^{- i α_{x}}$ and hence equal $R_{z} (- 2 α_{x})$ . The central $T$ has $2^{k} - 1$ controlled- $Z$ gates. Therefore the rewritten circuit has exactly the required shape and retains the identity in step 2.1.

4.1step 1.1step 2.1step 3.1F4F5algebra∎

Set $H = 2^{- 1 / 2} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ . Direct multiplication gives $H^{2} = I$ and $H X H = Z$ , so a controlled- $Z$ on a select-target pair equals $(I \otimes H) CNOT (I \otimes H)$ in that pair's control-first order. Each costs one CNOT and two one-qubit gates, with no added wire. Thus deleting the terminal $E_{r}$ saves exactly one CNOT in the central network. Every remaining central gate still acts on the first-wire target or reads other wires only as unchanged selects. The block products in steps 2.1–3.1 are ordinary exact matrix products, so no scalar phase or workspace promise has been suppressed.

Depends on

Used by

Exact QSD CNOT Upper Bound Theorem

Dependency tree · two levels

30 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

Shende, Bullock, and Markov, Synthesis of Quantum Logic Circuits, Appendix A.1 (standard reference, not scraped)