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:1011.4138

Quantum Algorithms for Tree Isomorphism and State Symmetrization

David J. Rosenbaum

Published Nov 18, 2010• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1011.4138

Related papers

Graph isomorphism and adiabatic quantum computing

Frank Gaitan, Lane Clark

In the graph isomorphism (GI) problem two $N$-vertex graphs $G$ and ${G}^{\ensuremath{'}}$ are given and the task is to determine whether there exists a permutation of the vertices of $G$ that preserves adjacency and transforms $G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}$. If yes, then $G$ and ${G}^{\ensuremath{'}}$ are said to be isomorphic; otherwise they are nonisomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and which also provides an approach to determining all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly (i) distinguishes nonisomorphic graphs; (ii) recognizes isomorphic graphs and determines the permutation(s) that connect them; and (iii) finds the automorphism group of a given graph $G$. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-complete subgraph isomorphism problem. The computational complexity of an adiabatic quantum algorithm is largely determined by the minimum energy gap $\ensuremath{\Delta}(N)$ separating the ground and first-excited states in the limit of large problem size $N\ensuremath{\gg}1$. Calculating $\ensuremath{\Delta}(N)$ in this limit is a fundamental open problem in adiabatic quantum computing, and so it is not possible to determine the computational complexity of adiabatic quantum algorithms in general, nor consequently, of the specific adiabatic quantum algorithms presented here. Adiabatic quantum computing has been shown to be equivalent to the circuit model of quantum computing, and so development of adiabatic quantum algorithms continues to be of great interest.

arXiv:1304.5773•Physical Review A•Feb 28, 2014•46 citations

Quantum state isomorphism problems for groups

Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban +1 more

We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA $\cap$ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP $\cap$ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.

quant-pharXiv:2605.12615•May 14, 2026•0 citations

The quantum algorithm for graph isomorphism problem

Xi Li, Hanwu Chen

The graph isomorphism (GI) problem is the computational problem of finding a permutation of vertices of a given graph $G_1$ that transforms $G_1$ to another given graph $G_2$ and preserves the adjacency. In this work, we propose a quantum algorithm to determine whether there exists such a permutation. To find such a permutation, we introduce isomorphic equivalent graphs of the given graphs to be tested. We proof that the GI problem of the equivalent graphs is equivalent to the GI problem of the given graphs. The idea of the algorithm is to determine whether there exists a permutation can transform the eigenvectors of the adjacency matrix of the equivalent graphs each other. The cost time of the algorithm is polynomial.

arXiv:1901.06530•Jan 19, 2019•3 citations

On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

Cristopher Moore, Alexander C. Russell, Piotr Śniady

It is known that any quantum algorithm for graph isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across $\Omega(n\log n)$ coset states. One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's algorithm for the HSP in the dihedral group, in which quantum states are adaptively combined and measured according to the decomposition of tensor products into irreducible representations. This “quantum sieve” starts with coset states and works its way down toward representations whose probabilities differ depending on, for example, whether the hidden subgroup is trivial or nontrivial. In this paper we show that no such approach can produce a polynomial-time quantum algorithm for graph isomorphism. Specifically, we consider the natural reduction of graph isomorphism to the HSP over the wreath product $S_n\wr\mathbb{Z}_2$. Using a recently proved bound on the irreducible characters of $S_n$, we show that no algorithm in this family can solve graph isomorphism in less than $\mathrm{e}^{\Omega(\sqrt{n})}$ time, no matter what adaptive rule it uses to select and combine quantum states. In particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time $\mathrm{e}^{O(\sqrt{n\log n})}$.

SIAM Journal on Computing•Jan 1, 2010•9 citations

An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem

François Le Gall

In this paper we consider the problem of testing whether two finite groups are isomorphic. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. Le Gall has constructed an efficient classical algorithm for a class of groups corresponding to one of the most natural ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group $A$ by a cyclic group $Z_m$ with the order of $A$ coprime with $m$. More precisely, the running time of that algorithm is almost linear in the order of the input groups. In this paper we present a quantum algorithm solving the same problem in time polynomial in the logarithm of the order of the input groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian group isomorphism problem exponentially faster than the best known classical algorithms.

arXiv:1001.0608•Leibniz international proceedings in informatics•Jan 1, 2010•5 citations

A Quantum-Inspired Algorithm for Graph Isomorphism

Innes L. Maxwell, Stefan N. van den Hoven, Jelmer J. Renema

The Noisy Intermediate-Scale Quantum (NISQ) era of technology in which we currently find ourselves is defined by non-universality, susceptibility to errors and noise, and a search for useful applications. While demonstrations of practical quantum advantage remain elusive in this era, it provides space to develop and analyze the advantages and limitations of systems and their ability to solve problems. In this work, we critically assess a proposed quantum algorithm for the graph isomorphism problem, implemented on a photonic quantum device. Inspired by the nature of this quantum algorithm, we formulate a necessary condition for the isomorphism of graphs encoded in Gaussian boson samplers and a classical algorithm to test for it. Our classical algorithm makes use of efficiently computable statistical properties of a quantum sampling system to show a pair of graphs fail to meet our necessary condition and thus cannot be isomorphic. We analyze our algorithm in the context of the inspiring, sampler-based quantum algorithm of Bràdler et. al., the classical color refinement algorithm, and the state-of-the-art quasi-polynomial Babai algorithm.

