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

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

Xuemei Gu, Mario Krenn, Manuel Erhard, Anton Zeilinger

Published Mar 28, 2018• 1 citation
OpenAlex

Abstract

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.

Related papers

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

Xuemei Gu, Manuel Erhard, Anton Zeilinger +1 more

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.

arXiv:1803.10736•Proceedings of the National Academy of Sciences•Feb 15, 2019•61 citations

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

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

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

Hard limits on the postselectability of optical graph states

Jeremy C. Adcock, Sam Morley-Short, Joshua W. Silverstone +1 more

Abstract Coherent control of large entangled graph states enables a wide variety of quantum information processing tasks, including error-corrected quantum computation. The linear optical approach offers excellent control and coherence, but today most photon sources and entangling gates—required for the construction of large graph states—are probabilistic and rely on postselection. In this work, we provide proofs and heuristics to aid experimental design using postselection. We introduce a versatile design rule for postselectable experiments: drawn as a graph, with qubit as vertices and gates and photon-pair sources as edges, an experiment may only contain cycles with an odd number of sources. We analyse experiments that use photons from postselected photon-pair sources, and lower bound the number of accessible classes of graph state entanglement in the non-degenerate case—graph state entanglement classes that contain a tree are are always accessible. The proportion of graph states accessible by postselection shrinks rapidly, however. We list accessible classes for various resource states up to 9 qubits. Finally, we apply these methods to near-term multi-photon experiments.

arXiv:1806.03263•Quantum Science and Technology•Nov 28, 2018•22 citations
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 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 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.
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.
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).
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.
Abstract Coherent control of large entangled graph states enables a wide variety of quantum information processing tasks, including error-corrected quantum computation. The linear optical approach offers excellent control and coherence, but today most photon sources and entangling gates—required for the construction of large graph states—are probabilistic and rely on postselection. In this work, we provide proofs and heuristics to aid experimental design using postselection. We introduce a versatile design rule for postselectable experiments: drawn as a graph, with qubit as vertices and gates and photon-pair sources as edges, an experiment may only contain cycles with an odd number of sources. We analyse experiments that use photons from postselected photon-pair sources, and lower bound the number of accessible classes of graph state entanglement in the non-degenerate case—graph state entanglement classes that contain a tree are are always accessible. The proportion of graph states accessible by postselection shrinks rapidly, however. We list accessible classes for various resource states up to 9 qubits. Finally, we apply these methods to near-term multi-photon experiments.