7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ The title and body of your question seem to pose different questions. The title seems to ask a general question. The body seems to ask a more specific question about Shor: "...but I'm curious if he conjectured that a quantum computer could factor integers ex nihilo..." You also seem to have already answered your own question, since you write that he was inspired by the presentations of others. Finally, if you want to know what Shor was thinking at the time, or how he was or was not inspired, then it might be best to just ask him. $\endgroup$
    – hft
    Mar 21, 2023 at 0:16
  • 4
    $\begingroup$ Shor's algorithm consists of two parts: a classical probabilistic reduction of factoring to order finding and a quantum algorithm for order finding. The reduction was found in 1975 by Miller. This makes it plausible that Shor's invention might not have been preceded by a conjecture about factoring per se but instead might have been the result of an attempt to answer the question: "What could one accomplish if one had an order-finding machine?". This is of course a mere speculation. Only @Peter Shor knows the truth :-) $\endgroup$ Mar 21, 2023 at 20:33

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.