The Proof in the Quantum Pudding

In early May, news reports gushed that a quantum computation device had for the first time outperformed classical computers, solving certain problems thousands of times faster. The media coverage sent ripples of excitement through the technology community. A full-on quantum computer, if ever built, would revolutionize large swathes of computer science, running many algorithms dramatically faster, including one that could crack most encryption protocols in use today.

Over the following weeks, however, a vigorous controversy surfaced among quantum computation researchers. Experts argued over whether the device, created by D-Wave Systems, in Burnaby, British Columbia, really offers the claimed speedups, whether it works the way the company thinks it does, and even whether it is really harnessing the counterintuitive weirdness of quantum physics, which governs the world of elementary particles such as electrons and photons.

Most researchers have no access to D-Wave’s proprietary system, so they can’t simply examine its specifications to verify the company’s claims. But even if they could look under its hood, how would they know it’s the real thing?

Verifying the processes of an ordinary computer is easy, in principle: At each step of a computation, you can examine its internal state — some series of 0s and 1s — to make sure it is carrying out the steps it claims.

A quantum computer’s internal state, however, is made of “qubits” — a mixture (or “superposition”) of 0 and 1 at the same time, like Schrödinger’s fabled quantum mechanical cat, which is simultaneously alive and dead. Writing down the internal state of a large quantum computer would require an impossibly large number of parameters. The state of a system containing 1,000 qubits, for example, could need more parameters than the estimated number of particles in the universe.

And there’s an even more fundamental obstacle: Measuring a quantum system “collapses” it into a single classical state instead of a superposition of many states. (When Schrödinger’s cat is measured, it instantly becomes alive or dead.) Likewise, examining the inner workings of a quantum computer would reveal an ordinary collection of classical bits. A quantum system, said Umesh Vazirani of the University of California, Berkeley, is like a person who has an incredibly rich inner life, but who, if you ask him “What’s up?” will just shrug and say, “Nothing much.”

“How do you ever test a quantum system?” Vazirani asked. “Do you have to take it on faith? At first glance, it seems that the obvious answer is yes.”

It turns out, however, that there is a way to probe the rich inner life of a quantum computer using only classical measurements, if the computer has two separate “entangled” components.

In the April 25 issue of the journal Nature, Vazirani, together with Ben Reichardt of the University of Southern California in Los Angeles and Falk Unger of Knight Capital Group Inc. in Santa Clara, showed how to establish the precise inner state of such a computer using a favorite tactic from TV police shows: Interrogate the two components in separate rooms, so to speak, and check whether their stories are consistent. If the two halves of the computer answer a particular series of questions successfully, the interrogator can not only figure out their internal state and the measurements they are doing, but also issue instructions that will force the two halves to jointly carry out any quantum computation she wishes.

“It’s a huge achievement,” said Stefano Pironio, of the Université Libre de Bruxelles in Belgium.

The finding will not shed light on the D-Wave computer, which is constructed along very different principles, and it may be decades before a computer along the lines of the Nature paper — or indeed any fully quantum computer — can be built. But the result is an important proof of principle, said Thomas Vidick, who recently completed his post-doctoral research at the Massachusetts Institute of Technology. “It’s a big conceptual step.”

In the short term, the new interrogation approach offers a potential security boost to quantum cryptography, which has been marketed commercially for more than a decade. In principle, quantum cryptography offers “unconditional” security, guaranteed by the laws of physics. Actual quantum devices, however, are notoriously hard to control, and over the past decade, quantum cryptographic systems have repeatedly been hacked.

The interrogation technique creates a quantum cryptography protocol that, for the first time, would transmit a secret key while simultaneously proving that the quantum devices are preventing any potential information leak. Some version of this protocol could very well be implemented within the next five to 10 years, predicted Vidick and his former adviser at MIT, the theoretical computer scientist Scott Aaronson.

“It’s a new level of security that solves the shortcomings of traditional quantum cryptography,” Pironio said.

Spooky Action

In 1964, the Irish physicist John Stewart Bell came up with a test to try to establish, once and for all, that the bafflingly counterintuitive principles of quantum physics are truly inherent properties of the universe — that the decades-long effort of Albert Einstein and other physicists to develop a more intuitive physics could never bear fruit.

Einstein was deeply disturbed by the randomness at the core of quantum physics — God “is not playing at dice,” he famously wrote to the physicist Max Born in 1926.

In 1935, Einstein, together with his colleagues Boris Podolsky and Nathan Rosen, described a strange consequence of this randomness, now called the EPR paradox (short for Einstein, Podolsky, Rosen). According to the laws of quantum physics, it is possible for two particles to interact briefly in such a way that their states become “entangled” as “EPR pairs.” Even if the particles then travel many light years away from each other, one particle somehow instantly seems to “know” the outcome of a measurement on the other particle: When asked the same question, it will give the same answer, even though quantum physics says that the first particle chose its answer randomly. Since the theory of special relativity forbids information from traveling faster than the speed of light, how does the second particle know the answer?

