Chronology of discovery of quantum phase estimation algorithm

Question

I'm a bit confused about exactly when the phase estimation algorithm was discovered. The Wiki article, as well as various textbooks and papers, says that it was introduced in 1995 by Alexei Kitaev, but Shor's algorithm, which uses phase estimation, was introduced in 1994 by Peter Shor. So was Peter Shor really the inventor of phase estimation, or did his original paper not include it?

Answer 1

It's really a fun game to revisit and consider those mid-late 90's papers, and the language that they used at the birth of the field. I continue to read these in awe and admiration.

Shor's original papers might not have used the same "modern" language of a Wikipedia article in 2022, but certainly reading his paper broadly he might come close to what we might call "quantum phase estimation". Maybe § 4 of this arXiv version of the paper gets closest to the quantum phase estimation as is understood after Kitaev's landmark work.

There are also all of these wonderful asides in Shor's paper to concepts that a course might now spend at least half-a-lecture explaining. Shor states that it "would be sufficient to observe solely the value of $|c\rangle$ in the first register, but for clarity we will assume that we observe both $|c\rangle$ and $|x^a\pmod n\rangle$." This throw-away line has caused much confusion and consternation among those learning the field, about why we don't need to measure the second register, but Shor just says it in passing.

Also the term "qubit" was only coined after Shor's pioneering paper! It boggles my mind today that all this work was done before any of this was internalized. Further still, remember Shor's original quantum Fourier transform was quickly improved by Coppersmith.

As to who first conceptualized the quantum phase estimation algorithm, Seth Lloyd, in his lecture at Keio University on the HHL algorithm, also posits that this was implicit in von Neumann's codification of measurement. See Lloyd's lecture here at about the 18 minute mark.

Rhetorically, is this similar to contending that Gauss anticipated the Fast Fourier Transform well before Cooley and Tukey (and, even before Fourier)?

(As an aside and on a lark, I reread Deutsch's chapter on quantum computing in The Fabric of Reality, which came out in ~1996. So many predictions! Some right, some off, some for the worse and some for better!)

Answer 2

According to "Quantum Computation and Quantum Information - 10th Anniversary Edition" by Nielsen & Chuang (pages 245 - 246)

Deutsch^Deu85 showed that the Fourier transform over the group $Z^n_2$ could be implemented efficiently on a quantum computer.

Shor^Sho94 realized to spectacular effect that quantum computers could efficiently implement the quantum Fourier transform over groups $Z_m$ for certain special values of $m$.

Inspired by this result Coppersmith^Cop94, Deutsch (unpublished), and Cleve (unpublished) gave the simple quantum circuits for computing the quantum Fourier transform over $Z_{2^n}$.

The Fourier transform over $Z_{2^n}$ was generalized to obtain a Fourier transform over an arbitrary finite Abelian group by Kitaev^Kit95, who also introduced the phase estimation procedure.