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

Quantum Algorithm to Search For Graph Automorphism and Local Clifford Orbit Detection

Q. Ten

Published Jun 8, 2026• 0 citations
Publisher

Abstract

We do not claim to solve the general graph automorphism problem. Whileit is a known strategy to attempt to solve the Graph isomorphism and autom-rphism problems on a quantum computer by treating them as a HSP oversome symmetric group this paper takes a different approach by using the graphformlism presented in [1] so we present a intrisically quantum algorithm for ex-ploring the local-Clifford (LC) equivalence neighborhood of a graph using thegraph-state data structure introduced by [1]. By leveraging efficient local com-plementation, edge complementation, and ancilla-driven set-complementationoperations, we construct a quantum superposition over the LC-orbit of a graphand introduce an oracle that implements structural invariants such as automor-phisms and fixed-point subgraphs. We show that amplitude amplification yieldsa quadratic speedup for detecting LC-invariant features compared to classicalrandomized search. Our method provides a provably correct quantum proce-dure for structural graph analysis within the graph-state formalism. The localCliford orbit is a massive, exponentially large space that cannot be searched ingeneral classically with polynomial time complexity

DOI
10.5281/zenodo.20590585

Related papers

Algorithmic approaches to graph states under the action of local Clifford groups

Moshen Bahramgiri

Graph states are quantum states (quantum codes) in qn-dimensional space ... (q being a power of some prime number) which can be described by graphs with edges labeled from the field of order q, Fq. Graph states are determined as a common eigenvector of independent elements of the n-fold Pauli group, on which the local Clifford group has a natural action. This action induces the natural action of the local Clifford group on graph states and hence, its action on graphs. Locally equivalent graphs can be described using this action. For q being a prime number, two graphs are locally equivalent when they are located on the same orbit of this action, in other words, when there is an element of the local Clifford group mapping one graph to the other one. When q is some power of a prime number, the definition of this action is the natural generalization of this action in the case where q is prime. We translate the action of local Clifford groups on graphs to a set of linear and quadratic equations in the field F,. In the case that q is an odd number, given two arbitrary graphs, we present an efficient algorithm (polynomial in n) to verify whether these graphs are locally equivalent or not. Moreover, we present a computational method to calculate the number of inequivalent graph states. We give some estimations on the size of the orbits of this action on graphs, and prove that when either q is equal to 2 or is an odd number, the number of inequivalent quantum codes (i.e., the number of classes of equivalency) is equal to ..., which is essentially as large as the total number of graphs.

•Jan 1, 2007•0 citations

Efficient algorithm to recognize the local Clifford equivalence of graph states

Maarten Van den Nest, Jeroen Dehaene, Bart De Moor

In Van den Nest et al. [Phys. Rev. A 69, 022316 (2004)] we presented a description of the action of local Clifford operations on graph states in terms of a graph transformation rule, known in graph theory as local complementation. It was shown that two graph states are equivalent under the local Clifford group if and only if there exists a sequence of local complementations which relates their associated graphs. In this Brief Report we report the existence of a polynomial time algorithm, published in A. Bouchet [Combinatorica 11, 315 (1991)], which decides whether two given graphs are related by a sequence of local complementations. Hence an efficient algorithm to detect local Clifford equivalence of graph states is obtained.

arXiv:quant-ph/0405023•Physical Review A•Sep 17, 2004•86 citations

Quantum Computation and Isomorphism Testing

David J. Rosenbaum

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.

•Jan 1, 2015•2 citations

Quantum Algorithms for Approximate Graph Isomorphism Testing

Prateek P. Kulkarni

The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on $n$ vertices drawn from the Erdős--Rényi distribution $\mathcal{G} (n,1/2)$ are considered approximately isomorphic if they can be made isomorphic by at most $k$ edge edits. We present a quantum algorithm based on MNRS quantum walk search over the product graph $Γ(G,H)$ of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity $\mathcal{O}(n^{3/2} \log n/\varepsilon)$, where $\varepsilon$ parameterizes the approximation threshold. We complement this with an $Ω(n^2)$ classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model. We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.

