Quantum Experiments and Graphs: Multiparty States as coherent superpositions of Perfect Matchings. (arXiv:1705.06646v2 [quant-ph] UPDATED)

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 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. We show explicitly how
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 properties of Graphs and Networks with quantum experiments
(such as critical exponents and phase transitions).

Article web page: