Proof of Lemma 1, pp. 5–6 — V_{n,G} is closed under adjoint when G is closed under inversion

Let $\mathcal G$ be an instruction set that is closed under inversion: with every gate $g$ it contains the gate $g^\dagger$ on the same number of qubits. Let $M \in \mathcal V_{n,\mathcal G}$ be the unitary of a depth-one $n$-qubit circuit over $\mathcal G$. Then

Moreover, if every gate of $\mathcal G$ is unitary, then $M$ is unitary, $M \in U(2^n)$.

This is the step "$U_1^\dagger, \dots, U_i^\dagger \in \mathcal V_{n,\mathcal G}$" in the proof of Lemma 1: it is what makes the set $S_i^\dagger$ of inverses of depth-$i$ unitaries equal to $S_i$. The unitarity clause lets $\mathcal V_{n,\mathcal G}$ (for a finite $\mathcal G$) serve as the layer set $V$ of the rest of the mission.

Formalization Note. Closure under inversion is QAlgorithms.ClosedUnderInverse, which adds $\langle k, g^\dagger\rangle$ for every gate $\langle k, g\rangle$; the adjoint of a matrix is star.