Consider you are given a Choi state $$ \sigma = (\mathcal{E} \otimes I) | \omega \rangle \langle \omega| \qquad {\rm with } \quad |\omega \rangle = \frac{1}{\sqrt{d}}\sum_{i} |ii \rangle \quad \textrm{generalized Bell state} $$ corresponding to the quantum channel $\mathcal{E}$. Since the Choi state contains all the information about the quantum channel, one might think that it should be possible to efficiently execute $\mathcal{E}(\rho)$ on some state $\rho$ only having access to $\sigma$ and $\rho$.
I found two channel execution schemes that both use the identity $\mathcal{E}(\rho) = {\rm tr}_2(\sigma (I \otimes \rho^t))$, but both do not seem to be efficient:
- is based on gate teleportation (https://arxiv.org/abs/quant-ph/9908010)
- describes a heralded measurement scheme based on the eigendecomposition of $\rho$ (https://arxiv.org/abs/1912.05418).
(1.) In the gate teleportation scheme, we need to post-select on the exponentially suppressed state $|0...0\rangle$, if we do not want to apply $\mathcal{E}$. If the Choi matrix was unitary, we could try to compile the conjugation of the Pauli-String $U R_{xz} U^\dagger = R'_{xz}$ as described in the paper, but this would still require knowledge about $U$.
(2.) The heralded measurement scheme has a similar problem. (Following section III of the second paper) one can sample from $\mathcal{E}(\rho)$, but the expectation value will be exponentially suppressed. Resolving this also requires an exponential amount of samples, in general.
Is there an efficient way to implement channel execution with the described resources? Or is there a simple way of seeing why channel execution needs exponential resources?
EDIT: After a few iterations with @NorbertSchuch, I feel like I need to reformulate my question.
If we were to do state tomography (as suggested in the second paper), you would be measuring $$ {\rm Tr}\left( \sigma (I \otimes \rho^t) \right) = \frac{1}{d} \mathcal{E}(\rho) $$ with the transpose $\rho^t$ and $d$ the dimension of the Hilbert space. I am worried about the exponential factor $\frac{1}{d}$ (that I think, is missing in the paper), as it will lead to an exponential growth in variance of $\mathcal{E}(\rho)$ and therefore an exponential number of required measurements. Say, we are interested in measuring an observable $O$ on the channel output, then we calculate the expectation value $$ {\rm Tr}\left( \sigma (I \otimes \rho^t) (O \otimes I) \right) = \frac{1}{d} {\rm Tr}\left( \mathcal{E}(\rho) O \right) $$ Hence, to get the correct expectation value ${\rm Tr}\left( \mathcal{E}(\rho) O \right)$, we would need to measure $\tilde O = d O$ whose variance is inflated by an exponential factor ${\rm Var}(\tilde O) = d^2 {\rm Var}(O)$. Assuming ${\rm Var}(O) = \mathcal{O}(1)$, this means that we need to use exponentially many samples to resolve the expectation value.
On the other hand, if I could directly execute the quantum channel, I could directly prepare $\mathcal{E}(\rho)$ and sample ${\rm Tr}\left( \mathcal{E}(\rho) O \right)$ without exponentially many samples (a priori).
This goes against my idea of the Choi–Jamiołkowski isomorphism. It seems like, in the discussed case, it is always more favourable to directly execute the quantum channel instead of accessing it through its Choi state. Now my question is whether there is a better measurement scheme/technique that restores the symmetry between quantum channel and Choi state and gets rid of the factor $d$ or (if not) whether one can show that sampling from Choi states is exponentially surpressed.
