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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Solving Graph Problems with Single-Photons and Linear Optics

Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield

Published Sep 17, 2023• 1 citation
Publisher

Abstract

An important challenge for current and near-term quantum devices is finding useful tasks that can be preformed on them. We first show how to efficiently encode a bounded$n\times n$matrix$A$into a linear optical circuit with$2n$modes. We then apply this encoding to the case where$A$is a matrix containing information about a graph$G$. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encoding$A$, and single-photon detectors can solve a range of graph problems including finding the number of perfect matchings of bipartite graphs, computing permanental polynomials, determining whether two graphs are isomorphic, and the k-densest subgraph problem. We also propose pre-processing methods to boost the probabilities of observing the relevant detection events and thus improve performance. Finally we present both numerical simulations and implementations on Quandela's Ascella photonic quantum processor to validate our findings.

DOI
10.1109/qce57702.2023.10239

Related papers

Solving graph problems with single photons and linear optics

Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield

An important challenge for current and near-term quantum devices is finding useful tasks that can be preformed on them. We first show how to efficiently encode a bounded $n\ifmmode\times\else\texttimes\fi{}n$ matrix $A$ into a linear optical circuit with $2n$ modes. We then apply this encoding to the case where $A$ is a matrix containing information about a graph $G$. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encoding $A$, and single-photon detectors can solve a range of graph problems including finding the number of perfect matchings of bipartite graphs, computing permanental polynomials, determining whether two graphs are isomorphic, and the $k$-densest subgraph problem. We also propose preprocessing methods to boost the probabilities of observing the relevant detection events and thus improve performance. Finally we present both numerical simulations and implementations on Quandela's Ascella photonic quantum processor to validate our findings.

arXiv:2301.09594•Physical Review A•Sep 6, 2023•19 citations

Quantum computation using linear optics

Gerard J Milburn

Summary form only given. Quantum computers are expected to increase the efficiency of solving problems such as factoring large integers. However an experimental implementation of even relatively simple quantum information processing with a few to a dozen qubits presents an enormous technological challenge. One of the earliest proposals for quantum computation is based on implementing a quantum bit with two optical modes containing one photon. The proposal is appealing due to the ease with which photon interference can be observed. However these early proposals required huge single photon optical nonlinearities. Unfortunately currently available optical nonlinearities are too weak and too noisy to be useful. Recently however we have discovered that efficient quantum computation is possible using only beam splitters, phase shifters, single photon sources and photodetectors. Our methods exploit feed forward from photo-detectors and are robust against errors from photon loss and detector inefficiency. In this tutorial I will outline this scheme, highlighting the technical challenges required to implement it. The tutorial will be relatively self contained with a brief introduction to quantum optics and quantum computation.

Quantum Electronics and Laser Science Conference•Jun 25, 2003•0 citations

Very-large-scale integrated quantum graph photonics

Jueming Bao, Zhaorong Fu, Tanumoy Pramanik +32 more

Abstract Graphs have provided an expressive mathematical tool to model quantum-mechanical devices and systems. In particular, it has been recently discovered that graph theory can be used to describe and design quantum components, devices, setups and systems, based on the two-dimensional lattice of parametric nonlinear optical crystals and linear optical circuits, different to the standard quantum photonic framework. Realizing such graph-theoretical quantum photonic hardware, however, remains extremely challenging experimentally using conventional technologies. Here we demonstrate a graph-theoretical programmable quantum photonic device in very-large-scale integrated nanophotonic circuits. The device monolithically integrates about 2,500 components, constructing a synthetic lattice of nonlinear photon-pair waveguide sources and linear optical waveguide circuits, and it is fabricated on an eight-inch silicon-on-insulator wafer by complementary metal–oxide–semiconductor processes. We reconfigure the quantum device to realize and process complex-weighted graphs with different topologies and to implement different tasks associated with the perfect matching property of graphs. As two non-trivial examples, we show the generation of genuine multipartite multidimensional quantum entanglement with different entanglement structures, and the measurement of probability distributions proportional to the modulus-squared hafnian (permanent) of the graph’s adjacency matrices. This work realizes a prototype of graph-theoretical quantum photonic devices manufactured by very-large-scale integration technologies, featuring arbitrary programmability, high architectural modularity and massive manufacturing scalability.

Nature Photonics•Apr 6, 2023•215 citations

Scalable Generation of Graph-State Entanglement through Realistic Linear Optics

Timothy P. Bodiya, Luming Duan

