{"id":"472f610c-d9bf-45c7-a824-98364390b6ce","arxiv_id":"2412.15778","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":1.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A practical tutorial on encoding combinatorial optimization problems as QUBO/Ising models and solving them with quantum annealers and QAOA on gate-based machines.","lead":"This paper is a tutorial that explains, step by step, how to turn combinatorial optimization problems into the QUBO or Ising form that quantum annealers and gate-based quantum computers can handle. It walks through worked examples on D-Wave and Qiskit, so a generalist can see the full workflow from problem statement to sampled results.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Figure 4's D-Wave code omits the -2*x3*z term from the Eq. (39) QUBO, so the printed recipe does not implement the derived objective; Eq. (40) also repeats x2 instead of x1. Corrections are straightforward, but the tutorial is not reproducible as printed.","rationale":"The paper is a tutorial whose value rests on the reproducibility of its recipes. I checked the main mathematical steps: the local reduction for negative monomials is exact for minimization, the Rosenberg penalty rule is sufficient when P = 1 + sum |aS|, and the arithmetic in Examples 9, 10, 14, and 17 is consistent. The serious defect is concrete: the D-Wave code in Figure 4 omits one interaction term from Eq. (39), and Eq. (40) contains a repeated-variable typo. These errors do not invalidate the quadratic-modeling theory, but they do undermine the promise that a reader can follow the printed examples as-is and obtain the stated QUBOs. The reader's CONDITIONAL verdict already captures the need for corrections, so my read does not change the verdict; it sharpens the specific condition that should be fixed before acceptance.","tokens_in":21224,"tokens_out":24003,"duration_ms":206715,"concrete_test":"Build the QUBO from Figure 4 line by line in dimod and compare its coefficients with Eq. (39). Then run both the printed QUBO and the corrected QUBO through dimod.ExactSolver on the Example 2 instance. If the printed QUBO's minimum-energy assignments or their energies differ from the corrected ones, the code does not faithfully encode the derived objective. Separately, verify Eq. (40) by substituting all 16 assignments of x1,x2,x3,t in the corrected expression and checking that the minimum over t reproduces the original cubic term's values.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is practical: a reader should be able to follow the recipes and run the provided source code. The most load-bearing defect is that the flagship quantum-annealer code in Figure 4 does not match the QUBO derived in Eq. (39). Eq. (39) contains the Rosenberg penalty term P(x2x3 - 2x2z - 2x3z + 3z), but line 5 of the code includes only '- 2 * Binary('x2') * Binary('z')' and omits the '- 2 * Binary('x3') * Binary('z')' term. This changes the objective function: for an infeasible assignment with x2=0, x3=1, and z=1, the intended penalty is 7 while the printed code evaluates 21, so the code minimizes a different problem than the one derived in the text. The same section contains a visible typo in Eq. (40), where the linear part inside the parentheses is written 'x2+x2+x3-2' (x2 repeated) instead of 'x1+x2+x3-2'. The underlying mathematical transformations appear sound, so the weak point is not the theory but the fidelity of the presented code and equations, which is exactly what a reader would need to reproduce the tutorial's examples.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This tutorial-style paper presents a practical introduction to solving combinatorial optimization problems on quantum annealers and gate-based quantum computers. It develops the standard pipeline: encoding variables as qubits (binary, integer, categorical, permutation), transforming constrained problems into unconstrained pseudo-Boolean objectives with penalties, reducing higher-order polynomials to QUBO via Rosenberg's global penalty or a local quadratization, mapping QUBO to Ising for D-Wave, and implementing the objective and mixer unitaries for QAOA on gate-based machines. The paper includes worked examples (MAX-SAT and constrained integer optimization), D-Wave Ocean code, Qiskit code, and a discussion of open questions.","tokens_in":21482,"tokens_out":15929,"duration_ms":130665,"significance":"If corrected, the paper would be a useful educational resource. Its strengths are the explicit step-by-step derivations, the closed-form penalty bound of Eq. (36), the correct QUBO/Ising conversion, and the QAOA circuit decomposition with CNOT/RZ and RX gates. The paper is honest about limitations, including open questions on penalty selection and the unclear practical speedup of QAOA. However, the tutorial's practical promise is currently compromised by mismatches between the printed formulas and the printed code and by an inconsistent optimization direction in the QAOA section; these affect reproducibility but are locally fixable.","major_comments":[{"comment":"Figure 4 does not implement the QUBO derived in Eq. (39). Eq. (39) contains the Rosenberg penalty P(x2x3 - 2x2z - 2x3z + 3z), but line 5 of the code omits the '- 2 * Binary('x3') * Binary('z')' term. The consequence is not cosmetic: for the feasible assignment (x2=1, x3=1, z=1), the intended penalty is 0 while the printed code evaluates 7*(1 - 2 + 3) = 14, so the code minimizes a different objective than the one derived and discussed. Since the paper's stated goal is to let readers reproduce the examples, this code/equation mismatch must be fixed.","section":"5.2, Figure 4 and Eq. (39)"},{"comment":"Section 6 states that the classical optimizer should 'maximize the expected value of HP' in Eq. (42), where HP is built directly from the objective function f to be minimized (Example 17). The provided code in Figures 8 and 10 instead uses scipy.optimize.minimize on classical_obj_fn, which returns the average value of f over the samples. For the minimization problems treated in this paper, the expectation of HP should be minimized, not maximized. As written, the text tells the reader to do the opposite of what the correct code does; this needs to be reconciled, e.g., by changing 'maximize' to 'minimize' throughout Section 6 or by defining HP as the negation of the objective.","section":"6, Eq. (42), Figures 8 and 10"},{"comment":"Equation (40) writes the local quadratization as '-36(x2 + x2 + x3 - 2)t', repeating x2; the correct expression, following the rule stated earlier in Section 5.1 for the monomial -36x1x2x3, is '-36(x1 + x2 + x3 - 2)t'. This typo appears in the final formula of the running example and would be copied verbatim by a reader.","section":"5.1, Eq. (40)"}],"minor_comments":[{"comment":"The displayed formula 'P(xy - 2xz - 2yx + 3z)' should be 'P(xy - 2xz - 2yz + 3z)'. The following sentence and Eq. (39) use the correct form, but the displayed formula is wrong as printed.","section":"5.1, Rosenberg penalty formula"},{"comment":"Figure 8 uses '# Omitted' for build_ansatz and classical_obj_fn, even though these are defined in Figures 9 and 10. The listing should either include the definitions inline or explicitly say 'see Figures 9 and 10'; as printed, the code in Figure 8 is not runnable by itself.","section":"8, Figures 8-10"},{"comment":"The sentence 'We only showed one example of local transformation that is valid when the coefficient of the monomial is positive in negative in minimization (or positive in maximization)' is garbled and should read 'negative in minimization (or positive in maximization)'.","section":"5.1, local transformation paragraph"}],"recommendation":"major_revision","confidential_remarks":"The paper is a tutorial rather than a research contribution; for a journal that publishes tutorials this is within scope. The main concern is reproducibility: the errors in Figure 4, Eq. (40), and the maximization/minimization inconsistency are all fixable, but as submitted the paper does not deliver on its central practical promise. If the authors correct these and provide the corrected code, I would support publication. There is no concern about novelty or authorship; the citation pattern is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a tutorial, not a research paper, and it does not pretend otherwise. It walks a reader from integer, MAX-SAT, and permutation problems to QUBO/Ising, penalty methods, Rosenberg quadratization, QAOA circuits, and gives two worked examples, one for D-Wave and one for Qiskit. The equations I spot-checked are correct, the discussion of limitations is honest, and the references are the standard ones. If you need a place to point a new grad student, this is one of the better recent write-ups.\n\nWhat is new: essentially nothing. The transformations come from Rosenberg, Dattani, and the standard QAOA literature. That is fine for a tutorial; the value is pedagogical packaging, and on the whole it is clear and careful.\n\nSoft spots: three, all connected to the paper's promise of being a practical recipe. First, Eq. (40) has x2+x2+x3-2 where it should be x1+x2+x3-2. Visible typo, obvious fix. Second, the D-Wave code in Figure 4 is missing the -2*Binary('x3')*Binary('z') term that appears in Eq. (39). The code as printed minimizes a different penalty expression than the one derived. For the infeasible assignment x2=0, x3=1, z=1, the intended penalty is 7 but the printed code evaluates 21, so the flagship annealer example is not reproducible as printed. Third, the Qiskit listings are not self-contained: build_ansatz and classical_obj_fn are marked 'Omitted', so a reader cannot run the QAOA section without reconstructing code from the text. None of these are deep flaws; they are exactly what a careful referee should catch, and they should be fixed in the accepted version.\n\nThe math itself holds up. The penalty bound P = 1 + sum |a_S| is standard and correctly derived, the QUBO-to-Ising conversion checks out, and the QAOA circuit decompositions are right. The paper also says plainly that no practical quantum advantage is demonstrated and cites the relevant skeptical literature. That is honest scholarship.\n\nWho is this for: practitioners and students who want a single readable path through the encoding pipeline. It will not change research, but it is a useful teaching artifact. If it reached me as an editor, I would send it to peer review rather than desk reject it, and I would ask for the two fixes above before accepting.","headline":"A solid, honest tutorial on QUBO/Ising encoding and QAOA; no new results, but the printed D-Wave code and Eq. (40) don't match the math and should be fixed before anyone uses it as a recipe.","tokens_in":22033,"tokens_out":2731,"would_cite":false,"duration_ms":23932,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","81P68","90C09"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper provides a complete, repeatable recipe that transforms arbitrary combinatorial optimization problems into QUBO form and runs them on quantum annealers and gate-based machines.","keywords":["quantum optimization","QUBO","Ising model","quantum annealing","QAOA","pseudo-Boolean optimization","combinatorial optimization","quadratization"],"falsifier":"Enumerate all assignments of a small problem with a known optimum, such as a five-variable MAX-SAT instance with a cubic objective term, after applying the tutorial's encoding, penalty, and quadratization steps; compare the QUBO's global minimum with the original problem's optimum. If any instance yields a minimum at an infeasible assignment or a different objective value, the recipe's correctness guarantee fails.","tokens_in":21012,"feed_emoji":"⚛️","tokens_out":12384,"duration_ms":90497,"temperature":0.7,"pith_summary":"This paper is a practical tutorial whose goal is to establish that a non-specialist can take a combinatorial optimization problem stated as a polynomial, a set of constraints, or a MAX-SAT instance and, by following a fixed sequence of steps, run it on either a quantum annealer or a gate-based quantum computer. The sequence is: encode solutions with binary variables, fold constraints into penalty terms, reduce all higher-order monomials to a quadratic pseudo-Boolean function (a QUBO), and translate that QUBO into an Ising Hamiltonian for an annealer or into a QAOA circuit for a gate-based machine. The paper demonstrates the recipe on a constrained integer polynomial and on a MAX-SAT instance, reporting sampled solutions from both hardware types. If the recipe holds, it gives researchers an entry point for experimenting with quantum optimization without first becoming quantum physicists.","feed_headline":"One recipe maps combinatorial problems onto quantum machines","feed_subtitle":"Encoding, penalty, and quadratization steps carry small problems from statement to annealer or QAOA","key_machinery":"The machine that carries the tutorial is the QUBO encoding pipeline, a fixed sequence of algebraic transformations that lands a small combinatorial problem on quantum hardware; here QUBO is a quadratic unconstrained binary optimization model, a pseudo-Boolean function whose terms multiply at most two binary variables. The load-bearing pieces are the QUBO/Ising equivalence $x_j=(1-s_j)/2$ with its coefficient mapping, the global penalty rule $P=1+\\sum_{S\\subseteq[n],S\\ne\\emptyset}|a_S|$, the global quadratization identity $P(xy-2xz-2yx+3z)$ for replacing a product by a new variable, the local transformation $a(\\sum_{j\\in S}x_j-|S|+1)t$ for negative-coefficient monomials, and the QAOA ansatz built from $U(H_P,\\gamma_k)U(H_M,\\beta_k)$ with the diagonal Hamiltonian obtained by substituting $Z_j$ for each Ising variable. Each piece converts the previous step's output into the next machine's input, from polynomial objective to quadratic form to Ising Hamiltonian to parameterized quantum circuit.","core_discovery":"The paper's central claim is that the entire path from problem statement to quantum execution can be systematized. Integer variables are expanded into binary bits, with the most-significant bit adjusted for intervals that are not powers of two; categorical variables and permutations are encoded one-hot with sum-to-one constraints; and every constraint becomes an additive penalty whose constant is set to $P=1+\\sum_{S\\subseteq[n],S\\ne\\emptyset}|a_S|$, the sum of absolute monomial coefficients plus one, so no infeasible solution can outrank the best feasible solution. High-degree monomials are then quadratized, either globally by replacing a product of two variables with a new variable and adding the penalty $P(xy-2xz-2yx+3z)$, or locally by replacing a negative-coefficient monomial with a quadratic expression involving a new auxiliary variable. The resulting QUBO is translated to an Ising model for annealers, or converted via $x_j=(1-s_j)/2$ into a diagonal problem Hamiltonian whose QAOA circuit uses only $RZ$, $CNOT$, and $RX$ gates. The tutorial reports sampled solutions for both hardware types, with optimal assignments appearing most frequently, and concludes that the reader can reproduce these executions from the provided code.","pith_inferences":["The paper leaves implicit that applying the pipeline naively grows the qubit count with the sizes of the variable domains, the constraints, and the auxiliary quadratization variables; a natural consequence is that the recipe's near-term value is pedagogical and benchmarking rather than competitive on large instances.","A testable extension would be to automate the search over alternative quadratizations for each high-degree monomial and compare which choice yields the smallest penalty constant or the best annealer success probability, since the paper does not prove the local transformation is optimal.","The paper notes that low-depth QAOA expectation values can be evaluated classically; this suggests the gate-based workflow could be restructured to tune angles on a classical computer and use the quantum device only for final sampling.","A broader inference, in line with the paper's closing discussion, is that once encoding is automated the main open challenge shifts to algorithm design: better penalty rules and problem-structure-aware transformations would matter more than the initial mapping to QUBO."],"forward_implications":["A reader can follow the tutorial's encoding rules to represent bounded integer, categorical, and permutation variables in binary form, so the recipe covers many NP-hard combinatorial problems in a uniform way.","Because the penalty constant rule $P=1+\\sum|a_S|$ is argued to separate feasible from infeasible solutions, constraints can be handled mechanically: square the transformed constraint and add a slack variable for inequalities.","Once the objective is a QUBO, the same object feeds both paradigms: it becomes an Ising Hamiltonian for quantum annealers and a diagonal problem Hamiltonian whose QAOA circuit is implemented with $RZ$, $CNOT$, and $RX$ gates.","The reported runs on small instances show optimal assignments as the most frequent samples on both kinds of hardware, which makes the workflow usable as a teaching and experimentation tool at current scales.","The paper's own discussion identifies penalty tuning, quadratization variable count, and transformation choice as open issues that determine whether the recipe scales beyond toy instances."],"supporting_citations":[{"why":"Supplies the global penalty expression used to replace a product of two variables by a new variable in order reduction.","marker":"[35]"},{"why":"Provides the compilation of local quadratization transformations for higher-order monomials, the alternative order-reduction strategy.","marker":"[16]"},{"why":"Defines the QUBO model that anchors the whole formulation workflow.","marker":"[29]"},{"why":"Introduces QAOA, the variational algorithm whose ansatz the tutorial constructs for gate-based machines.","marker":"[20]"},{"why":"Formulates adiabatic quantum computation, the theoretical basis for the quantum annealer paradigm.","marker":"[1]"},{"why":"States the adiabatic theorem, which underpins the claim that slow evolution keeps the annealer in the ground state.","marker":"[9]"},{"why":"Introduces quantum annealing in the transverse Ising model, the process that quantum annealer hardware implements.","marker":"[27]"}],"fun_headline_variants":["Encode, penalize, quadratize: the quantum optimization recipe","From statement to annealer: a systematic quantum mapping guide","Quantum optimization cookbook: from statement to QAOA or annealer","One recipe, many problems: quantum optimization made systematic","Small problems, big recipe: systematic quantum optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the paper's order-reduction rules and penalty-constant rule preserve the global optimum for every input problem, so that after transformation no infeasible solution is ever better than the true best feasible solution.","fun_headline_variants_meta":{"raw":{"variants":["Encode, penalize, quadratize: the quantum optimization recipe","From statement to annealer: a systematic quantum mapping guide","Quantum optimization cookbook: from statement to QAOA or annealer","One recipe, many problems: quantum optimization made systematic","Small problems, big recipe: systematic quantum optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001398,"raw_usage":{"total_tokens":5643,"prompt_tokens":922,"completion_tokens":4721,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":538,"completion_tokens_details":{"reasoning_tokens":4638}},"tokens_in":538,"tokens_out":4721,"duration_ms":29652,"temperature":1.0,"reasoning_tokens":4638,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:06:19.708972+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all assignments of a small problem with a known optimum, such as a five-variable MAX-SAT instance with a cubic objective term, after applying the tutorial's encoding, penalty, and quadratization steps; compare the QUBO's global minimum with the original problem's optimum. If any instance yields a minimum at an infeasible assignment or a different objective value, the recipe's correctness guarantee fails.","supporting_citations":[{"cited_title":"Cahiers Centre Etudes Rech","cited_arxiv_id":null,"evidence_quote":"Supplies the global penalty expression used to replace a product of two variables by a new variable in order reduction."},{"cited_title":"Reviews of Mod- ern Physics 90(1), 015002 (2018)","cited_arxiv_id":null,"evidence_quote":"Formulates adiabatic quantum computation, the theoretical basis for the quantum annealer paradigm."},{"cited_title":"Zeitschrift f¨ ur Physik51(3), 165–180 (1928)","cited_arxiv_id":null,"evidence_quote":"States the adiabatic theorem, which underpins the claim that slow evolution keeps the annealer in the ground state."},{"cited_title":"Physical Review E 58(5), 5355 (1998)","cited_arxiv_id":null,"evidence_quote":"Introduces quantum annealing in the transverse Ising model, the process that quantum annealer hardware implements."}],"review_version":1}