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

• URL: http://arxiv.org/abs/2511.01108v1
• Date: Sun, 02 Nov 2025 22:49:59 GMT
• Title: Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing
• Authors: Adrian Harkness, Hamidreza Validi, Ramin Fakhimi, Illya V. Hicks, Tamás Terlaky, Luis F. Zuluaga,
• Abstract summary: Quantum computing offers significant potential for solving NP-hardweighted (optimization) problems that are beyond the reach of classical computers.<n>One way to tap into this potential is by reformulating problems as a quadratic unconstrained binary optimization (QUBO) problem.<n>We present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max $k$-cut problem.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 critical for enabling the solution of the resulting QUBO in current and near-term quantum computing devices. Along these lines, we here focus on the (weighted) max $k$-cut problem, a fundamental combinatorial problem with wide-ranging applications that generalizes the well-known max cut problem. 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. Further, we benchmark the proposed QUBO reformulations to solve the max $k$-cut problem on a quantum computer simulator.

Related papers

• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  We introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization problem. We demonstrate practical viability of our method by comparing the performance of purely classical algorithms with the D-Wave Advantage 4.1 quantum annealer.
  arXiv  Detail & Related papers  (2024-04-26T21:29:42Z)
• Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems [0.0]
  Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
  arXiv  Detail & Related papers  (2023-11-16T09:19:01Z)
• Quantum-based Distributed Algorithms for Edge Node Placement and Workload Allocation [8.937905773981702]
  We present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation. Existing quantum solvers are limited to solving unconstrained binary programming problems. Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
  arXiv  Detail & Related papers  (2023-06-01T21:33:08Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problem [0.0]
  Quantum devices can be used to solve constrained optimization (COPT) problems. In this paper, we consider an important constrained COPT problem, in which the aim is to find an induced $k$-colorable subgraph. We derive two QUBO reformulations for the M$k$CS problem, and fully characterize the range of the penalty parameters that can be used in the QUBO reformulations.
  arXiv  Detail & Related papers  (2021-01-23T09:28:33Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.