Okay, quick, who can be the first to tell me what is drastically wrong with arXiv:0804.3076? (via rdv.) Winner gets a beer next time I see them. This is almost as fun as the game of trying to spot the error in papers claiming thethe discovery of a quantum algorithm for efficiently solving NP-complete problems.
O brave new quantum world!
Well first of all everyone knows SA stands for Simulated Annealing. I stopped reading after that egregious error.
Not all quantum algorithms give probabilistic results. Take, for instance the Deutsch-Jozsa algorithm, which is deterministic.
http://en.wikipedia.org/wiki/Deutsch-Jozsa_algorithm
How’s that? It’s 3/4ths of the way down the first page.
Geordie: either that or SA=sexaholics anonymous.
Wim: I’ve been told that there are actually communities where LaTeX has the same effect that Word has on our community, i.e. if it is written in LaTeX it must be crap.
Evan: Well that is certainly a misstatement they make. But it isn’t really the main bug in the paper.
Do I get a beer if I repeat what you said at RDV, ie. they don’t include fault tolerance in their constructions so you’d expect the thing would fail more or less like they say it does?
Ha! Geordie wins. Academic quantum computing lurkers, for shame, for shame, you’ve let D-Wave beat you to the answer. 🙂
Well I don’t know nothing about quantum computing, but the first sentence that rubbed me the wrong way was:
“A state vector denoting a basis vector in the entire 2L dimensional state space is written with a binary number, each digit representing the outcome of a measurement on a particular qubit.”
Later they require that the initial state be zero. It just seems like a very limited description of a state vector.
We are highly motivated by the promise of free beer.
Damn. Beaten by D-Wave again.
astephens gets a runner up beer: a near beer!
astephens: Simulated Annealing is the Chuck Norris of heuristics. Any sentence with Chuck Norris in it can be reformulated/improved by replacing Chuck with Simulated and Norris by Annealing.
For example: There is no theory of evolution, just a list of animals Simulated Annealing has allowed to live.
For example: There is no chin behind Simulated Annealing’s beard. There is only another fist.
For example: Simulated Annealing is so fast, it can run around the world and punch itself in the back of the head.
Damn I like that last one. Killer name for a paper.
astephens: Exactly.
The MS Word-like lay-out is definitely wrong.
The main argument in the paper seems to be that “operator imprecision errors propagate and grow during the course of a quantum computation”. It is true that a single logical error in SA can screw up the whole thing but this is not true for fault tolerant QEC circuits. Nor is it true that fault tolerant QEC doesn’t work for “the realistic case of small operator imprecision error in every gate”. It does work provided that the imprecision in every gate (over-rotation for example) is less than some amount.
Even if you pessimistically assume that SA can’t tolerate any logical errors FT QEC can be used to efficiently suppress the logical error rate until the algorithm has an acceptable success probability. This of course won’t be practical for large problem sizes or high physical error rates but this is not what the paper is talking about.
SA all they way. What is simulated annealing anyway?
SA all they way. What is simulated annealing anyway?
I think I get it Geordie. So like this? When taking the SAT, write simulated annealing for every answer. You will score over 8000.
Can I just say in defense of us academic QIP people that GTA $ came out today, and I saw several copies in our group this morning.
On a more serious note, this error seems to pop up all the time. I’m really shocked when I find out that a lot of people don’t realise that you can (and in some senses must) use a discrete set of gates for quantum computing.
Yeah, i stopped reading as soon as I found an obvious mistake.
For example: There is no theory of evolution, just a list of animals Simulated Annealing has allowed to live.
Wait a minute. The theory of evolution is simulated annealing *crosses arms*
I joined in this fun discussion a bit late. However, when I showed the paper to Todd Brun when it appeared on arxiv our first reaction was that, “Don’t these guys know about FT results?”
The near beer is collectible at any time from the great state of Washington, the upside down city of Melbourne, or any other potential gathering place of quantum obsessed peoples, like QIP etc.
Oh, and I’d like to see a fight between simulated annealing and picosat.
Eleanor that certainly deserves a beer!
Maybe I should consider buying the Etna Brewery to pay off my debts.
So, Dave, when are you coming to Melbourne? Or do I have to wing it to the Evergreen State to claim my near beer?
If only the price of hops wasn’t going through the roof!
You guys are much more blunt than I usually am (except with students :-). You’re also a lot more succinct.
This particular paper may be wrong, and the authors should be told that, but: as the field grows, and more engineers join, there are going to be more people who start with naive positions. The goal is not to run them off, but to teach them, so they can help us build these things :-).
P.S. “SA” is also Security Association.
Hey Dave. Can I get some kind of beer (I like ginger beer) for having sent the following note prior to your posts to some cryptographers who asked me about it? (I’ve now pointed them at your blog as well.)
—Eleanor
“This paper hasn’t gotten any attention any the quantum computing community as far as I can tell.
“I took a quick glance at the paper and am not surprised that people within the quantum computing community have ignored it. The authors spend a significant part of the paper describing simulation experiments showing that a popular quantum error correcting code is not robust against imprecision in the gates used. This result has long been known to the quantum computing community. Robust quantum computation requires using quantum error correction together with fault tolerant techniques; fault tolerant versions for the seven qubit code they use have long been known.
“The paper gives no indication that the authors are aware of any recent developments in quantum error correction and fault tolerant computation, let alone other approaches to robustness (e.g. decoherence-free subspaces, or the special robustness properties of adiabatic or topological quantum computing); their most recent citation on the subject of robustness is a 1998 paper or Nielsen and Chuang’s book of 2000 (though these references should have been sufficient for them to realize that the QECC code was known not to be robust and needed to be combined with fault tolerant techniques).
“If the paper gets much play in the crypto community, and there’s a good place for me to post a comment, let me know.”
Thanks, Dave!
Etna Brewery looks like it might be a good investment in these tough economic times!
No need to envy a good idea to wait until you need it I think in fact this job