quant-pharXiv:2603.02656•Mar 4, 2026•0 citations

Quantum Computing for Graph Partitioning with Optimal Speedup

Jincheng Zhang

Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.

•Sep 5, 2026•0 citations

Local Equivalences of Graph States

Nathan Claudet

Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.

quant-pharXiv:2511.22271•Nov 28, 2025•4 citations
We do not claim to solve the general graph automorphism problem. Whileit is a known strategy to attempt to solve the Graph isomorphism and autom-rphism problems on a quantum computer by treating them as a HSP oversome symmetric group this paper takes a different approach by using the graphformlism presented in [1] so we present a intrisically quantum algorithm for ex-ploring the local-Clifford (LC) equivalence neighborhood of a graph using thegraph-state data structure introduced by [1]. By leveraging efficient local com-plementation, edge complementation, and ancilla-driven set-complementationoperations, we construct a quantum superposition over the LC-orbit of a graphand introduce an oracle that implements structural invariants such as automor-phisms and fixed-point subgraphs. We show that amplitude amplification yieldsa quadratic speedup for detecting LC-invariant features compared to classicalrandomized search. Our method provides a provably correct quantum proce-dure for structural graph analysis within the graph-state formalism. The localCliford orbit is a massive, exponentially large space that cannot be searched ingeneral classically with polynomial time complexity
Graph states are quantum states (quantum codes) in qn-dimensional space ... (q being a power of some prime number) which can be described by graphs with edges labeled from the field of order q, Fq. Graph states are determined as a common eigenvector of independent elements of the n-fold Pauli group, on which the local Clifford group has a natural action. This action induces the natural action of the local Clifford group on graph states and hence, its action on graphs. Locally equivalent graphs can be described using this action. For q being a prime number, two graphs are locally equivalent when they are located on the same orbit of this action, in other words, when there is an element of the local Clifford group mapping one graph to the other one. When q is some power of a prime number, the definition of this action is the natural generalization of this action in the case where q is prime. We translate the action of local Clifford groups on graphs to a set of linear and quadratic equations in the field F,. In the case that q is an odd number, given two arbitrary graphs, we present an efficient algorithm (polynomial in n) to verify whether these graphs are locally equivalent or not. Moreover, we present a computational method to calculate the number of inequivalent graph states. We give some estimations on the size of the orbits of this action on graphs, and prove that when either q is equal to 2 or is an odd number, the number of inequivalent quantum codes (i.e., the number of classes of equivalency) is equal to ..., which is essentially as large as the total number of graphs.
In Van den Nest et al. [Phys. Rev. A 69, 022316 (2004)] we presented a description of the action of local Clifford operations on graph states in terms of a graph transformation rule, known in graph theory as local complementation. It was shown that two graph states are equivalent under the local Clifford group if and only if there exists a sequence of local complementations which relates their associated graphs. In this Brief Report we report the existence of a polynomial time algorithm, published in A. Bouchet [Combinatorica 11, 315 (1991)], which decides whether two given graphs are related by a sequence of local complementations. Hence an efficient algorithm to detect local Clifford equivalence of graph states is obtained.
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.
The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on nnn vertices drawn from the Erdős--Rényi distribution G(n,1/2)\mathcal{G} (n,1/2)G(n,1/2) are considered approximately isomorphic if they can be made isomorphic by at most kkk edge edits. We present a quantum algorithm based on MNRS quantum walk search over the product graph Γ(G,H)Γ(G,H)Γ(G,H) of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity O(n3/2log⁡n/ε)\mathcal{O}(n^{3/2} \log n/\varepsilon)O(n3/2logn/ε), where ε\varepsilonε parameterizes the approximation threshold. We complement this with an Ω(n2)Ω(n^2)Ω(n2) classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model. We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.
Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.