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.

Unoptimized recursive QSD decomposition and CNOT count

Statement

For every $n \geq 2$ , the recursive cosine-sine/demultiplexing construction gives an exact no-ancilla circuit for any $n$ -qubit unitary. At each nonterminal level, split off the first wire as target and let the recursive children act on the remaining contiguous wire interval; the node uses four recursive $(n - 1)$ -qubit unitaries, one multiplexed $R_{y}$ , and two multiplexed $R_{z}$ rotations, each with $n - 1$ controls. If $c_{n}$ is the construction's CNOT count, then $c_{2} \leq 3$ and $c_{n} \leq 4 c_{n - 1} + 3 \cdot 2^{n - 1} (n \geq 3), c_{n} \leq \frac{9}{16} 4^{n} - \frac{3}{2} 2^{n} .$ This is the unoptimized recursive count; it does not include cross-block cancellations or terminal diagonal extraction and makes no compilation-time or finite-precision claim.

Facts & Assumptions

Given: Exact matrix semantics, arbitrary one-qubit rotations, CNOT gates, the cosine-sine block decomposition, and two-block demultiplexing.

[F1]

Cosine-Sine Block Decomposition factors an even-dimensional unitary into two block-diagonal unitaries and a central block $(\begin{array}{cc} C_{0} & - S_{0} \\ S_{0} & C_{0} \end{array})$ with nonnegative diagonal entries satisfying $C_{0}^{2} + S_{0}^{2} = I$ .

[F2]

Demultiplexing a Two-Block Unitary factors each two-block unitary into two identical smaller unitaries surrounding a diagonal two-block factor $diag (D, D^{*})$ .

[F3]

Gray-Code Synthesis of a Multiplexed Axis Rotation exactly synthesizes a multiplexed $R_{y}$ with $2^{k}$ CNOTs for $k > 0$ .

[F4]

Gray-code synthesis of a multiplexed Z rotation exactly synthesizes a multiplexed $R_{z}$ with $2^{k}$ CNOTs for $k > 0$ .

[F5]

Exact Three-CNOT Synthesis of Two-Qubit Unitaries supplies an exact no-ancilla synthesis of every two-qubit unitary with at most three CNOTs and arbitrary one-qubit gates. Its direct matrix identity for the nonlocal two-qubit factor was inspected; this base case does not require expanding arbitrary one-qubit gates into a smaller primitive rotation alphabet.

[F6]

$t \mapsto (\cos t, \sin t)$ is a bijection from $[0, 2 π)$ onto the real unit circle supplies an angle for each nonnegative pair $(c, s)$ with $c^{2} + s^{2} = 1$ .

[F7]

Every nonzero complex number has a unique polar form $r (\cos θ + i \sin θ)$ with $r > 0$ and $- π < θ \leq π$ gives a real argument for each unit complex diagonal entry of $D$ .

[F8]

Finite circuit syntax and ordered wire labels fixes the ordered gate/layer syntax; Denotational semantics of a finite layered circuit gives the exact chronological matrix product; Finite circuit resource accounting counts CNOT occurrences.

Proof

1.1givenF1F3F6algebra

Apply [F1] to a $2^{n}$ -dimensional unitary, splitting the first wire from the remaining contiguous $n - 1$ wires. The central block acts on each select word $x$ by $(\begin{array}{cc} c_{x} & - s_{x} \\ s_{x} & c_{x} \end{array})$ . By [F6], choose $ϕ_{x}$ with $c_{x} = \cos ϕ_{x}$ and $s_{x} = \sin ϕ_{x}$ ; this block is the $R_{y} (2 ϕ_{x})$ convention used by [F3]. Thus the central block is one $(n - 1)$ -control multiplexed $R_{y}$ targeting the first wire.

1.2F1F2F4F7F8algebra

Apply [F2] to each of the two block-diagonal factors from [F1]. Each factor becomes two $(n - 1)$ -qubit unitaries on the remaining contiguous interval and one $diag (D, D^{*})$ . For each computational select word $x$ , write the diagonal entry $D_{x x} = e^{i α_{x}}$ using [F7]. Its action on the first wire is $diag (e^{i α_{x}}, e^{- i α_{x}}) = R_{z} (- 2 α_{x})$ , so this middle factor is one $(n - 1)$ -control multiplexed $R_{z}$ . Therefore the recursive circuit has four $(n - 1)$ -qubit calls and three multiplexed rotations in total. Their exact products compose as claimed by [F8].

1.3F3F4F5F8constructalgebra

At $n = 2$ , [F5] gives $c_{2} \leq 3$ . For $n \geq 3$ , the four recursive calls contribute at most $4 c_{n - 1}$ CNOTs. Each of the three $(n - 1)$ -control multiplexed rotations contributes $2^{n - 1}$ CNOTs by [F3] and [F4], giving $c_{n} \leq 4 c_{n - 1} + 3 \cdot 2^{n - 1}$ .

2.1step 1.3inductionalgebra∎

The claimed closed bound equals $3$ at $n = 2$ . If it holds at $n - 1$ , then $4 (\frac{9}{16} 4^{n - 1} - \frac{3}{2} 2^{n - 1}) + 3 \cdot 2^{n - 1} = \frac{9}{16} 4^{n} - \frac{3}{2} 2^{n},$ so induction proves the formula for every $n \geq 2$ . No further gate cancellations are used.

Depends on

Used by

Ninefold nearest-neighbor multiplexor routing Lemma

Dependency tree · two levels

39 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

Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov, Synthesis of Quantum Logic Circuits, arXiv:quant-ph/0406176v5 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)