Explicit construction for unitary extensions of completely positive and trace preserving (CPTP) maps? Given a completely positive and trace preserving map $\Phi : \textrm{L}(\mathcal{H})\to\textrm{L}(\mathcal{G})$, it is clear by the Kraus representation theorem that there exist $A_k \in \text{L}(\mathcal{H}, \mathcal{G})$ such that $\Phi(\rho) = \sum_k A_k \rho A_k^\dagger$ for all density operators $\rho$ on $\mathcal{H}$. (I'll consider the special case $\mathcal{H} = \mathcal{G}$ for simplicity.)
If we use then the system+environment model to express this action as $\Phi(\rho)=\text{Tr}_{\mathcal{H}_E} (Y\rho Y^\dagger)$ for an isometry $Y$ from $\mathcal{H}$ to $\mathcal{H}\otimes\mathcal{H}_E$, where $\mathcal{H}_E$ is an ancilla modelling the environment, what is an explicit construction for a unitary $U$ that has the same action on inputs of the form $\rho\otimes\left|0\right>\left<0\right|_E$? That is, how can I construct an explicit dilation of the map to a unitary acting on a larger space? I understand that this is possible by Steinspring's dilation theorem, but actually constructing an explicit form for the dialated unitary I have had much less success with.
 A: This is just to complement the other answer by providing a more explicit derivation.
We have a map $\Phi(\rho)=\sum_k A_k \rho A_k^\dagger$ and we want to find a unitary $\mathcal U$, acting on a bigger system+environment space, such that:
$$\newcommand{\tr}{\operatorname{tr}}
\tr_E\big(\mathcal U(\rho\otimes|0\rangle\!\langle0|)\mathcal U^\dagger\big) = \Phi(\rho), \tag1
$$
where $|0\rangle$ is some (pure) state of the environment.
To see the connection between $\mathcal U$ and the Kraus operators of $\Phi$, let us decompose it as
$$\mathcal U=
\sum_{ijkl} u_{ij,k\ell} |i\rangle\!\langle k|\otimes |j\rangle\!\langle \ell| \equiv
\sum_{ijkl} u_{ij,k\ell} |i,j\rangle\!\langle k,\ell|,
$$
where $i, j$ refer to the system and $k, l$ to the environment degrees of freedom.
The action of $\mathcal U$ over $\rho\otimes|0_E\rangle\!\langle0_E|$ gives
$$\begin{gathered}
\mathcal U(\rho\otimes|0_E\rangle\!\langle0_E|) \mathcal U^\dagger
= u_{ij,kl}u^*_{mn,pq}
  |ij\rangle\!\langle mn| \,\,
  \langle k\ell|(\rho\otimes|0\rangle\!\langle0|) |pq\rangle\\
  = u_{ij,k0}u^*_{mn,p0} \rho_{kp} \,\, |ij\rangle\!\langle mn|,
\end{gathered}$$
where every index is assumed to be implicitly summed over.
Taking the trace over the environment now gives:
\begin{aligned}
\tr_E\Big[\mathcal U(\rho\otimes|0_E\rangle\!\langle0_E|) \mathcal U^\dagger \Big]
= \sum_{ijkmp}
u_{ij,k0}u^*_{mj,p0} \rho_{kp} |i\rangle\!\langle m|
= \sum_j A^j \rho\, (A^j)^\dagger,
\end{aligned}
where we defined the linear operators $A^j$ with elements $(A^j)_{ik}\equiv u_{ij,k0}$.
The above tells us that the action of an arbitrary unitary evolution $\mathcal U$ on the enlarged space, when looking only at the effective evolution over the reduced state, amounts to a mapping of the form
$\rho\mapsto \sum_j A^j\rho (A^j)^\dagger$, as we expected.
In other words, (1) is verified with any $\mathcal U$ satisfying
$(\mathcal U)_{ik,j0}=A^k_{ij}$, or, equivalently,
$$(I\otimes \langle k\rvert)\mathcal U(I\otimes\lvert 0\rangle) = A^k.$$
An intuitive way to understand the above constraint is by considering the environment as the first space (so the opposite of the way we have written above). Note that this doesn't change anything of relevance, it is just a different way to represent the same things.
However, when the environment is the first space, we can think of $\mathcal U$ as composed of a number of blocks (submatrices), each one characterizing the action of $\mathcal U$ on the system when looking at a specific input-output combination over the environment.
The above reasoning can be pictured as following:

where in this example the environment has dimension 3.
With the above picture in mind, the condition $\sum_k A^{k\dagger}A^k=\mathbb 1$ is also straightforwardly understood: it is equivalent to asking the columns of $\mathcal U$ corresponding to the input state of the environment (that is, the columns in the middle block in the image above) to be a set of orthonormal vectors.
A: The isometry $Y:\mathcal H\rightarrow \mathcal H_E \otimes \mathcal H$ is
$$
Y=\left(\begin{array}{c} A_1 \\ \vdots \\ A_K
\end{array}\right)
 = \sum_k |k\rangle \otimes A_k\ .
$$
Clearly, 
$$
\mathrm{tr}_E(Y\rho Y^\dagger) = \sum_{kl} \mathrm{tr}(|k\rangle\langle l|) A_k\rho A_l^\dagger   =
\sum_k A_k \rho A_k^\dagger \ ,
$$
as desired.
Moreover, $Y$ is an isometry, $Y^\dagger Y=I$, i.e., its columns are orthonormal, which follows from the condition $\sum_k A_k^\dagger A_k=I$ (i.e., the map is trace preserving).  
Now if you want to obtain a unitary which acts on $|0\rangle\langle 0|\otimes \rho$ the same way $Y$ acts on $\rho$, you have to extend the matrix $Y$ to a unitary by adding orthogonal column vectors. For instance, you can pick linearly independent vectors from your favorite basis and orthonormalize. (Clearly, $U$ is highly non-unique, as its action on environment states other than $|0\rangle$ is not well defined.)
