Pages

December 30, 2010

Researchers have found a parallel computing algorithm that could offer quantum computer-speed performance

Researchers used an algorithm to evaluate potential speed in classical computation. Called the matrix multiplicative weights update method, it was developed from research in two mathematical fields of study, combinatorial optimization and learning theory.

The researchers showed that "for a certain class of semi-definite programs you can get not the exact answer but a very good approximate answer, using a very small amount of memory.

Scott Aaronson said that the algorithm could be used in commercial fields of computing, particularly in the field of semi-definite programming, which looks at ways of solving optimization problems. "These are very common in industrial optimization," he said.

Using an innovative argument based on polynomials over finite fields, the authors showed that IP contains PSPACE (Polynomial Space), the class of problems solvable by a classical computer using a polynomial amount of memory but possibly an exponential amount of time. PSPACE is known to encompass games of strategy, such as chess and Go. And thus, we get the surprising implication that, if aliens with infinite computational powers came to earth, they could not only beat humans at chess, but could also mathematically prove they were playing chess perfectly. Since it's not difficult to show that every IP problem is also a PSPACE problem, we obtain one of the most famous equations in CS: IP = PSPACE. This equation paved the way for many advances of a more down-to-earth nature: for example, in cryptography and program checking.

The authors have finally pinned down the power of quantum interactive proofs: they show that QIP = IP = PSPACE. In other words, quantum interactive proofs have exactly the same power as classical interactive proofs: both of them work for all problems in PSPACE but no other problems. In proving this, the authors confronted an extremely different challenge than that confronted in the earlier IP = PSPACE proof. Instead of demonstrating the power of interactive proofs, the authors had to show that quantum interactive proofs were weak enough to be simulated using polynomial memory: that is, QIP Í PSPACE.

To achieve this, the authors use a powerful recent tool called the multiplicative weights update method. Interestingly, computer scientists originally developed this method for reasons having nothing to do with quantum computing and, completing the circle, the QIP = PSPACE breakthrough is already leading to new work on the classical applications of the multiplicative weights method. This illustrates how advances in quantum and classical computing are sometimes increasingly difficult to tell apart.

Communications of the ACM : QIP = PSPACE



Communications of the ACM - QIP = PSPACE Breakthrough

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 gives 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.

What is an interactive proof system? Basically, it's an imagined process in which a prover (named Merlin) tries to convince a skeptical verifier (named Arthur) that a mathematical statement is true, by submitting himself to interrogation. Merlin, though untrustworthy, has unlimited computational powers; Arthur, by contrast, is limited to performing computations that take polynomial time. By asking Merlin pointed questions, Arthur can sometimes convince himself of a statement more quickly than by reading a conventional proof.

When confronted with a new model of computation, theoretical computer scientists' first instinct is to name the model with an inscrutable sequence of capital letters. And thus, in 1985, Goldwasser, Micali, and Rackoff as well as Babai defined the complexity class IP (Interactive Proofs), which consists of all mathematical problems for which Merlin can convince Arthur of a "yes" answer by a probabilistic, interactive protocol. They then asked: how big is IP? In a dramatic development in 1990, Lund et al. and Shamir showed that IP was larger than almost anyone had imagined.

Many papers and presentations on weights update method


If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks

Featured articles

Ocean Floor Gold and Copper
   Ocean Floor Mining Company

blog comments powered by Disqus