Quantum Information and Graph Theory: Emerging Connections
A fundamental theorem of quantum field theory states that the generating functionals of connected graphs and one-particle irreducible graphs are related by Legendre transformation. An equivalent statement is that the tree level Feynman graphs yield the solution to the classical equations of motion. Existing proofs of either fact are either lengthy or are short but less rigorous. Here we give a short transparent rigorous proof. On the practical level, our methods could help make the calculation of Feynman graphs more efficient.
Some years ago Valiant introduced a notion of \'matchgate\' and \'holographic algorithm\', based on properties of counting perfect matchings in graphs. This provided some new poly-time classical algorithms and embedded in this formalism, he recognised a remarkable class of quantum circuits (arising when matchgates happen to be unitary) that can be classically efficiently simulated. Subsequently various workers (including Knill, Terhal and DiVincenzo, Bravyi) showed that these results can be naturally interpreted in terms of the formalism of fermionic quantum computation.
We give an overview of several connections between topics in quantum information theory, graph theory, and statistical mechanics. The central concepts are mappings from statistical mechanical models defined on graphs, to entangled states of multi-party quantum systems. We present a selection of such mappings, and illustrate how they can be used to obtain a cross-fertilization between different research areas.
The idea of pseudo-randomness is to use little or no randomness to simulate a random object such as a random number, permutation, graph, quantum state, etc... The simulation should then have some superficial resemblance to a truly random object; for example, the first few moments of a random variable should be nearly the same. This concept has been enormously useful in classical computer science. In my talk, I\'ll review some quantum analogues of pseudo-randomness: unitary k-designs, quantum expanders (and their new cousin, quantum tensor product expanders), extractors.
Certain structures arising in Physics (mub\'s and sic-povm\'s) can be viewed as sets of lines in complex space that are as large as possible, given some simple constraints on the angles between distinct lines. The analogous problems in real space have long been of interest in Combinatorics, because of their relation to classical combinatorial structures. In the complex case there seems no reason for any combinatorial connection to exist.