2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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)$.

Improve this answer
$\endgroup$
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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)$. $\endgroup$
    – trillianhaze
    Mar 15 at 5:55
  • $\begingroup$ 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. $\endgroup$
    – Michele Amoretti
    Mar 15 at 10:12
  • $\begingroup$ 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. $\endgroup$
    – trillianhaze
    Mar 15 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.