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 the first paper we present an algorithm which solves it, via a translation into a QUBO problem of the so-called Apéry set of a numerical semigroup. This algorithm was specifically designed to run in an adiabatic quantum computer (a D-Wave 2X machine), and the performance problems for this precise setting are also discussed.
In the second paper two quantum algorithms are presented, which tackle other well–known problems in the context of numerical semigroups: the numerical semigroup membership problem (NSMP) and the Sylvester denumerant problem (SDP). These problems have a well-studied complexity in the classical framework, so they can be used to compare classical and quantum performances (although the quantum algorithms are still to be refined).
Researchers: José María Tornero Sánchez, J. Ossorio-Castillo.
Related project: Arithmetic Geometry, D-Modules and Singularities (MTM2016-75027-P)
Related publications:
- J. Ossorio-Castillo, J.M. Tornero: Resolution of the Frobenius problem with an adiabatic quantum computer. Advances in Intelligent Systems and Computing, to appear (2021). https://arxiv.org/abs/1907.01789
- J. Ossorio-Castillo, J.M. Tornero: Quantum algorithms for the Sylvester denumerant and the numerical semigroup membership problem. International Journal of Unconventional Computing, to appear (2021).
iMAT research line: ⊕ RL11. Algebra, Geometry and Topology
