The BQP (bounded-error, quantum, polynomial time) class of problems. From Prof. Aaronson’s 6.845 Quantum Complexity Theory.
The Complexonaut
Scott Aaronson travels the far reaches of computational complexity, shaping conventional and quantum computing.Larry Hardesty | MIT News Office
April 7, 2014
When he was in elementary school, Scott Aaronson, like many mathematically precocious kids of his generation, dreamed of making his own video games. He had only the foggiest notion of what that entailed, however.“I could try to imagine making my own game — I could draw a picture of what it should look like — but how does it come to life?” Aaronson recalls. “Maybe there’s some factory where they do all kinds of complicated machining to make Mario move around in the right way. Then a friend showed me this spaceship game that he had on his computer, and he said, ‘Here’s the code.’ Well, what is this? Some kind of summary of the game? ‘No, no, this is the game. If you change the code, the spaceship will do something different.’”
“I like to say that for me, this was like learning where babies came from,” Aaronson adds. “It was a revelation. And I was incredibly upset at my parents that they hadn’t told me earlier that this exists. Because I was already 11, and other kids had known programming since they were 8, and how would I ever catch up to them?”
As that anecdote attests, Aaronson was a young man in a hurry…
…[while an undergraduate at Cornell University], Aaronson learned from a fellow student about Shor’s algorithm, perhaps the most important theoretical result in quantum computing. Quantum computers are devices, still largely hypothetical, that would harness the strange behavior of matter at extremely small scales to perform computations. Discovered by Peter Shor in 1994, Shor’s algorithm is a quantum algorithm for factoring large numbers, one of the canonical NP problems that is easy to verify but apparently very hard to solve. Shockingly, Shor was able to show that for a quantum computer, solving the problem would be almost as easy as verifying it is for a classical computer.
“My first reaction was, ‘OK, this is probably some obvious crap that is getting hyped by the media,’” Aaronson says. But he had to know for sure, and he threw himself into the study of quantum computing. He came away convinced that, indeed, quantum computers would rewrite the rules of computational efficiency…
…Recently, Aaronson and his student Alex Arkhipov described an optical experiment that, if performed successfully, could, for the first time, use quantum mechanics to execute a calculation that’s infeasible with conventional computers. Read more…
Learn more about these subjects in Prof. Aaronson’s OCW courses:
