# If sampling the output of $U_1U_2$ is easy, is sampling the output of $(U_1U_2)^\dagger$ also easy?

Let $$U_1$$ and $$U_2$$ be $$n$$-qubit unitaries, and denote by $$P_{U_1U_2}(y \mid x) = |\langle y | U_1U_2 | x \rangle|^2$$ the probability of measuring $$y \in \{0,1\}^n$$ on input $$x \in \{0,1\}^n$$. Suppose $$P_{U_1U_2}(y \mid x)$$ is efficiently sampleable in the sense that there exists a classical probabilistic polynomial time algorithm $$A$$ such that on input $$x$$, $$A$$ outputs $$y$$ with probability $$P_{U_1U_2}(y \mid x)$$. Is it the case that $$P_{(U_1U_2)^\dagger}(y \mid x) = |\langle y | (U_1U_2)^\dagger | x \rangle|^2 = |\langle y | U_2^\dagger U_1^\dagger | x \rangle|^2$$ is also efficiently sampleable?

I feel like this should be the case but I cannot prove it. Perhaps there is a simple reason why or a paper on the topic.

We know that $$\begin{eqnarray} P_{(U_1U_2)^{\dagger}}(y\ \vert\ x) &=& \left\vert\langle y\vert(U_1U_2)^{\dagger}\vert x\rangle\right\vert^2 = \left\vert\left(\langle x\vert U_1U_2\vert y\rangle\right)^{\dagger}\right\vert^2 = \left\vert\langle x\vert U_1U_2\vert y\rangle^*\right\vert^2 \\&=& \left\vert\langle x\vert U_1U_2\vert y\rangle\right\vert^2 = P_{U_1U_2}(x\ \vert\ y),\end{eqnarray}$$ so if $$P_{U_1U_2}(y\ \vert\ x)$$ is efficiently sampleable for all bitstrings $$x$$ and $$y$$, then the same is true for $$P_{(U_1U_2)^{\dagger}}(y\ \vert\ x)$$.

Intuitively, I would say that if $$P_{U_1U_2}(y|x)$$ is efficiently sampleable, also $$P_{(U_1U_2)^\dagger}(y|x)$$ is efficiently sampleable as the quantum circuit for $$(U_1U_2)^\dagger$$ is just the reverse of the quantum circuit for $$U_1U_2$$.

• I agree, however I do not see how to use this intuition to formally prove what I am trying to show. To say $(U_1U_2)^\dagger$ is the reverse of $U_1U_2$ is just to say that $U_1U_2(U_1U_2)^\dagger = I$. But I don't see how to use this fact and the fact that $P_{U_1U_2}(y \mid x)$ is efficiently sampleable to contrive an algorithm that efficiently samples $P_{(U_1U_2)^\dagger}(y \mid x)$. Mar 15 at 5:55
• Doesn't efficiently sampleable ehere mens that you can efficiently simulate the circuit on a classical computer? This would mean that the circuit contains only gates from the Clifford group and measurements of Pauli group operators (see arxiv.org/abs/quant-ph/9807006v1), and the inverse circuit as well. The proof is based on the stabilizer formalism. If you want a statement in terms of probability, you should first try to express more formally the concept of efficiently sampleable probability. Mar 15 at 10:12
• Gottesman-Knill is not if and only if. I agree if $U_1$ and $U_2$ are Clifford operations, then the inverse is Clifford, and hence efficiently sampleable. But if a circuit is efficiently sampleable, it is not know if the circuit is necessarily Clifford. Rather than get into the details of what I mean by efficiently sampleable, it suffices to derive an efficiently computable algebraic relationship between $P_{U_1U_2}$ and $P_{(U_1U_2)^\dagger}$. This should be simple, but I don't see what the right expression is. Mar 15 at 17:36