To Einstein, these “spooky actions at a distance” implied that quantum physics was an incomplete theory. “Quantum mechanics is certainly imposing,” he wrote to Born. “But an inner voice tells me that it is not yet the real thing.”

Over the remaining decades of his life, Einstein searched for a way that the two particles could use classical physics to come up with their answers — hidden variables that could explain the behavior of the particles without a need for randomness or spooky actions.

But in 1964, Bell realized that the EPR paradox could be used to devise an experiment that determines whether quantum physics or a local hidden-variables theory correctly explains the real world. Adapted five years later into a format called the CHSH game (after the researchers John Clauser, Michael Horne, Abner Shimony and Richard Holt), the test asks a system to prove its quantum nature by performing a feat that is impossible using only classical physics.

Quantum Strategies

In the CHSH game, Bonnie and Clyde are separately “questioned” by a detective who gives them each a 0 or 1, chosen randomly. Bonnie and Clyde each “answer” by giving the detective a red or blue card. If either player (or both) received a 0, they must hand in matching colors to win. But if both players got a 1, they must hand in different colors to win.

One strategy is for Bonnie and Clyde to decide before the game that they will simply turn in their red cards, no matter what the detective asks them, which will give them a 75 percent chance of winning. If Bonnie and Clyde have only classical physics at their disposal, it turns out that this is the best they can do.

But Bonnie and Clyde can significantly increase their chance of winning if they share an EPR pair of particles. The players can agree ahead of time that after the detective hands them their questions, they will measure their particles in carefully chosen ways. The measurements are designed to produce a high chance of identical results when at least one of the players receives a 0, and a high chance of opposite results when the players both get 1s. If they follow this strategy, they have an 85.4 percent chance of winning.

The CHSH game is a coordination game, in which two collaborating players — Bonnie and Clyde, say — are questioned in separate interrogation rooms. Their joint goal is to give either identical answers or different answers, depending on what questions the “detective” asks them. Neither player knows what question the detective is asking the other player.

If Bonnie and Clyde can use only classical physics, then no matter how many “hidden variables” they share, it turns out that the best they can do is decide on a story before they get separated and then stick to it, no matter what the detective asks them, a strategy that will win the game 75 percent of the time. But if Bonnie and Clyde share an EPR pair of entangled particles — picked up in a bank heist, perhaps — then they can exploit the spooky action at a distance to better coordinate their answers and win the game about 85.4 percent of the time.

Bell’s test gave experimentalists a specific way to distinguish between quantum physics and any hidden-variables theory. Over the decades that followed, physicists, most notably Alain Aspect, currently at the École Polytechnique in Palaiseau, France, carried out this test repeatedly, in increasingly controlled settings. Almost every time, the outcome has been consistent with the predictions of quantum physics, not with hidden variables.

Aspect’s work “painted hidden variables into a corner,” Aaronson said. The experiments had a huge role, he said, in convincing people that the counterintuitive weirdness of quantum physics is here to stay.

If Einstein had known about the Bell test, Vazirani said, “he wouldn’t have wasted 30 years of his life looking for an alternative to quantum mechanics.” He simply would have convinced someone to do the experiment.

A Quantum Wrist Lock

The Bell test does more than allow a physical system to prove that it is quantum, the April findings show: It gives a way for a complex quantum system to establish just what its internal state is, and what measurements it is doing.

Reichardt, Unger and Vazirani showed that if Bonnie and Clyde are winning 85.4 percent of the time over many rounds of the CHSH game, then with almost perfect certainty, they must be doing it by measuring a large collection of EPR pairs — different pairs for different rounds of the game. In other words, Bonnie and Clyde can show, through their game performance, just what is going on inside their quantum devices, without opening the hood.

It’s the Bell test “on steroids,” Aaronson said.

Vazirani likened the new test to an aikido hold, in which a master can bend the wrist of a strong opponent in such a way that wriggling out of the hold would be unbearably painful. “Quantum systems are exponentially powerful, but if we do this simple check, we have a wrist lock on the quantum players,” he said. “It neutralizes their power.” If Bonnie and Clyde want to do as well as possible on the game, they can’t avoid revealing their internal state.

Once an aikido master has his opponent in a wrist lock, Vazirani said, he can lead his opponent around simply by pulling his wrist in the desired direction. In the same way, Vazirani and his colleagues show how you can force Bonnie and Clyde to carry out any quantum computation you wish, without letting them sneak in fake computations.

Computation by Wrist Lock

In computation by teleportation, Bonnie prepares quantum states called resource states, and Clyde “chains” these states together with other states by performing certain measurements. The end result of Bonnie and Clyde’s actions can be tailored to carry out any chosen quantum computation.

