The Exercise

Take a quantum system with $d$ levels, its state space $\mathbb{C}^d$ and its computational basis $|0\rangle, \dots, |d-1\rangle$; a unitary on it is a unitary $d \times d$ complex matrix. The simplest unitaries are the two-level ones. The exercise asks how many of them a product needs in order to equal a given unitary, and bounds that number from below: in every dimension $d$ there is a unitary $U$ that is not a product of fewer than $d - 1$ two-level unitaries.^✦

Two-level Unitaries

A two-level unitary $V$ on $\mathbb{C}^d$ is a unitary $d \times d$ matrix for which there are indices $p$ and $q$ such that $V$ agrees with the identity matrix outside the block where the rows $p$ and $q$ meet the columns $p$ and $q$: $$V_{ij} = \delta_{ij} \qquad \text{whenever } i \notin \{p, q\} \text{ or } j \notin \{p, q\}.$$(1)^✦ On the span of $|p\rangle$ and $|q\rangle$ such a $V$ acts as a $2 \times 2$ unitary. The indices need not differ, so a phase on a single basis state is a two-level unitary as well.

The Claim

What Is Checked

The claim is stated over the unitary $d \times d$ complex matrices and over the two-level unitaries of (1), multiplied in the order written.