Events & Calendars Cathy McGeoch: "Experimental Evaluation of an Adiabatic Quantum Computer"

I will describe experiments to evaluate the performance of a quantum computing system (hardware plus software) for solving NP-hard combinatorial optimization problems.

This unusual computing platform is manufactured by D-Wave Systems of Burnaby, Canada. It comprises a Linux front end with an analog hardware chip that contains up to 512 quantum bits (qubits) capable of quantum superposition. The hardware 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 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/quantum 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 3,000 times faster than CPLEX. (Recent tests on a newer chip suggest that speedup factors of 10,000 or more are possible.)

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.