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

DOI10.1007/S11128-022-03421-ZMaRDI QIDQ2107015zbMATH OpenOpenAlexFDO

Authors Rodolfo Quintero, David E. Bernal, Luis Fernando 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 computingChimera versus Pegasus D-wave annealerNISQ devicesQUBO reformulations

Mathematics Subject Classification ID

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

Recommendations

• Penalty and partitioning techniques to improve performance of QUBO solvers
• Reformulating the harmonious colouring problem for quantum annealing
• Quantum solutions for densest \(k\)-subgraph problems
• QUBO formulations for the graph isomorphism problem and related problems
• Modeling the Costas array problem in QUBO for quantum annealing

Cites work

• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• A MAX-CUT formulation of 0/1 programs
• A case study in programming a quantum annealer for hard operational planning problems
• 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
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Integer Programming
• Integer programming techniques for minor-embedding in quantum annealers
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• New bounds for the -k-cut and chromatic number of a graph
• On characterization of maximal independent sets via quadratic optimization
• On spectrum sharing games
• On the Shannon capacity of a graph
• Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
• Penalty and partitioning techniques to improve performance of QUBO solvers
• QUBO formulations for the graph isomorphism problem and related problems
• Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
• Reducibility among combinatorial problems
• Relationship between minimum gap and success probability in adiabatic quantum computing
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Some news about the independence number of a graph
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• The Maximum k-Colorable Subgraph Problem and Related Problems
• The approximation of maximum subgraph problems
• The maximum k-colorable subgraph problem and orbitopes
• The maximum k-colorable subgraph problem for chordal graphs

Cited in

(8)

• Quantum solutions for densest \(k\)-subgraph problems
• Solving the Kemeny ranking aggregation problem with quantum optimization algorithms
• Penalty and partitioning techniques to improve performance of QUBO solvers
• Reformulating the harmonious colouring problem for quantum annealing
• The set partitioning problem in a quantum context
• QUBO formulations of the longest path problem
• Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problem
• A copositive framework for analysis of hybrid Ising-classical algorithms

This page was built for publication: Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107015)