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:1810.10644 · Special Matrices

Graph isomorphism and Gaussian boson sampling

Kamil Brádler, Shmuel Friedland, Josh Izaac, Nathan Killoran, Daiqin Su

Published Jan 1, 2021• 49 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1515/spma-2020-0132

Related papers

Sample efficient graph classification using binary Gaussian boson sampling

Amanuel Anteneh, Olivier Pfister

We present a variation of a quantum algorithm for the machine learning task of classification with graph-structured data. The algorithm implements a feature extraction strategy that is based on Gaussian boson sampling (GBS), a near-term model of quantum computing. However, unlike the currently proposed algorithms for this problem, our GBS setup requires only binary (light or no light) detectors, as opposed to photon-number-resolving detectors. Binary detectors are technologically simpler and can operate near room temperature, making our algorithm much less complex and costly to implement physically. We also investigate the connection between graph theory and the Torontonian matrix function which characterizes the probabilities of binary GBS detection events.

arXiv:2301.01232•Physical Review A•Dec 11, 2023•3 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

Certification of Gaussian Boson Sampling via graphs feature vectors and kernels

Taira Giordani, Valerio Mannucci, Nicolò Spagnolo +4 more

Abstract Gaussian Boson Sampling (GBS) is a non-universal model for quantum computing inspired by the original formulation of the Boson Sampling (BS) problem. Nowadays, it represents a paradigmatic quantum platform to reach the quantum advantage regime in a specific computational model. Indeed, thanks to the implementation in photonics-based processors, the latest GBS experiments have reached a level of complexity where the quantum apparatus has solved the task faster than currently up-to-date classical strategies. In addition, recent studies have identified possible applications beyond the inherent sampling task. In particular, a direct connection between photon counting of a genuine GBS device and the number of perfect matchings in a graph has been established. In this work, we propose to exploit such a connection to benchmark GBS experiments. We interpret the properties of the feature vectors of the graph encoded in the device as a signature of correct sampling from the true input state. Within this framework, two approaches are presented. The first method exploits the distributions of graph feature vectors and classification via neural networks. The second approach investigates the distributions of graph kernels. Our results provide a novel approach to the actual need for tailored algorithms to benchmark large-scale Gaussian Boson Samplers.

arXiv:2202.07711•Quantum Science and Technology•Sep 30, 2022•9 citations

Quantum invariants and the graph isomorphism problem

P. W. Mills, R. P. Rundle, John H. Samson +4 more

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.

arXiv:1711.09842•Physical Review A•Nov 13, 2019•8 citations

Experimentally Finding Dense Subgraphs Using a Time-Bin Encoded Gaussian Boson Sampling Device

S. Sempere-Llagostera, Raj B. Patel, Ian A. Walmsley +1 more

Gaussian boson sampling is a quantum computing concept based on drawing samples from a multimode nonclassical Gaussian state using photon-number resolving detectors.It was initially posed as a near-term approach to achieve quantum advantage, and several applications have been proposed since, including the calculation of graph features.For the first time, we use a time-bin encoded interferometer to implement Gaussian boson sampling experimentally and extract samples to enhance the search for dense subgraphs in a graph.Our results indicate an improvement over classical methods for subgraphs of sizes three and four in a graph containing ten nodes.In addition, we numerically explore the role of imperfections in the optical circuit and on the performance of the algorithm.

arXiv:2204.05254•Physical Review X•Sep 30, 2022•20 citations

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
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.
We present a variation of a quantum algorithm for the machine learning task of classification with graph-structured data. The algorithm implements a feature extraction strategy that is based on Gaussian boson sampling (GBS), a near-term model of quantum computing. However, unlike the currently proposed algorithms for this problem, our GBS setup requires only binary (light or no light) detectors, as opposed to photon-number-resolving detectors. Binary detectors are technologically simpler and can operate near room temperature, making our algorithm much less complex and costly to implement physically. We also investigate the connection between graph theory and the Torontonian matrix function which characterizes the probabilities of binary GBS detection events.
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.
Abstract Gaussian Boson Sampling (GBS) is a non-universal model for quantum computing inspired by the original formulation of the Boson Sampling (BS) problem. Nowadays, it represents a paradigmatic quantum platform to reach the quantum advantage regime in a specific computational model. Indeed, thanks to the implementation in photonics-based processors, the latest GBS experiments have reached a level of complexity where the quantum apparatus has solved the task faster than currently up-to-date classical strategies. In addition, recent studies have identified possible applications beyond the inherent sampling task. In particular, a direct connection between photon counting of a genuine GBS device and the number of perfect matchings in a graph has been established. In this work, we propose to exploit such a connection to benchmark GBS experiments. We interpret the properties of the feature vectors of the graph encoded in the device as a signature of correct sampling from the true input state. Within this framework, two approaches are presented. The first method exploits the distributions of graph feature vectors and classification via neural networks. The second approach investigates the distributions of graph kernels. Our results provide a novel approach to the actual need for tailored algorithms to benchmark large-scale Gaussian Boson Samplers.
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.
Gaussian boson sampling is a quantum computing concept based on drawing samples from a multimode nonclassical Gaussian state using photon-number resolving detectors.It was initially posed as a near-term approach to achieve quantum advantage, and several applications have been proposed since, including the calculation of graph features.For the first time, we use a time-bin encoded interferometer to implement Gaussian boson sampling experimentally and extract samples to enhance the search for dense subgraphs in a graph.Our results indicate an improvement over classical methods for subgraphs of sizes three and four in a graph containing ten nodes.In addition, we numerically explore the role of imperfections in the optical circuit and on the performance of the algorithm.
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.