Several algorithms have been discovered that cannot be run on classical computing systems. These quantum algorithms require operations that are allowed by quantum mechanics but not by classical physics. In order to run any one of these algorithms, hardware is required that is capable of supporting all of the operations required by that particular algorithm.
One important class of quantum algorithms are the adiabatic quantum algorithms. Initially discovered in 2000 by scientists at MIT, these algorithms solve formally intractable computational problems in a novel way. These algorithms are of intense interest for two main reasons. The first is that special-purpose hardware build specifically to run them is the most mature enablement of any quantum computing algorithm to date. The second is that early analysis of these algorithms show exponential speed-ups over classical approaches on certain typical case NP-hard problems. If the polynomial scaling seen for small problems continues into the low thousands of variables, this would be of extreme practical importance, as NP-hard optimization problems of this size are ubiquitous in science and business.
Recently techniques have been introduced for calculating the run time of the quantum adiabatic algorithms for problems up to about 128 variables; see here and here. While this is still too small to ultimately answer questions about the asymptotic scaling of these approaches, it is sufficient to predict the expected performance of adiabatic quantum computers of up to 128 qubits, which perhaps not coincidentally is the number of qubits in the Rainier design.
The approach outlined in the above referenced papers are based on Quantum Monte Carlo (QMC) techniques. These approaches allows the run time of a quantum adiabatic algorithm to be estimated. The approach is embarrassingly parallel and can efficiently make use of large numbers of independent processors. It is also extremely computationally expensive. These two points make the calculation of the runtime of the adiabatic quantum algorithms using QMC techniques ideally suited to a large-scale Internet-based distributed computation.
D-Wave and Dr. Peter Young (a co-author on one of the QMC papers referenced previously) have built a distributed QMC platform to calculate the run time of a quantum adiabatic algorithm relevant to the experimental hardware at D-Wave. The project is called AQUA (Adiabatic QUantum Algorithms), with the distributed version called AQUA@home. The distributed computing technology is based on BOINC, the same technology that enables SETI@home and a host of other large-scale distributed scientific computations.
AQUA is currently running internally at D-Wave. We have set up an external server at http://aqua.dwavesys.com/ that will shortly go live. This server is set up to accept volunteer cycles from individuals who wish to contribute computer time to the AQUA project and make a direct contribution to the advancement of scientific understanding of the quantum adiabatic algorithms. The AQUA@home program runs at low priority in the background of any internet-connected computer. All of the data acquired from AQUA will be published, and everyone who contributes cycles to the project will receive copies of all the publications arising from this work.
The specific project we have been working on internally to test the AQUA system calculates the runtimes for a particular type of problem ideally suited to our hardware. These problems are spin glass problems and are known to be NP-hard. This type of problem will be the first thing we run on AQUA@home to ensure that everything is working properly and will be the basis of the first publication.
After this we plan to run AQUA@home to compute the expected run time of our 128-qubit superconducting adiabatic quantum computing system, running the quantum adiabatic algorithm it enables, on problems generated by the binary classification machine learning application we co-developed with Vasil Dentchev and Hartmut Neven at Google.
I believe that the outcome of this particular project has significant implications for the field of quantum computation, as currently there are no widely accepted meaningful commercial applications of quantum computers. If quantum adiabatic algorithms can solve machine learning problems better than the best known classical approaches that would be a game changer for quantum computation, which currently relies on insufficient amounts of government funding, primarily for its potential role in breaking certain asymmetric cryptosystems, which of course has limited interest to partners and investors in the commercial world.
To conclude I am including here a poll; this is the first time I’ve tried to do this… should be easier than implementing a distributed continuous imaginary time quantum monte carlo program.