Linear optics, combined with practical photon source and single-photon detectors, has provided a powerful tool to test a number of quantum information protocols. In the linear optics implementations, the post-selection technique based on photon detections typically plays a critical role. As one scales up the system, the post-selection technique generally leads to very inefficient (exponential) scaling of the overall efficiency, which limits the implementation to small systems. In the past few years, two approaches have been proposed to circumvent this obstacle for different kinds of quantum information processing. In the first approach, a remarkable proposal, generally referred to as linear optics quantum computation, was first put forward by Knill, Laflamme, and Mil-burn (KLM) [1] and then improved by a number of others. In this approach, one overcomes the scaling problem for linear optics computation through quantum error correction by requiring the efficiencies for the photon source and the detectors to attain a high threshold value [1]. The threshold efficiency has been improved considerably in the past few years, with the most recent estimate about Linear optics, combined with practical photon source and single-photon detectors, has provided a powerful tool to test a number of quantum information protocols. In the linear optics implementations, the post-selection technique based on photon detections typically plays a critical role. As one scales up the system, the post-selection technique generally leads to very inefficient (exponential) scaling of the overall efficiency, which limits the implementation to small systems. In the past few years, two approaches have been proposed to circumvent this obstacle for different kinds of quantum information processing. In the first approach, a remarkable proposal, generally referred to as linear optics quantum computation, was first put forward by Knill, Laflamme, and Mil-burn (KLM) [1] and then improved by a number of others. In this approach, one overcomes the scaling problem for linear optics computation through quantum error correction by requiring the efficiencies for the photon source and the detectors to attain a high threshold value [1]. The threshold efficiency has been improved considerably in the past few years, with the most recent estimate about 99.4%− 99.7% [2]. In the second approach proposed in Ref. [3], one uses linear optics for implementation of scalable quantum communication through the quantum repeater protocol. This approach overcomes the inefficient scaling through the divide-and-conquer method. In this protocol, one does not have a threshold requirement on the source and the detector efficiencies, which allows its implementation with the state-of-the-art photon detectors.

Frontiers in Optics•Jan 1, 2006•2 citations

Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip

Pingyu Zhu, Qilin Zheng, Kun Wang +6 more

Computing the number of perfect matchings of a graph is a famous #P-complete problem. In this work, taking the advantages of the frequency dimension of photon, we propose and implement a photonic perfect matching solver, by combining two key techniques, frequency grouping and multi-photon counting. Based on a broadband photon-pair source from a silicon quantum chip and a wavelength-selective switch, we configure graphs up to sixteen vertices and estimate the perfect matchings of subgraphs up to six vertices. The experimental fidelities are more than 90% for all the graphs. Moreover, we demonstrate that the developed photonic system can enhance classical stochastic algorithms for solving nondeterministic-polynomial-time(NP) problems, such as the Boolean satisfiability problem and the densest subgraph. Our work contributes a promising method for solving the perfect matchings problem, which is simple in experiment setup and convenient to transform or scale up the object graph by regulating the frequency-correlated photon pairs. Perfect matching counting is a famously hard problem. Here, the authors propose a photonic perfect matching solver by multi-photon coincidence of grouped broadband frequency-correlated photon pairs. The samples from the solver can also be used to enhance searching algorithms for NP problems such as SAT and densest subgraph.

