Pith. sign in

REVIEW 3 major objections 6 minor 27 references

Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2411.10062 v1 pith:A7MD44AC submitted 2024-11-15 math.OC quant-ph

Camille Grange (LITIS) , Marion Lavignac , Valentina Pozzoli , Eric Bourreau This is my paper · ORCID
classification math.OCquant-ph MSC 90C2790C1081P68
keywords QAOAPUBOQUBOrailwaytimetablingextendedbinpackingbinarypenaltyfunctionvariationalquantumalgorithmcombinatorialoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

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.

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 (3)
  1. [Section 4, Table 3 and Section 4.2] 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.
  2. [Section 4.1, Nshots = 10] 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.
  3. [Section 3.3.2, Proposition 3.6 and Eq. (1)] 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.
minor comments (6)
  1. [Section 2.3.1] 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.
  2. [Section 3.3.2] 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.
  3. [Section 4.1] 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.
  4. [Abstract] The sentence 'QAOA is one of the most short-term promising quantum-classical algorithm' has a grammar error; it should be 'algorithms'.
  5. [Table 2] 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.
  6. [Section 5] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation; the only self-citation is a minor, non-load-bearing implementation detail.

full rationale

The reformulation chain is constructive rather than circular. The PUBO penalty functions (Properties 2.5-2.7) are explicit polynomials whose 0/1 indicator property is proved by binomial identities, and the QUBO penalties are standard slack/linearization constructions. Proposition 2.2 gives a valid lower bound on penalty coefficients from fmax - fmin; the coefficients in Table 2 are derived from instance bounds, not fitted to QAOA outcomes. The central claim in Table 3 is an empirical comparison against classically computed optima on three instances, with no parameter fitted to the result. The only self-citation entering the implementation, Grange et al. (2023) Proposition 37 for the PUBO circuit decomposition (Section 4.1), is a published, parameter-free implementation detail and is not the source of the performance claim, so it is not load-bearing. The paper itself concedes in the Conclusion that 'the two reformulations we compare involve many simultaneous effects' and in Section 4.2 that 'it is undeniable that the number of qubits plays a role'; these are honest limitations on causal interpretation of the numerical gap, not circular steps. Accordingly, no circular step is identified; score 2 reflects only the minor non-load-bearing self-citation.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central claim rests on standard combinatorial identities and on modeling assumptions about the simplified railway problem. No new physical entities or fitted constants are introduced beyond the hand-chosen penalty coefficients.

free parameters (1)
  • Penalty coefficients lambda_u, lambda_c = 8, 10, 12
    Chosen by hand to exceed fmax - fmin (Proposition 2.2); not fitted to outcomes, but they set the height of penalty barriers and affect QAOA behavior. A different choice could change the performance gap.
assumptions (3)
  • standard math Standard binomial identities used in penalty function proofs (Newton's binomial formula, Pascal's triangle)
    Appendix A proofs rely on binomial sums; these are unproved background facts.
  • domain assumption The Extended Bin Packing simplification preserves the essence of the original SNCF railway timetabling problem
    Section 3.2 states the simplification retains core aspects, but this is an unvalidated modeling assumption; the simplified problem is a bin packing variant, not the full ILP.
  • domain assumption Each customer group has the same number of customers, normalizable to a unit group
    Section 3.2 says bigger groups can be duplicated, but this changes instance size and may alter the optimization landscape.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling." pith.science (2026). https://pith.science/paper/A7MD44AC

@misc{pith2026241110062,
  author       = {Pith},
  title        = {Pith review of: Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A7MD44AC}},
  note         = {Machine review of arXiv:2411.10062}
}
read the original abstract

Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.

Figures

Figures reproduced from arXiv: 2411.10062 by the authors.

Figure 1
Figure 1. Instance A [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
Figure 4
Figure 4. Details of the states returned by running QAOA 100 times for each of the 3 instances [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 24 canonical work pages

  1. [1]

    Ambainis, A., Balodis, K., Iraids, J., Kokainis, M., Pr \=u sis, K., and Vihrovs, J. (2019). Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1783--1793. SIAM

    work page 2019

  2. [2]

    K., Ahmed, E

    Azad, U., Behera, B. K., Ahmed, E. A., Panigrahi, P. K., and Farouk, A. (2022). Solving vehicle routing problem using quantum approximate optimization algorithm. IEEE Transactions on Intelligent Transportation Systems , 24(7):7564--7573

    work page 2022

  3. [3]

    K., Nannicini, G., Robert, A., Tavernelli, I., and Woerner, S

    Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., and Woerner, S. (2020). Improving variational quantum optimization using CVaR . Quantum , 4:256

    work page 2020

  4. [4]

    and Dahl, E

    Campbell, C. and Dahl, E. (2022). Qaoa of the highest order. In 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C) , pages 141--146. IEEE

    work page 2022

  5. [5]

    C., Endo, S., Fujii, K., McClean, J

    Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021). Variational quantum algorithms. Nature Reviews Physics , 3(9):625--644

    2021

  6. [6]

    Dalyac, C., Henriet, L., Jeandel, E., Lechner, W., Perdrix, S., Porcheron, M., and Veshchezerova, M. (2021). Qualifying quantum approaches for hard industrial optimization problems. a case study in the field of smart-charging of electric vehicles. EPJ Quantum Technology , 8(1):12

    work page 2021

  7. [7]

    de la Grand'rive, P. D. and Hullo, J.-F. (2019). Knapsack problem variants of qaoa for battery revenue optimisation. arXiv preprint arXiv:1908.02210

    work page Pith review arXiv 2019

  8. [8]

    Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028

    arXiv 2014

