2017/01/19 by Mark W. Coffey, Coffey, Mark W. · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1701.05584
openalex publication_date 2017/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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+[log2 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. Included too is a demonstration and commentary on a version of quantum search using a certain Ising model. Furthermore, an Appendix presents analytic results concerning the boundary for the easy-versus-hard problem-instance phase transition for the special case subset sum problem.