Happy 30th Anniversary to Shor's Algorithm! How challenging was the review process when it was first announced?

Question

Shor's algorithm dropped 30 years ago sometime in April, 1994. Peter Shor has given many wonderful accounts of the early history of the field and of what sparked his particular interest.

Shor has been very consistent in stating that he was inspired by D. Simon's preprint submitted to STOC '94; he initially saw that he could instantiate Simon's algorithm with primes $p$ such that $(p-1)$ is smooth by using a full Fourier transform over $\mathbb Z_{p-1}$ instead of Hadamard gates over $\mathbb Z_2^n$. Although the smooth case was known to already be classically efficient, he got a wholly different algorithm than the classical algorithm, which motivated him to work further. He finally cracked the general discrete log problem sometime in mid-April of 1994, and gave a talk at Bell Labs on a Tuesday around then (say, the 12th or 19th). He tells the story better than I ever could but by the end of that week he had fully cracked factoring as well.

Word travels fast and the internet was around but the arXiv was in its infancy; Shor had commented that he was emailing various versions of his preprints to researchers around that time. There are a pair of Usenet postings from May/June of that year, where Robert Solovay wanted to understand the algorithm "down to the bone" (his emphasis), and Solovay initiated a virtual study group for it.

Fast-forward 30 years and we have, also in April, the drop of Yilei Chen's paper on quantum algorithms for LWE problems. People have been digesting this algorithm - and judging solely from comments that I've seen, it's tough and dense. There have been many forums discussing the paper, including a Discord channel, as well as the usually robust and insightful comment section on Shtetl-Optimized's post about the paper. (Update: As of April 18, 2024, there appears to be a fatal error in the last step of Chen's algorithm, and he has withdrawn his claim.)

Nonetheless I really just wanted to sing happy-birthday for Shor's algorithm, but I guess we can ask, especially in light of Chen's paper and the comments about its breadth and density and the unofficial review process associated with it -

When Shor's preprint was cycling around through the lovely dialup world of 1994, were the knowledgeable folks understanding it right away, or did it still take a good deal of effort to fully appreciate? Were there any major or minor revisions to Shor's algorithm, found between April of 1994 and its publication later during this mid-90's version of peer review?

In the FOCS version he mentions contributions of many "too numerous to list". His FOCS paper is only eleven pages long - we can understand it now, in hindsight, but even still the FOCS paper was written in the language of Turing machines, not quantum circuits, never using the word "qubit".

Answer 1

^{Self-answer, marked CW}

---

I think most of the technical issues of Shor's algorithm were relatively easily addressed. I do seem to recall that the FOCS version has a minor typo in the number-theoretical part - this was corrected in later versions.

The initial quantum Fourier transform for both discrete log and factoring was also based on smooth numbers of mixed radix; Don Coppersmith quickly pointed out that we can always work in binary, at a small cost in precision.

I'll go out on a limb and say that the classical number-theory portions of the algorithm (e.g., the continued fraction portion) as well as the reduction of factoring to period finding and the implementation of the QFT were probably quickly appreciated right away. But I suspect that the physicists didn't understand much about Turing tapes or how one would implement modular exponentiation, while the computer scientists and mathematicians didn't fully appreciate the quantum portions of preparing the tape in superposition, unitarily evolving it, and measurement to collapse.

I would guess things became a lot clearer after Coppersmith's contribution - this enables a description of the algorithm with things like CCNOT gates, which is arguably much easier for everyone to understand. Although I also had heard that the original gate-model definition of BQP lacked the now-requisite uniformity condition - this was also quickly patched as well.

Probably the biggest hurdles were more conceptual and related to error accumulation; people didn't understand if quantum computers were analog devices or digital. The next chapter in Shor's annus mirabilis of 1994-95 is of course his initiation of quantum error correction (leading to the eventual proof the fault-tolerant theorem), which helped to digitize the analog.