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

Solving graph problems with single-photons and linear optics

Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield

Published Jan 23, 2023• 0 citations
arXivHTMLPDF

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.48550/arxiv.2301.09594

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\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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•0 citations

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.

Physical Review A•Sep 6, 2023•14 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

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

Pingyu Zhu, Qilin Zheng, Kun Wang +6 more

Abstract Computing the number of perfect matchings of a graph is a famous #P-complete problem. In this work, taking the outstanding 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 configured graphs up to sixteen vertices and calculated the perfect matchings of subgraphs up to six vertices. The experimental fidelities are more than 90% for all the graphs. The developed photonic system can be applied in solving nondeterministic-polynomial-time(NP)-complete problems, and we experimentally demonstrate the samples can enhance the random search for solving of the Boolean satisfiability problem and the finding of densest subgraph. Our perfect matching solver avoids destructive interference and does not need to consider the indistinguishability of photons. Moreover, it is simple and convenient to transform or scale up the graph by programming a wavelength-selective switch without changing the photonic source. Our work suggests an excellent platform for graph problem solving.

Nature Communications•Apr 22, 2025•2 citations

Single-photon device requirements for operating linear optics quantum computing outside the post-selection basis

Thomas D. Jennewein, Marco Barbieri, Andrew G. White

Photonics is a promising architecture for the realisation of quantum information processing, since the two-photon interaction, or non-linearity, necessary to build logical gates can efficiently be realised by the use of interference with ancillary photons and detection. Although single-photon sources and detectors are pivotal in realisations of such systems, clear guidelines for the required performance of realistic systems are yet to be defined. We present our detailed numerical simulation of several quantum optics circuits including sources and detectors all represented in multi-dimensional Fock-spaces, which allows us to obtain experimentally realistic performance bounds for these devices. In addition, the single-photon source based on switched parametric downconversion is studied, which in principle could reach the required performance. Three approaches for implementing the switching hierarchy of the photons are simulated, and their anticipated performance is obtained. Our results define the bar for the optical

•Feb 1, 2011•51 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•201 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 bounded n×nn \times nn×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 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 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 Computing the number of perfect matchings of a graph is a famous #P-complete problem. In this work, taking the outstanding 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 configured graphs up to sixteen vertices and calculated the perfect matchings of subgraphs up to six vertices. The experimental fidelities are more than 90% for all the graphs. The developed photonic system can be applied in solving nondeterministic-polynomial-time(NP)-complete problems, and we experimentally demonstrate the samples can enhance the random search for solving of the Boolean satisfiability problem and the finding of densest subgraph. Our perfect matching solver avoids destructive interference and does not need to consider the indistinguishability of photons. Moreover, it is simple and convenient to transform or scale up the graph by programming a wavelength-selective switch without changing the photonic source. Our work suggests an excellent platform for graph problem solving.
Photonics is a promising architecture for the realisation of quantum information processing, since the two-photon interaction, or non-linearity, necessary to build logical gates can efficiently be realised by the use of interference with ancillary photons and detection. Although single-photon sources and detectors are pivotal in realisations of such systems, clear guidelines for the required performance of realistic systems are yet to be defined. We present our detailed numerical simulation of several quantum optics circuits including sources and detectors all represented in multi-dimensional Fock-spaces, which allows us to obtain experimentally realistic performance bounds for these devices. In addition, the single-photon source based on switched parametric downconversion is studied, which in principle could reach the required performance. Three approaches for implementing the switching hierarchy of the photons are simulated, and their anticipated performance is obtained. Our results define the bar for the optical
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.