<p>It is possible to restrict the QMA verifier to single-qubit measurements and classical pre- and postprocessing (with randomness) while keeping QMA-completeness. </p>

<p>To see why, take any class of $k$-local QMA-complete Hamiltonians on qubits. By adding a constant of order $\mathrm{poly}(n)$ and rescaling with a $1/\mathrm{poly}(n)$ factor, the Hamiltonian can be brought into the form
$$
H=\sum_i w_i h_i\ ,
$$
where $w_i&gt;0$, $\sum_i w_i=1$, and $h_i = \tfrac12(\mathrm{Id}\pm P_i)$, where $P_i$ is a product of Paulis. Estimating the smallest eigenvalue of $H$ up to accuracy $1/\mathrm{poly}(n)$ is still QMA-hard.</p>

<p>We can now build a circuit which only uses single-qubit measurements which, given a state $|\psi\rangle$, accepts with probability $1-\langle\psi|H|\psi\rangle$ (which by construction is between $0$ and $1$).  To this end, first randomly pick one of the $i$'s according to the distribution $w_i$. Then, measure each of the Paulis in $P_i$, and take the parity $\pi$ of the outcomes, which is now related to $\langle\psi|h_i|\psi\rangle$ via
$$
\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .
$$
The circuit now outputs $1-\langle\psi|h_i|\psi\rangle$, and the output is therefore distributed according to $\langle\psi|H|\psi\rangle$.  </p>

<p>This is, if we picked a yes-instance of the (QMA-complete) local Hamiltonian problem, there is a state $|\psi\rangle$ such that this verifier will accept with some probability $\ge a$, while otherwise any state will be rejected with probability $\le b$, with $a-b&gt;1/\mathrm{poly}(n)$.  The variant of QMA where the verifier is restricted to one-qubit measurements is therefore QMA-complete for some $1/\mathrm{poly}(n)$ gap.  Finally, this version of QMA can be amplified using just the conventional amplification techniques for QMA, which finally proves it is QMA-complete independent of the gap (within the same range as QMA).</p>

CC BY-SA 3.0
2012-09-04T01:35:40.313Z
Could you give a brief explanation or reference to why the problem of estimating the smallest eigenvalue of $H$ is still QMA-hard? Thanks!
Henry Yuen
CC BY-SA 3.0
2012-09-04T07:00:10.953Z
We start from a Hamiltonian $H'$ for which this problem [up to $\epsilon=1/\mathrm{poly}(n)$] is QMA-complete, an change it into a Hamiltonian $H=x(H'+y)$, where $x=1/\mathrm{poly}(n)$ and $y=\mathrm{poly}(n)$, so estimating the G.S. energy of $H$ up to accuracy $x\epsilon=1/\mathrm{poly}(n)$ is still QMA-hard.
Norbert Schuch
CC BY-SA 3.0
2012-09-04T16:57:41.840Z
Can you always assume that $h_i$ is a projector onto an eigenspace of a Pauli Hamiltonian?
Henry Yuen
CC BY-SA 3.0
2012-09-04T18:22:39.213Z
Well, each term $h'$ in the original Hamiltonian can be written as a sum of $4^k$ Pauli products ($4^k=\mathrm{poly}(n)$ for $k=O(\log(n))$), and the prefactor of each Pauli product $P_i$ is $\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$.
Norbert Schuch
CC BY-SA 3.0
2012-09-03T16:38:18.247Z
2012-09-03T16:38:18.247Z
Norbert Schuch
<p>My interpretation of the question is that you are asking, may we assume that the verifier circuit for a QMA protocol uses only single-qubit measurements?  (The idea being that the prover sends you both the quantum proof and the quantum cluster state needed to implement the original verification circuit by "one-way quantum computing.")  </p>

<p>The problem, of course, is that the prover might not send you a valid cluster state at all.  So the verifier would have to test the received state to make sure that it really is a cluster state.  The verifier does this by making single-qubit measurements and checking the correlations satisfy the necessary stabilizer checks.  Since such testing is destructive to the state, there would need to be a procedure where the verifier is given many copies of the state, checks most of them, and uses a random one for the computation.  Do polynomially many copies suffice?  </p>

