= Solution
Let $|u_i\rangle$ denote the specified image of $|i\rangle|0\rangle$. Its components comprise $N-1$ distinct ordered-pair basis states, each with coefficient $\pm N^{-1/2}$, together with $|0,0\rangle$ with coefficient $N^{-1/2}$. Hence $\langle u_i|u_i\rangle=1$.
For distinct indices $i<j$, only two output basis states occur in both images. Their common $|0,0\rangle$ contributions have product $1/N$, while the $|i,j\rangle$ contributions have product $-1/N$. Thus
$$
\boxed{\langle u_i|u_j\rangle=\delta_{ij}.}
$$
The specified map is therefore a <linear isometry> on the $N$-dimensional input subspace. Complete the input vectors $|i,0\rangle$ to an <orthonormal basis> of the $N^2$-dimensional space, and independently complete their images $|u_i\rangle$ to another <orthonormal basis>. Map the first full basis to the second. This is a <unitary extension of a finite-dimensional isometry>, giving the required $\widetilde U$. \b[The prescribed columns are orthonormal, so a full <unitary extension> exists.] Its construction depends only on $N$, not on the unknown string, and is permitted by the question's exact-unitary assumption.
Back to article page
