2017/05/31 by Mario Krenn, Xuemei Gu, Anton Zeilinger · 96 citations
Computer Science · Physics and Astronomy · #Computer science #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum mechanics #Theoretical physics #quant-ph
paper · pdf · doi:10.1103/physrevlett.119.240403
published in Physical Review Letters 119(24), 240403 (American Physical Society) · 6+5 pages, 4+7 figures
arxiv created 2017/12/12 · openalex publication_date 2017/12/15 · arxiv updated 2017/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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).