<p>I don't think this is a known theorem.  I don't see an obvious counterexample (with a minute's thought), so it might be believable.  Known proof technology on testing states seems like it should be enough to check this.  For example, see Matthew McKague's paper arXiv:1010.1989 [quant-ph].  If you get a proof working, send the paper to QIP (deadline Oct. 5)!  </p>

CC BY-SA 3.0
2012-08-30T23:27:08.580Z
2012-08-30T23:27:08.580Z
Anonymous
<p>Perhaps I am misunderstanding this question. If you are asking whether you can implement the verifier circuit for a problem in QMA using a measurement based computation, where Merlin supplies the input layer, and Arthur supplies all further qubits in the resource state and entangles both sets of qubits before measurements commence, then the answer is trivially yes. This follows directly from the fact that any quantum circuit can be implemented as a measurement based computation whether you care about classical or quantum input. </p>

<p>You'll notice that in most papers on measurement based computation input sites are generally identified separately from the other sites, and this is why (i.e. specifically to deal with the case of quantum input).</p>

CC BY-SA 3.0
2012-09-05T11:47:18.930Z
Actually I'm unclear on this point.  In the papers of measurement-based computation I've looked at, the transformation is from any BQP circuit with classical input, to a one-way computation circuit starting from the cluster state.  That is, to say, it is NOT described as a transformation taking any arbitrary unitary circuit U to a measurement-based circuit U_1, regardless of the input.  While the complexity question I had asked, is now resolved following Norbert's answer, I would still like to understand this point.
Lior Eldar
CC BY-SA 3.0
2012-09-05T14:59:58.763Z
@LiorEldar: Then you should look at the original Raussendorf and Briegel paper or the Raussendorf, Browne and Briegel one. They explicitly construct circuits one gate at a time, showing that each measurement pattern implements a given gate on the input layer, which can be in an arbitrary state. You most definitely can implement arbitrary circuits on arbitrary inputs.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-05T18:25:00.153Z
Lior was actually around here in Aachen when we discussed this, and one way to understand the question is based on this idea: Could Merlin provide the proof built into an (untrusted) cluster state, and Arthur uses his one-qubit measurements to either verify the cluster or verify the proof using MBQC? (Maybe one could use similar ideas as in blind comp. where error correction is used?) Unfortunately, one doesn't need this nice idea to prove QMA-hardness. ;-(  However, I believe it is still an interesting question to understand if this would work, and you would be the expert to show this :-)
Norbert Schuch
CC BY-SA 3.0
2012-09-05T18:32:21.873Z
@Lior: If you want to use MBQC to verify the input, you of course also need to 2-qubit gates in addition to the one-qubit measurements (since you need to entangle the input with your cluster state).
Norbert Schuch
CC BY-SA 3.0
2012-09-05T18:36:51.943Z
@Joe: BTW, the same question for BQP (can we run BQP using 1-qubit measurements using an untrusted cluster state) is of course still open, and it feels to me that the ideas used in blind computation might be the way to go.
Norbert Schuch
CC BY-SA 3.0
2012-09-06T04:17:39.367Z
@Norbert: Ah, the issue of the cluster state being untrusted wasn't entirely clear from the question. Yes, this should be entirely possible using any verification scheme which works for blind QC (such as arXiv:1203.5217). The way the BQC protocol works, if you consider the post-selected case, there is a symmetry between preparation and measurement. The only difference you need to make is where there are dummy qubits (prepared in Z eigenstates). Instead these are prepared in the same way as the other qubits, but measured in Z (this is essentially just time reversing the circuit).
Joe Fitzsimons
CC BY-SA 3.0
2012-09-06T04:20:23.263Z
@NorbertSchuch You can actually simplify the scheme by removing the randomness in the preparation step, and it should still work. That said, I should also point out that Matt McKague has done some nice work on self-testing of graph states (see   arXiv:1010.1989) which is extremely relevant.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-05T08:45:25.610Z
2012-09-05T08:45:25.610Z
Joe Fitzsimons
<p>The theory of cluster-state computation is well-established by now, showing that any BQP circuit can be modified so it uses only single qubit quantum gates, possibly classically controlled, provided ample supply of a state known as the "cluster state" - which is a simple to produce stablizer state.</p>

<p>My question is: is a similar notion known for quantum verification - i.e.
can one replace QMA circuits with classically controlled 1-qubit gates, possibly using some "special state"?
At least initially, I'm unclear on why the cluster state can even work in this case.</p>

CC BY-SA 3.0
2012-08-30T22:54:28.417Z
If I understand correctly, is the problem that in QMA Merlin hands you a quantum proof that you have to somehow incorporate into the model? In other words, if it was QCMA instead of QMA, where Merlin just hands you a classical string, then we could just use the known results for BQP, right?
Robin Kothari
CC BY-SA 3.0
2012-08-31T06:04:26.613Z
Yes, that's correct.  Thank you for making this distinction.
Lior Eldar
CC BY-SA 3.0
2012-09-02T11:19:00.720Z
To start with, one could ask the same question for BQP: Can we perform any quantum computation given the power to do 1-qubit measurements, and given a supply of untrusted cluster states (or some other suitable state)?
Norbert Schuch
<quantum-computing>
One-way quantum verification
Lior Eldar
# One-way quantum verification

(Asked by: username_0 on 2012-08-30)

The theory of cluster-state computation is well-established by now, showing that any BQP circuit can be modified so it uses only single qubit quantum gates, possibly classically controlled, provided ample supply of a state known as the "cluster state" - which is a simple to produce stablizer state.

My question is: is a similar notion known for quantum verification - i.e.
can one replace QMA circuits with classically controlled 1-qubit gates, possibly using some "special state"?
At least initially, I'm unclear on why the cluster state can even work in this case.

**Tags:** quantum-computing

> **Comments:**
> **username_1**: If I understand correctly, is the problem that in QMA Merlin hands you a quantum proof that you have to somehow incorporate into the model? In other words, if it was QCMA instead of QMA, where Merlin just hands you a classical string, then we could just use the known results for BQP, right?  
> **username_0**: Yes, that's correct.  Thank you for making this distinction.  
> **username_2**: To start with, one could ask the same question for BQP: Can we perform any quantum computation given the power to do 1-qubit measurements, and given a supply of untrusted cluster states (or some other suitable state)?  

---

## 3 answers

### Answer by username_2 on 2012-09-03. Score: 7 | Accepted answer

It is possible to restrict the QMA verifier to single-qubit measurements and classical pre- and postprocessing (with randomness) while keeping QMA-completeness.

To see why, take any class of $k$-local QMA-complete Hamiltonians on qubits. By adding a constant of order $\mathrm{poly}(n)$ and rescaling with a $1/\mathrm{poly}(n)$ factor, the Hamiltonian can be brought into the form
$$
H=\sum\_i w\_i h\_i\ ,
$$
where $w\_i>0$, $\sum\_i w\_i=1$, and $h\_i = \tfrac12(\mathrm{Id}\pm P\_i)$, where $P\_i$ is a product of Paulis. Estimating the smallest eigenvalue of $H$ up to accuracy $1/\mathrm{poly}(n)$ is still QMA-hard.

We can now build a circuit which only uses single-qubit measurements which, given a state $|\psi\rangle$, accepts with probability $1-\langle\psi|H|\psi\rangle$ (which by construction is between $0$ and $1$). To this end, first randomly pick one of the $i$'s according to the distribution $w\_i$. Then, measure each of the Paulis in $P\_i$, and take the parity $\pi$ of the outcomes, which is now related to $\langle\psi|h\_i|\psi\rangle$ via
$$
\langle\psi|h\_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .
$$
The circuit now outputs $1-\langle\psi|h\_i|\psi\rangle$, and the output is therefore distributed according to $\langle\psi|H|\psi\rangle$.

This is, if we picked a yes-instance of the (QMA-complete) local Hamiltonian problem, there is a state $|\psi\rangle$ such that this verifier will accept with some probability $\ge a$, while otherwise any state will be rejected with probability $\le b$, with $a-b>1/\mathrm{poly}(n)$. The variant of QMA where the verifier is restricted to one-qubit measurements is therefore QMA-complete for some $1/\mathrm{poly}(n)$ gap. Finally, this version of QMA can be amplified using just the conventional amplification techniques for QMA, which finally proves it is QMA-complete independent of the gap (within the same range as QMA).

> **Comments:**
> **username_3**: Could you give a brief explanation or reference to why the problem of estimating the smallest eigenvalue of $H$ is still QMA-hard? Thanks!  
> **username_2**: We start from a Hamiltonian $H'$ for which this problem [up to $\epsilon=1/\mathrm{poly}(n)$] is QMA-complete, an change it into a Hamiltonian $H=x(H'+y)$, where $x=1/\mathrm{poly}(n)$ and $y=\mathrm{poly}(n)$, so estimating the G.S. energy of $H$ up to accuracy $x\epsilon=1/\mathrm{poly}(n)$ is still QMA-hard.  
> **username_3**: Can you always assume that $h_i$ is a projector onto an eigenspace of a Pauli Hamiltonian?  
> **username_2**: Well, each term $h'$ in the original Hamiltonian can be written as a sum of $4^k$ Pauli products ($4^k=\mathrm{poly}(n)$ for $k=O(\log(n))$), and the prefactor of each Pauli product $P_i$ is $\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$.  

