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

Physical Review A

Solving graph problems with single photons and linear optics

Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield

Published Sep 6, 2023• 14 citations
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\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.

DOI
10.1103/physreva.108.032405

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

arXiv:2301.09594•Jan 23, 2023•0 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

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

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

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•3 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\ifmmode×\else\texttimes\finn\ifmmode\times\else\texttimes\fi{}nn\ifmmode×\else\texttimes\fin 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.
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×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.
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.
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 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.
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.