<p>A paper which makes strong claims ought to be sufficiently clearly written for readers to  check those claims. I don't find the current (<a href="http://arxiv.org/pdf/1211.3405v2.pdf">http://arxiv.org/pdf/1211.3405v2.pdf)</a> version of this paper expresses its results clearly enough to make a concrete assessment.</p>

<p>But if it were, I'd want to check:</p>

<p>a) whether the quantum part of the algorithm solely consists of Pauli measurements on a cluster state. </p>

<p>Such a measurement-based quantum computation can be simulated using polytime classical processing (due to the Gottesman-Knill theorem), and hence one would have a solely <em>classical</em> superfast search algorithm.</p>

<p>b) whether the oracle used might be of a different type to the oracle in Grover's algorithm.</p>

<p>The oracle in Grover's algorithm has the property that it must <em>recognise</em> the target string, but, crucially, it does not need to <em>know</em> this string in advance, or be able to calculate that target string in polytime (see Nielsen and Chuang chapter 6 for a discussion of this).</p>

<p>Unless P=NP, an oracle which <em>knows</em> the target string needs to be more powerful than one which merely <em>recognises</em> it (consider a search for a solution of an NP-hard problem). I'd want to check whether the oracle here is of the "recognising" or "knowing" kind. If it is the second, then the extra computational power in the oracle might, on its own, explain any exponential improvement reported.</p>

CC BY-SA 3.0
2013-03-22T12:24:54.680Z
The authors have withdrawn their preprint from the arxiv. http://arxiv.org/abs/1211.3405v3
Dan Browne
CC BY-SA 3.0
2012-12-07T17:50:30.527Z
2012-12-07T18:15:24.983Z
2012-12-07T18:15:24.983Z
Dan Browne
<p>I think that this is an example of <a href="https://cstheory.meta.stackexchange.com/q/274/248">a preprint on a crank-friendly topic</a> (specifically it asks: "Is the new claimed [revolutionary result] correct?"). But there are specific remarks that can be made about the technical problems of the manuscript in question.</p>

<p>In the second-to-last paragraph on page 1, they indicate that the "measurement angles" are just going to be from the set $\{0,\pi\}$, so that they measure only the states $| \pm \rangle$ &mdash; or in the language of observables: only the operators $\pm X$ are measured. Echoing Dan's earlier answer, the cluster state is a stabilizer state. It has been known since at least 1997 (from <a href="http://arxiv.org/abs/quant-ph/9705052" rel="nofollow noreferrer">Daniel Gottesman's introduction of the stabilizer formalism</a>) that Pauli observable measurements on stabilizer states can be simulated efficiently. Indeed, the natural decision problems arising from such simulations belongs not only to $\mathsf P$, but to the rather low class $\mathsf \oplus\mathsf L \subseteq \mathsf{NC^2} \subseteq \mathsf P$, by <a href="http://arxiv.org/abs/quant-ph/0406196" rel="nofollow noreferrer">Aaronson+Gottesman (2004)</a>. Any such MBQC algorithm <em>cannot possibly</em> achieve an exponential speedup over a generic classical algorithm, let alone over other quantum algorithms.</p>

<p>Furthermore, they do not even describe how the black box for marking elements (or a suitable substitute) is to be implemented in the MBQC algorithm. They describe something along these lines in Eqns.&nbsp;(4) and&nbsp;(6), but they don't even describe how the angles are chosen, nor how it corresponds to any circuit which marks elements. They show other signs of confusion about Grover's algorithm, as they claim that the "tagging [performed by the oracle] is one to one, i.e. there is a single unique tag for each and every element in the search space". I don't know what that is supposed to mean, but it doesn't sound like the black box in Grover's algorithm to me.</p>

<p>So, with some inspection, I can say that it doesn't seem even to describe how it is meant to represent Grover's algorithm, and there is reason to believe it could never actually do so (nor surpass it) anyway.</p>

CC BY-SA 3.0
2012-12-10T14:55:31.067Z
2012-12-10T14:55:31.067Z
2017-03-16T15:45:13.547Z
Niel de Beaudrap
<p><a href="http://arxiv.org/abs/1211.3405" rel="noreferrer">http://arxiv.org/abs/1211.3405</a>   </p>

<p>The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm  </p>

<p>If this recent paper is true, it seems like a major advance for measurement based quantum computing.  The claim is based on numerical evidence, rather than a formal proof.  Is this as important/revolutionary as I think it is?</p>

<p>This makes me wonder: Is there a known relation between the speed of gate-based quantum computing and the speed of measurement-based quantum computing?</p>

