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:1711.09842 · Physical Review A

Quantum invariants and the graph isomorphism problem

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

Published Nov 13, 2019• 8 citations
arXivHTMLPDF

Abstract

Three graph invariants are introduced which may be measured from a quantum graph state and form examples of a framework under which other graph invariants can be constructed. Each invariant is based on distinguishing a different number of qubits. This is done by applying different measurements to the qubits to be distinguished. The performance of these invariants is evaluated and compared to classical invariants. We verify that the invariants can distinguish all nonisomorphic graphs with nine or fewer nodes. The invariants have also been applied to ``classically hard'' strongly regular graphs, successfully distinguishing all strongly regular graphs of up to 29 nodes, and preliminarily to weighted graphs. We have found that, although it is possible to prepare states with a polynomial number of operations, the average number of preparations required to distinguish nonisomorphic graph states scales exponentially with the number of nodes. We have so far been unable to find operators which reliably compare graphs and reduce the required number of preparations to feasible levels.

DOI
10.1103/physreva.100.052317

Related papers

Testing graph isomorphism using simple quantum circuits

Samuel Beasley, Ashley Montanaro

The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth $p=2$, this invariant numerically distinguishes all $10{,}486$ cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at $θ=π/2$ and $θ=π/4$. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.

quant-pharXiv:2610.19962•Oct 15, 2026•0 citations

Graph isomorphism and Gaussian boson sampling

Kamil Brádler, Shmuel Friedland, Josh Izaac +2 more

Abstract We introduce a connection between a near-term quantum computing device, specifically a Gaussian boson sampler, and the graph isomorphism problem. We propose a scheme where graphs are encoded into quantum states of light, whose properties are then probed with photon-number-resolving detectors. We prove that the probabilities of different photon-detection events in this setup can be combined to give a complete set of graph invariants. Two graphs are isomorphic if and only if their detection probabilities are equivalent. We present additional ways that the measurement probabilities can be combined or coarse-grained to make experimental tests more amenable. We benchmark these methods with numerical simulations on the Titan supercomputer for several graph families: pairs of isospectral nonisomorphic graphs, isospectral regular graphs, and strongly regular graphs.

arXiv:1810.10644•Special Matrices•Jan 1, 2021•49 citations

Multiparticle quantum walks for distinguishing hard graphs

Sachin Kasture, Shaheen Acheche, Loïc Henriet +1 more

Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).

arXiv:2501.03683•Jan 7, 2025•0 citations

Comparing Algorithms for Graph Isomorphism Using Discrete- and Continuous-Time Quantum Random Walks

Kenneth Rudinger, John King Gamble, Eric Bach +3 more

Berry and Wang [Phys. Rev. A {\bf 83}, 042317 (2011)] show numerically that a discrete-time quantum random walk of two noninteracting particles is able to distinguish some non-isomorphic strongly regular graphs from the same family. Here we analytically demonstrate how it is possible for these walks to distinguish such graphs, while continuous-time quantum walks of two noninteracting particles cannot. We show analytically and numerically that even single-particle discrete-time quantum random walks can distinguish some strongly regular graphs, though not as many as two-particle noninteracting discrete-time walks. Additionally, we demonstrate how, given the same quantum random walk, subtle differences in the graph certificate construction algorithm can nontrivially impact the walk's distinguishing power. We also show that no continuous-time walk of a fixed number of particles can distinguish all strongly regular graphs when used in conjunction with any of the graph certificates we consider. We extend this constraint to discrete-time walks of fixed numbers of noninteracting particles for one kind of graph certificate; it remains an open question as to whether or not this constraint applies to the other graph certificates we consider.

arXiv:1207.4535•Journal of Computational and Theoretical Nanoscience•Jun 20, 2013•19 citations

A graph isomorphism algorithm using signatures computed via quantum walk search model

Huiquan Wang, Junjie Wu, Xuejun Yang +1 more

In this paper, we propose a new algorithm based on a quantum walk search model to distinguish strongly similar graphs. Our algorithm computes a signature for each graph via the quantum walk search model and uses signatures to distinguish non-isomorphic graphs. Our method is less complex than those of previous works. In addition, our algorithm can be extended by raising the signature levels. The higher the level adopted, the stronger the distinguishing ability and the higher the complexity of the algorithm. Our algorithm was tested with standard benchmarks from four databases. We note that the weakest signature at level 1 can distinguish all similar graphs, with a time complexity of which that outperforms the previous best work except when it comes to strongly regular graphs (SRGs). Once the signature is raised to level 3, all SRGs tested can be distinguished successfully. In this case, the time complexity is , also better than the previous best work.

Journal of Physics A Mathematical and Theoretical•Feb 20, 2015•13 citations

Two-particle quantum walks applied to the graph isomorphism problem

John King Gamble, Mark G. Friesen, Dong Zhou +2 more

