Special Seminar: Why Quantum Computers Cannot Work

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.