[QIP-Sem] QIP seminar, Fri 2/22, 2:00 PM, 6C-442, Gil Kalai

[Peter Shor]

MIT Quantum Information Processing seminar
Friday 2/22 at 2:00 PM in 6C-442
-------------------------------------------------

 Gil Kalai (Hebrew University of Jerusalem and Yale University)

Why quantum computers cannot work, and how

Abstract:

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 integer n  in  C(log n)^3 steps. The question if quantum computer 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 notion of quantum error-correction and a remarkable theory of quantum fault-tolerance were developed.  
 What makes it still hard to believe that superior quantum computers can be built is that building universal quantum computers 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 in the understanding quantum mechanical systems (including in regimes where people do not expect such new insights.) 
  Here is my explanation for why (fault-tolerant) quantum computers cannot be built: 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. The challenge is to understand the systematic laws for this dependence.  (Of course, within the framework of quantum probability.) 
 In the lecture I will start with an argument for why implementations of topological quantum computing leading to highly stable qubits that "shortcuts" the need for traditional quantum fault-tolerance cannot work. I will continue to describe the distinctions between noisy quantum systems that enact quantum fault tolerance and those that do not, and concentrate on two formal distinctions. To this end I will describe my model of "smoothed Lindblad evolutions." I will also mention some highlights in a recent debate with Aram Harrow on the matter.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem