Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2206.11040 · Lecture notes in computer science

Penalty Weights in QUBO Formulations: Permutation Problems

Mayowa Ayodele

Published Jan 1, 2022• 56 citations
arXivHTMLPDF
DOI
10.1007/978-3-031-04148-8_11

Related papers

A Penalty-Based QUBO Formulation for Quantum Unit Commitment: Mitigating Slack Variable Constraints in QAOA

Aayush Sharma, Rashi Sinha, P. V. Manitha

International Conference on Ambient Intelligence, Knowledge Informatics and Industrial Electronics (AIKIIE)•Aug 1, 2026•0 citations

QUBO formulations for the graph isomorphism problem and related problems

Cristian S. Calude, Michael J. Dinneen, Richard Hua

Theoretical Computer Science•Jun 2, 2017•57 citations

AutoQUBO v2: Towards Efficient and Effective QUBO Formulations for Ising Machines

Justin Pauckert, Mayowa Ayodele, Marcos Diez García +2 more

The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•14 citations

Penalty and partitioning techniques to improve performance of QUBO solvers

Amit Verma, Mark W. Lewis

Discrete Optimization•Jun 29, 2020•77 citations

QUBO solver for combinatorial optimization problems with constraints

Fumiyo Takano, Motoi Suzuki, Y. Kobayashi +1 more

IEICE Technical Report; IEICE Tech. Rep.•Nov 21, 2019•7 citations

QUBO Formulation of the Shortest Path Algorithm and its Evaluation on a Quantum Annealer

Renáta Rusnáková, Martin Chovanec, Maroš Harahus +1 more

This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.

IEEE World Symposium on Applied Machine Intelligence and Informatics (SAMI)•Jan 23, 2025•0 citations
The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.
This study focuses on reformulating the shortest path problem in undirected weighted graphs into a QUBO problem, leveraging the D-Wave quantum annealing hybrid solver for execution. While A * search with heuristics, a widely used algorithm for solving shortest path problem, serves as a baseline for comparison, our primary contribution lies in analyzing the accuracy and benefits of the proposed QUBO formulation. Our analysis reveals that the proposed QUBO formulation together with selected quantum annealing hybrid solver is loosing its efficiency with increasing number of nodes. This is caused by the size of the problem and related penalty calculation but also by the architecture of the D-Wave QPU and design of the hybrid solver. We are proposing techniques to improve the results, such as graph pruning during preprocessing or penalty parameter tuning to achieve better, more accurate, results. This study provides valuable insights into the limitations of current approaches and explores the future applications of quantum computing in solving real-world challenges.