What do I mean by red herring, you might ask?
The etymology of the phrase may be the practice of saving a hunted fox by dragging a smoked herring across its trail – creating a new, useless scent trail. When smoked, herring turns bright red and is quite odoriferous. The latter trait made it possible to deliberately leave a strong trail on the ground to facilitate training hounds to track a scent. Having been so trained, hounds would readily follow the scent of the fish over that of the fox, allowing their quarry to escape.
Analogy clarification:: Fish –> factoring; Fox –> ever other application of QCs.
Scott Aaronson over at Shtetl-optimized recently posted a great description of Shor’s algorithm for non-specialists, in response to a request from JR Minkel, a Scientific American writer. Even though Scott has an alarming lack of musical taste he has few peers when it comes to describing complex technical issues to non-specialists.
The premise of Shor’s algorithm is this: take one (large) QC, one large product of prime numbers, shake well, out comes the factors of the large product of primes.
The algorithm is interesting because it produces this output (the factors) much faster than you can without a QC. It is also possibly interesting from the applications perspective because the problem it solves is important for certain types of code-breaking.
There is a particular type of encryption in use that uses the “hardness” of factoring large products of prime numbers to keep data secure. This particular approach would become vulnerable in a world with large QCs.
So let’s say we lived in a world with factoring machines available at Walmart. Would internet commerce collapse? Of course not. The most likely thing that would happen is that encryption software providers–the people who keep your credit card numbers secure–would change the “hard” part of their encryption to something that (1) wasn’t factoring and (2) was impervious to QCs. Is this technically possible? Absolutely. Also over time it’s likely that encryption — even retail encryption — will migrate over to quantum encryption.
So you might ask why the NSA cares about factoring at all. I can only speculate, but here are three possible reasons: (1) they have a mandate to be at the leading edge of understanding all things cryptanalytic, regardless of practical application; (2) the possibility that messages encrypted today have been stored somewhere and will be decrypted in 5-10 years with some new advanced technology (QC); (3) they are concerned that new non-factoring crypto algorithms will be developed.
Alright so why am I going on about this? The reason is that when asked what QCs are good at, many QC experts respond with the factoring example, when there are several other perfectly great quantum algorithms that would also fit the bill. Why the focus on factoring? I’m not entirely sure, but here are two possible reasons: (1) how the algorithm works is technically very interesting (when people understand it, they usually say, man that’s cool!); (2) usually researchers are financed by the NSA, so it’s self-serving to put a line in the intro to your paper that lists code-breaking as an application, and then every paper written about QC starts with the same sentence, and the meme takes hold.
Why does it matter that experts focus on factoring? There are two reasons. The first is that factoring isn’t interesting from the applications/commercial perspective. It is hard to imagine how a company could become successful building machines that did nothing but factor products of primes.
The second reason is that the application is very negative in the sense that it makes the world worse than it was before the tech was introduced. There is no social benefit to adding factoring to the list of things humans can do well (or if there is, I haven’t heard anyone mention it). This “no social benefit” issue is often ignored by scientists and technologists, but I think this is a huge mistake. Most people feel great about supporting technologies with a clear social benefit (cures for cancer, etc.); not so much for weapons.
I think it would do the whole QC field a lot of good if the people “out there” who aren’t experts could hear about the algorithms/applications that stand a chance of creating real value, like quantum simulation, or possibly applications of the recent NAND tree algorithm, or optimization.
Whenever people ask what QCs can do, there’s a tendency for people to respond with the factoring example, which I think is making it very difficult for any non NSA people (ie pretty much everybody) to get excited about QCs. It’s hard to get really excited about something that’s both commercially worthless and has no positive social upside.
If the scientists & management at Merck/Pfizer/Exxon/DE Shaw/Amgen/Corning/Dow etc. understood (in the same way the NSA understands Shor’s algorithm) that QCs could exponentially speed up their quantum chemistry calculations there would be 100s of millions of dollars of investment from these sources flowing into practical QC R&D. This is a wonderful thing called market pull which would benefit everybody in the QC field, even if you don’t personally care about actually getting these machines into the hands of end users.
In contrast to factoring, quantum simulation is both extremely commercially valuable (a large fraction of the world’s supercomputer cycles are currently spent solving the Schrodinger equation) and offers the possibility for huge social good (new clean energy sources, better medicines, cleaner chemical plants, etc.).
Maybe it’s time to put away the fish.