pith. sign in

arxiv: 2511.01108 · v2 · submitted 2025-11-02 · 🪐 quant-ph · cs.ET

Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing

Adrian Harkness , Hamidreza Validi , Ramin Fakhimi , Illya V. Hicks , Samuel Stein , Tam\'as Terlaky , Luis F. Zuluaga This is my paper

Pith reviewed 2026-05-18 00:47 UTC · model grok-4.3

classification 🪐 quant-ph cs.ET
keywords max-k-cutQUBO reformulationpenalty coefficientsquantum computingcombinatorial optimizationgraph partitioningtight penalties
0
0 comments X

The pith

Tight penalty coefficients for QUBO reformulations of max-k-cut depend only on weighted vertex degrees.

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

The paper establishes closed-form expressions for the smallest penalty coefficients that remain sufficient to enforce the constraints when the max-k-cut problem is rewritten as a QUBO. These expressions are functions of the weighted degrees of the vertices in the input graph. A sympathetic reader would care because unnecessarily large penalties degrade performance on near-term quantum hardware, while tight ones improve the chance of finding good solutions with adiabatic or gate-based methods. The characterizations apply to two distinct reformulation approaches and are backed by illustrative examples and simple numerical checks.

Core claim

For two distinct QUBO reformulations of the maximum k-cut problem, the minimal sufficient penalty coefficients admit closed-form characterizations whose values depend on the weighted degrees of the vertices of the graph defining the problem.

What carries the argument

Closed-form expressions for tight (minimal but sufficient) penalty coefficients expressed solely in terms of weighted vertex degrees.

If this is right

  • The resulting QUBO instances become more practical to solve on current and near-term quantum devices.
  • Penalty selection no longer requires problem-specific tuning beyond computing vertex degrees.
  • The approach contributes to scaling quantum methods for combinatorial optimization problems.

Where Pith is reading between the lines

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

  • The same degree-based logic may extend to QUBO reformulations of other graph partitioning problems such as min-cut or community detection.
  • Testing the formulas on larger or denser graphs would reveal whether the closed forms remain tight without modification.
  • Integration with existing quantum annealing workflows could reduce the overhead of penalty hyperparameter search.

Load-bearing premise

The minimal sufficient penalty coefficients can be written in closed form using only the weighted degrees of the vertices, without extra graph-specific conditions or adjustments.

What would settle it

A concrete graph where the proposed degree-based penalty coefficient either fails to prevent all constraint violations or is strictly larger than the smallest value that works.

Figures

Figures reproduced from arXiv: 2511.01108 by Adrian Harkness, Hamidreza Validi, Illya V. Hicks, Luis F. Zuluaga, Ramin Fakhimi, Samuel Stein, Tam\'as Terlaky.

Figure 1
Figure 1. Figure 1: Optimal solutions of the QUBO formulation (5) for the max 3-cut problem with different penalty coefficients. Left: optimal solution with 𝑐1 = 𝑐2 = 𝑐3 = 𝑐4 = 1+𝜖 that is optimal for the max 𝑘-cut problem. Right: optimal solution after changing 𝑐2 from 1 to 1 − 𝜖 that is infeasible for the max 𝑘-cut problem. with objective 𝑞(𝑥 ∗ ) = 5 (see [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Optimal solutions of the QUBO formulation (5) for the max 3-cut problem with different penalty coefficients. Left: optimal solution with 𝑐1 = 𝑐2 = 1.5 + 𝜖 and 𝑐3 = 𝑐4 = 1 + 𝜖 that is optimal for the max 𝑘-cut problem. Right: optimal solution after changing 𝑐2 from 1.5 + 𝜖 to 1.5 − 𝜖 that is still optimal for the max 𝑘-cut problem. 𝑑 + 4 /3 + 𝜖 = 1 + 𝜖 for any 𝜖 > 0, then the optimal solution of (13) is 𝑥 ∗… view at source ↗
Figure 3
Figure 3. Figure 3: Optimal solutions of the R-QUBO model for the max 3-cut problem with different penalty coefficients. Left: optimal solution with 𝑐1 = 𝑐4 = 𝑐5 = 2 + 𝜖 and 𝑐2 = 𝑐3 = 3 + 𝜖 that is optimal for the max 𝑘-cut problem. Right: optimal solution after changing 𝑐2 from 3 + 𝜖 to 3 − 𝜖 that is infeasible for the max 𝑘-cut problem. Note that the tightest penalty coefficients given in Corollary 1 for the QUBO reformulat… view at source ↗
Figure 4
Figure 4. Figure 4: Optimal solutions of the R-QUBO model for the max 3-cut problem with different penalty coefficients. Left: optimal solution with 𝑐1 = 𝑐3 = 3 + 𝜖, 𝑐4 = 𝑐5 = 2 + 𝜖, and 𝑐2 = 4 + 𝜖 that is optimal for the max 𝑘-cut problem. Right: optimal solution after changing 𝑐2 from 4 + 𝜖 to 4 − 𝜖 that is still an optimal solution for the max 𝑘-cut problem. and 𝑐2 = 𝑑 + 2 − 2𝑑 − 2 + 𝜖 = 4 + 𝜖 for any 𝜖 > 0, then the optim… view at source ↗
Figure 5
Figure 5. Figure 5: Approximation ratios of sample solutions of the BQO and R-BQO formulations of the max [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Expected approximation ratio and probability of feasibility of solutions to the QUBO ( [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Optimal solutions of the QUBO formulation (5) for the max 3-cut problem with different penalty coefficients. Left: optimal solution with 𝑐1 = 𝑐5 = 1 + 𝜖 that is optimal for the max 𝑘-cut problem. Center: optimal solution with 𝑐1 = 1 + 𝜖 and 𝑐5 = 1 − 𝜖 that is infeasible for the max 𝑘-cut problem. Right: optimal solution with 𝑐1 = 1 − 𝜖 and 𝑐5 = 1 + 𝜖 that is infeasible for the max 𝑘-cut problem. 𝑐1 = − −2 … view at source ↗
Figure 8
Figure 8. Figure 8: Optimal solutions of the R-QUBO model for the max 3-cut problem with different penalty coefficients: (left) an optimal solution 𝑥 ∗ of the BQO model with 𝑐1 = 𝑐4 = 𝑐5 = 2 + 𝜖 and 𝑐2 = 𝑐3 = 4 + 𝜖, and (right) an infeasible solution 𝑥ˆ of the BQO model after changing 𝑐2 from 4 + 𝜖 to 4 − 𝜖. every vertex 𝑣 ∈ {1, 4, 5} and any 𝜖 > 0, then the optimal solution of (24) is 𝑥 ∗ with 𝑞¯(𝑥 ∗ ) = 6 (see [PITH_FULL_I… view at source ↗
read the original abstract

Quantum computing offers significant potential for solving NP-hard combinatorial (optimization) problems that are beyond the reach of classical computers. One way to tap into this potential is by reformulating combinatorial problems as a quadratic unconstrained binary optimization (QUBO) problem. The solution of the QUBO reformulation can then be addressed using adiabatic quantum computing devices or appropriate quantum computing algorithms on gate-based quantum computing devices. In general, QUBO reformulations of combinatorial problems can be readily obtained by properly penalizing the violation of the problem's constraints in the original problem's objective. However, characterizing tight (i.e., minimal but sufficient) penalty coefficients for this purpose is important and non-trivial for enabling the solution of the resulting QUBO in current and near-term quantum computing devices. Along these lines, we present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max $k$-cut problem whose values depend on the (weighted) degree of the vertices of the graph defining the problem. These findings contribute to the ongoing effort to make quantum computing a viable tool for solving combinatorial problems at scale. We support our theoretical results with illustrative examples and simple numerical results.

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 / 2 minor

Summary. The manuscript claims to derive closed-form characterizations of tight (minimal but sufficient) penalty coefficients for two distinct QUBO reformulations of the Max-k-Cut problem on weighted graphs. These coefficients are expressed solely in terms of the weighted degrees of the vertices, with the theoretical results illustrated by examples and supported by simple numerical experiments on small instances.

Significance. If the claimed closed-form expressions are rigorously tight and free of hidden graph-specific adjustments, the work would provide a practical advance for mapping Max-k-Cut to QUBO without manual penalty tuning. This could improve solution quality and scalability on near-term quantum annealers and gate-based devices, where large penalties degrade performance. The emphasis on degree-only dependence is a notable strength if proven general.

major comments (2)
  1. [§3.2, Eq. (9)] §3.2, Eq. (9): The bound used to establish tightness of the penalty for the first reformulation is derived from the weighted degree sum alone. It is unclear whether this bound remains valid when a vertex is reassigned across the k partitions while other vertices are simultaneously optimized, as the objective may admit larger gains through cut contributions that are not captured by the per-vertex degree term.
  2. [§4, Eq. (17)] §4, Eq. (17): The closed-form penalty for the second reformulation is stated to be minimal and sufficient based on vertex degrees. However, the derivation sketch does not explicitly compare against the maximum objective improvement obtainable by violating the one-hot constraint for k > 2, leaving open the possibility that the expression is sufficient but not tight for general k or non-uniform weight distributions.
minor comments (2)
  1. [Numerical results] The numerical experiments section would benefit from reporting the specific k values and graph densities tested, as well as a direct comparison of solution quality when using the proposed penalties versus modestly smaller values.
  2. [Introduction] Notation for the two reformulations (e.g., the precise mapping of binary variables to partitions) should be introduced earlier and used consistently to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of our manuscript and for providing constructive comments. We respond to each major comment below.

read point-by-point responses

  1. Referee: [§3.2, Eq. (9)] The bound used to establish tightness of the penalty for the first reformulation is derived from the weighted degree sum alone. It is unclear whether this bound remains valid when a vertex is reassigned across the k partitions while other vertices are simultaneously optimized, as the objective may admit larger gains through cut contributions that are not captured by the per-vertex degree term.

    Authors: We thank the referee for raising this point. The tightness proof for the penalty coefficient in Eq. (9) relies on bounding the maximum possible objective improvement from violating the one-hot constraint for any single vertex. This improvement is at most the weighted degree of the vertex, since the cut value contributed by a vertex equals the sum of weights of edges connecting it to vertices in other partitions, which cannot exceed its total weighted degree irrespective of the partition assignments of other vertices. Simultaneous optimization of other vertices cannot produce additional gains beyond this per-vertex bound because the objective function is additive over edges and the relevant terms for the violating vertex involve only its incident edges. Thus, the bound is valid and the penalty is tight. revision: no

  2. Referee: [§4, Eq. (17)] The closed-form penalty for the second reformulation is stated to be minimal and sufficient based on vertex degrees. However, the derivation sketch does not explicitly compare against the maximum objective improvement obtainable by violating the one-hot constraint for k > 2, leaving open the possibility that the expression is sufficient but not tight for general k or non-uniform weight distributions.

    Authors: We acknowledge that the derivation in Section 4 is concise. To address this, we will expand the explanation in the revised manuscript to explicitly show the comparison of the penalty against the maximum objective gain from violating the one-hot constraint. This maximum gain, even for k > 2 and arbitrary weight distributions, remains bounded by the weighted degree of the vertex, as violating the constraint allows at most the full degree contribution to the objective without exceeding it. The closed-form expression is therefore tight. We will include this detailed comparison in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in penalty coefficient derivations

full rationale

The paper presents closed-form characterizations of tight penalty coefficients for two QUBO reformulations of max-k-cut, expressed as functions of weighted vertex degrees. These are derived from the problem's objective and constraints (penalizing partition violations) without evidence of self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations. The abstract and structure indicate a direct theoretical derivation from graph properties, supported by examples, making the central claims self-contained rather than reducing to inputs by construction. No steps meet the criteria for circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard QUBO penalty construction for combinatorial constraints and basic graph properties; no free parameters, new entities, or ad-hoc axioms beyond the domain assumption that tight penalties admit closed-form degree-based expressions.

axioms (2)
  • domain assumption QUBO reformulations of max-k-cut are formed by adding penalty terms to enforce the assignment constraints of the original problem.
    Standard technique referenced in the abstract for obtaining the reformulations.
  • ad hoc to paper Tight (minimal but sufficient) penalty coefficients exist and can be characterized in closed form using only the weighted degrees of the vertices.
    Central claim of the paper; the abstract presents this as the key theoretical result.

pith-pipeline@v0.9.0 · 5768 in / 1501 out tokens · 46750 ms · 2026-05-18T00:47:06.698283+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

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

  1. [1]

    Challenges and opportunities in quantum optimization

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas B \"a rtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, et al. Challenges and opportunities in quantum optimization. Nature Reviews Physics, pages 1--18, 2024

    work page 2024

  2. [2]

    Adiabatic quantum computation

    Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90 0 (1): 0 015002, 2018

    work page 2018

  3. [3]

    Benchmarking A dvantage and D - W ave 2000 Q quantum annealers with exact cover problems

    Dennis Willsch, Madita Willsch, Carlos D Gonzalez Calaza, Fengping Jin, Hans De Raedt, Marika Svensson, and Kristel Michielsen. Benchmarking A dvantage and D - W ave 2000 Q quantum annealers with exact cover problems. Quantum Information Processing, 21 0 (4): 0 141, 2022

    work page 2000

  4. [4]

    A Quantum Approximate Optimization Algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. URL https://arxiv.org/abs/1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  5. [5]

    Gate-based superconducting quantum computing

    Sangil Kwon, Akiyoshi Tomonaga, Gopika Lakshmi Bhai, Simon J Devitt, and Jaw-Shen Tsai. Gate-based superconducting quantum computing. Journal of Applied Physics, 129 0 (4), 2021

    work page 2021

  6. [6]

    The Quadratic Unconstrained Binary Optimization Problem

    Abraham P Punnen. The Quadratic Unconstrained Binary Optimization Problem. Springer, Cham, Switzerland., 2022

    work page 2022

  7. [7]

    Benchmarking quantum optimization for the maximum-cut problem on a superconducting quantum computer

    Maxime Dupont, Bhuvanesh Sundar, Bram Evert, David E Bernal Neira, Zedong Peng, Stephen Jeffrey, and Mark J Hodson. Benchmarking quantum optimization for the maximum-cut problem on a superconducting quantum computer. Physical Review Applied, 23 0 (1): 0 014045, 2025

    work page 2025

  8. [8]

    Evidence for the utility of quantum computing before fault tolerance

    Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. Evidence for the utility of quantum computing before fault tolerance. Nature, 618 0 (7965): 0 500--505, 2023

    work page 2023

  9. [9]

    The I sing model is NP -complete

    Barry A Cipra. The I sing model is NP -complete. SIAM News, 33 0 (6): 0 1--3, 2000

    work page 2000

  10. [10]

    Finding independent sets in a graph using continuous multivariable polynomial formulations

    James Abello, Sergiy Butenko, Panos M Pardalos, and Mauricio GC Resende. Finding independent sets in a graph using continuous multivariable polynomial formulations. Journal of Global Optimization, 21: 0 111--137, 2001

    work page 2001

  11. [11]

    Continuous approaches for solving discrete optimization problems

    Panos M Pardalos, Oleg A Prokopyev, and Stanislav Busygin. Continuous approaches for solving discrete optimization problems. Handbook on modelling for discrete optimization, pages 39--60, 2006

    work page 2006

  12. [12]

    Ising formulations of many NP problems

    Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2: 0 5, 2014

    work page 2014

  13. [13]

    Performance of hybrid quantum-classical variational heuristics for combinatorial optimization

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

    work page 2019

  14. [14]

    Quantum annealing applied to de-conflicting optimal trajectories for air traffic management

    Tobias Stollenwerk, Bryan O’Gorman, Davide Venturelli, Salvatore Mandra, Olga Rodionova, Hokkwan Ng, Banavar Sridhar, Eleanor Gilbert Rieffel, and Rupak Biswas. Quantum annealing applied to de-conflicting optimal trajectories for air traffic management. IEEE transactions on intelligent transportation systems, 21 0 (1): 0 285--297, 2019

    work page 2019

  15. [15]

    A QUBO formulation for minimum loss network reconfiguration

    Filipe FC Silva, Pedro MS Carvalho, Lu \' s AFM Ferreira, and Yasser Omar. A QUBO formulation for minimum loss network reconfiguration. IEEE Transactions on Power Systems, 38 0 (5): 0 4559--4571, 2022

    work page 2022

  16. [16]

    QUBO formulations for training machine learning models

    Prasanna Date, Davis Arthur, and Lauren Pusey-Nazzaro. QUBO formulations for training machine learning models. Scientific reports, 11 0 (1): 0 10029, 2021

    work page 2021

  17. [17]

    A max-cut formulation of 0/1 programs

    Jean B Lasserre. A max-cut formulation of 0/1 programs. Operations Research Letters, 44 0 (2): 0 158--164, 2016

    work page 2016

  18. [18]

    What works best when? a systematic evaluation of heuristics for max-cut and QUBO

    Iain Dunning, Swati Gupta, and John Silberholz. What works best when? a systematic evaluation of heuristics for max-cut and QUBO . INFORMS Journal on Computing, 30 0 (3): 0 608--624, 2018

    work page 2018

  19. [19]

    Advances for quantum-inspired optimization

    Fred Glover and Gary Kochenberger. Advances for quantum-inspired optimization. In Tutorials in Operations Research: Emerging and Impactful Topics in Operations. INFORMS, 2022

    work page 2022

  20. [20]

    Solving the minimum sum coloring problem: Alternative models, exact solvers, and metaheuristics

    Yu Du, Fred Glover, Gary Kochenberger, Rick Hennig, Haibo Wang, and Amit Hulandageri. Solving the minimum sum coloring problem: Alternative models, exact solvers, and metaheuristics. INFORMS Journal on Computing, 37 0 (2): 0 199--211, 2025

    work page 2025

  21. [21]

    Quantum computing in the NISQ era and beyond

    John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2: 0 79, 2018

    work page 2018

  22. [22]

    QUBO formulations for the graph isomorphism problem and related problems

    Cristian S Calude, Michael J Dinneen, and Richard Hua. QUBO formulations for the graph isomorphism problem and related problems. Theoretical Computer Science, 701: 0 54--69, 2017

    work page 2017

  23. [23]

    Integer programming techniques for minor-embedding in quantum annealers

    David E Bernal, Kyle EC Booth, Raouf Dridi, Hedayat Alghassi, Sridhar Tayur, and Davide Venturelli. Integer programming techniques for minor-embedding in quantum annealers. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 17th International Conference, CPAIOR 2020, Vienna, Austria, September 21--24, 2020, Proceed...

    work page 2020

  24. [24]

    Improved QUBO formulations for D - W ave quantum computing

    Alexander Fowler. Improved QUBO formulations for D - W ave quantum computing . PhD thesis, University of Auckland, 2017

    work page 2017

  25. [25]

    Translating constraints into QUBO s for the quadratic knapsack problem

    Tariq Bontekoe, Frank Phillipson, and Ward van der Schoot. Translating constraints into QUBO s for the quadratic knapsack problem. In International Conference on Computational Science, pages 90--107. Springer, 2023

    work page 2023

  26. [26]

    Characterizing and benchmarking QUBO reformulations of the knapsack problem

    Rodolfo A Quintero and Luis F Zuluaga. Characterizing and benchmarking QUBO reformulations of the knapsack problem. Technical Report ISE Technical Report 21T-028, Lehigh University, Department of Industrial and Systems Engineering, 2021. available at https://engineering.lehigh.edu/sites/engineering.lehigh.edu/files/_DEPARTMENTS/ise/pdf/tech-papers/21/21T_028.pdf

    work page 2021

  27. [27]

    Rodolfo Quintero, David Bernal, Tam \'a s Terlaky, and Luis F. Zuluaga. Characterization of QUBO reformulations for the maximum k -colorable subgraph problem. Quantum Information Processing, 21 0 (3): 0 89, 2022

    work page 2022

  28. [28]

    The maximum k -colorable subgraph problem and related problems

    Olga Kuryatnikova, Renata Sotirov, and Juan C Vera. The maximum k -colorable subgraph problem and related problems. INFORMS Journal on Computing, 34 0 (1): 0 656--669, 2022

    work page 2022

  29. [29]

    QUBO formulations and characterization of penalty parameters for the multi-knapsack problem

    Evren G \"u ney, Joachim Ehrenthal, and Thomas Hanne. QUBO formulations and characterization of penalty parameters for the multi-knapsack problem. IEEE Access, 13: 0 47086--47098, 2025

    work page 2025

  30. [30]

    Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer

    Marcos Diez Garc \' a, Mayowa Ayodele, and Alberto Moraglio. Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 184--187, 2022

    work page 2022

  31. [31]

    Penalty and partitioning techniques to improve performance of QUBO solvers

    Amit Verma and Mark Lewis. Penalty and partitioning techniques to improve performance of QUBO solvers. Discrete Optimization, 44: 0 100594, 2022

    work page 2022

  32. [32]

    A copositive framework for analysis of hybrid I sing-classical algorithms

    Robin Brown, David E Bernal Neira, Davide Venturelli, and Marco Pavone. A copositive framework for analysis of hybrid I sing-classical algorithms. SIAM Journal on Optimization, 34 0 (2): 0 1455--1489, 2024

    work page 2024

  33. [33]

    Approximating the k -multicut problem

    Daniel Golovin, Viswanath Nagarajan, and Mohit Singh. Approximating the k -multicut problem. In SODA, volume 6, pages 621--630. Citeseer, 2006

    work page 2006

  34. [34]

    A QUBO formulation of minimum multicut problem instances in trees for D - W ave quantum annealers

    William Cruz-Santos, Salvador E Venegas-Andraca, and Marco Lanzagorta. A QUBO formulation of minimum multicut problem instances in trees for D - W ave quantum annealers. Scientific reports, 9 0 (1): 0 17216, 2019

    work page 2019

  35. [35]

    Improved approximation algorithms for MAX k - CUT and MAX BISECTION

    Alan Frieze and Mark Jerrum. Improved approximation algorithms for MAX k - CUT and MAX BISECTION . Algorithmica, 18 0 (1): 0 67--81, 1997

    work page 1997

  36. [36]

    Optimal cuts in graphs and statistical mechanics

    JC Angl \`e s d'Auriac, M Preissmann, and A Seb \"o . Optimal cuts in graphs and statistical mechanics. Mathematical and Computer Modelling, 26 0 (8-10): 0 1--11, 1997

    work page 1997

  37. [37]

    Complexity: knots, colourings and counting, volume 186

    Dominic JA Welsh. Complexity: knots, colourings and counting, volume 186. Cambridge university press, 1993

    work page 1993

  38. [38]

    Practical data-oriented microaggregation for statistical disclosure control

    Josep Domingo-Ferrer and Josep Maria Mateo-Sanz. Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and data Engineering, 14 0 (1): 0 189--201, 2002

    work page 2002

  39. [39]

    o tschel, Michael J \

    Francisco Barahona, Martin Gr \"o tschel, Michael J \"u nger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36 0 (3): 0 493--513, 1988

    work page 1988

  40. [40]

    Models and solution techniques for frequency assignment problems

    Karen I Aardal, Stan PM Van Hoesel, Arie MCA Koster, Carlo Mannino, and Antonio Sassano. Models and solution techniques for frequency assignment problems. Annals of Operations Research, 153: 0 79--129, 2007

    work page 2007

  41. [41]

    The capacitated max k -cut problem

    Daya Ram Gaur, Ramesh Krishnamurti, and Rajeev Kohli. The capacitated max k -cut problem. Mathematical Programming, 115: 0 65--72, 2008

    work page 2008

  42. [42]

    Efficient encoding of the weighted max k -cut on a quantum computer using QAOA

    Franz G Fuchs, Herman ie Kolden, Niels Henrik Aase, and Giorgio Sartor. Efficient encoding of the weighted max k -cut on a quantum computer using QAOA . SN Computer Science, 2 0 (2): 0 1--14, 2021

    work page 2021

  43. [43]

    From the quantum approximate optimization algorithm to a quantum alternating operator ansatz,

    Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12 0 (2), 2019. doi:10.3390/a12020034

    work page doi:10.3390/a12020034 2019

  44. [44]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, USA, 10th edition, 2011. URL https://bit.ly/33TrYs5

    work page 2011

  45. [45]

    XY mixers: Analytical and numerical results for the quantum alternating operator ansatz

    Zhihui Wang, Nicholas C Rubin, Jason M Dominy, and Eleanor G Rieffel. XY mixers: Analytical and numerical results for the quantum alternating operator ansatz. Physical Review A, 101 0 (1): 0 012320, 2020

    work page 2020

  46. [46]

    Embedding inequality constraints for quantum annealing optimization

    Tom \'a s Vysko c il, Scott Pakin, and Hristo N Djidjev. Embedding inequality constraints for quantum annealing optimization. In Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1, pages 11--22. Springer, 2019

    work page 2019

  47. [47]

    Gurobi Optimizer Reference Manual , 2025

    Gurobi Optimization, LLC . Gurobi Optimizer Reference Manual , 2025. URL https://www.gurobi.com

    work page 2025

  48. [48]

    IBM ’s Q iskit tool chain: W orking with and developing for real quantum computers

    Robert Wille, Rod Van Meter, and Yehuda Naveh. IBM ’s Q iskit tool chain: W orking with and developing for real quantum computers. In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1234--1240. IEEE, 2019

    work page 2019

  49. [49]

    IBM Q experience as a versatile experimental testbed for simulating open quantum systems

    Guillermo Garc \' a-P \'e rez, Matteo AC Rossi, and Sabrina Maniscalco. IBM Q experience as a versatile experimental testbed for simulating open quantum systems. npj Quantum Information, 6 0 (1): 0 1, 2020

    work page 2020

  50. [50]

    Fakealmadenv2, 2025

    IBM. Fakealmadenv2, 2025. URL https://docs.quantum.ibm.com/api/qiskit-ibm-runtime/fake-provider-fake-almaden-v2

    work page 2025

  51. [51]

    Breves communications

    IG Rosenberg. Breves communications. 0-1 optimization and non-linear programming. Revue fran c aise d'automatique, informatique, recherche op \'e rationnelle. Recherche op \'e rationnelle , 6 0 (V2): 0 95--97, 1972

    work page 1972

  52. [52]

    Ising machines as hardware solvers of combinatorial optimization problems

    Naeimeh Mohseni, Peter L McMahon, and Tim Byrnes. Ising machines as hardware solvers of combinatorial optimization problems. Nature Reviews Physics, 4 0 (6): 0 363--379, 2022

    work page 2022