I will describe experiments to evaluate the performance of a quantum computing system (hardware plus software), for solving combinatorial optimization problems.
This unusual computing platform is manufactured by D-Wave Systems, Burnaby, Canada. It comprises a Linux front end together with an analog hardware chip containing qubits that are capable of quantum superposition. The chip solves optimization problems by a process known as quantum annealing (QA), based on the principles of adiabatic quantum computation (AQC).
Performance comparisons included three conventional solvers – IBM’s CPLEX, an open-source implementation of Tabu Search, and a branch-and-bound solver that performed well in a recent satisfiability competition. The solvers were tested using instances from three NP-Hard optimization problems: Quadratic Unconstrained Boolean Optimization (QUBO), Weighted Max 2-SAT (W2SAT), and the Quadratic Assignment Problem (QAP).
On general problems the hybrid software/hardware solver was competitive with, and sometimes outperformed, the conventional solvers. On “native” instances that can be solved directly in hardware, the quantum system found optimal solutions thousands of times faster than its nearest competitor, CPLEX.
I will also describe some tests to learn how performance of the quantum hardware depends on input properties.
This is joint work with Cong Wang of Simon Fraser University.
Megamenu Social