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

<p>Similarly, is there an analogue of <span class="math-container">$\mathsf{QMA}(2) = \mathsf{QMA}(k)$</span> where Merlin provides to Arthur <span class="math-container">$k = O(1)$</span> "independent" accesses to unitaries <span class="math-container">$U_1, \dots, U_k$</span>?</p>

<p>Bonus points if these are secretly equivalent to the usual notions of <span class="math-container">$\mathsf{QMA}$</span> and <span class="math-container">$\mathsf{QMA}(2)$</span> :) </p>

<hr>

<p>The context is that in my application I want Arthur to implement, given <span class="math-container">$\ket{\psi}$</span> from Merlin, the Householder transformation <span class="math-container">$I - 2\ket{\psi}\bra{\psi}$</span>. Unfortunately, I don't know how to do this given only <span class="math-container">$\ket{\psi}$</span>, even if I'm allowed to corrupt <span class="math-container">$\ket{\psi}$</span> 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). </p>

<p><strong>Edit</strong> - Martin Schwarz has pointed out that the part of the question below the line was proved to not be possible by <a href="https://arxiv.org/pdf/1105.4032.pdf" rel="nofollow noreferrer">Kumar and Paraoanu</a>. The first part of the question remains valid though, I think. </p>

<p><strong>Edit 2 (5/20)</strong> -  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 <span class="math-container">$\rho$</span> of <span class="math-container">$U$</span>. Applying <span class="math-container">$U$</span> to a state <span class="math-container">$\sigma$</span> then corresponds to teleporting <span class="math-container">$\sigma$</span> into the first (block of) qubit(s) of <span class="math-container">$\rho$</span>, 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 <a href="https://arxiv.org/abs/1004.0411" rel="nofollow noreferrer">Beigi, Shor, and Watrous</a>. 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. </p>

CC BY-SA 4.0
2020-04-19T19:50:34.207Z
There is a no-go result about implementing a reflection about a given but unknown quantum state: https://arxiv.org/pdf/1105.4032.pdf
Martin Schwarz
CC BY-SA 4.0
2020-04-20T21:36:01.353Z
Oh awesome - I'll edit the post accordingly, thanks!
bean
CC BY-SA 4.0
2020-04-21T07:03:23.217Z
FYI, in [this paper](https://arxiv.org/abs/1608.00281) it is shown how to *approximate* a reflection around an unknown state given a number of copies of that state.
smapers
CC BY-SA 4.0
2020-05-14T18:51:43.630Z
@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$.
Subhayan
CC BY-SA 4.0
2020-05-21T00:10:34.643Z
@Subhayan, yes, that would be fine. Is there a reference that I can look at to learn more about this?
bean
CC BY-SA 4.0
2020-05-21T00:30:31.313Z
I made an edit to the question regarding an approach that I think works when the unitary is only over a constant number of qubits. However, as far as I can tell this fails for general unitaries (which I'd like to be over polynomially many qubits).
bean
<complexity-classes><quantum-computing><quantum-information>
Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?
bean
# Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

(Asked by: username_0 on 2020-04-18)

$\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** - username_1 has pointed out that the part of the question below the line was proved to not be possible by [Kumar and Paraoanu](https://arxiv.org/pdf/1105.4032.pdf). 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](https://arxiv.org/abs/1004.0411). 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.

**Tags:** complexity-classes, quantum-computing, quantum-information

> **Comments:**
> **username_1**: There is a no-go result about implementing a reflection about a given but unknown quantum state: https://arxiv.org/pdf/1105.4032.pdf  
> **username_0**: Oh awesome - I'll edit the post accordingly, thanks!  
> **username_2**: FYI, in [this paper](https://arxiv.org/abs/1608.00281) it is shown how to *approximate* a reflection around an unknown state given a number of copies of that state.  
> **username_3**: @username_0, 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$.  
> **username_0**: @username_3, yes, that would be fine. Is there a reference that I can look at to learn more about this?  
> **username_0**: I made an edit to the question regarding an approach that I think works when the unitary is only over a constant number of qubits. However, as far as I can tell this fails for general unitaries (which I'd like to be over polynomially many qubits).  

---

## 0 answers

