Friday, October 5, 2012

The CIA and Jeff Bezos Bet on Quantum Computing

http://www.technologyreview.com/news/429429/the-cia-and-jeff-bezos-bet-on-quantum-computing/

With funding from the Amazon founder and the CIA's investment arm, the Canadian company D-Wave is gaining momentum for its revolutionary approach to computing.

Entangled: This is part of the structure that cools and shields the D-Wave processor so it can (apparently) conduct its quantum calculations.

D-Wave Systems
Inside a blocky building in a Vancouver suburb, across the street from a dowdy McDonald's, is a place chilled colder than anywhere in the known universe. Inside that is a computer processor that Amazon founder Jeff Bezos and the CIA's investment arm, In-Q-Tel, believe can tap the quirks of quantum mechanics to unleash more computing power than any conventional computer chip. Bezos and In-Q-Tel are in a group of investors who are betting $30 million on this prospect.
If the bet works out, some of the world's thorniest computing problems, such as the hunt for new drugs or efforts to build artificial intelligence, would become dramatically less challenging. This development would also clear the tainted reputation of D-Wave Systems, the startup whose eight-year-long effort to create a quantum computer has earned little more than skepticism bordering on ridicule from prominent physicists.

D-Wave's supercooled processor is designed to handle what software engineers call "optimization" problems, the core of conundrums such as figuring out the most efficient delivery route, or how the atoms in a protein will move around when it meets a drug compound. "Virtually everything has to do with optimization, and it's the bedrock of machine learning, which underlies virtually all the wealth creation on the Internet," says Geordie Rose, D-Wave's founder and chief technology officer. In machine learning, a branch of artificial intelligence, software examines information about the world and formulates an appropriate way to act in the future. It underpins technologies such as speech recognition and product recommendations and is a priority for research by companies, such as Google and Amazon, that rely on big data.

"Our intelligence community customers have many complex problems that tax classical computing architecture," Robert Ames, vice president for information and communication technologies at In-Q-Tel, said in a statement released today. In-Q-Tel's primary "customer" is the CIA, and the National Security Agency is another. Both are known to be investing heavily in automated intelligence gathering and analysis.

Rose, a confident Canadian with a guitar and samurai sword propped in the corner of his windowless office, has been making grand claims to journalists since 2007, when he unveiled D-Wave's first proof-of-concept processor at a high-profile event at the Computer History Museum in Mountain View, California. Attendees saw a D-Wave processor (apparently) solve sudoku puzzles and find a close match to a particular drug molecule in a collection of other compounds. But in the weeks, months, and years that followed, skepticism and accusations of fraud rained down on the company from academic experts on quantum computing. Rose's initial predictions about how quickly the company would increase the size and capabilities of its chips fell by the wayside, and the company, although still well-funded, was publicly quiet.

Signing up Bezos and In-Q-Tel—the company's most prominent backers yet—is the latest in a series of events that suggest D-Wave thinks it is ready to finally answer its critics. In May 2011, the company published a paper in the prestigious journal Nature that critical academics said was the first to prove D-Wave's chips have some of the quantum properties needed to back up Rose's claims. Artificial intelligence researchers at Google regularly log into a D-Wave computer over the Internet to try it out, and 2011 also saw the company sign its first customer. Defense contractor Lockheed Martin paid $10 million for a computer for research into automatically detecting software bugs in complex projects such as the delayed F-35 fighter (see "Tapping Quantum Effects for Software that Learns"). Questions remain about just how its technology works, but D-Wave says more evidence is forthcoming. It is readying an improved processor that Rose calls the company's first true product rather than a piece of research equipment. D-Wave is expected to announce other major customers in coming months.

Cold Spot
Step inside D-Wave's ground-floor office suite and you're greeted by bland meeting rooms, offices, and cubicles. But open the correct door off the main corridor and you emerge into a bright white lab space dominated by four black monoliths—D-Wave's computers. Roughly cube-shaped, and around 10 feet tall, they emit a rhythmic, high-pitched sound as supercooled gases circulate inside. Each of the machines has a door on the side and is mostly empty, with what looks like a ray gun descending from the ceiling, a widely spaced stack of five metal discs of decreasing size held together with cables, struts, and pipes plated with gold and copper. It is actually a cold gun: the structure is a chilly -259 °F (4 °Kelvin) at the wide end and a few thousandths of a degree above absolute zero at its tip, where D-Wave's inch-square chip can be found. Not even the deepest reaches of space are this cold, or so shielded from magnetic fields as this chip, which is etched at a plant in Silicon Valley from a niobium alloy that becomes superconducting at ultralow temperatures.

The processor in every computer you've used is made from silicon and patterned with transistors that create logic gates—switches that are either on (represented by a 1 in the computer's programming) or off (a 0).  D-Wave's processors are also made up of elements that switch between 1 and 0, but they are loops of niobium alloy—there are 512 of them in the newest processor. These loops are known as qubits and can trap electrical current, which circles inside the loops either clockwise (signified by a 0) or counterclockwise (1). Smaller superconducting loops called couplers link the qubits so they can interact and even influence one another to flip between 1 and 0.

