← Back to papers
An adiabatic quantum algorithm for the Frobenius problem
J. Ossorio-Castillo, J. Tornero·July 3, 2019
MathematicsPhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
The (Diophantine) Frobenius problem is a well-known NP-hard problem (also called the stamp problem or the chicken nugget problem) whose origins lie in the realm of combinatorial number theory. In this paper we present an adiabatic quantum algorithm which solves it, using the so-called Apery set of a numerical semigroup, via a translation into a QUBO problem. The algorithm has been specifically designed to run in a D-Wave 2X machine.