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)


SQuInT Chief Organizer
Akimasa Miyake, Assistant Professor

SQuInT Co-Organizer
Mark M. Wilde, Assistant Professor LSU

SQuInT Administrator
Gloria Cordova
505 277-1850

SQuInT Founder
Ivan Deutsch, Regents' Professor

Tweet About SQuInT 2018!