09 February 2007
Blog Home : February 2007 : Permalink
Twenty years before most scientists expected it, a commercial company has announceda quantum computer that promises to massively speed up searches and optimisation calculations.
D-Wave of British Columbia has promised to demonstrate a quantum computer next Tuesday, that can carry out 64,000 calculations simultaneously (in parallel "universes"), thanks to a new technique which rethinks the already-uncanny world of quantum computing. But the academic world is taking a wait-and-see approach.
Obviously there is bound to be a good deal of skepticism and the company website is rather bland at present - they say a new website will show up mid-Feb i.e. after the demos.
The key I think is the NP-complete problem because, as you probably recall from your theoretical computer science lectures, once you can solve one NP-complete problem in polynomial time you can solve all of them and very many popular problems such as routing convergence algorithms, scheduling algorithms and so on turn out to be NP-complete. So if this works and if the cost can be reduced to some reasonable level (currently the process seems to involve very low temperatures) then we could well see a "quantum leap" in our computer knowledge. As well as talking about the 5milliKelvin operating temperature, the CTO's blog explains what the demo will be doing like this:The Orion system is a hardware accelerator designed to solve a particular NP-complete problem called the two dimensional Ising model in a magnetic field. It is built around a 16-qubit superconducting adiabatic quantum computer processor. The system is designed to be used in concert with a conventional front end for any application that requires the solution of an NP-complete problem.
...
At the demo, what we’re going to do is run two different applications, live, on an Orion system residing in Burnaby, BC. Orion is designed such that it can be used remotely, and this is the mode we’ll be using for the demos.
The first application is a pattern matching application applied to searching databases of molecules. This is an app that we developed internally at D-Wave. This is an example of how to apply Orion to problems arising from association (or conflict) graphs.
The second is a third-party planning/scheduling application for assigning people to seats subject to constraints. Anyone who has tried to plan seating arrangements for a wedding should be familiar with this one. This is an example of applying Orion to constraint satisfaction problems.
As I understand it the second problem is a classic NP-complete problem which is not just useful in its own right (seating people on aircraft etc.) but is closely related to many scheduling problems such as those that schools, universities etc. struggle mightily with when trying to create classe timetables. However just becuase we have a problem moved from NP to P time does not mean we have a truly scalable general purpose solution. If the algorithm is proportional to say N5 or N6 then the change from NP to P still gives us a long time to solve problems when N is a few million (as it can easily be for a number of useful NP complete problems)