This delicate setup is designed so that the layout of qubits conforms to an algorithm that solves a particular kind of optimization problem at the core of many tasks difficult to solve on a conventional processor. It's like a specialized machine in a factory able to do one thing really well, on a particular kind of raw material. Performing a calculation on D-Wave's chip requires providing that raw material, in the form of the numbers to be fed into its hard-coded algorithm. It's done by setting the qubits into a pattern of 1s and 0s, and fine-tuning how the couplers allow the qubits to interact. After a wait of less than a second, the qubits settle into new values that represent a lower state of energy for the processor, and reveal a potential solution to the original problem.

What happens during that crucial wait is a kind of quantum mechanical argument. The qubits enter a strange quantum state where they are simultaneously both 1 and 0, like Schrodinger's cat being both dead and alive, and lock into a strange synchronicity known as entanglement, a phenomenon once described by Einstein as "spooky." That allows the system of qubits to explore every possible final configuration in an instant, before settling into on the one that is simplest or very close to it.

At least, that's what D-Wave's scientists say. Many questions remain about what actually happens inside the company's chips, not least in the heads of the company's own physicists, engineers, and computer scientists. "We're building this system empirically, not just following the theory," says Jeremy Hilton, the D-Wave vice president who leads its processor development. He and the company's other engineers don't know for sure what's happening in the chip, but as long as each design generates answers to the problems posed, the finer details of the quantum physics taking place inside can wait for retrospective validation.

It's an attitude that seems to have played well with investors, but it still rankles academics. "At an engineering level they've put together a setup that's impressive in various ways," says Scott Aaronson, an MIT professor who studies the limits of quantum computation. "But in terms of the evidence that they're solving problems using quantum mechanics faster than you could classically, I don't think it's there yet." A fierce critic of D-Wave in the years following its 2007 demo, Aaronson softened his stance last year after the company's Nature paper showing quantum effects. "In the past there was an enormous gap between the marketing claims and where the science was and that's come down, but there's still a gap," says Aaronson, who visited the company's labs in February. "The burden of proof is on them and they haven't met the burden yet."

Aaronson's biggest gripe is that the design of D-Wave's system could plausibly solve problems without quantum effects, in which case it would simply be a very weird conventional computer. He and other critics say the company must still prove two things: that its qubits really can enter superpositions and become entangled, and that the chip delivers a significant "quantum speed-up" compared to a classical computer working on the same problem. So far the company has presented proof of neither in a peer-reviewed forum.

Rose says that D-Wave is working on proving evidence of entanglement, and that recent head-to-head tests against classical computers showed it pulling ahead on the kind of computing problem that it is designed to solve.

Aaronson also says the way D-Wave's processor is hard-coded for one particular type of problem will inhibit the range of problems it might solve. In addition, the relatively small number of qubits on the processor today means it can handle only tiny strings of data. Using mathematical tricks to translate a problem into the right form to deal with those limitations, and reversing the process once D-Wave's chip has given its answer, could cause significant slowdowns, says Aaronson. Rose counters that a quantum processor will be fast enough to overcome any such penalties, and he says he has engineers working on ways to automatically translate normal programming code into what a D-Wave chip needs.

Whether or not D-Wave can satisfy Aaronson and other skeptics doesn't necessarily matter to investors and technology companies. That's because in so many areas of business, computing power is crucial to maintaining a competitive advantage, says Steve Jurvetson, a partner at venture capital firm Draper Fisher Jurvetson, who has invested in D-Wave twice and calls it "the most singular swing-for-the-fences technology" he ever funded. "The application space for this," he says, "is anywhere we've had to fall back on an heuristic—a rule of thumb—to solve a problem: day traders, molecular modeling, anyone in e-commerce and the Googles and Microsofts of the world." Companies such as Lockheed, Amazon, and big pharma companies are most familiar with the limits of conventional computers and will be first in line, says Jurvetson, but designing a new car or a new online store could also benefit.

Companies and government agencies have another, perhaps more urgent motivation to take a chance on a startup that has a beguiling idea but a few troubling loose ends. There is good reason to believe that the exponential growth in computing power seen over the last few decades is ending, says Bob Lucas, who directs research on supercomputing and quantum computing at the University of Southern California, where Lockheed's D-Wave computer is installed. Many of the regular advances in computing power have come from connections on chips shrinking year after year, but with leading chip maker Intel currently working on making them just 14 nanometers across, there's not much smaller things can get. "We're living in the last 10 years of exponential growth of [classical] computing power, and alternatives to that will become more of interest," Lucas says. He adds that through his experiments on Lockheed's D-Wave system he has been converted from "highly skeptical to cautiously optimistic" about the technology.