Qip Pspace Breakthrough

Theoretical computer scientists have been working on quantum computer technology for years now. Now, it appears that a group of researchers has shown that existing computing technology may be able to eventually match the performance of a quantum computer. Check out the excerpt below from cacm.acm.org and then you can also find additional articles at the end of this post for more information.

Quantum computers rocketed to public attention—or at least to the attention of a specific part of the public sector—in the mid-1990s with the discovery that a computer operating on quantum principles could solve certain problems exponentially faster than we know how to solve them with computers today. The most famous of these problems is factoring large numbers, a feat that would enable one to break most of the cryptography currently used on the Internet. While quantum computers large enough to do anything useful haven’t been built yet, the theory of quantum computing has developed rapidly.

Researchers have discovered quantum algorithms for a variety of problems, such as searching databases and playing games. However, it is now clear that for a wide range of problems, quantum computers offer little or no advantage over their classical counterparts.

The following paper describes a breakthrough result that ives a very general situation in which quantum computers are no more useful than classical ones. The result settles a longstanding problem about quantum interactive proof systems showing they are no more (or less) powerful than classical interactive proof systems.” (via Communications of the ACM - cacm.acm.org)

Written on January 2, 2011