---

### Answer by username_4 on 2012-08-30. Score: 3

My interpretation of the question is that you are asking, may we assume that the verifier circuit for a QMA protocol uses only single-qubit measurements? (The idea being that the prover sends you both the quantum proof and the quantum cluster state needed to implement the original verification circuit by "one-way quantum computing.")

The problem, of course, is that the prover might not send you a valid cluster state at all. So the verifier would have to test the received state to make sure that it really is a cluster state. The verifier does this by making single-qubit measurements and checking the correlations satisfy the necessary stabilizer checks. Since such testing is destructive to the state, there would need to be a procedure where the verifier is given many copies of the state, checks most of them, and uses a random one for the computation. Do polynomially many copies suffice?

I don't think this is a known theorem. I don't see an obvious counterexample (with a minute's thought), so it might be believable. Known proof technology on testing states seems like it should be enough to check this. For example, see Matthew McKague's paper arXiv:1010.1989 [quant-ph]. If you get a proof working, send the paper to QIP (deadline Oct. 5)!


---

### Answer by username_5 on 2012-09-05. Score: 2

Perhaps I am misunderstanding this question. If you are asking whether you can implement the verifier circuit for a problem in QMA using a measurement based computation, where Merlin supplies the input layer, and Arthur supplies all further qubits in the resource state and entangles both sets of qubits before measurements commence, then the answer is trivially yes. This follows directly from the fact that any quantum circuit can be implemented as a measurement based computation whether you care about classical or quantum input.

You'll notice that in most papers on measurement based computation input sites are generally identified separately from the other sites, and this is why (i.e. specifically to deal with the case of quantum input).

> **Comments:**
> **username_0**: Actually I'm unclear on this point.  In the papers of measurement-based computation I've looked at, the transformation is from any BQP circuit with classical input, to a one-way computation circuit starting from the cluster state.  That is, to say, it is NOT described as a transformation taking any arbitrary unitary circuit U to a measurement-based circuit U_1, regardless of the input.  While the complexity question I had asked, is now resolved following Norbert's answer, I would still like to understand this point.  
> **username_5**: @LiorEldar: Then you should look at the original Raussendorf and Briegel paper or the Raussendorf, Browne and Briegel one. They explicitly construct circuits one gate at a time, showing that each measurement pattern implements a given gate on the input layer, which can be in an arbitrary state. You most definitely can implement arbitrary circuits on arbitrary inputs.  
> **username_2**: Lior was actually around here in Aachen when we discussed this, and one way to understand the question is based on this idea: Could Merlin provide the proof built into an (untrusted) cluster state, and Arthur uses his one-qubit measurements to either verify the cluster or verify the proof using MBQC? (Maybe one could use similar ideas as in blind comp. where error correction is used?) Unfortunately, one doesn't need this nice idea to prove QMA-hardness. ;-(  However, I believe it is still an interesting question to understand if this would work, and you would be the expert to show this :-)  
> **username_2**: @Lior: If you want to use MBQC to verify the input, you of course also need to 2-qubit gates in addition to the one-qubit measurements (since you need to entangle the input with your cluster state).  
> **username_2**: @Joe: BTW, the same question for BQP (can we run BQP using 1-qubit measurements using an untrusted cluster state) is of course still open, and it feels to me that the ideas used in blind computation might be the way to go.  
> **username_5**: @Norbert: Ah, the issue of the cluster state being untrusted wasn't entirely clear from the question. Yes, this should be entirely possible using any verification scheme which works for blind QC (such as arXiv:1203.5217). The way the BQC protocol works, if you consider the post-selected case, there is a symmetry between preparation and measurement. The only difference you need to make is where there are dummy qubits (prepared in Z eigenstates). Instead these are prepared in the same way as the other qubits, but measured in Z (this is essentially just time reversing the circuit).  
> **username_5**: @NorbertSchuch You can actually simplify the scheme by removing the randomness in the preparation step, and it should still work. That said, I should also point out that Matt McKague has done some nice work on self-testing of graph states (see   arXiv:1010.1989) which is extremely relevant.  

---

