$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By this I mean that the quantum polynomial-time verifier is allowed to apply $\ket{\psi} \mapsto U\ket{\psi}$ once during its computation. Overall, we accept if there exists a $U$ that makes the computation accept w.h.p. and reject otherwise.

Similarly, is there an analogue of $\mathsf{QMA}(2) = \mathsf{QMA}(k)$ where Merlin provides to Arthur $k = O(1)$ "independent" accesses to unitaries $U_1, \dots, U_k$?

Bonus points if these are secretly equivalent to the usual notions of $\mathsf{QMA}$ and $\mathsf{QMA}(2)$ :)

The context is that in my application I want Arthur to implement, given $\ket{\psi}$ from Merlin, the Householder transformation $I - 2\ket{\psi}\bra{\psi}$. Unfortunately, I don't know how to do this given only $\ket{\psi}$, even if I'm allowed to corrupt $\ket{\psi}$ in the course of applying the transformation. If someone happens to know how to do this, this would also resolve my particular problem (although I think the question might be interesting independent of my application).

Edit - Martin Schwarz has pointed out that the part of the question below the line was proved to not be possible by Kumar and Paraoanu. The first part of the question remains valid though, I think.

Edit 2 (5/20) - When the unitary in question is only over a constant number of qubits, one possible approach is to have Merlin send the Choi-Jamiolkowski representation $\rho$ of $U$. Applying $U$ to a state $\sigma$ then corresponds to teleporting $\sigma$ into the first (block of) qubit(s) of $\rho$, where we abort if the teleportation fails. I'm not sure about soundness but we maybe can use a combination of the quantum de Finetti theorem and quantum state tomography to ensure soundness, following Beigi, Shor, and Watrous. However, both of these tools are prohibitively expensive for states over more than a constant number of qubits. Furthermore, teleportation only succeeds with with probability inverse exponential in the number of qubits (and we cannot correct because errors may not commute with the unitary). Thus, it seems to me that this does not, at least naively, work for unitaries over more than a constant number of qubits.

  • 3
    $\begingroup$ There is a no-go result about implementing a reflection about a given but unknown quantum state: arxiv.org/pdf/1105.4032.pdf $\endgroup$ Apr 19, 2020 at 19:50
  • $\begingroup$ Oh awesome - I'll edit the post accordingly, thanks! $\endgroup$
    – bean
    Apr 20, 2020 at 21:36
  • 2
    $\begingroup$ FYI, in this paper it is shown how to approximate a reflection around an unknown state given a number of copies of that state. $\endgroup$
    – smapers
    Apr 21, 2020 at 7:03
  • $\begingroup$ @bean, Can you modify your application to let Merlin do gate teleportation? That needs one-way communication. That way if Arthur is holding the state $ \psi$ Merlin can help do $U \psi$. That is to say, if your goal is to implement the Householder transform with the help of Merlin, I think that can be done. But not by sending the state $\psi$. $\endgroup$
    – Subhayan
    May 14, 2020 at 18:51
  • $\begingroup$ @Subhayan, yes, that would be fine. Is there a reference that I can look at to learn more about this? $\endgroup$
    – bean
    May 21, 2020 at 0:10


Your Answer

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