13
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Robin Kothari
    Aug 30, 2012 at 22:54
  • $\begingroup$ Yes, that's correct. Thank you for making this distinction. $\endgroup$
    – Lior Eldar
    Aug 31, 2012 at 6:04
  • $\begingroup$ 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)? $\endgroup$
    – Norbert Schuch
    Sep 2, 2012 at 11:19

3 Answers 3

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Could you give a brief explanation or reference to why the problem of estimating the smallest eigenvalue of $H$ is still QMA-hard? Thanks! $\endgroup$
    – Henry Yuen
    Sep 4, 2012 at 1:35
  • $\begingroup$ 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. $\endgroup$
    – Norbert Schuch
    Sep 4, 2012 at 7:00
  • $\begingroup$ Can you always assume that $h_i$ is a projector onto an eigenspace of a Pauli Hamiltonian? $\endgroup$
    – Henry Yuen
    Sep 4, 2012 at 16:57
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Norbert Schuch
    Sep 4, 2012 at 18:22
3
$\begingroup$

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)!

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Lior Eldar
    Sep 5, 2012 at 11:47
  • $\begingroup$ @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. $\endgroup$
    – Joe Fitzsimons
    Sep 5, 2012 at 14:59
  • $\begingroup$ 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 :-) $\endgroup$
    – Norbert Schuch
    Sep 5, 2012 at 18:25
  • $\begingroup$ @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). $\endgroup$
    – Norbert Schuch
    Sep 5, 2012 at 18:32
  • $\begingroup$ @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. $\endgroup$
    – Norbert Schuch
    Sep 5, 2012 at 18: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.