I believe the first publication of the proof of the QMA-completeness of the Local Hamiltonian Problem is as portions of a chapter in the book Classical and Quantum Computation, by Kitaev, Shen, and Vyilyi, published in Russian in 1999 (with an English translation later in 2003). Up until the book publication, the research papers that referenced the QMA-completeness of the LHP had cited a talk by Kitaev and titled "Quantum NP", at the second QIP/AQIP conference hosted by DePaul University in Chicago in January 1999. The agenda for the conference is still available on the web, and looking at the presenters and the abstracts of their presentation gives me shivers.
I have heard a rumor that Kitaev had worked out the details of the problem and the proof of its QMA-completeness while flying to Chicago. The story I had heard was that the conference encouraged presenters to discuss something novel, and Kitaev started thinking about the Cook-Levin theorem and wondering how to port it over to quantum computing. If so, to me it's a pretty fascinating anecdote, that such a foundational theorem was cobbled together on a flight in preparation for a talk about quantum computing, only four and a half years after Shor '94. I can imagine a pre-9/11, four-hour airplane flight from the west coast of the US to O'Hare Airport, with a handsome young Russian gentleman scribbling away on theoretical computer science and the limits it can teach us about quantum mechanics and the physical world itself.
But is there any source or other evidence to the story about the airplane flight, or am I confusing and exaggerating things? Given that the presentation at DePaul was probably the first enabling disclosure of the proof, was it worked out on the airplane as almost a last-minute afterthought?
