Technical Perspective: QIP = PSPACE Breakthrough

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.

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.

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.

When quantum computing first came along, almost every topic in theoretical CS was ripe for reexamination in light of quantum effects. In 1999, Kitaev and Watrous defined the complexity class QIP (Quantum Interactive Proofs), which is like IP except that now Arthur and Merlin both have quantum computers at their disposal, and can send and receive quantum messages.

Because of the ‘exponential parallelism’ inherent in quantum mechanics—a state of n quantum bits (or qubits) requires a vector of 2ⁿ complex numbers to describe—it was a reasonable guess that sending and receiving quantum messages would let Arthur verify even more mathematical statements than he could using classical interaction. In the beginning, though, all that seemed clear was that quantum interactive proofs were at least as powerful as classical ones: IP = PSPACE Í QIP.

The reason is what I call the "Clark Kent principle": like Superman concealing his powers, a quantum computer can always "hide its quantumness" and emulate a classical computer if necessary. So the real question is whether QIP is larger than IP. Kitaev and Watrous managed to show that QIP was contained in EXP, the class of problems solvable by a classical computer using an exponential amount of time. Since EXP is believed to be strictly larger than PSPACE, this put QIP somewhere in a no-man’s-land between PSPACE and EXP.

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.

Back to Top

Back to Top