Quantum Logic Gates

Quantum Shannon Decomposition

A recursive method that breaks any n-qubit unitary into two-qubit gates, achieving near-optimal CNOT counts.

The method

The quantum Shannon decomposition (QSD) recursively factors an arbitrary n-qubit unitary into smaller pieces. Each level splits an n-qubit gate into (n-1)-qubit gates conditioned on one qubit, using the cosine-sine decomposition of the unitary matrix. Unrolling the recursion reaches single- and two-qubit gates at the base.

The cosine-sine step

Kronos motion — quantum verdict

Any 2^n × 2^n unitary can be written via the cosine-sine decomposition as a product of block-diagonal unitaries and a central rotation whose blocks are cosines and sines. The block-diagonal parts are uniformly-controlled (multiplexed) gates on n-1 qubits, and the central part is a multiplexed RY rotation.

Multiplexed gates

A uniformly-controlled or multiplexed gate applies a different single-qubit rotation for each pattern of the control qubits. These decompose efficiently into a sequence of CNOTs interleaved with rotations, using a Gray-code ordering so that consecutive controls differ in one bit, minimizing the entangling gate count.

CNOT scaling

QSD produces a generic n-qubit unitary using a CNOT count that scales as roughly (23/48)·4^n, within a small constant factor of the theoretical lower bound of about (1/4)·4^n. For two qubits it recovers the optimal three-CNOT result. This makes QSD the standard fallback for compiling arbitrary dense unitaries.

python

def qsd_cnot_estimate(n):
    # leading-order CNOT count for generic n-qubit unitary
    return round((23/48)*4**n - (3/2)*2**n + 4/3)
print(qsd_cnot_estimate(3))

Uses

QSD is used whenever a circuit must realize a unitary given only as a matrix — state preparation, isometry embedding, and block-encoding of operators. It sits at the top of the decomposition hierarchy, feeding two-qubit blocks to KAK synthesis. See KAK decomposition and gate decomposition.