Isometry Completion and Synthesis

The initial list is orthonormal by the input hypothesis. If the current list is orthonormal, then for each $w_i\in L$ the residual satisfies $⟨r_j,w_i⟩=⟨e_j,w_i⟩-{\sum }_{w\in L}⟨e_j,w⟩⟨w,w_i⟩=0$ by [F2] and orthonormality. If it is nonzero, division by its positive norm gives a unit vector orthogonal to every previous column; if it is zero, $e_j$ already lies in their span. Thus each update preserves orthonormality and puts $e_j$ in the span of the updated list.

After the finite loop, every standard basis vector $e_j$ lies in the final span by step 1.1. The standard basis spans ${\mathbb{C}}^M$, so the final orthonormal list spans ${\mathbb{C}}^M$ and has exactly $M$ vectors. If $z={\sum }_{j=1}^M{c}_j{w}_j$ is its expansion in that list, orthonormality and [F2] give $\mathrm{\parallel }z{\mathrm{\parallel }}_2^2={\sum }_j\mathrm{\mid }{c}_j{\mathrm{\mid }}^2$; the same coordinate calculation for the standard basis gives $\mathrm{\parallel }Wc{\mathrm{\parallel }}_2^2={\sum }_j\mathrm{\mid }{c}_j{\mathrm{\mid }}^2$. Thus the column map $W$ preserves norms and is injective by [F4]. By [F5] it is surjective in finite dimension, hence invertible; as a square norm-preserving map it is unitary by [F4]. Its first $D$ columns are the original list, namely $V$.

For $D=2^n$, $M=2^w$, [F3] identifies $\mathrm{\mid }{0}^{w-n}⟩\mathrm{\mid }x⟩$ with the standard basis vector $e_{{\mathrm{enc}}_n(x)}$ among the first $D$ vectors. The declared permutation obeys $\mathrm{\Pi }(\mathrm{\mid }x⟩\mathrm{\mid }{0}^{w-n}⟩)=\mathrm{\mid }{0}^{w-n}⟩\mathrm{\mid }x⟩$. The first $D$ columns of $W$ then give $(W\mathrm{\Pi })(\mathrm{\mid }x⟩\mathrm{\mid }{0}^{w-n}⟩)=V\mathrm{\mid }x⟩$ for every computational basis input $x$; linearity gives the identity on the entire clean-input subspace.

For $w\ge 1$, $W\mathrm{\Pi }$ is a unitary on a positive-width register, so applying the QSD interface [A1] directly to this matrix gives the stated CNOT bound, with its one-qubit case at $w=1$. The permutation is absorbed into the target matrix before synthesis, so no separate permutation gate count is added. If $w=0$, then $n=0$ and $W\mathrm{\Pi }=V$ is a scalar on $\mathbb{C}$. By [F6], the only zero-wire circuit denotes $1$, so a circuit realizes this scalar exactly only when $V=I$; the matrix completion of steps 1.1–3.1 does not itself claim a general zero-width synthesis. The construction places no condition on the $M$ output coordinates beyond the isometry equation, so it makes no claim that the extra output wires are clean.