# Is there an efficient way to execute a quantum channel using its Choi state?

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:

1. is based on gate teleportation (https://arxiv.org/abs/quant-ph/9908010)
2. 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.

• What are the rules of the game? You get one copy of the Choi state and one of the input, and you want to know if you can apply it with unit probability? Or do you get several copies? Or do you know the state you want to apply it to? Commented Jun 21, 2023 at 15:25
• I would be interested in either. Let us be generous and say I can prepare arbitrary many copies of the Choi-state. Also I know the (a priori arbitrary) input state and could in principle prepare arbitray many copies of that, too. In the end, of course, all resources and execution time should stay polynomial. Commented Jun 21, 2023 at 19:14
• In that case, what prevents me from doing tomography? Commented Jun 22, 2023 at 12:37
• For a full state tomography, I would need exponentially many copies, wouldn't I? If I did shadow tomography, I would be limited in the observables I can predict. Commented Jun 22, 2023 at 13:52
• True, but it still seems to suggest that in a setting where you want to apply a channel many times to a set of input states you can prepare, the times you need to request the Choi state of the channel (if that is the cost) goes to a constant, or only grows very moderatly, with the number of applications. Commented Jun 22, 2023 at 15:13

In general, the optimal retrieval probability of a unitary channel reads $$\frac{N}{N-1+d^2}$$, where $$d$$ is the Hilbert space dimension and $$N$$ the number of available copies of the unitary. Thus, in order to make the probability constant in system size, $$N=\mathcal{O}(d^2)$$ is necessary.