Experimental Evaluation of an Adiabiatic Quantum System for Combinatorial Optimization (10 pages)
This paper presents an experimental study of algorithms based on quantum annealing (a type of AQC computation)running on a special-purpose D-Wave Two platform containing 439 quantum bits (qubits). Earlier systems with between 84 and 108 qubits have been used for finding Ramsey numbers, binary classifi cation in image matching, and 3D protein folding.
The “native” problem for this system is a restriction to Chimera-structured inputs defi ned in Section 2 of the Ising
Spin Model (IM). Native instances can be solved directly on the quantum hardware (QA), while general inputs are solved by a hybrid approach (called Blackbox) that alternates heuristic search with hardware queries.
We report on two experimental projects. First, QA and Blackbox are compared to three conventional software solvers:
CPLEX, METSlib tabu search (TABU), and a branch-and-bound solver called Akmaxsat (AK) . The solvers are evaluated using instances from three NP-Hard problems: Quadratic Unconstrained Binary Optimization (QUBO); Weighed Maximum 2-Satisfi ability (W2SAT), and the Quadratic Assignment Problem (QAP).
In horserace terms, QA dominates on the Chimera-structure QUBO problems: at the largest problem size n = 439, CPLEX (best among the software solvers), returns comparable results running about 3600 times slower than the hardware. On the W2SAT problems, Blackbox, AK, and TABU all find optimal solutions within the same time frame. On the QAP problems, Blackbox nds best solutions in 28 of 33 cases, compared to 9 cases for TABU (the next-best solver on these inputs).
Note that these results can be regarded as “snapshots” of performance for specifi c implementations on specifi c input sets, nothing more. Experimental studies of heuristics are notoriously diffi cult to generalize.
Future research will likely turn up better solvers and strategies. As a case in point, our second project compares the V5
hardware chip used in our first study to a V6 chip that became operational after the study was completed. V6 is three to five times faster than V5, and can solve problems as large as n = 502 (502 qubits).
Conclusions and future work
This paper reports on the first experiments we know of to compare performance of a quantum annealing system to conventional software approaches, using instances from three NP-Hard optimization problems. In all three experiments the V5 hardware or its hybrid counterpart Blackbox found solutions that tied or bettered the best solutions found by software solvers. Performance was especially impressive on instances that can be solved directly in hardware. On the largest problem sizes tested, the V5 chip found optimal solutions in less than half a second, while the best software solver, CPLEX, needed 30 minutes to fi nd all optimal solutions.
We have also carried out some tests to compare V6 to the software solvers; very preliminary results suggest that on QUBO instances with n = 503, the hardware can find optimal solutions around 10,000 times faster than CPLEX.
Our results have turned up many ideas for future experiments, including expanding these tests to a wider set of problem domains and solvers; looking at how problem transformations a ect performance; developing good algorithms and heuristics for minor-embedding in hardware graphs; and investigating ideas for auto-tuning Blackbox. There is also much work to be done in understanding how performance of hardware chips like V5 and V6 depends on input parameters, including size, density, objective function, and weight distributions and scale.
It would of course be interesting to see if highly tuned implementations of, say, tabu search or simulated annealing
could compete with Blackbox or even QA on QUBO problems; some preliminary work on this question is underway. The open questions about the fundamental capabilities of adiabatic quantum computers, algorithms, and models of computation are myriad, too many to be listed here.
If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.