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

Theoretical Computer Science

QUBO formulations for the graph isomorphism problem and related problems

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

Published Jun 2, 2017• 57 citations
Publisher
DOI
10.1016/j.tcs.2017.04.016

Related papers

Improved QUBO Formulation of the Graph Isomorphism Problem

Richard Hua, Michael J. Dinneen

SN Computer Science•Sep 3, 2019•11 citations

Various QUBO Formulations of the Graph Isomorphism Problem and Related Problems

Daisuke Takafuji, Koji Nakano, Yasuaki Ito +6 more

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The graph isomorphism problem is one of the applications of combinatorial optimization, and is not known to be solvable in polynomial time. The problem is also not known to be NP-complete. We propose four QUBO formulations for graph isomorphism problem instances. We also propose four QUBO formulations for induced subgraph isomorphism problem instances and two QUBO formulations for subgraph isomorphism problem instances, which are NP-complete problems. We solve QUBO instances defined by our QUBO formulations, using known QUBO solvers: Gurobi optimizer, Fixstars Amplify AE and OpenJij with SA.

Bulletin of Networking, Computing, Systems, and Software•Mar 1, 2024•0 citations

QUBO formulations of the longest path problem

Joey McCollum, Thomas Krauss

Theoretical Computer Science•Feb 9, 2021•9 citations

Succinct Quantum Proofs for Graph Non-Isomorphism

KEISUKE TANAKA

•Jan 1, 2001•0 citations

A QUBO Formulation For the K-densest Common Subgraph Isomorphism Problem Via Quantum Annealing

Nan Huang

In this paper, we extend the algorithm of [6] to solve the k-densest maximum common subgraph problem. By solving the k-densest maximum common subgraph isomorphism problem, we find high complexity common substructures between input graphs. We prove that our proposed objective function always gives the right answer to the corresponding QUBO problem.

IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)•Dec 16, 2020•1 citation

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
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The graph isomorphism problem is one of the applications of combinatorial optimization, and is not known to be solvable in polynomial time. The problem is also not known to be NP-complete. We propose four QUBO formulations for graph isomorphism problem instances. We also propose four QUBO formulations for induced subgraph isomorphism problem instances and two QUBO formulations for subgraph isomorphism problem instances, which are NP-complete problems. We solve QUBO instances defined by our QUBO formulations, using known QUBO solvers: Gurobi optimizer, Fixstars Amplify AE and OpenJij with SA.
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.