Quantum computers are hypothetical devices based on quantum physics that can out-perform classical computers. A famous algorithm by Peter Shor shows that quantum computers can factor an n-digit integer in n^3 steps, exponentially better than the number of steps required by the best known classical algorithms. The question of whether quantum computers are realistic is one of the most fascinating and clear-cut scientific problems of our time. What makes it hard to believe that superior quantum computers *can* be built is that building them represents a completely new reality in terms of controlled and observed quantum evolutions, and also a new computational complexity reality. What makes it hard to believe that quantum computers *cannot* be built is that this may require profoundly new insights into the understanding of quantum mechanical systems.

The main concern from the start was that quantum systems are inherently noisy; we cannot accurately control them, and we cannot accurately describe them. To overcome this difficulty, a fascinating theory of quantum error-correction and quantum fault-tolerance were developed. My expectation is that understanding the "fault-tolerance barrier"---the formal distinction between quantum systems with and without quantum fault-tolerance---will lead to an understanding of why quantum fault-tolerance and quantum computational speed-up are not possible.

My explanation for why (fault-tolerant) quantum computers cannot be built is that quantum systems based on special-purpose quantum devices are subject to noise which systematically depends on the quantum evolution of the system; this dependence reflects dependence of the noise on the quantum device, and the dependence of the quantum device on the quantum evolution it is performing. (Here, a "quantum device" refers both to man-made and to natural devices.) This systematic dependence causes general-purpose quantum computers to fail, and also special devices demonstrating a computational speed-up.

The challenge is to understand the systematic laws that govern this dependence. In the lecture I will propose a mathematical model for realistic noisy quantum systems called "smoothed Lindblad evolution," and discuss some further conjectures on the behavior of realistic noisy quantum computers. I will also mention how noise-sensitivity in the sense of Benjamini, Kalai & Schramm (1999) is relevant to the study of recent proposals for demonstrating quantum speed-up without quantum fault-tolerance.