Possibilities and Limitations of Quantum Computing

This year's Cor Baayen Award was given to CWI researcher Ronald de Wolf. He received the award for his work on the potential computer of the future: the quantum computer. De Wolf proved several limitations of this revolutionary computation model. He discovered new quantum algorithms that are more efficient than classical algorithms. Furthermore, he successfully applied quantum proof techniques on classical algorithms.

The mantra of quantum computing is the statement 'information is physical'. Information processing and computation are physical processes, and hence subject to the laws of physics. To the best of our knowledge, these laws are quantum mechanical - and quite weird. In contrast, most current computer science is based on models of classical physics. For example, a Turing machine's read-write head is always in a specific position and its memory cells contain definite information (0 or 1). In the 1980s, Richard Feynman and David Deutsch incorporated the laws of quantum mechanics into the model. This gave quite a different picture. In quantum computing the memory cells can be in a 'superposition' of 0 and 1 at the same time, and different computational paths can 'interfere' with each other destructively or constructively, much like waves.

Quantum computers strengthen the computational paths leading to correct solutions. This can be compared to constructive interference of waves. Photo courtesy of John K.N. Murphy, www.hotquanta.com

Roughly speaking, a quantum algorithm works by going through many computational paths simultaneously, in superposition, and using interference to strengthen the paths leading to a correct output. Halfway through the 1990s researchers like Shor and Grover discovered quantum algorithms for factoring integers and searching databases that are more efficient than their classical equivalents. These discoveries made quantum computing one of the hottest fields around. Whether quantum computers can actually be built is the focus of much research in experimental physics. However, many people feel this effort will bear fruit regardless of the outcome. Even if the construction of a quantum computer is impossible, the research has led to valuable new insights in quantum physics.

The CWI group centred around Paul Vitányi and Harry Buhrman was one of the first in Europe to take up quantum computing as a serious research topic. In 1997 de Wolf became a PhD student there and at the University of Amsterdam. Around that time nobody knew whether quantum computers were superior to their classical equivalents. Together with co-authors, particularly Harry Buhrman, de Wolf proved various strong limitations on quantum computers. For most problems they are not significantly faster than classical computers. These limitations were proved by reducing complexity theoretic questions to algebraic questions about degrees of multivariate polynomials. Sufficient prove of strong -often optimal- lower bounds on the time a quantum algorithm needs to compute a Boolean function, can be given by proving a lower bound on the degree of an n-variate polynomial approximating that function.

Moreover, de Wolf also contributed to the discovery of some quantum algorithms and protocols that outperform their classical counterparts. One example of this is a 'quantum fingerprinting' scheme. It allows two separated parties to compare large chunks of data more efficiently than classical computers. By assigning small quantum states to long classical strings, the amount of data that has to be exchanged for this operation can be exponentially reduced. In the future this technique could for example be used to create digital autographs.

After receiving his PhD in September 2001, de Wolf moved to the USA to become a postdoc at UC Berkeley. There he showed, together with Berkeley grad student Iordanis Kerenidis, that quantum computing techniques could be used as a tool to prove new results in classical computer science. Specifically, they analyzed 2-query locally decodable error-correcting codes. This scheme allows each encoded bit to be individually decoded by looking at only two bits of the codeword, instead of first decoding the entire codeword. Such locally decodable codes have been the focus of much research recently, but the previous best general lower bounds on their length were only polynomial. Using techniques from quantum computing, Kerenidis and de Wolf established for the first time an exponential lower bound. No proof of this result is known that uses just classical proof techniques.

This classical-theorem-with-a-quantum-proof significantly adds to the relevance of quantum computing within computer science in general, since its impact does not depend on the actual building of a quantum computer. As a bonus, the quantum techniques yield quantum protocols for the cryptographic task of 'private information retrieval' that are more efficient than the best known classical protocols. Currently, de Wolf works at CWI as a postdoc. His main research focus is still quantum computing.

Please contact:
Ronald de Wolf
Tel: +31205924078
E-mail: rdewolfcwi.nl
http://homepages.cwi.nl/~rdewolf