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:1803.10736 · Proceedings of the National Academy of Sciences

Quantum experiments and graphs II: Quantum interference, computation, and state generation

Xuemei Gu, Manuel Erhard, Anton Zeilinger, Mario Krenn

Published Feb 15, 2019• 61 citations
arXivHTMLPDF

Abstract

We present an approach to describe state-of-the-art photonic quantum experiments using graph theory. There, the quantum states are given by the coherent superpositions of perfect matchings. The crucial observation is that introducing complex weights in graphs naturally leads to quantum interference. This viewpoint immediately leads to many interesting results, some of which we present here. First, we identify an experimental unexplored multiphoton interference phenomenon. Second, we find that computing the results of such experiments is #P-hard, which means it is a classically intractable problem dealing with the computation of a matrix function Permanent and its generalization Hafnian. Third, we explain how a recent no-go result applies generally to linear optical quantum experiments, thus revealing important insights into quantum state generation with current photonic technology. Fourth, we show how to describe quantum protocols such as entanglement swapping in a graphical way. The uncovered bridge between quantum experiments and graph theory offers another perspective on a widely used technology and immediately raises many follow-up questions.

DOI
10.1073/pnas.1815884116

Related papers

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•1 citation

Quantum experiments and hypergraphs: Multiphoton sources for quantum interference, quantum computation, and quantum entanglement

Xuemei Gu, Lijun Chen, Mario Krenn

We introduce the concept of hypergraphs to describe quantum optical experiments with probabilistic multiphoton sources. Every hyperedge represents a correlated photon source, and every vertex stands for an optical output path. Such a general graph description provides new insights for producing complex high-dimensional multiphoton quantum entangled states, which go beyond limitations imposed by pair creation via spontaneous parametric down-conversion. Furthermore, the properties of hypergraphs can be investigated experimentally. For example, the NP-complete problem of deciding whether a hypergraph has a perfect matching can be answered by experimentally detecting multiphoton events in quantum experiments. By introducing complex weights in hypergraphs, we show a general many-particle quantum interference and manipulating entanglement in a pictorial way. Our work paves the path for the development of multiphoton high-dimensional state generation and might inspire new applications of quantum computations using hypergraph mappings.

arXiv:2003.01910•Physical Review A•Mar 13, 2020•33 citations

Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings

Mario Krenn, Xuemei Gu, Anton Zeilinger

We show a surprising link between experimental setups to realize high-dimensional multipartite quantum states and graph theory. In these setups, the paths of photons are identified such that the photon-source information is never created. We find that each of these setups corresponds to an undirected graph, and every undirected graph corresponds to an experimental setup. Every term in the emerging quantum superposition corresponds to a perfect matching in the graph. Calculating the final quantum state is in the #P-complete complexity class, thus it cannot be done efficiently. To strengthen the link further, theorems from graph theory-such as Hall's marriage problem-are rephrased in the language of pair creation in quantum experiments. We show explicitly how this link allows one to answer questions about quantum experiments (such as which classes of entangled states can be created) with graph theoretical methods, and how to potentially simulate properties of graphs and networks with quantum experiments (such as critical exponents and phase transitions).

arXiv:1705.06646•Physical Review Letters•Dec 15, 2017•92 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

Quantum experiments and graphs. III. High-dimensional and multiparticle entanglement

Xuemei Gu, Lijun Chen, Anton Zeilinger +1 more

Quantum entanglement plays an important role in quantum information processes, such as quantum computation and quantum communication. Experiments in laboratories are unquestionably crucial to increase our understanding of quantum systems and inspire new insights into future applications. However, there are no general recipes for the creation of arbitrary quantum states with many particles entangled in high dimensions. Here we exploit a recent connection between quantum experiments and graph theory and answer this question for a plethora of classes of entangled states. We find experimental setups for Greenberger-Horne-Zeilinger states, $W$ states, general Dicke states, and asymmetrically high-dimensional multipartite entangled states. This result sheds light on the producibility of arbitrary quantum states using photonic technology with probabilistic pair sources and allows us to understand the underlying technological and fundamental properties of entanglement.

arXiv:1812.09558•Physical Review A•Mar 25, 2019•50 citations

Graph-theoretic insights on the constructability of complex entangled states

L. Sunil Chandran, Rishikesh R. Gajjala

