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

Solving graph problems with single photons and linear optics

Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield

Published Sep 6, 2023• 19 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\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•1 citation

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

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

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

Thomas 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 1 Knill, E, Laflamme, R and Milburn, GJ. 2001. Nature, 409: 46–52. [Crossref], [PubMed], [Web of Science ®] , [Google Scholar]. 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 down-conversion 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 devices needed to achieve the first level of linear-optics quantum computing outside the coincidence basis.

arXiv:1012.1868•Journal of Modern Optics•Feb 10, 2011•88 citations

Quantum Experiments and Graphs II: Computation and State Generation with Probabilistic Sources and Linear Optics

Xuemei Gu, Mario Krenn, Manuel Erhard +1 more

We show how general linear optical quantum entanglement experiments with probabilistic sources can be described using graph theory. By introducing complex weights in undirected graphs, we can naturally work with quantum superpositions. This immediately leads to many interesting results, some of which we present here. Firstly, we identify a conceptually new and experimentally completely unexplored method to solve classically intractable problems with quantum experiments. The problem is in the complexity class #P-complete, and deals with the computation of a generalization of the matrix function Permanent. Second, we show that a recent no-go result applies generally to linear optical quantum experiments, thus revealing important insights to quantum state generation with current photonic technology. Third, we show how to easily understand in a graphical way quantum experiments such as entanglement swapping. This connection offers a novel perspective on a widely used technology, and immediately raises many new questions.

•Mar 28, 2018•2 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 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.
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.
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.
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 1 Knill, E, Laflamme, R and Milburn, GJ. 2001. Nature, 409: 46–52. [Crossref], [PubMed], [Web of Science ®] , [Google Scholar]. 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 down-conversion 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 devices needed to achieve the first level of linear-optics quantum computing outside the coincidence basis.
We show how general linear optical quantum entanglement experiments with probabilistic sources can be described using graph theory. By introducing complex weights in undirected graphs, we can naturally work with quantum superpositions. This immediately leads to many interesting results, some of which we present here. Firstly, we identify a conceptually new and experimentally completely unexplored method to solve classically intractable problems with quantum experiments. The problem is in the complexity class #P-complete, and deals with the computation of a generalization of the matrix function Permanent. Second, we show that a recent no-go result applies generally to linear optical quantum experiments, thus revealing important insights to quantum state generation with current photonic technology. Third, we show how to easily understand in a graphical way quantum experiments such as entanglement swapping. This connection offers a novel perspective on a widely used technology, and immediately raises many new questions.
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.