Uncategorized —

A detour into the strange world of quantum computing

A Vancouver startup promises to demo the first commercial quantum computer on …

On Tuesday, a startup company called DWave is going to be publicly demoing a quantum computing system that they call Orion. Is this the dawn of a new era of computing, or simply an exercise in hype? It's hard to say prior to the announcement, but my guess is a little of both. To fully appreciate why, we'll have to take a detour into the strange world of quantum computing.

Speeding calculations through superposition

In what passes for normal in the quantum world, a properly prepared quantum object kept in isolation from the environment will actually exist in all possible states (be they energy, spin, etc.) at once—it exists as a superposition of states. Depending on the inputs to the system, a single state will be the most probable one occupied; repeated measurements of the same, freshly-prepared system can identify this most probable state. If you think of that object as a bit, it's easy to see how calculations can be done: set it in a ground state, perform a calculation by providing an input that influences its state, and then read it. Repeat the process a few times to get the probabilities sorted, and you've done a 1-bit calculation with a quantum bit, or qbit.

Needless to say, such a computer would badly underperform whatever is currently running your cell phone. But in the quantum world, two objects can be entangled; the state of one is linked to the state of another. Thanks to the combination of superposition and entanglement, this two particle system will simultaneously exist in 22 states, but with only one probable state, influenced by experimental inputs. As more entangled particles are added, the system can simultaneously explore 2n possible answers, where n is the number of qbits.

This ability to explore a large number of states simultaneously has applications for a subset of a class of math problems called NP-complete. Those of you wanting to learn more about NP-complete problems can read more at Nobel Intent this afternoon, but their most important feature is that there are no algorithms that work consistently to find a solution to an NP-complete problem. This leaves brute-force testing of possible answers as the only generalized approach. The difficulty of solving an NP-complete problem is the foundation for the cryptography we all rely on to ensure the security of our transactions on the internet. But a 128-bit quantum computer could, via superposition, potentially test all keys at once, providing a rapid answer to an otherwise unapproachable problem.

Bringing theory to the real world

So, why is AMD talking about making one of their cores a GPU and not a quantum coprocessor? For one, allowing any of the quantum objects to interact with their environment will immediately destroy the entanglement, eliminating the system's superposition of states. Avoiding this takes a room full of equipment, much of it dedicated to chilling qbits to temperatures near absolute zero. For another, it's not always clear how to provide the system an input so that a single superposed state becomes probable. A few algorithms have been described (including a quantum database search) but currently, only a limited number of problems can be explored by a quantum computer.

Because of these limitations, quantum computers have rarely escaped the world of academic research labs. But DWave has attracted some academic talent, as well as both private and governmental funding. That combination of minds and money has gotten them to a point where they're ready to demonstrate a 16-bit quantum computer on Tuesday at the Computer History Museum. A repeat of the demo will occur on their home turf on Thursday; Ars will have a reporter in attendance.

The computer itself won't be traveling to the demo; it will be accessed remotely. It operates at 5 milliKelvin, just a hair above absolute zero, which requires some specialized equipment. The qbits are laid out on a four-by-four grid, and each is entangled with up to eight of its neighbors. It is designed specifically to solve NP-complete problems by reading the free energy state of the qbits, putting it in the class of computers called "adiabatic." There is some doubt within the quantum computing community regarding the utility of adiabatic systems compared to some of the alternatives being explored; a detailed examination of these issues appears at Nobel Intent.

It appears that there may be a number of additional reasons to question whether Orion will perform as promised. These go well beyond the Ars staff's ability to analyze the arguments; it's worth noting, however, that our physics expert (Chris Lee) was unable to find a single paper on this sort of system published by anyone at DWave. Although DWave's head scientist supplies links to some relevant publications coming out of the academic community, not all of these appear to have survived peer review.

Is DWave's demo all about their market position?

Dwave's demos will show Orion crunching through a database search and handling a seating plan with a large number of constraints, such as you might find at a wedding reception. It's probably safe to say that, despite any of the doubts about the company, Orion will almost certainly show a major speed advance when applied to these two problems. But, given the limitations and questions, and the fact that DWave doesn't appear to currently be hurting for money, why are they bothering?

I think Jon Stokes's recent analysis of the extension of x86 into new markets is probably informative here. Even when an x86 processor isn't necessarily the "best" solution (in terms of price or power requirements), the extensive set of software tools, support chips, and human expertise may make up for any deficiencies. I think DWave's announcement may be their attempt to try to become the x86 of the quantum world.

As best as anyone is aware (and as evidenced by the lack of a competing set of press releases), nobody else is close to putting together a usable quantum computer. The adiabatic system they're using may not wind up being the "best" in terms of its practicality or ability to solve a wide range of problems (the academic world is primarily working with other systems) but it's apparently ready for some sort of usage now. And that may be all DWave needs. If they can convince others to work with their system—code additional algorithms, provide high-level interfaces to Orion, work around its limitations—their approach may not have to be the "best" in any sense.

In order to induce developers to begin building up an Orion-specific toolkit, DWave plans to provide free access to Orion to anyone interested in porting software to it over the next few months. If this lure works out, it can ensure two things. First, that DWave will have customers interested in paying for access as more sophisticated successors to Orion come online. As second, that by the time other quantum system comes online, it will face a competitor with a variety of advantages in terms of tools and expertise.

You must to comment.