TheoremStatement: AI-adaptedProof: 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.

QSD CNOT Upper Bound

Statement

Reuse QC11 exact QSD: no-ancilla $n$ -qubit $U$ needs at most $(23 / 48) 4^{n} - (3 / 2) 2^{n} + 4 / 3$ CNOTs. Report one-qubit gates separately; a CNOT count alone is not total classical compilation time. Use $n \geq 2$ for this formula; $n = 1$ needs zero CNOT. For $n = 0$ , an exact circuit exists only for the identity scalar $U = 1$ , realized by the empty circuit.

Facts & Assumptions

Given: n ordered qubits and exact no-ancilla QSD as in QC11.

[A1]

Exact QSD CNOT Upper Bound proves the exact no-ancilla CNOT formula, including its recursive central controlled- $Z$ absorption identity and terminal diagonal-migration identity.

Proof

1.1A1given

For $n \geq 2$ , apply [A1] to the given unitary. Its exact no-ancilla QSD construction uses at most $(23 / 48) 4^{n} - (3 / 2) 2^{n} + 4 / 3$ CNOTs. This is an upper bound for that construction, with both savings proved by the supplier, and makes no lower-bound or optimality assertion.

2.1A1givencases∎

For $n = 1$ , a one-qubit $U$ is itself an allowed one-qubit gate and uses zero CNOT; for $n = 0$ , [A1] states that an exact empty-register circuit exists if and only if the scalar unitary is $1$ , realized by the empty circuit with no gates. The formula from [A1] is not used in these cases. One-qubit gates remain a separate resource, and no classical compilation-time bound follows.

Depends on

Exact QSD CNOT Upper Bound

Used by

Two-qubit QSD CNOT upper-bound instance Example

Dependency tree · two levels

14 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 (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)