8

Peter Shor has given wonderful accounts of the development of his algorithm, with a lot of detail on the activity in the field at around the early-mid 90's. He's been very free about emphasizing that his algorithm was inspired by Umesh Vazirani's ~1993 presentation at Bell Labs and especially by Dan Simon's later-developed algorithm, but I'm curious if, in particular, he conjectured that a quantum computer could factor integers ex nihilo and then developed his algorithm, or, alternatively, if the idea that quantum computers could maybe factor integers was already expressed and was part of the zeitgeist at the time...

Did anyone (...in writing) propose that a quantum computer could efficiently factor large integers before Shor developed his algorithm, or was Shor alone in guessing that it could work (and then solving it?)

The hardness of factoring and its cryptographic applications were well established by the early 90's, with PGP's 1991 release of RSA on the early, hacky world wide web. Also, quantum computers were definitely starting to be "a thing" around then as well - Greg Egan's 1992 Sci-Fi novel Quarantine has a lovely quote presupposing a quantum computer's capabilities to evaluate function in superposition.

When Deutsch and Jozsa describe their algorithm in 1992 they do mention factoring in the context of distinguishing between search problems and function evaluation problems on a classical, deterministic computer and a probabilistic computer. But, they don't seem to explicitly suppose that a quantum computer could factor large numbers.

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83

1 Answers1

2

I think the best answer we can say now is that nothing was written down formally in any peer-reviewed paper before Shor's discovery; however, there were some ideas floating around on some Usenet forums just slightly before then. Most noteworthy, a pair of Usenet postings by Kevin Brown with a "joke" headline entitled "Can Schrodinger's Cat Factor Numbers" was published in late February, 1994, which is a couple of months before Shor's breakthrough in mid-April of that year. Brown has been running the mathpages weblog for a while; John Baez was able to point Brown to Deutsch's earlier work but it seemed otherwise not to go much further.

Nonetheless, Brown's postings were particularly prescient about at least some of what is in Shor's (and Grover's) algorithm. For example in his first posting he appears to anticipate what we'd now call amplitude amplification (as "some sort of feedback amplification [that] could be used to enhance the R=0 outcome"), while in a later posting on the thread suggests to "repeatedly fire photons" through slits, and "restrict our interaction to just the collector screen behind the slits" so as to "find a pattern of interference that reveals the superimposed wave functions". Brown also appears to note that parallelism wouldn't be sufficient but interference is a prerequisite to any improvements over classicality.

Brown has a lovely account of some of the history on his website here. Therein, he does ponder whether Shor was aware of those particular Usenet postings at that time; Shor seems to imply that Brown's postings were not in the forefront of his (Shor's) mind, but he (Shor) was probably very close to cracking the discrete logarithm problem then anyways.

Other not-so-serious postings include the following this April Fool's Day, 1994 posting on a "Quantum Parallel Computer"; Shor mentions being aware of an April Fool's Day posting but was confident that he had solved factoring only by mid-April. Also of note an earlier sci.physics thread from May 1993 appears suspicious of anthropic reasoning and proposes an "Anthropic Computer" to factor numbers in different Everettian universes.

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83