We show that the quantum dynamics of interacting and noninteracting quantum particles are fundamentally different in the context of solving a particular computational problem. Specifically, we consider the graph isomorphism problem, in which one wishes to determine whether two graphs are isomorphic (related to each other by a relabeling of the graph vertices), and focus on a class of graphs with particularly high symmetry called strongly regular graphs (SRGs). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of nonisomorphic SRGs and show that interacting particles can distinguish nonisomorphic graphs that noninteracting particles cannot. We obtain the following specific results. (1) We prove that quantum walks of two noninteracting particles, fermions or bosons, cannot distinguish certain pairs of nonisomorphic SRGs. (2) We demonstrate numerically that two interacting bosons are more powerful than single particles and two noninteracting particles, in that quantum walks of interacting bosons distinguish all nonisomorphic pairs of SRGs that we examined. By utilizing high-throughput computing to perform over 500 million direct comparisons between evolution operators, we checked all tabulated pairs of nonisomorphic SRGs, including graphs with up to 64 vertices. (3) By performing a short-time expansion of the evolution operator, we derive distinguishing operators that provide analytic insight into the power of the interacting two-particle quantum walk.

arXiv:1002.3003•Physical Review A•May 13, 2010•145 citations
Three graph invariants are introduced which may be measured from a quantum graph state and form examples of a framework under which other graph invariants can be constructed. Each invariant is based on distinguishing a different number of qubits. This is done by applying different measurements to the qubits to be distinguished. The performance of these invariants is evaluated and compared to classical invariants. We verify that the invariants can distinguish all nonisomorphic graphs with nine or fewer nodes. The invariants have also been applied to ``classically hard'' strongly regular graphs, successfully distinguishing all strongly regular graphs of up to 29 nodes, and preliminarily to weighted graphs. We have found that, although it is possible to prepare states with a polynomial number of operations, the average number of preparations required to distinguish nonisomorphic graph states scales exponentially with the number of nodes. We have so far been unable to find operators which reliably compare graphs and reduce the required number of preparations to feasible levels.
The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth p=2p=2p=2, this invariant numerically distinguishes all 10,48610{,}48610,486 cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at θ=π/2θ=π/2θ=π/2 and θ=π/4θ=π/4θ=π/4. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.
Abstract We introduce a connection between a near-term quantum computing device, specifically a Gaussian boson sampler, and the graph isomorphism problem. We propose a scheme where graphs are encoded into quantum states of light, whose properties are then probed with photon-number-resolving detectors. We prove that the probabilities of different photon-detection events in this setup can be combined to give a complete set of graph invariants. Two graphs are isomorphic if and only if their detection probabilities are equivalent. We present additional ways that the measurement probabilities can be combined or coarse-grained to make experimental tests more amenable. We benchmark these methods with numerical simulations on the Titan supercomputer for several graph families: pairs of isospectral nonisomorphic graphs, isospectral regular graphs, and strongly regular graphs.
Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).
Berry and Wang [Phys. Rev. A {\bf 83}, 042317 (2011)] show numerically that a discrete-time quantum random walk of two noninteracting particles is able to distinguish some non-isomorphic strongly regular graphs from the same family. Here we analytically demonstrate how it is possible for these walks to distinguish such graphs, while continuous-time quantum walks of two noninteracting particles cannot. We show analytically and numerically that even single-particle discrete-time quantum random walks can distinguish some strongly regular graphs, though not as many as two-particle noninteracting discrete-time walks. Additionally, we demonstrate how, given the same quantum random walk, subtle differences in the graph certificate construction algorithm can nontrivially impact the walk's distinguishing power. We also show that no continuous-time walk of a fixed number of particles can distinguish all strongly regular graphs when used in conjunction with any of the graph certificates we consider. We extend this constraint to discrete-time walks of fixed numbers of noninteracting particles for one kind of graph certificate; it remains an open question as to whether or not this constraint applies to the other graph certificates we consider.
In this paper, we propose a new algorithm based on a quantum walk search model to distinguish strongly similar graphs. Our algorithm computes a signature for each graph via the quantum walk search model and uses signatures to distinguish non-isomorphic graphs. Our method is less complex than those of previous works. In addition, our algorithm can be extended by raising the signature levels. The higher the level adopted, the stronger the distinguishing ability and the higher the complexity of the algorithm. Our algorithm was tested with standard benchmarks from four databases. We note that the weakest signature at level 1 can distinguish all similar graphs, with a time complexity of which that outperforms the previous best work except when it comes to strongly regular graphs (SRGs). Once the signature is raised to level 3, all SRGs tested can be distinguished successfully. In this case, the time complexity is , also better than the previous best work.
We show that the quantum dynamics of interacting and noninteracting quantum particles are fundamentally different in the context of solving a particular computational problem. Specifically, we consider the graph isomorphism problem, in which one wishes to determine whether two graphs are isomorphic (related to each other by a relabeling of the graph vertices), and focus on a class of graphs with particularly high symmetry called strongly regular graphs (SRGs). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of nonisomorphic SRGs and show that interacting particles can distinguish nonisomorphic graphs that noninteracting particles cannot. We obtain the following specific results. (1) We prove that quantum walks of two noninteracting particles, fermions or bosons, cannot distinguish certain pairs of nonisomorphic SRGs. (2) We demonstrate numerically that two interacting bosons are more powerful than single particles and two noninteracting particles, in that quantum walks of interacting bosons distinguish all nonisomorphic pairs of SRGs that we examined. By utilizing high-throughput computing to perform over 500 million direct comparisons between evolution operators, we checked all tabulated pairs of nonisomorphic SRGs, including graphs with up to 64 vertices. (3) By performing a short-time expansion of the evolution operator, we derive distinguishing operators that provide analytic insight into the power of the interacting two-particle quantum walk.