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 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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Apéry, R.: Sur les branches superlinéaires des courbes algébriques. C. R. Acad. Sci. Paris 222, 1198–1200 (1946)
Apéry, R.: Irrationalité de \(\zeta (2)\) et \(\zeta (3)\). In: Luminy Conference on Arithmetic. Astérisque, vol. 61, pp. 11–13 (1979)
Barahona, F.: On the computational complexity of Ising spin glass models. J. Phys. A: Math. Gen. 15(10), 32–41 (1982)
Boixo, S., et al.: Quantum annealing with more than one hundred qubits. arXiv preprint arXiv:1304.4595 (2013)
Boot, M., Reinhardt, S., Roy, A.: Partitioning optimization problems for hybrid classical/quantum execution. Technical report, D-Wave Systems, Inc. (2017)
Brauer, A.: On a problem of partitions. Am. J. Math. 64, 299–312 (1942)
Brauer, A., Shockley, J.E.: On a problem of Frobenius. J. Reine Angew. Math. 211, 215–220 (1962)
Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7(5), 193–209 (2008)
Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10(3), 343–353 (2011)
D-Wave Systems Inc: D-Wave: Programming with QUBOs. Release 1.5.1-beta4, 09-1002A-B (2016)
D-Wave Systems Inc: D-Wave: Programming with QUBOs. Release 2.3, 09-1002A-B (2016)
Fourer, R., Gay, D.M., Kernighan, B.W.: A modeling language for mathematical programming. Manag. Sci. 36(5), 519–554 (1990)
Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Duxbury Press (2002)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)
Greenberg, H.: An algorithm for a linear Diophantine equation and a problem of Frobenius. Numer. Math. 34(4), 349–352 (1980)
Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2018). http://www.gurobi.com. Accessed 23 Feb 2019
Ising, E.: Report on the theory of ferromagnetism. Z. Phys. 31, 253–258 (1925)
Johnson, M.W., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194 (2011)
McGeoch, C.C.: Adiabatic quantum computation and quantum annealing: theory and practice. Synth. Lect. Quantum Comput. 5(2), 1–93 (2014)
Ossorio-Castillo, J.: jqnoc/numsem: numsem console (2018). https://doi.org/10.5281/zenodo.1257967
Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Courier Corporation (1998)
Ramírez-Alfonsín, J.L.: Complexity of the Frobenius problem. Combinatorica 16(1), 143–147 (1996)
Ramírez-Alfonsín, J.L.: The Diophantine Frobenius problem. Oxford University Press, Oxford (2005)
Rosales, J.C., García-Sánchez, P.A.: Numerical Semigroups. Springer, New York (2009). https://doi.org/10.1007/978-1-4419-0160-6
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ossorio-Castillo, J., Tornero, J.M. (2022). Resolution of the Frobenius Problem with an Adiabatic Quantum Computer. In: Arai, K. (eds) Intelligent Computing. Lecture Notes in Networks and Systems, vol 283. Springer, Cham. https://doi.org/10.1007/978-3-030-80119-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-80119-9_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-80118-2
Online ISBN: 978-3-030-80119-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)