Nature Communications•Apr 22, 2025•3 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•66 citations
An important challenge for current and near-term quantum devices is finding useful tasks that can be preformed on them. We first show how to efficiently encode a boundedn×nn\times nn×nmatrixAAAinto a linear optical circuit with2n2n2nmodes. We then apply this encoding to the case whereAAAis a matrix containing information about a graphGGG. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encodingAAA, and single-photon detectors can solve a range of graph problems including finding the number of perfect matchings of bipartite graphs, computing permanental polynomials, determining whether two graphs are isomorphic, and the k-densest subgraph problem. We also propose pre-processing methods to boost the probabilities of observing the relevant detection events and thus improve performance. Finally we present both numerical simulations and implementations on Quandela's Ascella photonic quantum processor to validate our findings.
An important challenge for current and near-term quantum devices is finding useful tasks that can be preformed on them. We first show how to efficiently encode a bounded $n\ifmmode\times\else\texttimes\fi{}n$ matrix AAA into a linear optical circuit with 2n2n2n modes. We then apply this encoding to the case where AAA is a matrix containing information about a graph GGG. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encoding AAA, and single-photon detectors can solve a range of graph problems including finding the number of perfect matchings of bipartite graphs, computing permanental polynomials, determining whether two graphs are isomorphic, and the kkk-densest subgraph problem. We also propose preprocessing methods to boost the probabilities of observing the relevant detection events and thus improve performance. Finally we present both numerical simulations and implementations on Quandela's Ascella photonic quantum processor to validate our findings.
Summary form only given. Quantum computers are expected to increase the efficiency of solving problems such as factoring large integers. However an experimental implementation of even relatively simple quantum information processing with a few to a dozen qubits presents an enormous technological challenge. One of the earliest proposals for quantum computation is based on implementing a quantum bit with two optical modes containing one photon. The proposal is appealing due to the ease with which photon interference can be observed. However these early proposals required huge single photon optical nonlinearities. Unfortunately currently available optical nonlinearities are too weak and too noisy to be useful. Recently however we have discovered that efficient quantum computation is possible using only beam splitters, phase shifters, single photon sources and photodetectors. Our methods exploit feed forward from photo-detectors and are robust against errors from photon loss and detector inefficiency. In this tutorial I will outline this scheme, highlighting the technical challenges required to implement it. The tutorial will be relatively self contained with a brief introduction to quantum optics and quantum computation.
Abstract Graphs have provided an expressive mathematical tool to model quantum-mechanical devices and systems. In particular, it has been recently discovered that graph theory can be used to describe and design quantum components, devices, setups and systems, based on the two-dimensional lattice of parametric nonlinear optical crystals and linear optical circuits, different to the standard quantum photonic framework. Realizing such graph-theoretical quantum photonic hardware, however, remains extremely challenging experimentally using conventional technologies. Here we demonstrate a graph-theoretical programmable quantum photonic device in very-large-scale integrated nanophotonic circuits. The device monolithically integrates about 2,500 components, constructing a synthetic lattice of nonlinear photon-pair waveguide sources and linear optical waveguide circuits, and it is fabricated on an eight-inch silicon-on-insulator wafer by complementary metal–oxide–semiconductor processes. We reconfigure the quantum device to realize and process complex-weighted graphs with different topologies and to implement different tasks associated with the perfect matching property of graphs. As two non-trivial examples, we show the generation of genuine multipartite multidimensional quantum entanglement with different entanglement structures, and the measurement of probability distributions proportional to the modulus-squared hafnian (permanent) of the graph’s adjacency matrices. This work realizes a prototype of graph-theoretical quantum photonic devices manufactured by very-large-scale integration technologies, featuring arbitrary programmability, high architectural modularity and massive manufacturing scalability.
Linear optics, combined with practical photon source and single-photon detectors, has provided a powerful tool to test a number of quantum information protocols. In the linear optics implementations, the post-selection technique based on photon detections typically plays a critical role. As one scales up the system, the post-selection technique generally leads to very inefficient (exponential) scaling of the overall efficiency, which limits the implementation to small systems. In the past few years, two approaches have been proposed to circumvent this obstacle for different kinds of quantum information processing. In the first approach, a remarkable proposal, generally referred to as linear optics quantum computation, was first put forward by Knill, Laflamme, and Mil-burn (KLM) [1] and then improved by a number of others. In this approach, one overcomes the scaling problem for linear optics computation through quantum error correction by requiring the efficiencies for the photon source and the detectors to attain a high threshold value [1]. The threshold efficiency has been improved considerably in the past few years, with the most recent estimate about Linear optics, combined with practical photon source and single-photon detectors, has provided a powerful tool to test a number of quantum information protocols. In the linear optics implementations, the post-selection technique based on photon detections typically plays a critical role. As one scales up the system, the post-selection technique generally leads to very inefficient (exponential) scaling of the overall efficiency, which limits the implementation to small systems. In the past few years, two approaches have been proposed to circumvent this obstacle for different kinds of quantum information processing. In the first approach, a remarkable proposal, generally referred to as linear optics quantum computation, was first put forward by Knill, Laflamme, and Mil-burn (KLM) [1] and then improved by a number of others. In this approach, one overcomes the scaling problem for linear optics computation through quantum error correction by requiring the efficiencies for the photon source and the detectors to attain a high threshold value [1]. The threshold efficiency has been improved considerably in the past few years, with the most recent estimate about 99.4%− 99.7% [2]. In the second approach proposed in Ref. [3], one uses linear optics for implementation of scalable quantum communication through the quantum repeater protocol. This approach overcomes the inefficient scaling through the divide-and-conquer method. In this protocol, one does not have a threshold requirement on the source and the detector efficiencies, which allows its implementation with the state-of-the-art photon detectors.
Computing the number of perfect matchings of a graph is a famous #P-complete problem. In this work, taking the advantages of the frequency dimension of photon, we propose and implement a photonic perfect matching solver, by combining two key techniques, frequency grouping and multi-photon counting. Based on a broadband photon-pair source from a silicon quantum chip and a wavelength-selective switch, we configure graphs up to sixteen vertices and estimate the perfect matchings of subgraphs up to six vertices. The experimental fidelities are more than 90% for all the graphs. Moreover, we demonstrate that the developed photonic system can enhance classical stochastic algorithms for solving nondeterministic-polynomial-time(NP) problems, such as the Boolean satisfiability problem and the densest subgraph. Our work contributes a promising method for solving the perfect matchings problem, which is simple in experiment setup and convenient to transform or scale up the object graph by regulating the frequency-correlated photon pairs. Perfect matching counting is a famously hard problem. Here, the authors propose a photonic perfect matching solver by multi-photon coincidence of grouped broadband frequency-correlated photon pairs. The samples from the solver can also be used to enhance searching algorithms for NP problems such as SAT and densest subgraph.
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.