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• 59 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•10 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•10 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

Quantum search algorithm for graph isomorphism problem

A. E. Kirichkov

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jan 1, 2008•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.