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.

Exact Three-CNOT Synthesis of Two-Qubit Unitaries

Statement

Every $U \in U (4)$ has an exact circuit with no ancillas, at most three CNOT gates, and arbitrary one-qubit gates. The scalar phase is implemented as a one-qubit scalar gate and is not discarded.

Facts & Assumptions

Given: Exact matrix semantics, both CNOT orientations, and the Cartan decomposition.

[F1]

Exact Two-Qubit Cartan Decomposition: $U = e^{i δ} (A \otimes B) N (a, b, c) (C \otimes D)$ , where $N (a, b, c) = e^{i (a X \otimes X + b Y \otimes Y + c Z \otimes Z)}$ and $A, B, C, D \in S U (2)$ .

[F2]

One-Qubit Euler Decomposition: every $S U (2)$ factor and every scalar one-qubit unitary has an exact Euler realization using the QC7 rotation convention.

[F3]

Pauli formula for an axis rotation: $R_{n} (t) = \cos (t / 2) I - i \sin (t / 2) (n \cdot σ)$ for real unit $n$ .

[F4]

The Pauli matrices: $X, Y, Z$ are the displayed Pauli matrices in the ordered computational basis.

[F5]

CNOT and Control-Target Order: the first-wire-control CNOT maps $∣ a, t ⟩$ to $∣ a, t \oplus a ⟩$ ; its wire order is part of the definition.

[F6]

Denotational semantics of a finite layered circuit: chronological circuit layers $L_{1}, \dots, L_{d}$ denote the exact matrix product $U_{L_{d}} \dots U_{L_{1}}$ .

[F7]

Finite circuit resource accounting: size and gate costs count the occurrences declared in the explicit operation model; gate access is not inferred from a matrix alone.

[F8]

The computational basis is orthonormal: the ordered two-qubit computational basis is orthonormal.

Proof

1.1givenF1F2F3F4F5F8algebra

The Pauli matrices in [F4] give commuting products $X X, Y Y, Z Z$ . On the even-parity subspace with ordered basis $(∣ 00 ⟩, ∣ 11 ⟩)$ , $X X$ and $Y Y$ restrict to $X$ and $- X$ , while $Z Z$ restricts to $I$ . Hence $N$ restricts there to $e^{i c} e^{i (a - b) X}$ , whose entries are $e^{i c} \cos (a - b)$ on the diagonal and $i e^{i c} \sin (a - b)$ off diagonal. On the odd-parity basis $(∣ 01 ⟩, ∣ 10 ⟩)$ , $X X$ and $Y Y$ both restrict to $X$ and $Z Z$ restricts to $- I$ , so the block is $e^{- i c} e^{i (a + b) X}$ . These two blocks give $N (a, b, c) = (\begin{array}{cccc} e^{i c} \cos (a - b) & 0 & 0 & i e^{i c} \sin (a - b) \\ 0 & e^{- i c} \cos (a + b) & i e^{- i c} \sin (a + b) & 0 \\ 0 & i e^{- i c} \sin (a + b) & e^{- i c} \cos (a + b) & 0 \\ i e^{i c} \sin (a - b) & 0 & 0 & e^{i c} \cos (a - b) \end{array}) .$ In basis $00, 01, 10, 11$ , the two CNOT orientations are $C_{12} = (\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}), C_{21} = (\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{array}) .$ Here $C_{12}$ is the gate from [F5] and $C_{21}$ is obtained by interchanging the wire names. Both displayed permutations are unitary because they permute the orthonormal basis in [F8]. Using [F3] with the Pauli matrices [F4] gives the QC7 rotation convention in [F2]; multiplication of those rotations and the displayed CNOT permutations gives exactly $N (a, b, c) = e^{i π / 4} (R_{z} (π / 2) \otimes I) C_{21} (I \otimes R_{y} (π / 2 - 2 b)) C_{12} (R_{z} (π / 2 - 2 c) \otimes R_{y} (2 a - π / 2)) C_{21} (I \otimes R_{z} (- π / 2)) .$ All entries agree with the two parity blocks above; thus this is an exact identity, including its scalar.

2.1step 1.1F1F2F6F7algebra∎

The factorization in step 1.1 uses three CNOTs and otherwise one-qubit rotations. By [F2], the local factors $A, B, C, D$ and the scalar $e^{i δ}$ in [F1] have exact one-qubit implementations; $e^{i δ} I_{4} = (e^{i δ} I_{2}) \otimes I_{2}$ . The circuit product [F6] therefore equals the written factorization exactly, and [F7] counts three CNOT occurrences and no additional wires.

Depends on

Used by

Dependency tree · two levels

42 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

Farrokh Vatan and Colin Williams, Optimal quantum circuits for general two-qubit gates, arXiv:quant-ph/0308006v2 (standard reference, not scraped)
Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock, Smaller Two-Qubit Circuits for Quantum Communication and Computation, NIST full-text publication (standard reference, not scraped)