{"id":"17e5cfce-3b69-4883-8f80-7435e3d9f24a","arxiv_id":"2411.10062","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"On three tiny railway-timetabling instances, QAOA with a polynomial (PUBO) encoding returned optimal feasible solutions in 55-71% of runs versus 4-8% for a quadratic (QUBO) encoding.","lead":"This paper compares two ways of encoding a simplified railway timetabling problem for the quantum algorithm QAOA, a quadratic (QUBO) and a polynomial (PUBO) encoding. On three tiny instances, PUBO found optimal solutions far more often, but the experiments mix several causes. Generalists may read it for a clear illustration that problem formulation matters for near-term quantum optimization.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The PUBO-vs-QUBO numerical advantage may be an artifact of unequal qubit counts and 10-shot sampling; the comparison is not controlled.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing concern: the numerical comparison conflates qubit count, sampling noise, slack variables, and penalty shape. This is not a flaw in the mathematical reformulations, which appear correct, but in the evidential support for the abstract's 'PUBO outperforms QUBO' claim. The paper's own discussion and conclusion concede the confound, so the authors are aware of it; nevertheless, the quantitative claim is the paper's central contribution and the current evidence does not isolate it. A controlled rerun with exact expectation values and qubit-matched PUBO padding would settle whether the gap is a formulation effect or a sampling-size artifact. The reader's CONDITIONAL verdict is appropriate; my analysis does not move it.","tokens_in":18102,"tokens_out":6583,"duration_ms":73608,"concrete_test":"Rerun all three instances of Section 4 with QAOA p=1 and COBYLA, but replace the 10-shot sampling with a noiseless statevector computation of the exact expectation value at each optimizer step. In a second arm, pad the PUBO circuit with spectator qubits (zero-cost terms) so that its qubit count matches the QUBO's. If the optimal-solution fractions in Table 3 converge or reverse, the claimed PUBO advantage is an artifact of qubit count and shot noise; if they remain separated under both arms, the formulation/landscape effect is real.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central numerical claim—Section 4, Table 3—is that (Extended-BP-PUBO) returns optimal solutions in 55–71% of runs while (Extended-BP-QUBO) returns 4–8%, with 0% infeasible versus 10–13%. But the two formulations differ in several simultaneous ways: qubit count (7/9/11 vs 15/17/20), Hilbert-space size sampled by 10 shots per COBYLA step, the presence of slack variables (s, r^bin) in the QUBO that must also be optimized, and penalty shape (binary vs squared-integer). The paper itself acknowledges in Section 4.2 that 'it is undeniable that the number of qubits plays a role' and in the Conclusion that 'the two reformulations we compare involve many simultaneous effects.' Because only 10 shots are used per iteration, the probability of measuring a good basis state depends exponentially on qubit count; the QUBO search space is 2^8 to 2^9 times larger than the PUBO one on these instances. The observed performance gap is therefore consistent with a pure sampling-size effect and does not by itself establish that the binary-penalty PUBO encoding is intrinsically better. The theoretical reformulations in Sections 2–3 appear internally consistent; the weak link is the uncontrolled experiment, and no code, circuits, or raw logs are provided for independent verification.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the choice of unconstrained binary optimization formulation for QAOA. It proposes a generic reformulation of polynomial constrained problems into PUBO, a specialized PUBO with binary-valued penalties for linear constraints, and two generic QUBO reformulations. It applies the PUBO-with-binary-penalties and one QUBO reformulation to a simplified railway timetabling problem modeled as an Extended Bin Packing problem, and reports numerical QAOA results on three small instances in which the PUBO formulation returns optimal solutions much more often than the QUBO formulation. The theoretical reformulations are proven in Section 2 and Appendix A, but the numerical comparison is not controlled for several confounding factors.","tokens_in":18417,"tokens_out":6811,"duration_ms":69079,"significance":"If the numerical claim were established, the paper would provide a practically useful insight: the choice of polynomial degree and penalty shape can materially affect QAOA performance, and a PUBO formulation with binary penalties may be preferable for problems with linear constraints. The paper also contains a genuinely reusable methodological contribution: a generic transformation from (IP-poly) to PUBO, a specific construction of binary-valued penalties for linear constraints, and a valid lower bound on penalty coefficients in Proposition 2.2. The proofs in Appendix A are detailed and machine-checkable in principle. However, the experimental evidence currently does not support the headline claim because the PUBO and QUBO formulations differ simultaneously in qubit count, slack variables, penalty range, and circuit depth, and the authors explicitly acknowledge these confounds in Sections 4.2 and 5.","major_comments":[{"comment":"The central claim that the PUBO formulation outperforms the QUBO formulation is not established by the reported experiment. The two formulations differ in at least four simultaneous ways: number of qubits (7/9/11 versus 15/17/20), presence of slack variables (s, r^bin) in the QUBO, penalty function shape (binary versus squared-integer), and the resulting circuit depth. The authors themselves state in Section 4.2 that 'it is undeniable that the number of qubits plays a role' and in the Conclusion that 'the two reformulations we compare involve many simultaneous effects.' This explicit admission means the observed gap in optimal-solution rates (55-71% versus 4-8%) cannot be attributed to the PUBO encoding without a controlled comparison. I recommend additional experiments that isolate these factors, for example by padding the PUBO circuit with idle qubits to match the QUBO qubit count, or by comparing a PUBO with non-binary penalties and a QUBO without slack variables for the (Uni) constraints. The raw data, random seeds, and code should also be made available so the experiment can be reproduced.","section":"Section 4, Table 3 and Section 4.2"},{"comment":"The use of only 10 shots per COBYLA iteration creates a severe sampling-size confound. With 10 shots, the probability of measuring a given optimal basis state declines exponentially with the number of qubits, and the QUBO search space is 2^8 to 2^9 times larger than the PUBO search space on these instances. The observed performance gap is therefore consistent with a pure sampling-size effect: QAOA on the QUBO formulation simply has fewer shots relative to the size of the Hilbert space. To support the claim, the authors should either scale the number of shots to the search space dimension (e.g., take 2^{n_QUBO-n_PUBO} times more shots for QUBO) or compute the expectation value exactly at each iteration, as they themselves suggest in the Conclusion. Without such a control, the numerical advantage reported in Table 3 does not demonstrate that the binary-penalty PUBO encoding is intrinsically better.","section":"Section 4.1, Nshots = 10"},{"comment":"The QUBO baseline is a specific formulation with slack variables, and the paper does not compare against alternative QUBO formulations that would reduce the confound. For the (Uni) constraint, a slack-free quadratic penalty exists: sum_{i<j in G_j} y_{i,j} y_{j,j} is 0 if at most one train is chosen and at least 1 otherwise. For the (Capa) constraint, a squared slack may be necessary for a quadratic formulation, but the paper should still test how much of the observed gap is due to the slack variables per se versus the polynomial degree, for example by comparing (Extended-BP-PUBO) against a PUBO formulation with non-binary (e.g., squared) penalties while keeping the same variable set. Without such ablations, the conclusion that 'the PUBO reformulation outperforms the QUBO one' conflates the effect of the formulation with the effect of the specific QUBO construction chosen.","section":"Section 3.3.2, Proposition 3.6 and Eq. (1)"}],"minor_comments":[{"comment":"The text says the binary decomposition requires floor(log2(x)) + 1 variables, but x is a variable and the expression should refer to an upper bound on the variable's range; also the case x = 0 is undefined and should be handled separately.","section":"Section 2.3.1"},{"comment":"In the definition of rbin_i, the formula writes '2k' but should be '2^l' to match the summation index l, and the variable k is reused inconsistently.","section":"Section 3.3.2"},{"comment":"The sentence justifying Nshots = 10 as maintaining 'a reasonable ratio between the sample size and the search space size' is misleading because 10 shots versus a search space of up to 2^20 states is not a reasonable ratio; the sentence should be rephrased or the choice justified differently.","section":"Section 4.1"},{"comment":"The sentence 'QAOA is one of the most short-term promising quantum-classical algorithm' has a grammar error; it should be 'algorithms'.","section":"Abstract"},{"comment":"The notation (fmin; fmax) for the range of objective function values would be clearer as [fmin, fmax], and the reference to 'Optimal solutions (in red)' should explicitly point to Figures 1-3, which are not described in the main text.","section":"Table 2"},{"comment":"The phrase 'future work should also be dedicated to assess the impact of the noise' should read 'to assessing the impact of noise', and the paper could cite the original COBYLA method (Powell, 1994) and the Qiskit library for completeness.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The theoretical parts are solid and likely publishable; the numerical claim is the advertised payoff and currently lacks controlled evidence. The authors' own statements in Sections 4.2 and 5 already concede the main confounds, so the revision path is clear. I would not reject the paper outright, but the experiment needs substantial rework before the claim can be accepted. The self-citation to Grange et al. (2023) for the PUBO circuit decomposition is appropriate and does not appear to be a novelty issue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Camille,\n\nThe theory part is solid and the authors deserve credit. The generic PUBO reformulation with binary-valued penalties for linear constraints is presented cleanly, the proofs in Appendix A check out, and Proposition 2.2's penalty bound is standard but valid. Applying this to a simplified railway timetabling problem (extended bin packing) is a sensible case study. They are also transparent: they openly state that the two formulations differ in several ways at once and that the qubit count plays a role. That honesty is rare.\n\nThe soft spot is the numerical claim. The headline result—PUBO returning optimal solutions 55–71% of the time versus 4–8% for QUBO—is real on these three instances, but the experiment is not controlled. QUBO has roughly double the qubits because of slack variables, a search space 2^8–2^9 times larger, only 10 shots per iteration, and a different penalty shape. Any one of those differences could produce the gap. The paper's own discussion acknowledges this. Without a slack-free QUBO baseline, a qubit-matched comparison, or exact expectation values instead of shot noise, the claim that the formulation itself is better is not established. No code, circuits, or raw logs are provided, so independent verification is impossible.\n\nThe binary penalty formulas are not really new—they are inclusion-exclusion over subsets, similar to constructions in Lucas (2014) and others—but the generic packaging for linear constraints is a useful reference. The self-citation to Grange et al. (2023) is fine; that decomposition is published and not the contested part.\n\nWho is this for? Researchers working on QAOA formulation choice will find a clean worked example and penalty constructions they can lift. It is not evidence of a general PUBO advantage. I would send it to peer review because the formulation question is real and the theory is usable, but I would require major revision: controlled experiments separating qubit count from penalty shape, more instances, and shipped artifacts. As it stands, the conclusion should be framed as a hypothesis, not a demonstrated outperformance.","headline":"Solid theory and honest caveats, but the PUBO-vs-QUBO numerical advantage is not established because the comparison conflates qubit count, slack variables, and penalty shape.","tokens_in":18883,"tokens_out":2128,"would_cite":false,"duration_ms":21962,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C10","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a polynomial binary encoding with 0-1 penalty terms outperforms the quadratic encoding for QAOA on a simplified railway timetabling problem.","keywords":["QAOA","PUBO","QUBO","railway timetabling","extended bin packing","binary penalty function","variational quantum algorithm","combinatorial optimization"],"falsifier":"Run the same three instances with a slack-free QUBO formulation, or with the PUBO and QUBO qubit counts matched by adding idle qubits to the PUBO circuit, using the same COBYLA settings; if the QUBO then reaches or exceeds the PUBO feasible-optimal rates, the paper's claim that the binary-penalty PUBO formulation is the better encoding for this problem would be refuted.","tokens_in":17964,"feed_emoji":"🚆","tokens_out":11770,"duration_ms":114400,"temperature":0.7,"pith_summary":"This paper makes the case that the encoding of a constrained optimization problem into an unconstrained binary model is itself a performance lever for the Quantum Approximate Optimization Algorithm (QAOA). It develops generic recipes for converting any polynomial constrained problem into either a Polynomial Unconstrained Binary Optimization (PUBO) problem or a Quadratic Unconstrained Binary Optimization (QUBO) problem, and it constructs a PUBO variant, for linear constraints, whose penalty terms evaluate to exactly 0 or 1. The recipes are applied to a simplified industrial railway timetabling problem formulated as an extended bin packing problem. In 100 QAOA runs on each of three small instances, the PUBO formulation returned a feasible solution in every run and an optimal solution in 55-71% of runs, while the QUBO formulation returned an optimal solution in only 4-8% of runs and an infeasible solution in 10-13%. The point is that the choice of polynomial degree and penalty shape can materially change practical QAOA quality on this problem class.","feed_headline":"Polynomial binary model beats quadratic for quantum railway timetabling","feed_subtitle":"Three small instances: every PUBO run stayed feasible, with 55-71% optimal, against 4-8% for QUBO.","key_machinery":"The load-bearing machinery is a family of closed-form penalty functions built from elementary symmetric sums of the binary variables. For a linear inequality constraint like $\\sum_i x_i \\le c$, the formula $$\\$pi_c^{{\\mathrm{inf}}$}(x)=\\sum_{k=c+1}^{n}(-1)^{k-c+1}\\binom{k-1}{c}\\sum_{|I|=k}\\prod_{i\\in I}x_i$$ evaluates to $0$ when the constraint holds and to exactly $1$ when it is violated. Similar identities handle equality constraints, lower-bound constraints, and the capacity constraint $(1-x_i)\\pi_0+x_i\\pi_1$. These step penalties are what make the PUBO landscape mimic the original constrained problem. The generic PUBO penalty for a polynomial constraint is the product $\\prod_{j=0}^{UB_k}(\\sum_{\\gamma}\\beta_{k,\\gamma}x^{\\gamma}+j)$, whereas the QUBO route linearizes cubic and higher monomials and inserts slack variables $s_j$ and $r_i$ into squared penalties; that insertion is what enlarges the search space and creates the packet structure in the loss values.","core_discovery":"The paper's central claim is that, for the extended bin packing formulation of the railway timetabling problem, a PUBO model with binary-valued penalties is a better input to QAOA than the standard QUBO model with slack variables and squared penalties. Numerically, on three small instances, the PUBO model dominates: no infeasible solutions in 300 total runs and optimal rates between 55% and 71%, against 4% to 8% optimal rates and 10% to 13% infeasible rates for QUBO. The paper attributes the gap to three simultaneous causes: PUBO uses roughly half as many qubits, it introduces no auxiliary slack variables that can take values making the penalty terms nonzero even when the original decisions are optimal, and its penalty landscape is a flat 0/1 step rather than a quadratic ramp, so the classical optimizer spends less effort wandering in meaningless penalty packets. The authors explicitly note that these effects are entangled and say that distinguishing them requires further study.","pith_inferences":["If the binary-valued penalty landscape is the active ingredient, then a qubit-matched comparison, padding the PUBO circuit to the QUBO width or removing slack variables from the QUBO, would be the decisive test; the paper lists this as future work rather than running it.","The same generic PUBO encoding should transfer to other variational quantum algorithms that minimize polynomial objectives, since those algorithms would inherit the smaller search space and the flat penalty steps.","On noisy quantum hardware the ranking could plausibly reverse, because the paper notes the QUBO circuit has smaller depth and would therefore accumulate less gate noise; the simulator results isolate the formulation effect but not the noise effect.","The qualitative mechanism identified here, that slack variables let penalty terms dominate and blur the nominal objective, likely generalizes beyond bin packing to any QUBO reformulation that introduces auxiliary variables."],"forward_implications":["On the three instances tested, the binary-penalty PUBO reformulation makes QAOA return a feasible solution in every run, while the QUBO reformulation returns infeasible solutions in 10-13% of runs.","Optimal-solution rates rise from 4-8% with QUBO to 55-71% with PUBO on the same instances, so the encoding choice changes what a fixed shot budget delivers.","Because the reformulation method is generic for polynomial constrained problems, the same binary-penalty construction applies to any scheduling or packing problem with linear constraints without new derivation work.","The QUBO formulation uses roughly twice as many qubits as PUBO, so adopting polynomial models is also a way to shrink the quantum resource footprint of the same nominal problem.","The paper's suggested follow-ups, comparing generic PUBO to generic QUBO and computing exact expectation values, would determine how much of the gap comes from the binary penalties themselves rather than from qubit count and slack variables."],"supporting_citations":[{"why":"Introduces QAOA, the hybrid quantum-classical algorithm whose performance the paper measures.","marker":"Farhi et al. (2014)"},{"why":"Provides the general variational quantum algorithm presentation and the circuit decomposition used to implement the PUBO Hamiltonian.","marker":"Grange et al. (2023)"},{"why":"Supplies the standard QUBO modeling and penalty-term practice that the paper's quadratic reformulation follows.","marker":"Glover et al. (2022)"},{"why":"Gives the Ising/QUBO formulations of NP problems that establish the quadratic encoding as the default baseline.","marker":"Lucas (2014)"},{"why":"A prior PUBO-versus-QUBO comparison for traveling salesman variants that the paper extends with a generic method.","marker":"Salehi et al. (2022)"},{"why":"A prior higher-order QAOA comparison cited as evidence that PUBO formulations can improve results.","marker":"Campbell and Dahl (2022)"},{"why":"Earlier evidence that PUBO outperforms QUBO for continuous optimization with QAOA, motivating the same question here.","marker":"Stein et al. (2023)"},{"why":"An earlier study comparing QUBO reformulation choices for graph coloring that motivates treating the input formulation as a performance lever.","marker":"Tabi et al. (2020)"}],"fun_headline_variants":["PUBO beats QUBO in quantum railway timetabling","Polynomial binary model wins for QAOA railway scheduling","Quantum railway timetabling: PUBO outperforms QUBO","Poly quadratic showdown: PUBO wins on railway timetabling","For quantum railway timetabling, PUBO surpasses QUBO"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result depends on the chosen quadratic model being a fair baseline: that formulation uses extra slack variables and squared penalties, so the measured gap could come from those choices and from the doubled qubit count rather than from the polynomial penalty design itself.","fun_headline_variants_meta":{"raw":{"variants":["PUBO beats QUBO in quantum railway timetabling","Polynomial binary model wins for QAOA railway scheduling","Quantum railway timetabling: PUBO outperforms QUBO","Poly quadratic showdown: PUBO wins on railway timetabling","For quantum railway timetabling, PUBO surpasses QUBO"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000379,"raw_usage":{"total_tokens":2016,"prompt_tokens":952,"completion_tokens":1064,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":977}},"tokens_in":568,"tokens_out":1064,"duration_ms":10984,"temperature":1.0,"reasoning_tokens":977,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:00:59.164308+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same three instances with a slack-free QUBO formulation, or with the PUBO and QUBO qubit counts matched by adding idle qubits to the PUBO circuit, using the same COBYLA settings; if the QUBO then reaches or exceeds the PUBO feasible-optimal rates, the paper's claim that the binary-penalty PUBO formulation is the better encoding for this problem would be refuted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the general variational quantum algorithm presentation and the circuit decomposition used to implement the PUBO Hamiltonian."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard QUBO modeling and penalty-term practice that the paper's quadratic reformulation follows."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Ising/QUBO formulations of NP problems that establish the quadratic encoding as the default baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"A prior PUBO-versus-QUBO comparison for traveling salesman variants that the paper extends with a generic method."},{"cited_title":"and Dahl, E","cited_arxiv_id":null,"evidence_quote":"A prior higher-order QAOA comparison cited as evidence that PUBO formulations can improve results."},{"cited_title":"u lein, J., Zielinski, S., K \\","cited_arxiv_id":null,"evidence_quote":"Earlier evidence that PUBO outperforms QUBO for continuous optimization with QAOA, motivating the same question here."},{"cited_title":"H., Kallus, Z., H \\'a ga, P., Kozsik, T., Glos, A., and Zimbor \\'a s, Z","cited_arxiv_id":null,"evidence_quote":"An earlier study comparing QUBO reformulation choices for graph coloring that motivates treating the input formulation as a performance lever."}],"review_version":1}