Tag Archives: bit

Quantum Computation: Spooky Arithmetic

Quantum computation holds the promise of vastly superior performance over traditional digital systems based on bits that are either “on” or “off”. Yet for all the theory, quantum computation still remains very much a research enterprise in its very infancy. And, because of the peculiarities of the quantum world — think Schrödinger’s cat, both dead and alive — it’s even difficult to measure a quantum computer at work.

From Wired:

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 swaths 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.

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.

Read the whole article here.