If you simply asked Bonnie and Clyde to carry out these actions, they could do something else and lie to you about it, and you would never know. But you can outsmart them by slipping the special instructions in with many rounds of the CHSH game. Now, when you ask Bonnie to create a resource state, she doesn’t know whether Clyde has been asked to chain some states together or to play the CHSH game. She can’t afford to cheat, because when Clyde is playing the CHSH game, you’ll know what range of outcomes to expect. The same is true when Clyde is asked to chain states together. When you give them both the special instructions, they could theoretically cheat without detection — but they’ll never know when to do it.

The idea is to use a form of quantum computation called computation by teleportation, developed in 1999 by Daniel Gottesman, now of the Perimeter Institute in Waterloo, Ontario, and Isaac Chuang, now of MIT. The new protocol involves randomly slipping in the instructions for these computations during multiple rounds of the CHSH game. If Bonnie and Clyde want to keep hitting their 85.4 percent mark, they also have to perform these special instructions honestly, or their dishonesty will be apparent. The detective can trust the outcome of their computations, even if she doesn’t trust Bonnie and Clyde.

We won’t be seeing computers built on these principles anytime soon. The protocol must be made more efficient and fault-tolerant, Pironio cautioned, before it can be used to extract guaranteed computations from an untrusted quantum computer. In any case, the technological challenges in trying to build any quantum computer are immense. Nevertheless, he said, “it’s an important breakthrough.”

Trusting Untrusted Devices

While testing a real quantum computer using the new protocol remains a distant prospect, the protocol’s potential application in quantum cryptography is already starting to come into focus.

When it comes to transmitting secret information, the fact that measurement alters a quantum system becomes a boon, not a curse: An eavesdropper can’t listen in without leaving noticeable traces. The quantum cryptography protocols developed to date offer perfect security, provided they are implemented perfectly. But therein lies the catch: Quantum devices are famously hard to control, and, as we’ve seen, hard to check. As a result, they are potentially vulnerable to “side channel” attacks, in which information leaks out to an eavesdropper through device flaws. Commercial quantum cryptography devices have been dogged by security breaches over the past decade.

Reichardt, Unger and Vazirani have now created a quantum cryptography protocol that is, in principle, impervious to such attacks, as it doesn’t require users to trust finicky quantum devices. Instead, the protocol builds in a proof that the devices are working properly, a feature known as “device independence” that has been a major focus of quantum cryptography research for the past 15 years.

In the new protocol, the two devices at opposite ends of the transmission share a collection of EPR pairs, on which they perform measurements that determine the bits of a secret key. By mixing in these measurements with many rounds of the CHSH game, the devices can prove to their users that they are really doing what they claim.

The security of the key rests on a quantum physics principle called “monogamy of entanglement.” According to this principle, if two particles are entangled as an EPR pair, then neither particle can flirt with even the tiniest bit of entanglement with any other particle in the universe. This means that no matter what tools a potential eavesdropper has at her disposal, nothing will allow her to predict anything about the secret key.

The protocol isn’t efficient enough for practical implementation. But by loosening up the requirements about how much information users need to collect about their devices, Vazirani and Vidick have created a protocol whose key transmission rate is well within the bounds of practicality.

There are still substantial hurdles to overcome before such an apparatus can be built, Pironio said. Currently, it’s hard to transmit entangled photons over long distances without some photons getting lost in the process, which can compromise security.

Vidick remains optimistic, however. “Equipment is getting better very quickly,” he said.

While the idea of basing security on the Bell test is “very satisfying,” it’s important to be aware of the limitations of device-independent quantum cryptography, cautioned Nicolas Gisin, of the University of Geneva, a co-founder of the quantum cryptography company ID Quantique.

Proponents of the concept are fond of saying that since it’s not necessary to trust your devices, you could even buy them from an adversary. But that idea glosses over potential vulnerabilities. For example, the adversary could simply hide a radio transmitter inside one of the boxes that would broadcast the values of the secret key to an eavesdropper. “Unconditional security does not exist,” Gisin said.

What device-independent quantum cryptography does offer, though, is the promise that the only parts of your system that you have to check are the portions that use classical physics — like the box itself and the program that runs the protocol and tallies the results. Unlike the quantum devices, these are parts you can check as thoroughly as you wish. “Provided the classical part is trusted, you don’t have to trust the quantum part,” Gisin said.

For Vazirani, the most important implications of the new work lie not in its potential applications, but in its philosophical significance — the fact that it is possible to probe the secret inner life of a quantum system.

A classical being isn’t permitted to peek inside a quantum system and “see what is happening behind the scenes,” Vazirani said. “But it turns out that in this indirect way, you can look behind the curtain.

“To me, what’s most exciting is that it is possible to do this at all,” he said. “It need not have been this way.”

This article was reprinted on Wired.com.