TY - JOUR
AB - 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 correspond 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 grpah. Calculating the final quantum state is in the complexity class #P-complete, thus 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. This link allows to answer questions about quantum experiments (such as which classes of entangled states can be created) with graph theoretical methods, and potentially simulate problems in Graph Theory with quantum experiments.
AU - Krenn, M.
AU - Gu, X.
AU - Zeilinger, A.
DA - 2017/12/15/
DO - 10.1103/PhysRevLett.119.240403
ET - 2018/01/11/
JF - Physical Review Letters
PY - 2017
SE - 2017/05/22/
SP - 240403
TI - Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings
UR - https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.119.240403
VL - 119
ER -