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?
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) 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.
I think that this is an example of a preprint on a crank-friendly topic (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) 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). 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.
