Entanglement is a key resource for quantum computers. However, the lack of entanglement can also be a powerful concept in quantum computation.
The unintuitive features of quantum mechanics have delighted and confounded physicists in equal measure for over a century. A central aspect of quantum theory is the super-strong quantum correlation known as entanglement. This "spooky action at a distance" enables many of the most well-known and surprising examples of quantum effects, such as quantum teleportation, and is considered to be an essential component of the exponential speed-ups that can be achieved by quantum computers over standard ("classical") computers. However, recent work at the Centre for Quantum Information and Foundations at the University of Cambridge, in collaboration with the University of Washington, has shown that the absence of entanglement can also lead to significant computational advantages.
This work takes place in the setting of so-called quantum Merlin-Arthur games. In this framework, a prover (Merlin) sends a computationally limited verifier (Arthur) a quantum state, which Arthur uses as a resource ("proof") to enable him to solve a computationally challenging problem. We think of Merlin as being all-powerful, but not to be trusted: Arthur must check the proof to ensure that Merlin does not trick him into answering incorrectly. This is a model for problems which cannot necessarily be solved efficiently, but whose solutions can be verified efficiently by a quantum computer. Many natural problems in quantum physics turn out to fall into this category.
A natural generalisation of this framework is to give Arthur access to more than one prover, but to separate the provers and not to allow them to communicate. If Arthur receives two or more unentangled quantum states as proofs, he might be able to use them to solve problems which he could not solve with access to just one quantum state. The reason for this is that Arthur may be able to validate the proofs against each other to check for errors or malicious modifications by the provers. By contrast with the classical setting, where multiple proofs can simply be concatenated together, the fact that separate quantum proofs are unentangled is crucial to enable this cross-checking.
Figure 1: Multiple unentangled quantum proofs can be simulated by only two proofs.
Our work centres on the notoriously hard boolean satisfiability problem 3-SAT, for which no classical (or indeed quantum) algorithms are known that run in time subexponential in the length of the input. Surprisingly, we show that 3-SAT can in fact be solved efficiently by a quantum computer, as long as it is given access to two unentangled proofs, the length of each of which is approximately the square root of the size of the input. As classical computers appear to require proofs approximately as long as the original input to solve 3-SAT efficiently, this implies a significant quantum advantage.
It was previously known that 3-SAT can be solved efficiently, given access to a large number of unentangled quantum proofs. In order to use this prior work to prove our new result, we develop and analyse an efficient quantum algorithm that certifies that the state of a large number of quantum systems is unentangled, given only two copies of the quantum state to be tested. This result then allows Arthur, given two unentangled proofs, to simulate multiple unentangled proofs, and to use the previously known protocol to solve 3-SAT.
On the flip side, our result implies obstructions to classical simulation of two-prover unentangled quantum proof systems. If such systems could be efficiently simulated classically, this would imply classical algorithms for 3-SAT that run in less than exponential time, which are considered very unlikely to exist. It turns out that these proof systems are connected to many central tasks in quantum information theory. For example, our work implies computational hardness of estimating the capacity of quantum communication channels, detecting bipartite entanglement, and estimating ground-state energies of certain classes of quantum system. Thus the apparently arcane framework of quantum proof systems with multiple unentangled provers is in fact closely related to other aspects of quantum information theory, and is even connected to optimisation problems from outside the field.
While entanglement is seen as the basis of quantum computational power, our work implies that the absence of entanglement can also be desirable. Future work aims to determine the precise computational power of multiple quantum proofs, and also to investigate intriguing connections to the power of entanglement in quantum information transmission.
Link: http://arxiv.org/abs/1001.0017
Please contact:
Ashley Montanaro,
Centre for Quantum Information and Foundations, Centre for Mathematical Sciences, Cambridge
Tel: +44 1223 760383 begin_of_the_skype_highlighting +44 1223 760383 end_of_the_skype_highlighting
E- mail:
