Wednesday, January 05, 2005
Limits on Efficient Computation in the Physical World
So you've completely mastered Nielsen and Chuang, where do you go next on the road to understanding quantum computing? I'll admit there's a lot more I could learn from the basic texts before entirely turning my attention to other things, and in the vast ocean of arxiv.org, it's hard to know where to go next.
But one wothwhile stop is here: The dissertation of Scott Aaronson: Limits on Efficient Computation in the Physical World (phD
candidate, UC Berkeley). It's a pretty interesting read that seems to cover a lot of central points in the computer science side of QC. Along with presenting some new results, it ties together many of Aaronson's (and others') previously published papers, giving a lot more context and motivation then what appears in the raw papers themselves.
From Chapter 1:
"For me, quantum computing matters because it combines two of the great mysteries bequeathed to us by the twentieth century: the nature of quantum mechanics, and the ultimate limits of computation. It would be astonishing if such an elemental connection between these mysteries shed no new light on either of them. And indeed, there is already a growing list of examples-we will see several of them in this thesis-in which ideas from quantum computing have led to new results about classical computation.
"[I]n this thesis I will show how adopting a computer science perspective can lead us to ask better questions-nontrivial but answerable questions, which put old mysteries in a new light even when they fall short of solving them."