Show all 27 references
  1. [9]

    Glover, F., Kochenberger, G., Hennig, R., and Du, Y. (2022). Quantum bridge analytics i: a tutorial on formulating and using qubo models. Annals of Operations Research , 314(1):141--183

    2022

  2. [10]

    Grange, C., Poss, M., and Bourreau, E. (2023). An introduction to variational quantum algorithms for combinatorial optimization problems. 4OR , 21(3):363--403

    2023

  3. [11]

    Grange, C., Poss, M., Bourreau, E., T’kindt, V., and Ploton, O. (2024). Moderate exponential-time quantum dynamic programming across the subsets for scheduling problems. European Journal of Operational Research

    2024

  4. [12]

    G., Venturelli, D., and Biswas, R

    Hadfield, S., Wang, Z., O'gorman, B., Rieffel, E. G., Venturelli, D., and Biswas, R. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms , 12(2):34

    2019

  5. [13]

    and Nishimori, H

    Kadowaki, T. and Nishimori, H. (1998). Quantum annealing in the transverse ising model. Physical Review E , 58(5):5355

    1998

  6. [14]

    Kea, K., Huot, C., and Han, Y. (2023). Leveraging knapsack qaoa approach for optimal electric vehicle charging. IEEE Access

    2023

  7. [15]

    and Prakash, A

    Kerenidis, I. and Prakash, A. (2020). A quantum interior point method for LPs and SDPs . ACM Transactions on Quantum Computing , 1(1):1--32

    2020

  8. [16]

    Kurowski, K., Pecyna, T., Slysz, M., R \'o \.z ycki, R., Walig \'o ra, G., and Weglarz, J. (2023). Application of quantum approximate optimization algorithm to job shop scheduling problem. European Journal of Operational Research

    2023

  9. [17]

    Li, L., Fan, M., Coram, M., Riley, P., Leichenauer, S., et al. (2020). Quantum optimization with a novel Gibbs objective function and ansatz architecture search. Physical Review Research , 2(2):023074

    2020

  10. [18]

    Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics , page 5

    2014

  11. [19]

    Montanaro, A. (2020). Quantum speedup of branch-and-bound algorithms. Physical Review Research , 2(1):013056

    2020

  12. [20]

    Nannicini, G. (2019). Performance of hybrid quantum-classical variational heuristics for combinatorial optimization. Physical Review E , 99(1):013304

    2019

  13. [21]

    Nannicini, G. (2021). Fast Quantum Subroutines for the Simplex Method . In Singh, M. and Williamson, D. P., editors, Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19-21, 2021, Proceedings , volume 12707 of ...

    2021

  14. [22]

    Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum , 2:79

    2018

  15. [23]

    Quintero, R., Bernal, D., Terlaky, T., and Zuluaga, L. F. (2022). Characterization of qubo reformulations for the maximum k-colorable subgraph problem. Quantum Information Processing , 21(3):89

    2022

  16. [24]

    Ruan, Y., Marsh, S., Xue, X., Liu, Z., Wang, J., et al. (2020). The quantum approximate algorithm for solving traveling salesman problem. Computers, Materials & Continua , 63(3):1237--1247

    2020

  17. [25]

    Salehi, \"O ., Glos, A., and Miszczak, J. A. (2022). Unconstrained binary models of the travelling salesman problem variants for quantum optimization. Quantum Information Processing , 21(2):67

    2022

  18. [26]

    u lein, J., Zielinski, S., K \

    Stein, J., Chamanian, F., Zorn, M., N \"u lein, J., Zielinski, S., K \"o lle, M., and Linnhoff-Popien, C. (2023). Evidence that pubo outperforms qubo when solving continuous optimization problems with the qaoa. In Proceedings of the Companion Conference on Genetic and Evolutio...

    2023

  19. [27]

    H., Kallus, Z., H \'a ga, P., Kozsik, T., Glos, A., and Zimbor \'a s, Z

    Tabi, Z., El-Safty, K. H., Kallus, Z., H \'a ga, P., Kozsik, T., Glos, A., and Zimbor \'a s, Z. (2020). Quantum optimization for the graph coloring problem with space-efficient embedding. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) , pages ...

    2020

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.