Carnegie Mellon University

The Piper

CMU Community News

Piper Logo
April 01, 2011

Lecture Spotlight

Buhl Lecturer Looks for Limits to Quantum Computing

By Amy Pavlak

AronsonFor years science fiction writers have dreamed up fanciful possibilities for what quantum computers can do, including jettisoning characters into parallel universes or creating their own alternate realities.

Computer scientist Scott Aaronson is more interested in what quantum computers can’t do.

“In my opinion, the most exciting possible outcome of quantum computing research would be to discover a fundamental reason why quantum computers are not possible,” wrote Aaronson in a 2008 Scientific American article. “Such a failure would overturn our current picture of the physical world, whereas success would merely confirm it.”

Aaronson, an associate professor of electrical engineering and computer science at MIT, will discuss “Quantum Computing and the Limits of the Efficiently Computable” during the annual Buhl Lecture at 4:30 p.m., Friday, April 29 in the Mellon Institute Auditorium.

The Buhl Lecture, sponsored by the Department of Physics, brings an internationally recognized scientist to campus to give a public lecture on a topic of current interest in physics.

Quantum computing, an idea proposed nearly 30 years ago by the famous physicist Richard Feynman and others, exploits the physical properties of particles in the quantum world to solve certain computational problems dramatically faster than today’s computers. While a standard computer obeys the laws of classical physics, a quantum computer adheres to the laws of quantum mechanics — which are significantly different.

“Quantum computing experiments focus attention directly on the most mystifying features of quantum mechanics — and I hope that the less we can sweep those puzzles under the rug, the more we will be forced to understand them,” Aaronson wrote.

During his talk, Aaronson will discuss what quantum computers are, whether they can be built on a large scale, and what’s known today about their capabilities and limitations. He’ll even go beyond quantum computers to touch on speculative models of computation, including closed timelike curves and nonlinearities in the Schrodinger equation.

Aaronson’s work on the subject of quantum computing has included limitations of quantum algorithms in the black-box model, the learnability of quantum states, and quantum versus classical proofs and advice. He writes a popular blog (, and is the creator of the Complexity Zoo (, an online encyclopedia of computational complexity theory.

What: 2011 Buhl Lecture    
Who: Scott Aaronson, associate professor of electrical engineering and computer science at MIT
When: 4:30 p.m., Friday, April 29
Where: Mellon Institute Auditorium