Quantum computers are still a dream, but the era of quantum communication is here. A new experiment out of Paris has demonstrated, for the first time, that quantum communication is superior to classical ways of transmitting information.
“We are the first to show a quantum advantage for transmitted information that two parties have to share to perform a useful task,” said Eleni Diamanti, an electrical engineer at Sorbonne University and a co-author of the result along with Iordanis Kerenidis, a computer scientist at Paris Diderot University, and Niraj Kumar.
Quantum machines — which exploit quantum properties of matter to encode information — are widely expected to revolutionize computing. But progress has been slow. While engineers labor to build rudimentary quantum computers, theoretical computer scientists have confronted a more fundamental obstacle: They’ve been unable to prove that classical computers will never be able to perform the tasks quantum computers are designed for. This past summer, for example, a teenager from Texas proved that a problem long thought to be quickly solvable only on a quantum computer can be done rapidly on a classical computer as well.
However, in the realm of communication (rather than computation), the benefits of a quantum approach are certifiable. More than a decade ago computer scientists proved that, at least theoretically, quantum communication beats classical ways of sending messages for certain tasks.
“Mostly people have looked at computational tasks. One big advantage is that with communication tasks, the advantages are provable,” Kerenidis said.
In 2004, Kerenidis and two other computer scientists imagined a scenario in which one person needed to send information to another so that the second person could answer a particular question. The researchers proved that a quantum setup could accomplish the task by transmitting exponentially less information than a classical system. But the quantum setup they imagined was purely theoretical—and far beyond the technology of the time.
“We could prove this quantum advantage, but it was difficult to actually implement the quantum protocol,” Kerenidis said.
The new work carries out a modified version of the scenario that Kerenidis and colleagues envisaged. The question addressed in the paper involves two users, Alice and Bob. Alice has a set of numbered balls. Each ball is randomly colored red or blue. Bob wants to know whether a particular pair of balls, chosen at random, has the same color or different colors. Alice wants to send Bob the smallest amount of information she can while still ensuring that Bob can answer his question.
This problem is called the “sampling matching problem.” It has implications for cryptography and digital currency, where users often want to exchange information without necessarily divulging everything they know. It’s also well-suited to demonstrating a quantum communication advantage.
“You can’t just say, ‘I want to send you a movie or something that’s one gigabyte and encode it into a quantum state’” and expect to find a quantum advantage, said Thomas Vidick, a computer scientist at the California Institute of Technology. “You have to look at tasks that are more subtle.”
To solve the matching problem classically, Alice has to send Bob an amount of information proportional to the square root of the number of balls. But the unorthodox nature of quantum information makes a more efficient solution possible.