pith. sign in

arxiv: 1907.01789 · v1 · pith:RAXXHR7Qnew · submitted 2019-07-03 · 🧮 math.CO · quant-ph

An adiabatic quantum algorithm for the Frobenius problem

Joaqu\'in Ossorio-Castillo , Jos\'e M. Tornero This is my paper

Pith reviewed 2026-05-25 10:32 UTC · model grok-4.3

classification 🧮 math.CO quant-ph
keywords Frobenius problemadiabatic quantum algorithmQUBOApéry setnumerical semigroupDiophantine equationsquantum annealing
0
0 comments X

The pith

An adiabatic quantum algorithm solves the Frobenius problem by encoding the Apéry set as a QUBO.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an adiabatic quantum algorithm for the Frobenius problem, an NP-hard Diophantine question that asks for the largest integer not expressible as a non-negative combination of given coprime generators. It constructs this algorithm by converting the Apéry set of the corresponding numerical semigroup into a quadratic unconstrained binary optimization problem. The resulting formulation is intended to run on adiabatic quantum hardware such as the D-Wave 2X. A sympathetic reader would care because the approach supplies a concrete quantum route to an instance of a classically hard number-theory task.

Core claim

The authors present an adiabatic quantum algorithm that solves the Frobenius problem by translating the Apéry set of a numerical semigroup into a QUBO whose ground state encodes the Frobenius number, with the algorithm specifically engineered for execution on a D-Wave 2X machine.

What carries the argument

The encoding of the Apéry set into a QUBO problem whose ground state identifies the Frobenius number.

If this is right

  • The algorithm yields the Frobenius number for any pair of coprime generators once the corresponding QUBO is solved by adiabatic evolution.
  • Numerical-semigroup problems become accessible to quantum-annealing hardware through this encoding.
  • The method supplies an explicit reduction from the Frobenius problem to an instance of quadratic unconstrained binary optimization.
  • Small instances can be executed and verified directly on D-Wave 2X hardware.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same encoding strategy could be examined for semigroups generated by more than two integers.
  • Reliable performance would depend on the size of the QUBO that current annealing hardware can solve without excessive error.
  • Direct comparison against classical dynamic-programming solutions on the same small instances would test the mapping.
  • If the ground-state correspondence holds, the approach might extend to related Diophantine optimization tasks.

Load-bearing premise

The Apéry-set construction can be encoded as a QUBO whose ground state corresponds exactly to the Frobenius number and that the D-Wave 2X hardware will return that ground state with sufficient reliability for the instances considered.

What would settle it

Run the algorithm on the semigroup generated by 4 and 7, whose known Frobenius number is 9, and check whether the returned value matches 9.

Figures

Figures reproduced from arXiv: 1907.01789 by Joaqu\'in Ossorio-Castillo, Jos\'e M. Tornero.

