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

A proposal for an efficient quantum algorithm solving the graph isomorphism problem

P. W. Mills, R. P. Rundle, V. M. Dwyer, Todd Tilma, Simon J. Devitt, John H. Samson, M. J. Everitt

Published Nov 27, 2017• 1 citation
OpenAlex

Related papers

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

Solving the Graph Isomorphism Problem on a Quantum Annealer

Zoe Gonzalez Izquierdo, Itay Hen, Ruilin Zhou

Bulletin of the American Physical Society•Mar 4, 2020•0 citations

Quantum Algorithms for Tree Isomorphism and State Symmetrization

David J. Rosenbaum

The graph isomorphism problem is theoretically interesting and also has many practical applications. The best known classical algorithms for graph isomorphism all run in time super-polynomial in the size of the graph in the worst case. An interesting open problem is whether quantum computers can solve the graph isomorphism problem in polynomial time. In this paper, an algorithm is shown which can decide if two rooted trees are isomorphic in polynomial time. Although this problem is easy to solve efficiently on a classical computer, the techniques developed may be useful as a basis for quantum algorithms for deciding isomorphism of more interesting types of graphs. The related problem of quantum state symmetrization is also studied. A polynomial time algorithm for the problem of symmetrizing a set of orthonormal states over an arbitrary permutation group is shown.

arXiv:1011.4138•Nov 18, 2010•2 citations

Quantum Algorithms for Graph and Algebra Problems

Sebastian Dörn

Recent Advances in Computer Science and Communications•Jan 9, 2010•1 citation

Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs

Omar Shehab, Samuel J. Lomonaco

The quantum hidden subgroup approach is an actively studied approach to solve combinatorial problems in quantum complexity theory. With the success of the Shor's algorithm, it was hoped that similar approach may be useful to solve the other combinatorial problems. One such problem is the graph isomorphism problem which has survived decades of efforts using the hidden subgroup approach. This paper provides a systematic approach to create arbitrarily large classes of classically efficiently solvable graph automorphism problems or easy graph automorphism problems for which hidden subgroup approach is guaranteed to always fail irrespective of the size of the graphs no matter how many copies of coset states are used. As the graph isomorphism problem is believed to be at least as hard as the graph automorphism problem, the result of this paper entails that the hidden subgroup approach is also guaranteed to always fail for the arbitrarily large classes of graph isomorphism problems. Combining these two results, it is argued that the hidden subgroup approach is essentially a dead end and alternative quantum algorithmic approach needs to be investigated for the graph isomorphism and automorphism problems.

arXiv:1705.00760•May 2, 2017•1 citation

A Quantum Algorithm for the Sub-graph Isomorphism Problem

Nicola Mariella, Andrea Simonetto

We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.

arXiv:2111.09732•ACM Transactions on Quantum Computing•Oct 26, 2022•7 citations
The graph isomorphism problem is theoretically interesting and also has many practical applications. The best known classical algorithms for graph isomorphism all run in time super-polynomial in the size of the graph in the worst case. An interesting open problem is whether quantum computers can solve the graph isomorphism problem in polynomial time. In this paper, an algorithm is shown which can decide if two rooted trees are isomorphic in polynomial time. Although this problem is easy to solve efficiently on a classical computer, the techniques developed may be useful as a basis for quantum algorithms for deciding isomorphism of more interesting types of graphs. The related problem of quantum state symmetrization is also studied. A polynomial time algorithm for the problem of symmetrizing a set of orthonormal states over an arbitrary permutation group is shown.
The quantum hidden subgroup approach is an actively studied approach to solve combinatorial problems in quantum complexity theory. With the success of the Shor's algorithm, it was hoped that similar approach may be useful to solve the other combinatorial problems. One such problem is the graph isomorphism problem which has survived decades of efforts using the hidden subgroup approach. This paper provides a systematic approach to create arbitrarily large classes of classically efficiently solvable graph automorphism problems or easy graph automorphism problems for which hidden subgroup approach is guaranteed to always fail irrespective of the size of the graphs no matter how many copies of coset states are used. As the graph isomorphism problem is believed to be at least as hard as the graph automorphism problem, the result of this paper entails that the hidden subgroup approach is also guaranteed to always fail for the arbitrarily large classes of graph isomorphism problems. Combining these two results, it is argued that the hidden subgroup approach is essentially a dead end and alternative quantum algorithmic approach needs to be investigated for the graph isomorphism and automorphism problems.
We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.