Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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 if quantum computers are realistic is one of the most fascinating and clear-cut scientific problems of our time, and my work is geared toward a negative answer. 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 for 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 human-made and to natural devices.) This systematic dependence causes general-purpose quantum computers to fail, and more specifically, for any attempted implementation of a general-purpose quantum device the error rate scales up with the number of qubits (the quantum-memory building-blocks) and thus causes fault tolerance and quantum speed-up to fail. The challenge is to understand the systematic laws for this dependence. In the lecture I will proposed 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 study recent proposals for demonstrating quantum speed-up without quantum fault-tolerance.