Isometry Unitary Completion

Input. Integers $1\le D\le M$, ordered orthonormal bases of ${\mathbb{C}}^D$ and ${\mathbb{C}}^M$, and an exact $M\times D$ matrix $V$ whose columns are orthonormal, so $V$ represents a linear isometry in the convention of Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces. Arithmetic is ideal exact complex arithmetic with conjugation, norms, square roots, and exact zero tests; no bit-time bound is part of this procedure.

Procedure. Initialize an ordered list $L$ with the $D$ columns of $V$. For $j=0,1,\dots ,M-1$, compute

$r_j=e_j-{\sum }_{w\in L}⟨e_j,w{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}w\mathrm{.}$

If $\mathrm{\parallel }{r}_j{\mathrm{\parallel }}_2=0$, leave $L$ unchanged. Otherwise append $r_j\mathrm{/}\mathrm{\parallel }{r}_j{\mathrm{\parallel }}_2$ to $L$. After the finite loop, return the square matrix $W$ whose columns are the final list, and return INVALID if the input dimensions or orthonormal-column condition fail.

For integer widths $0\le n\le w$, put $D=2^n$, $M=2^w$, and $a=w-n$. The input data and clean workspace use the ordered tensor-register convention of Ordered tensor registers, their inner product, and wire permutations and the big-endian basis encoding of Big-endian encoding of ordered bit strings. A clean workspace register starts at $\mathrm{\mid }{0}^a⟩$ under Clean and dirty ancillas. Let $\mathrm{\Pi }$ be the ordered wire permutation that swaps the $n$-wire data block with the $a$-wire zero-workspace block, so $\mathrm{\Pi }(\mathrm{\mid }x⟩\mathrm{\mid }{0}^a⟩)=\mathrm{\mid }{0}^a⟩\mathrm{\mid }x⟩$. This sends the declared clean-input basis to the first $D$ standard basis vectors. The matrix $W\mathrm{\Pi }$ is the full-unitary extension interface used by Isometry Completion and Synthesis ↗.