Figure 1
Figure 1. Figure 1: File apery_set_member.mod param n := 3; param a := 1 11 2 19 3 23; [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: File numerical_semigroup.dat model apery_set_member.mod; data numerical_semigroup.dat; let s := 30; let i := 5; option solver gurobi; solve; display X; display K; [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: File apery_set_member.run 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Output for apery_set_member.run model apery_set_member.mod; data numerical_semigroup.dat; let s := 30; option solver gurobi; param apery_set {0..s-1}; for {l in 0..s-1} { let i := l; solve; let apery_set[l] := T; } display apery_set; [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: File apery_set.run apery_set [*] := 0 0 4 34 8 38 12 42 16 46 20 80 24 84 28 88 1 61 5 65 9 69 13 103 17 77 21 111 25 55 29 89 2 92 6 66 10 100 14 44 18 78 22 22 26 56 3 33 7 67 11 11 15 45 19 19 23 23 27 57 ; [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Output for apery_set.run Thus, as the difficulty of obtaining f(S) this way increments with respect to the number s we choose (we have to solve s ILPs), the smartest way of proceeding is by solving it in the case where s = min(S \ {0}) (i.e., s = a1, as done by [16]). The AMPL file that represents this approach is shown in [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: File frobenius_number.run f = 81 [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: File apery_set_member_lagr.mod with a large enough value of λ, we can obtain the same results without additional calls to the solver and just one iteration for each of the elements of the Apéry set. On the other hand, if we exceed in the value for λ, we would also need just one iteration per ωi , but the solver would need more time in order to find the global optimum. The latter behavior can be observed wh… view at source ↗
Figure 10
Figure 10. Figure 10: File apery_set_lagr.run 10 [PITH_FULL_IMAGE:figures/full_fig_p010_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Output for apery_set_lagr.run and λ (0) = 0 apery_set [*] := 0 0 4 34 8 38 12 42 16 46 20 80 24 84 28 88 1 61 5 65 9 69 13 103 17 77 21 111 25 55 29 89 2 92 6 66 10 100 14 44 18 78 22 22 26 56 3 33 7 67 11 11 15 45 19 19 23 23 27 57 ; iterations [*] := 0 1 3 1 6 1 9 1 12 1 15 1 18 1 21 1 24 1 27 1 1 1 4 1 7 1 10 1 13 1 16 1 19 1 22 1 25 1 28 1 2 1 5 1 8 1 11 1 14 1 17 1 20 1 23 1 26 1 29 1 ; lambdas [*] :… view at source ↗
Figure 12
Figure 12. Figure 12: Output for apery_set_lagr.run and λ (0) = 100 more concretely by one of the few D-Wave machines that currently exist worldwide. Our unconstrained problem, in QUBO form, is shown below (please note that, if x ∈ {0, 1}, then x = x 2 ): c0 + Xu m=0 cmkm + Xn j=1 Xtj l=0 cjlxjl! + X 1≤j<j0≤n   X 0≤l<l0≤min(tj ,tj 0 ) iqjl,j0 l 0xjlxj 0 l 0   + Xn j=1 "Xtj l=0 Xu m=0 qjl,mxjlkm !# + X 0≤m<m0≤u qm,m0 , wher… view at source ↗
Figure 13
Figure 13. Figure 13: Example of .qubo file 3 bits, find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec 001 -1.80000 Energy of solution 0 Number of Partitioned calls, 1 output sample 0.03002 seconds of classic cpu time [PITH_FULL_IMAGE:figures/full_fig_p012_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Output for the example .qubo file 12 [PITH_FULL_IMAGE:figures/full_fig_p012_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Introducing a problem inside the D-Wave 2X [PITH_FULL_IMAGE:figures/full_fig_p013_15.png] view at source ↗
read the original 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 Ap\'ery 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims to present an adiabatic quantum algorithm for the Frobenius problem (largest integer not expressible as non-negative integer combination of two coprime positive integers) by using the Apéry set of the associated numerical semigroup, translating the problem of finding its minimal element into a QUBO whose ground state is solved via quantum annealing on a D-Wave 2X machine.

Significance. If the QUBO encoding is proven correct and the hardware returns the ground state reliably, the work would supply a concrete quantum-annealing approach to an NP-hard problem in combinatorial number theory, with the Apéry-set reduction providing an explicit combinatorial bridge. The design is tailored to existing D-Wave hardware, which is a practical strength. However, the absence of a tightness proof for the penalties and of any verification that the returned state equals the Frobenius number limits the immediate significance to a proof-of-concept mapping.

major comments (2)
  1. [QUBO formulation] The QUBO construction (the translation of semigroup membership and ordering constraints into quadratic penalties): no analytic bound or proof is supplied showing that the chosen penalty coefficients dominate all feasible violations for arbitrary coprime generators a and b. Without this, it is possible for an invalid binary string to receive lower energy than the true minimal Apéry-set element, so the D-Wave output is not guaranteed to solve the Frobenius problem.
  2. [Results / Experiments] No experimental section or table verifies that the QUBO ground state recovered by the annealer equals the known Frobenius number on any concrete instance; the central claim therefore rests on an unverified assumption about both the encoding and the hardware behavior.
minor comments (1)
  1. [Abstract] The abstract states the algorithm 'solves' the problem but does not qualify the claim with the size limitations of current D-Wave instances or the requirement that the penalties be tight.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable comments on our paper. We address each major comment below and indicate how we plan to revise the manuscript.

read point-by-point responses

  1. Referee: [QUBO formulation] The QUBO construction (the translation of semigroup membership and ordering constraints into quadratic penalties): no analytic bound or proof is supplied showing that the chosen penalty coefficients dominate all feasible violations for arbitrary coprime generators a and b. Without this, it is possible for an invalid binary string to receive lower energy than the true minimal Apéry-set element, so the D-Wave output is not guaranteed to solve the Frobenius problem.

    Authors: The referee correctly identifies that our manuscript does not include a general analytic proof that the penalty terms dominate all possible violations for arbitrary coprime a and b. The QUBO is constructed by encoding the Apéry set conditions with quadratic penalties chosen to be larger than the maximum possible contribution from the objective terms for the instances we consider. We agree that without a general bound, the correctness is not rigorously proven for all cases. We will revise the manuscript to include a discussion of the penalty selection and, where possible, derive bounds for the penalty coefficients in terms of a and b. revision: yes

  2. Referee: [Results / Experiments] No experimental section or table verifies that the QUBO ground state recovered by the annealer equals the known Frobenius number on any concrete instance; the central claim therefore rests on an unverified assumption about both the encoding and the hardware behavior.

    Authors: Our manuscript presents the algorithmic mapping and does not include experimental results from the D-Wave 2X. This is because the focus is on the formulation of the problem as a QUBO rather than on hardware performance. We acknowledge that empirical verification on concrete examples would be beneficial to demonstrate the approach. We will add an experimental section with results for small values of a and b, comparing the recovered ground state to the known Frobenius number. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is a direct constructive reduction

full rationale

The paper presents a translation of the Frobenius problem (via Apéry set) into a QUBO instance whose ground state is asserted to encode the solution, to be solved on D-Wave hardware. No equations appear that define a quantity in terms of itself, no fitted parameters are relabeled as predictions, and no load-bearing uniqueness theorems or ansatzes are imported via self-citation. The construction is self-contained as an explicit penalty-based encoding; any question of whether the penalties are provably tight is a correctness issue, not a circularity reduction. The derivation chain therefore does not collapse to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract; the ledger is therefore empty.

pith-pipeline@v0.9.0 · 5600 in / 1129 out tokens · 36969 ms · 2026-05-25T10:32:42.470363+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    Release 1.5.1-beta4, 09-1002A-B., tech

    D-Wave: Programming with QUBOs. Release 1.5.1-beta4, 09-1002A-B., tech. rep., D-Wave Sys- tems, Inc., 2016

    work page 2016

  2. [2]

    Release 2.3, 09-1002A-B., tech

    D-Wave: Programming with QUBOs. Release 2.3, 09-1002A-B., tech. rep., D-Wave Systems, Inc., 2016

    work page 2016

  3. [3]

    http://www.gurobi.com, 2018

    Gurobi Optimizer Reference Manual. http://www.gurobi.com, 2018. Accessed: 2019-02-23

    work page 2018

  4. [4]

    Apéry,Géométrie algébrique - sur les branches superlineaires des courbes algebriques, Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 222 (1946), pp

    R. Apéry,Géométrie algébrique - sur les branches superlineaires des courbes algebriques, Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 222 (1946), pp. 1198–1200

    work page 1946

  5. [5]

    , Irrationalité deζ (2) etζ (3), Astérisque, 61 (1979), p. 1

    work page 1979

  6. [6]

    Barahona, On the computational complexity of Ising spin glass models, Journal of Physics A: Mathematical and General, 15 (1982), p

    F. Barahona, On the computational complexity of Ising spin glass models, Journal of Physics A: Mathematical and General, 15 (1982), p. 3241

    work page 1982

  7. [7]

    Quantum annealing with more than one hundred qubits

    S. Boixo, T. F. Rønnow, S. V. Isakov, Z. W ang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer , Quantum annealing with more than one hundred qubits, arXiv preprint arXiv:1304.4595, (2013)

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  8. [8]

    Booth, S

    M. Booth, S. Reinhardt, and A. Roy , Partitioning optimization problems for hybrid classi- cal/quantum execution, tech. rep., D-Wave Technical Report, 2017

    work page 2017

  9. [9]

    Brauer, On a problem of partitions, American Journal of Mathematics, 64 (1942), pp

    A. Brauer, On a problem of partitions, American Journal of Mathematics, 64 (1942), pp. 299– 312

    work page 1942

  10. [10]

    Brauer and J

    A. Brauer and J. E. Shockley , On a problem of Frobenius, Journal für die Reine und Ange- wandte Mathematik, 211 (1962), pp. 215–220

    work page 1962

  11. [11]

    Choi, Minor-embedding in adiabatic quantum computation: I

    V. Choi, Minor-embedding in adiabatic quantum computation: I. The parameter setting problem, Quantum Information Processing, 7 (2008), pp. 193–209

    work page 2008

  12. [12]

    Minor-universal graph design, Quantum Information Processing, 10 (2011), pp

    , Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design, Quantum Information Processing, 10 (2011), pp. 343–353

    work page 2011

  13. [13]

    Fourer, D

    R. Fourer, D. M. Gay, and B. W. Kernighan , A modeling language for mathematical programming, Management Science, 36 (1990), pp. 519–554

    work page 1990

  14. [14]

    , AMPL: A Modeling Language for Mathematical Programming, Duxbury Press, 2002

    work page 2002

  15. [15]

    Glover, Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13 (1986), pp

    F. Glover, Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13 (1986), pp. 533–549

    work page 1986

  16. [16]

    Greenberg , An algorithm for a linear Diophantine equation and a problem of frobenius, Numerische Mathematik, 34 (1980), pp

    H. Greenberg , An algorithm for a linear Diophantine equation and a problem of frobenius, Numerische Mathematik, 34 (1980), pp. 349–352

    work page 1980

  17. [17]

    Ising, Report on the theory of ferromagnetism, Zeitschrift für Physik, 31 (1925), pp

    E. Ising, Report on the theory of ferromagnetism, Zeitschrift für Physik, 31 (1925), pp. 253–258

    work page 1925

  18. [18]

    M. W. Johnson, M. H. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al. ,Quantum annealing with manufactured spins, Nature, 473 (2011), p. 194

    work page 2011

  19. [19]

    C. C. McGeoch , Adiabatic quantum computation and quantum annealing: Theory and practice, Synthesis Lectures on Quantum Computing, 5 (2014), pp. 1–93. 14

    work page 2014

  20. [20]

    librosa/librosa: 0.6.3,

    J. Ossorio-Castillo, jqnoc/numsem: numsem console. https://doi.org/10.5281/zenodo. 1257967, 2018

    work page doi:10.5281/zenodo 2018

  21. [21]

    C. H. Papadimitriou and K. Steiglitz , Combinatorial optimization: algorithms and complex- ity, Courier Corporation, 1998

    work page 1998

  22. [22]

    J. L. Ramírez-Alfonsín , Complexity of the Frobenius problem, Combinatorica, 16 (1996), pp. 143–147

    work page 1996

  23. [23]

    30, Oxford University Press on Demand, 2005

    , The Diophantine Frobenius problem, vol. 30, Oxford University Press on Demand, 2005

    work page 2005

  24. [24]

    J. C. Rosales and P. A. García-Sánchez , Numerical semigroups, vol. 20, Springer Science & Business Media, 2009. 15

    work page 2009