quant-pharXiv:2512.24423•Jan 1, 2026•0 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.
In the graph isomorphism (GI) problem two NNN-vertex graphs GGG and ${G}^{\ensuremath{'}}$ are given and the task is to determine whether there exists a permutation of the vertices of GGG that preserves adjacency and transforms $G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}$. If yes, then GGG and ${G}^{\ensuremath{'}}$ are said to be isomorphic; otherwise they are nonisomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and which also provides an approach to determining all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly (i) distinguishes nonisomorphic graphs; (ii) recognizes isomorphic graphs and determines the permutation(s) that connect them; and (iii) finds the automorphism group of a given graph GGG. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-complete subgraph isomorphism problem. The computational complexity of an adiabatic quantum algorithm is largely determined by the minimum energy gap $\ensuremath{\Delta}(N)$ separating the ground and first-excited states in the limit of large problem size $N\ensuremath{\gg}1$. Calculating $\ensuremath{\Delta}(N)$ in this limit is a fundamental open problem in adiabatic quantum computing, and so it is not possible to determine the computational complexity of adiabatic quantum algorithms in general, nor consequently, of the specific adiabatic quantum algorithms presented here. Adiabatic quantum computing has been shown to be equivalent to the circuit model of quantum computing, and so development of adiabatic quantum algorithms continues to be of great interest.
We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA ∩\cap∩ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP ∩\cap∩ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.
The graph isomorphism (GI) problem is the computational problem of finding a permutation of vertices of a given graph G1G_1G1​ that transforms G1G_1G1​ to another given graph G2G_2G2​ and preserves the adjacency. In this work, we propose a quantum algorithm to determine whether there exists such a permutation. To find such a permutation, we introduce isomorphic equivalent graphs of the given graphs to be tested. We proof that the GI problem of the equivalent graphs is equivalent to the GI problem of the given graphs. The idea of the algorithm is to determine whether there exists a permutation can transform the eigenvectors of the adjacency matrix of the equivalent graphs each other. The cost time of the algorithm is polynomial.
It is known that any quantum algorithm for graph isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across Ω(nlog⁡n)\Omega(n\log n)Ω(nlogn) coset states. One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's algorithm for the HSP in the dihedral group, in which quantum states are adaptively combined and measured according to the decomposition of tensor products into irreducible representations. This “quantum sieve” starts with coset states and works its way down toward representations whose probabilities differ depending on, for example, whether the hidden subgroup is trivial or nontrivial. In this paper we show that no such approach can produce a polynomial-time quantum algorithm for graph isomorphism. Specifically, we consider the natural reduction of graph isomorphism to the HSP over the wreath product Sn≀Z2S_n\wr\mathbb{Z}_2Sn​≀Z2​. Using a recently proved bound on the irreducible characters of SnS_nSn​, we show that no algorithm in this family can solve graph isomorphism in less than eΩ(n)\mathrm{e}^{\Omega(\sqrt{n})}eΩ(n​) time, no matter what adaptive rule it uses to select and combine quantum states. In particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time eO(nlog⁡n)\mathrm{e}^{O(\sqrt{n\log n})}eO(nlogn​).
In this paper we consider the problem of testing whether two finite groups are isomorphic. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. Le Gall has constructed an efficient classical algorithm for a class of groups corresponding to one of the most natural ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group AAA by a cyclic group ZmZ_mZm​ with the order of AAA coprime with mmm. More precisely, the running time of that algorithm is almost linear in the order of the input groups. In this paper we present a quantum algorithm solving the same problem in time polynomial in the logarithm of the order of the input groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian group isomorphism problem exponentially faster than the best known classical algorithms.
The Noisy Intermediate-Scale Quantum (NISQ) era of technology in which we currently find ourselves is defined by non-universality, susceptibility to errors and noise, and a search for useful applications. While demonstrations of practical quantum advantage remain elusive in this era, it provides space to develop and analyze the advantages and limitations of systems and their ability to solve problems. In this work, we critically assess a proposed quantum algorithm for the graph isomorphism problem, implemented on a photonic quantum device. Inspired by the nature of this quantum algorithm, we formulate a necessary condition for the isomorphism of graphs encoded in Gaussian boson samplers and a classical algorithm to test for it. Our classical algorithm makes use of efficiently computable statistical properties of a quantum sampling system to show a pair of graphs fail to meet our necessary condition and thus cannot be isomorphic. We analyze our algorithm in the context of the inspiring, sampler-based quantum algorithm of Bràdler et. al., the classical color refinement algorithm, and the state-of-the-art quasi-polynomial Babai algorithm.