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.
In the laboratory setup used in the new work, Alice and Bob communicate via laser pulses. Each pulse represents a single ball. The pulses go through a beam splitter, which sends half of each pulse toward Alice and half toward Bob. As a pulse passes by Alice, she can shift something called the phase of the laser pulse to encode information about each ball — whether it’s red or blue.
Meanwhile Bob encodes information about the pairs of balls he cares about into his half of the laser pulses. The pulses then converge in another beam splitter, where they interfere with each other. The way in which the two sets of pulses interfere with each other reflects differences in the way the phase of each pulse has been shifted. Bob can read the interference pattern on nearby photon detectors.
Up until the moment that Bob “reads” Alice’s laser message, Alice’s quantum message is capable of answering any question about any pair. But in the act of reading the quantum message, he destroys it, yielding information about just one pair of balls.
This characteristic of quantum information — that it carries the potential to be read many ways but can ultimately be read only one way — dramatically reduces the amount of information that needs to be transmitted to solve the sampling matching problem. If Alice needs to send Bob 100 classical bits to ensure he can answer his question, she can accomplish the same objective in about 10 qubits, or quantum bits.
“It’s the sort of proof-of-principle stuff you have to do if you’re going to build up a real quantum network,” said Graeme Smith, a physicist at JILA in Boulder, Colorado, who works on quantum technology.
The new experiment is an unalloyed triumph over classical methods. The researchers went into the experiment knowing exactly how much information needed to be transmitted classically to solve the problem. They then indisputably demonstrated that it could be solved in a far leaner fashion by quantum means. “It’s nice in this paper to see people really making a good effort to make sure the thing they’re doing is hard classically, and then doing the hard thing” using quantum methods, Smith said.
The result also suggests an alternative route for achieving a long-standing goal in computer science: proving that quantum computers reign over classical ones. Such quantum “supremacy” has been hard to establish in the purely computational realm, but many important problems hinge on more than just computation.
“Combining what we can do with computing and communication power, putting these two things together, would make it easier to prove a quantum advantage,” Kerenidis said.