In 1993, Bernstein and Vazirani had demonstrated a superpolynomial query complexity speedup for quantum computers over classical computers. Charlie Bennett wrote a article in Nature in April 1993 about these new recent developements in quantum computing. In this article, Charlie wrote:
An early but probably vain hope was that quantum parallelism might provide a fast way of solving problems such as factoring or the travelling-salesman problem, which appear to be hard in the same way as finding a needle in a haystack is hard, that is because they involve a search for a successful solution among exponentially many candidates. A computer able to test all the candidates in parallel, and signal unambiguously if it found one that worked, would solve these problems exponentially faster than known methods.
It is easy to program a quantum computer to branch out into exponentially many computational paths; the difficult part is getting the paths to intefere in a useful way at the end, so that the answer comes out with a non-negligible probability. This difficulty is illustrated by the factoring problem above. Suppose the quantum computer is programmed to factor a 100-digit number by trying in parallel to divite it by all numbers of fifty digits or fewer. If any of the approximately 10^50 computation yeilds a zero remainder, it will in a sense have solved the problem. But if there is only one successful path, the interference pattern among all the paths, which determines the behaviour of the computer as a whole, will scarecely be affected. Quantum computers cannot amplify an answer found on a single computation to a detectable level because interference is an additive process, to which each path contributes only as much weight as it started out with.
How strange: to use brute force factoring as the example of a hard problem for quantum computing! Amazingly, Charlie wasn’t even the first to perform this strange analogy. Here is Greg Egan in the book Quarantine in 1992:
Let a computer smear-with the right kind of quantum randomness-and you create, in effect, a ‘parallel’ machine with an astronomical number of processors…All you have to do is to be sure that when you collapse the system, you choose the version that happened to find a needle in the mathematical haystack.
Which makes one wonder, why the heck were all these people thinking about factoring and quantum computers right before Shor’s discovery? Strange, no?
Maybe Shor read Bennett’s 1993 article and took up the gauntlet. Talking of gauntlets, here is a mitten for your readers.
Again, here is the mitten
The way I remember it, pre-Shor, factoring was always the “archetypal” quantum computing problem. Never the traveling salesman, which seems like it would be easier to “program” on a quantum computer, doesn’t it?