I think if I had to choose an official question for quantum computing it would be the question “where are all the quantum algorithms?” I mean, every time I talk to someone outside of quantum computing it seems like this is the first question they ask (followed closely by “when is a large quantum computer going to be built?”)
Of course this question ignores a lot of hard work put in by a lot of people to come up with new quantum algorithms. Efficient quantum algorithms like solving Pell’s equation, estimating certain Gauss sums, solving hidden shift problems (more here), and solving certain non-abelian hidden subgroup problems, just for example. But when you mention these algorithms, you invariably find that these algorithms are just viewed as “variants of Shor’s algorithm.” In a sense this is true, but how true is it? Certainly many of the algorithms listed above require a lot more than “just Shor.”
In my mind it is useful to partition Shor’s algorithm for factoring into two parts (pun, pun, pun.) One part of Shor’s algorithm is the part of the algorithm that uses a fourier transform to efficiently solve a hidden subgroup problem. The second part is realizing that the solution of a hidden subgroup problem can be used to efficiently factor. What most people mean when they say that our quantum algorithms are “just Shor” is that they mimic the first part of the algorithm, i.e. they use a fourier transform. And indeed, all of the algorithms I list above use, in some manner, quantum fourier transforms. But they certainly don’t necessarily use them in the same, straightforward, manner they are used in Shor’s algorithm.
Last week I was in San Diego at a meeting on quantum algorithms. During part of the meeting we broke up into small groups and attempted to reason about where the field of quantum algorithms was going and then regroup to hear what each group had said. Wim van Dam made the following observation, which I found both funny and very striking. Wim noted that the Toffoli gate and the Hadamard gate are universal for quantum computing (see here for a simple proof by Dorit Aharonov.) The Toffoli gate is, of course, a “classical” gate which is universal for classical computation. The Hadamard gate is nothing more that the quantum fourier transform over the simplest of all groups, the cyclic group with two elements, Z_2. What does this mean? This means, as Wim said, that EVERY QUANTUM ALGORITHM IS NOTHING MORE THAN FOURIER TRANSFORMS AND CLASSICAL COMPUTATION! Ha! I love it!
Of course this points out the absurdity of in calling all algorithms after Shor, “like Shor.” Certainly they bear a resemblance, but isn’t this resemblance due to the fact that classical computations plus fourier transforms is all the quantum algorithms will ever be able to achieve? In one manner I ask this question in jest, but in another more serious manner, I do not think this view is all that crazy. That universal gate set of classical computing plus the Hadamard is, I think, a striking result. Might it be a key to understanding all our quantum algorithms and coming up with new ones? I think this is a great question and since I won’t be teaching until winter term I will have plenty of hours to mull it over!
O brave new quantum world!
(1)“where are all the quantum algorithms?â€
(2)“when is a large quantum computer going to be built?â€
Excellent questions.
“variants of Shor’s algorithm.†A reasonable point of view.
“EVERY QUANTUM ALGORITHM IS NOTHING MORE THAN FOURIER TRANSFORMS AND CLASSICAL COMPUTATION! Ha! I love it!” Well, every person is just a collection of protons, electrons and neutrons. So what. This does not answer questions (1) and (2)
I think another reason why many people are not very impressed by your list of non-Shor algorithms is that these algorithms are of little practical utility to most people (scientists included). Pell’s equation is quite esoteric. Most scientists and engineers have never heard of it. And those very special non-abelian hidden subgroup problems that you allude to, what is their practical utility to the average housewife, or to the average hardware or software engineer?
I think you should prepare a table with 3 columns (1) description of problem solved by the algorithm (be specific, don’t use vague, evasive terms like “certain hidden subgroup problems” or “just as an example” or “to name a few”) (2)advantage, if any, of solving this problem using a quantum computer instead of a classical computer (3)practical use of solving this problem.
You have given us only column (1).
Isn’t the theory of classical algorithms in a pretty sorry state too? All the new algorithms these days just seem to be variations on the whole FOR LOOP thing…
rrtucci, Grover’s algorithm gives an advantage over classical algorithms for solving a vast array of problems. Of course, this advantage doesn’t yield an exponential speed up, but it is a real speed up and it is useful.
Ah jeez rrtucci, now you’ve gone and pissed me off (well as pissed off as I get which is to say not very 🙂 )
“EVERY QUANTUM ALGORITHM IS NOTHING MORE THAN FOURIER TRANSFORMS AND CLASSICAL COMPUTATION! Ha! I love it!†Well, every person is just a collection of protons, electrons and neutrons. So what. This does not answer questions (1) and (2)
Dude, it was a joke. That is what the word “Ha!” means. And you forgot photons in your description of the consituents of every person.
All of the quantum algorithms I mentioned offer exponential speedups over the best known classical algorithms.
Pell’s equation is obscure? It’s at least a thousand years old, having been studied first in India in the seventh century CE and then later by Lagrange among others. It is also the basis of a public key cryptosystem which is broken by Hallgren’s quantum algorithm. It is certainly obscure to engineers, but obscure to mathematicians? I hope not.
My point, you obviously didn’t noticed, was not that these algorithms solve all important problems that the average joe will care about. In fact no where in my post do I even bring up this question. My point, you obviously didn’t notice, was that to call these other algorithms modifications of Shor is a great disservice, and I might say quite an insult, to the inventors of those algorithms. But don’t take my word for it, read the damn papers. Then you wouldn’t get so upset about my using “evasive terms” because you’d know what the hell I was talking about.
Sorry if my response is snarky, but I’ve had it up to here with people taking pot shots at quantum algorithms without actually lifting their lazy bones to actually read and understand the papers. Have we found an algorithm which surpasses Shor’s algorithm? Certainly no. Have we found interesting quantum algorithms, which offer exponential speedups over classical algorithms and are not variants of Shor’s algorithm Certainly yes. So to your,
“variants of Shor’s algorithm.†A reasonable point of view.
I call BS.
More algorithms would be nice, but what I would really like to see are more applications of the algorithms we already have.
Most humans are excited by applications, not algorithms. A good application captures the imagination and makes it easy to understand why the technology might be important.
The quantum chemistry applications (at least one of these was published in Science a while back) are a good example of this. At their heart all of these are just phase estimation. But phase estimation by itself is over the head of 100 \pm \eps % of the world’s population. A new tool that can help scientists understand disease, anybody can understand.
Another issue that I would love to see change is that most QC people ignore the fact that NP-complete style problems are naturally suited to certain quantum computational models, like AQC and its variants. Even square root speedups matter ALOT for big problems, and NP-complete problems are everywhere.
hi Geordie,
“The quantum chemistry applications (at least one of these was published in Science a while back) are a good example of this.”
do you mean ‘Simulated Quantum Computation of Molecular Energies’? [doi:10.1126/science.1113479]
Hi Ron,
Yes that’s the one I’m referring to. It provides a method to calculate ground state energies of molecules as functions of fixed (classical) nuclear positions.
From the Introduction of “Introduction to Computational Chemistry”, Frank Jensen (p.4): “Chemistry is knowing the energy as a function of the nuclear coordinates.”
hi Geordie,
is Trinity prototype already suitable to solve this kind of quantum chemistry computational problem?
Pontiff, I found your post interesting as I have asked (myself) the first question often.
Other than your post, which admits to being incomplete, do you (or anyone else here) know of a source where the collected successes in finding potential uses for a quantum computer are compiled?
I have started searching the links on the arxiv, but it is already becoming tedious…
Much obliged.
Hey Thumble, I don’t know of a good up to date listing of quantum algorithms! Sounds like someone should write one or at least provide a wiki to collect them in some nice manner that is updatible.
Well, there are already to quantum wikis: quantiki and qwiki. I’m not sure whether either has such a page, but it would certainly be a worthwhile addition.
Here is the quantiki page on algorithms (I didn’t do it). It may be incomplete, but it’s a start…
http://www.quantiki.org/wiki/index.php/Category:Quantum_Algorithms
Really helpful submit!
First we define a function to make a 3-qubit QFT quantum program. This is a mix of Hadamard and CPHASE gates, with a final bit reversal correction at the end consisting of a single SWAP gate.