Southwest Quantum Information and Technology

Adiabatic quantum computing solution of the knapsack problem

Presenting Author: Mark W. Coffey, Colorado School of Mines

We illustrate the adiabatic quantum computing solution of the knapsack problem with both integer profits and weights. For problems with n objects (or items) and integer capacity c, we give specific examples using both an Ising class problem Hamiltonian requiring n+c qubits and a much more efficient one using n+[\log_2 c]+1 qubits. The discussion includes a brief mention of classical algorithms for knapsack, applications of this commonly occurring problem, and the relevance of further studies both theoretically and numerically of the behavior of the energy gap.

Read this article online: https://arxiv.org/abs/1701.05584

(Session 5 : Thursday from 5:00pm-7:00pm)