D-Wave demos quantum computer
By Steve Leibson, Tensilica, Inc. -- EDN, February 15, 2007
D-Wave, a Canadian company developing what it expects to be the world's first commercial quantum computer, unveiled a 16-qubit, proof-of-concept version of the hardware today. Probably. The venue was the Computer History Museum in Mountain View, California. Principals from D-Wave talked about the vast potential market for quantum computers and then gave a short demonstration, by remote control via the Internet. The actual quantum computer, dubbed Orion, resides in Burnaby—a suburb of Vancouver, British Columbia in Canada. So if there really was a quantum computer at the other end of the Internet, it did indeed solve some problems.
D-Wave's target is solving a set of problems known as NP-complete, which are complex problems that involve searching for a "best" answer given a large set of alternatives and constraints. These problems can be solved by today's computers using brute-force search methods but such methods take large amounts of time—many years for very complex problems. Briefly, D-Wave's Orion solves such problems by holding all possible solutions in a superposed state in a 16-qubit register, arranged in a ring on the 5x5 mm chip. A qubit is a quantum storage element that can hold a 0 or 1 (like a digital bit) and an infinite number of intermediate states, all in simultaneous superposition. The qubit's operation depends on the physics of quantum mechanics and, consequently, Orion operates at 4 mK (that's 4 thousandths of a Kelvin above absolute zero).
Orion accepts queries phrased in the common and familiar SQL (structured query language). The queries take the form of a general question: Given a set of elements and a way of ordering these elements, what is the "best" ordering given the following constraints? This type of problem commonly occurs in a large number of business domains including semiconductors (placement and routing), bioinformatics (molecule matching), logistics, finance, entertainment, communications, and security. Perhaps the most famous such problem is the "traveling salesman problem," which tries to minimize the distance a salesperson must travel while visiting a fixed set of cities.
Usually, the exact answer to these NP-complete problems cannot be found on conventional computers (Turing machines) except by exhaustive search. Algorithms exist to shorten the search by producing approximate answers, but these problems still take a long time, even when an approximate answer is sufficient. D-Wave's Orion determines the answer to such problems by creating "graphs" of problem solutions, superimposing all such graphs onto Orion's 16-qubit storage register, and then searching all answers in parallel to find the solution with the lowest energy, which is the right answer based on the graph constructions.
The process of obtaining the final answer is called "coherence" and after the answer has gelled in the storage register, it is read out as a binary value. Consequently, Orion can only produce 16-bit answers at the moment, which makes it a demonstration vehicle instead of a product because the machine's 16-bit range makes it approximately 100 times slower than current hardware based on familiar microprocessors. However, D-Wave's intent is to produce 1024-qubit machines based on Orion technology within the next 18 months. That machine would be approximately 10x faster than conventional microprocessor-based computers when solving NP-complete problems.
D-Wave CTO Giordie Rose was almost coy in his approach to not revealing exactly how Orion works. The 16-qubit register is built onto a chip using conventional optical semiconductor lithography methods and is fabricated at JPL in Pasadena, California. Orion's qubits are built from niobium SQUIDs (superconducting quantum interference devices), which have been used since their development in 1964 as sensitive magnetometers. Orion's 16-qubit chip is plunged into a bath of liquid helium at the cold end of a diffusion refrigerator and held at a temperature of 4 mK. Although not explicitly mentioned, there must also be a magnetic field involved.
Problem solving on the 16-qubit chip takes three major steps. First, the graphs are constructed by conventional computers and loaded into the 16-qubit chip as a superposed group. Each graph consists of a set of bits (1 or -1) and relationships between adjacent bits (alike, not alike, or no coupling). A graph represents an individual problem solution and each graph has a different energy level. Once all the graphs are loaded and superposed in the qubit register, the energy level on the 16-qubit chip is "slowly" lowered (possibly by altering the external magnetic field, SQUIDs are exquisitely sensitive to changes in magnetic flux) until the chip can hold only the solution graph with the lowest energy. The other superposed graphs vanish because the system lacks the energy to hold them. The solution-finding process uses a mechanism called quantum tunneling to make transitions among energy states, which makes Orion somewhat different from other quantum computing projects that rely on quantum entanglement. The remaining solution state is extracted as a simple binary value in the final step.
This solution-finding process is called adiabatic quantum computing and it was envisioned in theory before D-Wave built Orion. In fact, development of the adiabatic quantum computing algorithm set the direction for Orion's development. Details of how the solutions are superposed, how long it takes to achieve coherence, and the method used to produce coherence remain proprietary. Technical details are decidedly sketchy at this point.
D-Wave's event ended with three demonstrations of problem solving. The first problem was to find the closest structural match to a molecule of Prilosec (an early drug used against acid stomach) from a list of 97 other molecules. The structures of all the molecules were assembled as graphs and loaded into Orion's 16 qubits. In a matter of less than a minute, Orion delivered an ordered list of structurally similar molecules. Such a capability might be used to search for new drugs. In the second demonstration, Orion assembled a seating chart for a dinner party based on a number of constraints. This sort of problem is routine at weddings and at large diplomatic dinners. In the third demonstration, Orion quickly solved a number of randomly generated Sudoku puzzles.
D-Wave's plan is to pursue machines with larger qubit registers as the path to creating commercially viable products. The company plans to have a 32-qubit machine operating by the end of this year. In 2008, it plans to first develop a 512-qubit machine and then have a 1024-qubit machine by the end of the year. Because the announcement was a technology demonstration, no pricing or availability was announced. D-Wave's position is that quantum computers like Orion will complement rather than replace conventional computers. They're probably right.
Steve Leibson is a former EDN chief editor who now works for Tensilica, and volunteers as a docent at The Computer History Museum in Mountain View, CA.
