Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

DOI10.1007/s11128-022-03421-zOpenAlexW3125232052MaRDI QIDQ2107015

David E. Bernal, Rodolfo Quintero, Luis F. Zuluaga, Tamás Terlaky

Publication date: 29 November 2022

Published in: Quantum Information Processing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.09462

zbMATH Keywords

combinatorial optimizationquantum computingNISQ devicesChimera versus Pegasus D-wave annealerQUBO reformulations

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12) Other nonclassical models of computation (68Q09)

Related Items

Solving the Kemeny ranking aggregation problem with quantum optimization algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• The maximum \(k\)-colorable subgraph problem and orbitopes
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• The maximum k-colorable subgraph problem for chordal graphs
• QUBO formulations for the graph isomorphism problem and related problems
• A MAX-CUT formulation of 0/1 programs
• A case study in programming a quantum annealer for hard operational planning problems
• Integer programming techniques for minor-embedding in quantum annealers
• Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
• On characterization of maximal independent sets via quadratic optimization
• On spectrum sharing games
• Penalty and partitioning techniques to improve performance of QUBO solvers
• A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Integer Programming
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Some news about the independence number of a graph
• The approximation of maximum subgraph problems
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• Relationship between minimum gap and success probability in adiabatic quantum computing
• Reducibility among Combinatorial Problems
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
• Finding independent sets in a graph using continuous multivariable polynomial formulations.