Quantum Information and Graph Theory: Emerging Connections
In arXiv:quant-ph/0608223, quantum network coding was proved to be no more useful than simply routing the quantum transmissions in some directed acyclic networks. This talk will connect this result, monogamity of entanglement, and graph theoretic properties of the networks involved.
It is well-known that if a graph G_1 can be obtained from another graph G_2 by removing a degree-2 vertex and combing its two neighbors, the graph state |G_1> can be obtained from |G_2> through LOCC. In this talk, I will describe how to construct a graph G\' from a given graph G so that (a) The maximum degree of G\', Delta(G\'), is no more than 3. (b) G can be obtained from G\' by a sequence of contraction operations described above. (c) The treewidth of G\', tw(G\'), is no more than tw(G)+1. (d) The construction takes exp(O(tw(G))) time.
It is well known that the toric code model supports abelian anyons. It can be realized on a square lattice of qubits, where the anyons are represented by the endpoints of strings of Pauli operators. We will demonstrate that the non-abelian Ising model can be realized in a similar way, where now the string operators are elements of the Clifford group. The Ising anyons are shown to be essentially superpositions of the abelian toric code ones, reproducing the required fusion, braiding and statistical properties.
This talk will report recent work on two themes that relate concepts in graph theory to problems in quantum information theory. We will discuss the quantum analogue of expander graphs which prove to be of key importance when de-randomizing algorithms in classical computer science. Using powerful ideas of discrete phase space methods, efficiently implementable quantum expanders can be constructed based on an argument that barely fills three lines.
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.
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.
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.
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.
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.
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.