When is this map completely positive? Consider the complex $n$-by-$n$ matrices $M_n$. 
Suppose that $A_i$, for $i=1,\ldots,n^2$, satisfy $\mathrm{Tr}(A_i^*
A_j)=\delta_{ij}$, so that together they form an orthonormal basis for
$M_n$. Define a linear map $T \colon M_n \to M_n \otimes M_n$ by $T(A_i) = A_i \otimes A_i$.

Question: when is $T$ completely positive?

For example, if $A_i$ are the matrices with a single entry one and the rest zeroes in some fixed basis of $\mathbb{C}^n$, then $T$ is completely positive. In fact, I think these might be the only examples. If $T$ is completely positive, then the following are equivalent to $A_i$ being matrix units as in the above example:


*

*each $A_i$ has rank one;

*each positive semidefinite $A_i$ has trace one;

*the set $\{0,A_1,\ldots,A_{n^2}\}$ is closed under multiplication;

*$T(1)$ is idempotent;

*$T^*(1) \leq 1$;

*$T$ preserves trace.


These are sufficient conditions, but proving they are sufficient doesn't use  $\mathrm{Tr}(A_i^* A_j)=\delta_{ij}$ at all. Are they necessary?
 A: This is not a complete answer, but it might help.
The map $T: A_i \mapsto A_i \otimes A_i$ sends, by its very definition, the orthonormal family $(A_i)$ to an orthonormal family. It is therefore an isometry for the Hilbert-Schmidt norms.
But there are not that many completely positive maps $M_n \to M_m$ which are also isometries for the Hilbert-Schmidt-norms. Namely such a map is of the form $T(x)= D \pi(x)$, for some (not necessarily unital) $*$-homomorphism $\pi$ and some positive operator $D=T(1)\in M_m$ commuting with the range of $\pi$. This is an if-and-only-if condition provided that $\|D\|_{HS}=\sqrt n$. This statement is probably known. If you want I can expand the proof I have in mind.
This implies that such a map satisfies $Tr\circ T=c Tr$ for some positive $c=Tr(D)/n$, and more generally that for any $p>0$, $\|Tx\|_p = c_p \|x\|_p$ for $c_p=\|D\|_p/n^{1/p}$.
Coming back to your problem, I do not see how to conclude, you can already find a couple of necessary conditions on the $A_i$'s for the map $T(A_i)=A_i \otimes A_i$ to be completely positive.

Matthew asked for a proof of

A linear map $T:M_n\to M_m$ is completely positive and isometric for the Hilbert-Schmidt norm if and only if $T$ is of the form $T(x)= D \pi(x)$, for some (not necessarily unital) $*$-homomorphism $\pi$ and some positive operator $D=T(1)\in M_m$ commuting with the range of $\pi$, and such that $\|D\|_{HS}=\sqrt n$.

I only prove the "only if" direction. Assume that $T$ is cp and isometric for the Hilbert-Schmidt norm. Using the fact that $T$ is cp, by Stinespring's theorem, there is a (finite dimensional) Hilbert space $H$ and a linear map $V:\mathbb C^m \to H\otimes \mathbb C^n$ such that $T$ can be decomposed as $T(x)=V^* 1_H \otimes x V$. I claim that the assumption that $T$ is isometric implies that $VV^*$ is of the form $A \otimes 1_n$ for some positive $A \in B(H)$ (in particular $V V^*$ commutes with $1\otimes x$ for all $x \in M_n$). This will imply that $T(x) T(y) = T(1) T(xy) = T(xy) T(1)$ for all $x,y \in M_n$, and hence putting $\pi(x) = T(x) T(1)^{-1}$ (with the convention $0/0=0$) we get the proposition.
The claim is not complicated to check. By the trace property, $\langle Tx,Ty \rangle = Tr(VV^* (1\otimes x) V V^* (1\otimes y^* ))$. Writing $VV^* = \sum B_{i,j} \otimes e_{i,j}$, taking $x=e_{i,j}$, $y=e_{s,t}$, and using that $T$ preserves the scalar product, one gets $\langle e_{i,j},e_{s,t}\rangle= Tr(B_{s,i}B_{j,t})$. But $VV^*$ being self-adjoint, this becomes $\delta_{i,s}\delta_{j,t}= \langle B_{s,i},B_{t,j}\rangle$. This implies that $B_{s,i}=0$ if $s\neq i$ and that the matrices $B_{i,i}$ are all of Hilbert-Schmidt norm $1$, and that $\langle B_{i,i},B_{j,j}\rangle=1$. Thus (equality in Cauchy-Schwartz inequality), the $B_{i,i}$'s are all equal, to some matrix $U$. This proves the claim.
A: Further to the linear map $T: M_n \rightarrow M_n \otimes M_n$ defined above by setting $T(A_i):=A_i \otimes A_i$, consider the linear map $E: M_n \rightarrow \mathbb{C}$ defined by setting $E(A_i) := 1$ for all $i=1,...,n^2$.
Let $\eta: \mathbb{C} \rightarrow M_n \otimes M_n^\ast$ and $\epsilon: M_n^\ast \otimes M_n \rightarrow \mathbb{C}$ be the cups and caps of CP maps:
$$
\eta(1) := \sum_{i} A_i \otimes A_i^\ast
\hspace{1cm}
\epsilon(A_i^\ast \otimes A_j) := \delta_{ij} 
$$
Also, let $\sigma := M_n \otimes M_n^\ast \rightarrow M_n^\ast \otimes M_n$ be the swap of CP maps:
$$
\sigma(A_i \otimes A_j^\ast) := A_j^\ast \otimes A_i
$$
If $T$ is a CP map, then so is $E$, because the latter can be obtained from the former by composition and tensor product with the CP maps $id_{M_n}$, $\eta$, $\epsilon$ and $\sigma$:
$$
E = \left(id_{M_n}\otimes (\epsilon \circ \sigma)\right) \circ (T \otimes id_{M_n}) \circ \eta
$$
By the way $T$ and $E$ are defined, $(T, E, T^\dagger, E^\dagger)$ is a special commutative $\dagger$-Frobenius algebra of linear maps. If $T$ is CP, then $(T, E, T^\dagger, E^\dagger)$ is a special commutative $\dagger$-Frobenius algebra of CP maps.
By Corollary 7 of https://arxiv.org/abs/2110.07074v2, such an algebra necessarily arises by "doubling" of a special commutative $\dagger$-Frobenius algebra $(t, e, t^\dagger, e^\dagger)$ of linear maps. The latter are defined as follows, for some choice of OBN $|\phi_i\rangle$ on $\mathbb{C}^n$:
$$
t(|\phi_i\rangle) := |\phi_i\rangle\otimes|\phi_i\rangle
\hspace{1cm}
e(|\phi_i\rangle) := 1
$$
Hence, $T$ takes the form $T(|\phi_i\rangle\langle\phi_j|) := |\phi_i\rangle\langle\phi_j| \otimes |\phi_i\rangle\langle\phi_j|$, as originally conjectured.
