This new paper
arXiv:1201.1707
An improved formalism for the Grover search algorithm,
by James M. Chappell (1,2) , M. A. Lohe (2), Lorenz von Smekal (3), Azhar Iqbal (1) and Derek Abbott (1)
- School of Electrical and Electronic Engineering, University of Adelaide 5005, Australia
- School of Chemistry and Physics, University of Adelaide, South Australia 5005, Australia
- Institut f¨ur Kernphysik, Technische Universit¨at Darmstadt, Schlossgartenstraße 9, 64289 Darmstadt, Germany
“rediscovers” the fixed-point version of Grover’s algorithm that I invented and presented in the following paper:
arXiv:1001.5200
An Adaptive, Fixed-Point Version of Grover’s Algorithm,
by Robert R. Tucci
The Chappell et al. paper has 24 references but does not refer to my paper, even though their paper and mine are eerily similar. Compare them yourself. With the excellent Google and ArXiv search engines, I would say there is zero probability that none of its five authors knew about my paper before they wrote theirs. (I have also written multiple posts in this blog describing my algorithm and linking to my arxiv paper about it, so nobody can claim that it was kept well hidden)
Addendum Jan 16, 2012:
Now that my emotions have calmed down, I was able to look at the Chappell et al paper more carefully. Our algorithms are more different than I initially thought. I’m not sure yet if one algorithm is faster or more accurate than the other. They may be about the same, or they may not be. More analysis will be required to answer this. I still think Chappell et al should have mentioned my paper. I would have done so if I had been in their shoes. After all, my paper was published 2 years earlier than theirs, and it solves the same problem, albeit using a different strategy.
Quantum Bayesian Networks 
Well, without having studied either paper in detail, I can see at least several flaws that disqualify your work from being cited by serious people:
1. You list no institutional affiliation.
2. You only cite 4 references, one of which is your own.
#2 is by far the more serious offense. Everyone knows that citations are the lifeblood of academia, and by declining to throw off a couple dozen cites of tangential relevance, you are refusing to play ball. Give a gift, get a gift!
Comment by Esteban — January 10, 2012 @ 5:36 am
1) “You list no institutional affiliation.” I am not an Academic. I guess you think that gives you or anyone else the right to steal my work.
2) If someone has done something before me, I do not omit to mention their work and claim that I am the first one to have done it. I feel morally obligated to mention their prior work and I always do.
I do not mention references just to brown nose their authors or to promote my friends like you do. I do not pad the list of references with marginally relevant ones and omit the ones I really used.
Comment by rrtucci — January 10, 2012 @ 6:19 am
Plagiarism is a serious offense. Since your paper is in arXiv it has been published (in any relevant sense of the term). If you haven’t done so already I’d email all the authors and confront them with the evidence – politely but firmly pointing out that they plagiarized your work as they omit any reference.
I noticed one of the authors is German. The German secretary of defense was recently forced to step down after it was found he plagiarized his Ph.D. thesis. His old alma mater also stripped him of the title.
I just bring this up to illustrate that this is not taken lightly in Germany – it’ll easily destroy a career.
Comment by Henning Dekant — January 10, 2012 @ 9:26 pm
Dear Robert,
We have only just seen your website, and have the following response
regarding our Grover paper:
1) It would have been best to email us directly in the first instance so
we could have replied sooner.
2) Your paper is timestamped 2010; however the results of our paper was initially
presented at the Cairns CQIQC conference in July 2008.
3) The intention of our paper is not a research article. It is a tutorial
paper. We now see this isn’t made very clear. Should we publish this further,
it will be made clear.
4) We had not seen your paper before. Our paper is based on the standard
Grover search, not a fixed point search. Hence, your paper did not come
to our attention, as we were not concerned with that specific topic and
indeed the fixed point search is not mentioned at all in our paper.
5) Your paper builds upon the fixed point Grover search (Grover 2005),
whereas our tutorial builds on the original Grover search (Grover 1996),
showing how to represent it using geometric algebra (GA). The exact
search we employ is the conventional one modifying the standard
Grover operator by replacing the scalar -1 with a complex phase
slowing the search slightly allowing the solution to be found reliably in
a finite number of steps. As is known, the Grover operator represents
reflections and rotations which we describe with GA as it is known to
be a natural formalism for this. Your approach, therefore, is qualitatively
different as firstly it has nothing to do with GA and secondly your
solution is obtained via the fixed point search.
6) In summary, your approach is based on a fixed-point iteration
(using infinite steps with diminishing phase changes) to reach the
exact solution whereas our approach uses the original Grover search
which changes the wave function phase in a discrete number of steps.
Our use of GA gives an efficient representation (without matrices
or complex numbers) and the ability to visualize these discrete phase
changes as 3D rotations.
Please confirm if this clarifies the situation.
Regards,
James Chappell et al.
Comment by James Chappell — January 12, 2012 @ 6:23 am
1) “Please confirm if this clarifies the situation.”
No it doesn’t.
2) “Your paper is timestamped 2010; however the results of our paper was initially presented at the Cairns CQIQC conference in July 2008.”
Your paper never mentions the Cairns Conference. I googled the following terms and got nothing:
cairns Chappell lohe grover algorithm
3) “We had not seen your paper before.”
I do not believe for one moment that 5 scientists who were able to locate 24 references, all less relevant than mine, were not able to locate mine using the Google or ArXiv search engines.
An obvious Google search of
grover “bloch sphere”
lists my work as the first entry. I hope you and your friends publish a new version in arxiv with a very clear apology or I am writing to the deans of each of your schools.
Well meaning people would have mentioned my paper and compared it with yours. My algorithm converges very, very quickly, so I think that to claim that yours is significantly better because it converges in a finite number of steps whereas mine takes an infinite number of steps, misses an important point. The point is that there were no efficient, “fixed-point” algorithms before mine. There was one “fixed point” algorithm by Grover that was very inefficient. “fixed point” includes converging in a finite number of steps.
Sincerely,
Dr. Robert Tucci
Comment by rrtucci — January 12, 2012 @ 12:15 pm
It’s also curious that you never use in your paper, not even in the introduction, the term “fixed point”. This term was introduced by Grover in this context, and has been used by all workers in the field ever since. Sounds to me that you were studiously trying to separate yourself from my paper, a paper which you claim you knew nothing about.
Comment by rrtucci — January 12, 2012 @ 12:32 pm
One more thing. Above, I used the word “efficiently” in a loose fashion. Let me be more precise. My algorithm still converges to an arbitrary precision in order sqrt(N) queries, which is optimal according to papers like
Grover’s quantum searching algorithm is optimal
Christof Zalka
http://arxiv.org/abs/quant-ph/9711070
If your algorithm converges exactly for all instances, then the best it can do it is also in order sqrt(N) queries. So there doesn’t seem to be any clear advantage to your algorithm. The Grover’s “pi/3” fixed-point algorithm does not take order sqrt(N) queries to coverge. I believe its complexity is worse than that.
Comment by rrtucci — January 12, 2012 @ 2:07 pm
revision:
I said:
“An obvious Google search of
grover “bloch sphere”
lists my work as the first entry.”
Google searches are tailored to each person and obviously change with time. Some people might not get it exactly as the first entry, as I’m getting it, but I’m pretty sure you’ll get it, at least today, on the first page of search results.
Comment by rrtucci — January 12, 2012 @ 4:46 pm
Just googled grover “bloch sphere”:
I get your paper as the fourth entry:
[PDF]
Quantum Computing – Lecture Notes
http://www.cs.washington.edu/homes/oskin/quantum-notes.pdf
Qubit – Wikipedia, the free encyclopedia
en.wikipedia.org/wiki/Qubit
Quantum gate – Wikipedia, the free encyclopedia
en.wikipedia.org/wiki/Quantum_gate
[PDF]
An Adaptive, Fixed-Point Version of Grover’s Algorithm
arxiv.org/pdf/1001.5200
Comment by Henning Dekant — January 12, 2012 @ 5:08 pm
I cannot believe someone working in the field can claim to be unaware of the Grover-Tucci (aka “Gucci”) algorithm.
Comment by Felix Bloch — January 12, 2012 @ 8:00 pm
Felix Bloch is reaching out from the grave to leave snide comments. This is getting exciting!
Comment by Henning Dekant — January 12, 2012 @ 8:12 pm
LOL
Felix Bloch, you should start a blog (or write a novel, or both)
Comment by rrtucci — January 12, 2012 @ 8:24 pm
What exactly is the issue here? It seems the Chappell paper is not fixed-point, but the Tucci paper is. Doesn’t that make them quite different?
Comment by With Luv from Grover — January 12, 2012 @ 11:37 pm
Do not let the bastards get away with this! In all seriousness, I think the next step is to file a lawsuit. Name the University of Adelaide as well as the individual authors. This will enable you to subpoena computer records. At the very least you will be able to prove that your paper was downloaded to U of A’s IP long before their publication date. That would leave them with some explaining to do! Maybe you will even hit the jackpot, and get the emails showing them conspiring to avoid crediting you.
Comment by Esteban — January 13, 2012 @ 4:35 am
commenter 13:
Sorry. For some mysterious reason, your comment got filtered out automatically as spam. I noticed it only now. I omitted your other 2 comments because of the expletives in them.
“fixed-point” is a term often used in topology. In our context, as used by Grover and most workers after him, a “fixed-point algorithm” is one that converges to an a priori stipulated, arbitrarily small neighborhood of the fixed point, aka the target state. Chappell seems to be claiming that his algorithm is not a fixed point algorithm. False, if one uses any reasonable definition of fixed-point algorithm.
Chappell seems to be claiming that his algorithm is very different from mine because it reaches the fixed point exactly instead of approximately. My algorithm converges to an arbitrary neighborhood of the target state in order sqrt(N) queries, so it is optimal according to the Zalka reference that I gave above. If Chappell’s algorithm also converges, it is also a fixed point algorithm, and, according to Zalka, cannot converge faster than in order sqrt(N) queries .
Chappell et al also seem to be claiming in their paper that their Grover algorithm is the first one to use 3D Bloch sphere geometry. False. I used 3D Bloch sphere geometry very frequently in mine.
Chappell also claims that none of the 5 authors knew about my paper. I think that is a lie, and not a very credible one, as I hope I have proven with the example of a google search for keywords grover and “bloch sphere”. I also used the arxiv search engine and searched for the same 2 keywords. result: My paper was the only paper with those 2 keywords in its abstract.
Chappell also claims that he first presented the identically same algorithm in a conference in 2008, but he has presented no verifiable proof of that claim. I think it is odd that 5 scientists took almost 4 years to publish in arxiv, a website which all of them have used many times before, and which publishes papers without delay. 5 scientists taking 4 years to publish a result, that is equivalent to one scientist like me taking 20 years to publish something.
Comment by rrtucci — January 14, 2012 @ 12:47 pm
Clarification
I looked up “fixed point” in wikipedia. According to wikipedia, the term has multiple meanings
http://en.wikipedia.org/wiki/Fixed_point
I’m a physicist and it seems that we use the term more loosely than mathematicians do. I’ve been using it very generally to mean the same as what mathematicians call a “limit point” or “cluster point”. Mathematicians use “fixed point” to mean a special type of limit point.
Anybody who has looked even briefly at my paper or read my blog posts about my algorithm will not be confused by this. I actually explicitly define what I mean by “fixed point algorithm” in the abstract of my paper.
I also want to add that the reason I believe my algorithm converges in order sqrt(N) queries is because it converges better than Grover’s classical algorithm, and that one converges (to a precision of 1/sqrt(N) but no better) in order sqrt(N) queries. Also, convergence in order sqrt(N) queries is the best you can do, according to Zalka.
Comment by rrtucci — January 14, 2012 @ 10:24 pm
[…] Vogelstein points me to this blog entry by Robert Tucci, diplomatically titled “Unethical or Really Dumb (or both) […]
Pingback by Fun fight over the Grover search algorithm « Statistical Modeling, Causal Inference, and Social Science — January 15, 2012 @ 8:20 pm
One problem that I see with their algorithm is that they have to count the number of queries very carefully or else they will overshoot. With my algorithm, one just has to do more than a certain number of queries.
Comment by rrtucci — January 16, 2012 @ 7:59 pm
test question:
All quantum computerists put their papers in arxiv. Chappell et al did too.
Search arxiv for any papers with the word “grover” in the title
http://arxiv.org/find/all/1/ti:+grover/0/1/0/all/0/1
Mine is number 12 on the list. Now, what is the probability that 5 australian scientists can read 12 titles?
Comment by rrtucci — January 17, 2012 @ 3:53 am
Let me quote Aram at Andrew Gelman’s blog. Says it all (about Aram)
aram says:
January 17, 2012 at 12:56 am
The Gucci comment was a joke. Note that it was signed by Felix Bloch.
Outsiders to quantum computing should be aware that these are both pretty minor papers (no offense…).
Comment by rrtucci — January 17, 2012 @ 1:35 pm
Why is there any argument here?
a) Tucci admits the algorithms are more different than he first thought, which is what Chappell maintained.
b) Nobody is under any obligation to cite an non-peer reviewed manuscript, especially if the content is different
and not relevant to the point at hand. As far as I can see, the Chappell paper is not making any claim of originality.
It is simply a tutorial that shows how to re-write the *original* Grover algorithm in a way that avoids bra-ket notation,
and simplifies it.
So what is all the big fuss about? Can everyone get some sleep now?
Comment by Felx the Cat — January 20, 2012 @ 5:14 am