Quantum Information and Graph Theory: Emerging Connections - 2008

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. will discuss some of the history of the real problems, and describe some recent work that relates the complex problems to some very interesting classes of graphs.

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. I\'ll talk about relations between them, efficient constructions, and possible applications. Some of the material is joint work with Matt Hastings and Richard Low.

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. For example, we show how width parameters in graph theory such as \'tree-width\' and \'rank-width\', which may be used to assess the computational hardness of evaluating partition functions, are intimately related with the entanglement measure \'entanglement width\', which is used to asses to computational power of resource states in quantum information. Furthermore, using our mappings we provide simple techniques to relate different statistical mechanical models with each other via basic graph transformations. These techniques can be used to prove that that there exist models which are \'complete\' in the sense that every other model can be viewed as a special instance of such a complete model via a polynomial reduction. Examples of such complete models include the 2D Ising model in an external field, as well as the zero-field 3D Ising model. Joint work with W. Duer, G. de las Cuevas, R. Huebener and H. Briegel

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. In this talk I will outline how unitary matchgates and their simulability arise from considering a Clifford algebra of anticommuting symbols, and then I\'ll discuss some avenues for further generalisation and interesting properties of matchgate circuits. In collaboration with Akimasa Miyake, University of Innsbruck.

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. On the conceptual level, our methods yield a new, unifying view of the structure of perturbative quantum field theory, and they reveal the fundamental role played by the Euler characteristic of graphs. This is joint work with D.M. Jackson (UW) and A. Morales (MIT)

We find that the overlapping of a topological quantum color code state, representing a quantum memory, with a factorized state of qubits can be written as the partition function of a 3-body classical Ising model on triangular or Union Jack lattices. This mapping allows us to test that different computational capabilities of color codes correspond to qualitatively different universality classes of their associated classical spin models. By generalizing these statistical mechanical models for arbitrary inhomogeneous and complex couplings, it is possible to study a measurement-based quantum computation with a color code state and we find that their classical simulatability remains an open problem. We complement the meaurement-based computation with the construction of a cluster state that yields the topological color code and this also gives the possibility to represent statistical models with external magnetic fields. Joint work with M.A. Martin-Delgado.

A comprehensive graph theoretical and finite geometrical study of the commutation relations between the generalized Pauli operators of N-qudits is performed in which vertices/points correspond to the operators and edges/lines join commuting pairs of them. As per two-qubits, all basic properties and partitionings of the corresponding Pauli graph are embodied in the geometry of the generalized quadrangle of order two. Here, one identifies the operators with the points of the quadrangle and groups of maximally commuting subsets of the operators with the lines of the quadrangle. The three basic partitionings are (a) a pencil of lines and a cube, (b) a Mermin\'s array and a bipartite-part and (c) a maximum independent set and the Petersen graph. These factorizations stem naturally from the existence of three distinct geometric hyperplanes of the quadrangle, namely a set of points collinear with a given point, a grid and an ovoid, which answer to three distinguished subsets of the Pauli graph, namely a set of six operators commuting with a given one, a Mermin\'s square, and set of five mutually non-commuting operators, respectively. The generalized Pauli graph for multiple qubits is found to follow from symplectic polar spaces of order two, where maximal totally isotropic subspaces stand for maximal subsets of mutually commuting operators. The substructure of the (strongly regular) N-qubit Pauli graph is shown to be pseudo-geometric, i. e., isomorphic to a graph of a partial geometry. Finally, the (not strongly regular) Pauli graph of a two-qutrit system is introduced; here it turns out more convenient to deal with its dual in order to see all the parallels with the two-qubit case and its surmised relation with the generalized quadrangle Q(4, 3), the dual ofW(3). Joint work with Metod Saniga. Based on arXiv:quant-ph/0701211.

Recently a simple but perhaps profound connection has been observed between the unitary solutions of the Yang-Baxter Equations (YBE) and the entangled Bell states and their higher dimensional (or more-qubit) extensions, the generalized GHZ states. We have shown that this connection can be made more explicit by exploring the relation between the solutions of the YBE and the representations of the extra-special two-groups. This relationship brings certain topological-like features to quantum information theory, and makes a connection to the well-known Jones polynomials which are topological invariants of knots and links. This emerging connection may deepen our understanding, through new representations of extra-special two-groups, of quantum error correction and topological quantum computation. This work is a collaboration with Eric Rowell, Zhenghan Wang, Molin Ge, and Yong-Zhang.

Measurement-based quantum computation is unusual among quantum computational models in that it does not have an obvious classical analogue. In this talk, I shall describe some new results which shed some new light on this. In the one-way model [1], computation proceeds by adaptive single-qubit measurements on a multi-qubit entangled \'cluster state\'. The adaptive measurements require a classical computer, which processes the previous measurement outcomes to determine the correct bases for the following measurement. We shall describe a generalisation of the model where this classical \'side-computation\' plays a more central role. We shall show that this classical computer need not be classically universal, and can instead by performed by a limited power \'CNOT computer\' - a reversible classical computer whose generating gate set consists of CNOT and NOT. The CNOT computer is not universal for classical computation and is believed to be less powerful. Most notably in the context of quantum computation, it is the class of computer sufficient for the efficient simulation of Clifford group circuits [2] - a closely related result. This motivates the question of what resource states would be universal for classical computation, if the control computer is in the CNOT class. We shall answer this question with several examples. Leading from these examples, a natural question is thus, is \'classically universal measurement based computation\' possible with solely classical physics? By considering different settings, we shall answer this question both in the negative and positive, and draw some striking connections with some well-known techniques from models of generalised no-signalling theories. [1] R. Raussendorf and H.J. Briegel, Phys Rev Lett (2001) 86 5188 [2] S. Aaronson and D. Gottesman, Phys Rev A (2004) 70 052328 This is joint work with Janet Anders. We would like to acknowledge inspiring and fruitful discussions with Hans Briegel, Akimasa Miyake, Robin Blume Kohout and Debbie Leung.

New and exotic phases as well as remarkable entanglement behaviors emerge in condensed matter systems (and quantum devices) living (fabricated) on graphs. To illustrate this, I will discuss the properties of Josephson junction networks fabricated on comb and star graphs and of spin models living on pertinent fiber-graphs.

I will discuss a quantum algorithm for the exact evaluation of the classical Potts partition function for a class of graphs (and hypergraphs) related to a family of classical cyclic codes. I will also present a mapping I recently constructed from quantum circuit instances to graphs and discuss some relationships to the classical Ising partition function.