Understanding Quantum Computing

Stephen DeAngelis

September 18, 2013

Let’s face it quantum computing is not an easy subject. Understanding, for example, that a qubit can simultaneously represent both a 0 and 1 and that it would only take 300 qubits to hold all of the data that has ever been created since the big bang takes a little mind bending. In previous posts about quantum computing, I’ve noted that scientists have argued about whether the computer designed and marketed by D-Wave is a quantum computer. You would think that such a thing would be easy to determine; but you would be wrong. Erica Klarreich explains:

“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.” [“Is That Quantum Computer for Real? There May Finally Be a Test,” Wired, 23 August 2013]

Before continuing the discussion about the difficulty of determining whether a machine is a quantum computer or not, you should watch the following video. As Mike James reports, “This animation … might give you some idea as to why quantum computers are more powerful – or potentially more powerful – than a classical computer.” [“Quantum Computers Animated,” I Programmer, 25 August 2013] As terrific as the animation is, James warns that you are still likely “to be mystified. Quantum computers are difficult to understand because they rely on the mathematics of quantum mechanics and most people don’t understand the math.”

 

 

If you watched the video, then it will be easier for you understand what James writes next:

“It is too easy to say that the reason a quantum computer is more powerful is that a qubit, or quantum bit, can represent a zero and a one at the same time. This seems like a powerful idea, but it doesn’t really give you much that is new in terms of computation. It is only when you allow a set of qubits to be entangled do you get really new behavior. When qubits are entangled the result of one measurement affects another and you can use it for encryption and computation. The big problem is that entangled states are corrupted by any interactions with the outside world – a problem known as decoherence. So far this has made building quantum computers with more than a small number of qubits difficult.”

Eric Limer adds, “Someday, somehow, quantum computing is going to change the world as we know it. Even the lamest quantum computer is orders of magnitude more powerful than anything we could ever make today. But figuring out how to program one is ridiculously hard.” [“Why Programming a Quantum Computer Is So Damn Hard,” Gizmodo, 23 August 2013] Jeremy O’Brien, a professor at the University of Bristol, agrees with Limer about how difficult it is to code for a quantum computer. “A quantum computer can do things faster for you, but someone has to program it,” he states, “and at the moment there are only a handful of people around the world who would be qualified.” If that situation remains, he and colleagues know that it will mean that there will be “a dearth of skilled coders when the expected quantum revolution finally arrives.” To remedy that situation, they are making available to “anyone with a web browser” a quantum chip capable running basic algorithms over the internet. [“Quantum chip connected to internet is yours to command,” NewScientist, 6 September 2013]

 

Limer’s claim that quantum computing is “going to change the world” leaves the impression that there is something magical about a quantum computer. James reminds us, however:

“A quantum computer cannot compute anything that a classical computer cannot. Indeed the operation of a quantum computer can be simulated by a classical computer, but it might take longer than the lifetime of the universe to complete the job. Quantum computers promise fast solutions nothing more.”

That’s really the point. Quantum computers will allow us to make computations that, for all practical purposes, are currently impossible. Will this change the world? Possibly. James points out that D-Wave’s machine is “a quantum annealing device which can be used to solve specific optimization problems. It is more like a quantum analog computer than anything else.” That’s been part of the controversy and brings us back to Klarreich’s article about trying to figure out if a computer is really quantum computer. She writes:

“It turns out … 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, [Umesh Vazirani of the University of California, Berkeley], 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.'”

Klarreich’s article contains a lot more interesting information about the quirkiness of quantum physics and you should check it out. Researchers are continuing to make breakthroughs in the area of quantum computing; but, no one has any idea when a true quantum computer (i.e., one that can be confirmed by the interrogation test) will be built.