CC BY-SA 3.0
2012-11-19T11:15:43.457Z
MBQC and the circuit model can each simulate the other with constant overhead. Ultimately an MBQC can be viewed as a circuit model computation, so it can never offer a speed up over what can be achieved directly in the circuit model.
Joe Fitzsimons
<cc.complexity-theory><ds.algorithms><quantum-computing>
Major advance for measurement based quantum computing?
Jim Graber
# Major advance for measurement based quantum computing?

(Asked by: username_0 on 2012-11-17)

<http://arxiv.org/abs/1211.3405>

The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm

If this recent paper is true, it seems like a major advance for measurement based quantum computing. The claim is based on numerical evidence, rather than a formal proof. Is this as important/revolutionary as I think it is?

This makes me wonder: Is there a known relation between the speed of gate-based quantum computing and the speed of measurement-based quantum computing?

**Tags:** cc.complexity-theory, ds.algorithms, quantum-computing

> **Comments:**
> **username_1**: MBQC and the circuit model can each simulate the other with constant overhead. Ultimately an MBQC can be viewed as a circuit model computation, so it can never offer a speed up over what can be achieved directly in the circuit model.  

---

## 2 answers

### Answer by username_2 on 2012-12-07. Score: 8

A paper which makes strong claims ought to be sufficiently clearly written for readers to check those claims. I don't find the current ([http://arxiv.org/pdf/1211.3405v2.pdf)](http://arxiv.org/pdf/1211.3405v2.pdf) version of this paper expresses its results clearly enough to make a concrete assessment.

But if it were, I'd want to check:

a) whether the quantum part of the algorithm solely consists of Pauli measurements on a cluster state.

Such a measurement-based quantum computation can be simulated using polytime classical processing (due to the Gottesman-Knill theorem), and hence one would have a solely *classical* superfast search algorithm.

b) whether the oracle used might be of a different type to the oracle in Grover's algorithm.

The oracle in Grover's algorithm has the property that it must *recognise* the target string, but, crucially, it does not need to *know* this string in advance, or be able to calculate that target string in polytime (see Nielsen and Chuang chapter 6 for a discussion of this).

Unless P=NP, an oracle which *knows* the target string needs to be more powerful than one which merely *recognises* it (consider a search for a solution of an NP-hard problem). I'd want to check whether the oracle here is of the "recognising" or "knowing" kind. If it is the second, then the extra computational power in the oracle might, on its own, explain any exponential improvement reported.

> **Comments:**
> **username_2**: The authors have withdrawn their preprint from the arxiv. http://arxiv.org/abs/1211.3405v3  

---

### Answer by username_3 on 2012-12-10. Score: 6

I think that this is an example of [a preprint on a crank-friendly topic](https://cstheory.meta.stackexchange.com/q/274/248) (specifically it asks: "Is the new claimed [revolutionary result] correct?"). But there are specific remarks that can be made about the technical problems of the manuscript in question.

In the second-to-last paragraph on page 1, they indicate that the "measurement angles" are just going to be from the set $\{0,\pi\}$, so that they measure only the states $| \pm \rangle$ — or in the language of observables: only the operators $\pm X$ are measured. Echoing Dan's earlier answer, the cluster state is a stabilizer state. It has been known since at least 1997 (from [Daniel Gottesman's introduction of the stabilizer formalism](http://arxiv.org/abs/quant-ph/9705052)) that Pauli observable measurements on stabilizer states can be simulated efficiently. Indeed, the natural decision problems arising from such simulations belongs not only to $\mathsf P$, but to the rather low class $\mathsf \oplus\mathsf L \subseteq \mathsf{NC^2} \subseteq \mathsf P$, by [Aaronson+Gottesman (2004)](http://arxiv.org/abs/quant-ph/0406196). Any such MBQC algorithm *cannot possibly* achieve an exponential speedup over a generic classical algorithm, let alone over other quantum algorithms.

Furthermore, they do not even describe how the black box for marking elements (or a suitable substitute) is to be implemented in the MBQC algorithm. They describe something along these lines in Eqns. (4) and (6), but they don't even describe how the angles are chosen, nor how it corresponds to any circuit which marks elements. They show other signs of confusion about Grover's algorithm, as they claim that the "tagging [performed by the oracle] is one to one, i.e. there is a single unique tag for each and every element in the search space". I don't know what that is supposed to mean, but it doesn't sound like the black box in Grover's algorithm to me.

So, with some inspection, I can say that it doesn't seem even to describe how it is meant to represent Grover's algorithm, and there is reason to believe it could never actually do so (nor surpass it) anyway.


---