The most efficient automated way to construct a large class of quantum photonic experiments is via abstract representation of graphs with certain properties. While new directions were explored using Artificial intelligence and SAT solvers to find such graphs, it becomes computationally infeasible to do so as the size of the graph increases. So, we take an analytical approach and introduce the technique of local sparsification on experiment graphs, using which we answer a crucial open question in experimental quantum optics, namely whether certain complex entangled quantum states can be constructed. This provides us with more insights into quantum resource theory, the limitation of specific quantum photonic systems and initiates the use of graph-theoretic techniques for designing quantum physics experiments.

arXiv:2304.06407•Quantum•Jul 3, 2024•2 citations
We present an approach to describe state-of-the-art photonic quantum experiments using graph theory. There, the quantum states are given by the coherent superpositions of perfect matchings. The crucial observation is that introducing complex weights in graphs naturally leads to quantum interference. This viewpoint immediately leads to many interesting results, some of which we present here. First, we identify an experimental unexplored multiphoton interference phenomenon. Second, we find that computing the results of such experiments is #P-hard, which means it is a classically intractable problem dealing with the computation of a matrix function Permanent and its generalization Hafnian. Third, we explain how a recent no-go result applies generally to linear optical quantum experiments, thus revealing important insights into quantum state generation with current photonic technology. Fourth, we show how to describe quantum protocols such as entanglement swapping in a graphical way. The uncovered bridge between quantum experiments and graph theory offers another perspective on a widely used technology and immediately raises many follow-up questions.
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.
We introduce the concept of hypergraphs to describe quantum optical experiments with probabilistic multiphoton sources. Every hyperedge represents a correlated photon source, and every vertex stands for an optical output path. Such a general graph description provides new insights for producing complex high-dimensional multiphoton quantum entangled states, which go beyond limitations imposed by pair creation via spontaneous parametric down-conversion. Furthermore, the properties of hypergraphs can be investigated experimentally. For example, the NP-complete problem of deciding whether a hypergraph has a perfect matching can be answered by experimentally detecting multiphoton events in quantum experiments. By introducing complex weights in hypergraphs, we show a general many-particle quantum interference and manipulating entanglement in a pictorial way. Our work paves the path for the development of multiphoton high-dimensional state generation and might inspire new applications of quantum computations using hypergraph mappings.
We show a surprising link between experimental setups to realize high-dimensional multipartite quantum states and graph theory. In these setups, the paths of photons are identified such that the photon-source information is never created. We find that each of these setups corresponds to an undirected graph, and every undirected graph corresponds to an experimental setup. Every term in the emerging quantum superposition corresponds to a perfect matching in the graph. Calculating the final quantum state is in the #P-complete complexity class, thus it cannot be done efficiently. To strengthen the link further, theorems from graph theory-such as Hall's marriage problem-are rephrased in the language of pair creation in quantum experiments. We show explicitly how this link allows one to answer questions about quantum experiments (such as which classes of entangled states can be created) with graph theoretical methods, and how to potentially simulate properties of graphs and networks with quantum experiments (such as critical exponents and phase transitions).
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.
Quantum entanglement plays an important role in quantum information processes, such as quantum computation and quantum communication. Experiments in laboratories are unquestionably crucial to increase our understanding of quantum systems and inspire new insights into future applications. However, there are no general recipes for the creation of arbitrary quantum states with many particles entangled in high dimensions. Here we exploit a recent connection between quantum experiments and graph theory and answer this question for a plethora of classes of entangled states. We find experimental setups for Greenberger-Horne-Zeilinger states, WWW states, general Dicke states, and asymmetrically high-dimensional multipartite entangled states. This result sheds light on the producibility of arbitrary quantum states using photonic technology with probabilistic pair sources and allows us to understand the underlying technological and fundamental properties of entanglement.
The most efficient automated way to construct a large class of quantum photonic experiments is via abstract representation of graphs with certain properties. While new directions were explored using Artificial intelligence and SAT solvers to find such graphs, it becomes computationally infeasible to do so as the size of the graph increases. So, we take an analytical approach and introduce the technique of local sparsification on experiment graphs, using which we answer a crucial open question in experimental quantum optics, namely whether certain complex entangled quantum states can be constructed. This provides us with more insights into quantum resource theory, the limitation of specific quantum photonic systems and initiates the use of graph-theoretic techniques for designing quantum physics experiments.