Characterization of QUBO reformulations for the maximum $k$-colorable
subgraph problem
- URL: http://arxiv.org/abs/2101.09462v1
- Date: Sat, 23 Jan 2021 09:28:33 GMT
- Title: Characterization of QUBO reformulations for the maximum $k$-colorable
subgraph problem
- Authors: Rodolfo Quintero, David Bernal, Tam\'as Terlaky, and Luis F. Zuluaga
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum devices can be used to solve constrained combinatorial optimization
(COPT) problems thanks to the use of penalization methods to embed the COPT
problem's constraints in its objective to obtain a quadratic unconstrained
binary optimization (QUBO) reformulation of the COPT. However, the particular
way in which this penalization is carried out, affects the value of the penalty
parameters, as well as the number of additional binary variables that are
needed to obtain the desired QUBO reformulation. In turn, these factors
substantially affect the ability of quantum computers to efficiently solve
these constrained COPT problems. This efficiency is key towards the goal of
using quantum computers to solve constrained COPT problems more efficiently
than with classical computers. Along these lines, we consider an important
constrained COPT problem; namely, the maximum $k$-colorable subgraph (M$k$CS)
problem, in which the aim is to find an induced $k$-colorable subgraph with
maximum cardinality in a given graph. This problem arises in channel assignment
in spectrum sharing networks, VLSI design, human genetic research, and
cybersecurity. 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. Further, one of the QUBO reformulations of the M$k$CS
problem is obtained without the need to introduce additional binary variables.
To illustrate the benefits of obtaining and characterizing these QUBO
reformulations, we benchmark different QUBO reformulations of the M$k$CS
problem by performing numerical tests on D-Wave's quantum annealing devices.
These tests also illustrate the numerical power gained by using the latest
D-Wave's quantum annealing device.
Related papers
- Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing [0.0]
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.
arXiv Detail & Related papers (2025-11-02T22:49:59Z) - Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers [4.266376725904727]
Variational Quantum Algorithms (VQAs) typically require constrained problems to be reformulated as unconstrained ones using penalty methods.
A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints.
We explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions.
These step-like penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights.
arXiv Detail & Related papers (2025-04-17T03:20:02Z) - Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler [0.0]
We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes.
Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices.
arXiv Detail & Related papers (2024-06-20T12:25:00Z) - 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) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - 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) - Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary
Optimization [44.96576908957141]
We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
arXiv Detail & Related papers (2022-03-23T18:00:03Z) - Testing a QUBO Formulation of Core-periphery Partitioning on a Quantum
Annealer [3.093890460224435]
We present a new kernel that quantifies success for the task of computing a core-periphery partition for an undirected network.
Finding the associated optimal partitioning may be expressed in the form of a quadratic unconstrained binary optimization problem.
We compare this approach with existing core-periphery partitioning methods.
arXiv Detail & Related papers (2022-01-05T11:08:09Z) - 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) - 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) - An Ensemble Approach for Compressive Sensing with Quantum [1.8477401359673713]
We leverage the idea of a statistical ensemble to improve the quality of quantum annealing based binary compressive sensing.
Our experiments, on a D-Wave 2000Q quantum processor, demonstrated that the proposed ensemble scheme is notably less sensitive to the calibration of the penalty parameter.
arXiv Detail & Related papers (2020-06-08T15:32:22Z)
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.