Quantum Information and Graph Theory: emerging connections

Conference Date: 
Monday, April 28, 2008 (All day) to Friday, May 2, 2008 (All day)
Scientific Areas: 
Quantum Information


The interface between graph theory and quantum information processing is emerging as a surprisingly large and diversified research environment. This context embraces many scenarios: on the one side, aspects of algebraic, topological, and structural graph theory; on the other side, special classes of quantum states, correlations, and the classical simulatability of quantum processes. In the light of the latest developments, two mathematical topics require special attention: (i) local graph transformations and their algebraic invariants; (ii) "nonlocal" graph measures of structural complexity. The first subject appears to be useful in the study of one-way quantum computation, error correction and fault-tolerance. The second one covers several roles in the theory of entanglement and in the classical simulatability of quantum circuits. This meeting will bring together people with different know-how, but linked by an interest in common notions, even if such notions are hidden behind disjoint terminologies and applications.
The workshop has three focus areas:
  • Local graph-theoretical operations.
  • Measures of connectivity and entanglement.
  • Uses of graph states in quantum information processing and simulation of quantum systems.
These topics focus on local properties of graphs, how they interplay with global properties of graphs, and how these properties are used in quantum information processing and other areas.  Questions of interest include: "Which global properties are invariant under local operations?", "Which measures of the global strength of graphs like connectivity relate to properties of quantum systems such as entanglement?", "How versatile are these global properties under alternations, e.g., to which extend can quantum mechanical systems corresponding to graphs with weak global properties be simulated classically?", "How can global graph properties be utilized in quantum computing, and how do they relate to studies of entanglement and non-locality?"


Hans Briegel, Innsbruck

Hector Bombin, Madrid

Sougato Bose, London

Dan Browne, London

Jens Eisert, London

Steve Flammia, PI

Jim Geelen, Waterloo

Joseph Geraci, Toronto

Chris Godsil, Waterloo

Aram Harrow, Bristol

Richard Jozsa, Bristol

Elham Kashefi, Oxford

Achim Kempf, Waterloo

Debbie Leung, Waterloo

Akimasa Miyake, Innsbruck

Jiannis Pachos, Leeds, UK

Simon Perdrix, Paris

Michel Planat, FEMTO-ST, France

Yaoyun Shi, Ann Arbor

Pasquale Sodano, Perugia

Maarten van den Nest, Garching

Yong-Shi Wu, Utah


Hector Bombin, Madrid, ES

Statistical Mechanical Models and Topological Color Codes.

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.

Saugato Bose, London, UK

Spin graphs for quantum communication and ground state entanglement


In this talk, two specific directions of research in quantum information are presented which could potentially gain from graph theory. The first is the study of quantum communication using systems of perpetually interacting qubits (or spins) as a databus. After introducing the topic through the simplest examples of linear chains of spins as transmitters of quantum information, we briefly  

mention existing work on quantum communication through more general graphs of spins. We then explain why the transmission of quantum information between vertices of a graph in the case of an isotropic  

Heisenberg interaction (between the spins placed at these vertices) depends on the Laplacian of the graph. How the quality of communication varies when starts cutting edges after starting a fully  

connected graph will be discussed *. Another direction is related to the entanglement naturally present in the ground state of a graph of perpetually interacting spins: various specific examples --- fully  

connected, star and tree will be discussed. Some easily solvable interactions obtained by putting higher spins in specific vertices of simple graphs will also be discussed. In the end we also present an  

example where one can get a "graph independent" ground state by placing qudits with exchange interactions on an arbitrary graph. (* The first part of the talk is based on ongoing work with

Simone Severini, Stefano Mancini and Andrea Casaccino, while the second part is based on work with Vladimir Korepin and Christopher Hadley)


Hans Briegel, Innsbruck, AT

Fundamentals of universality in one-way quantum computation

We study different notions of universality in quantum computation. We derive necessary criteria for so-called CQ-universality in measurement-based (one-way) quantum computation. We discuss the role of type-II entanglement monotones in this context and, in particular, the entanglement width and its relation to the rank width used in graph theory

Literature: M. Van den Nest, W. Dür, A. Miyake, and H.J. Briegel, New J. Phys. 9, 204 (2007).

Anne Broadbent, University of Montreal 

Universal Blind Quantum Computation 


I will present a new protocol that was developed entirely in the measurement-based model for quantum computation. Our protocol allows Alice to have Bob carry out a quantum computation for her such that Alice's inputs, outputs and computation remain perfectly private, and where Alice does not require any quantum computational power or memory. Alice only needs to be able to prepare single qubits from a finite set and send them to Bob, who has the balance of the required quantum computational resources. Our protocol is interactive: after the initial preparation of quantum states, Alice and Bob use two-way classical communication which enables Alice to drive the computation, giving single-qubit measurement instructions to Bob, depending on previous measurement outcomes. Our protocol is efficient and is presented for the special case of a classical-input, and classical-output; modifications allow the general case of quantum inputs and outputs. We also discuss the use of authentication in order for Alice to detect an uncooperative Bob.

Based on joint work with Joseph Fitzsimons and Elham Kashefi

Dan Browne, University College London, UK 

Is there a classical analogue of measurement-based quantum computation?


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.

Jens Eisert, London, UK

Tales from Graphland 

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. We also briefly report news on novel measurement-based models of quantum computing, based on quantum systems distributed on a graph, beyond one-way computing. 

Work done in collaboration with D. Gross 

D. Gross, J. Eisert, "Quantum Margulis expanders", Quant. Inf. Comp. (2008), arXiv:0710.0651.

D. Gross, J. Eisert, "Quantum computational wires", in preparation (2008).

D. Gross, J. Eisert, N. Schuch, D. Perez-Garcia, "Measurement-based quantum computation beyond the one-way model", Phys. Rev. A 76, 052315 (2007), arXiv:0706.3401.

D. Gross, J. Eisert, "Novel schemes for measurement-based quantum computation", Phys. Rev. Lett. 98, 220503 (2007).

Steve Flammia, Perimeter Institute

Universal graph states from the optical frequency comb


One-way quantum computing allows any quantum algorithm to be implemented by the sole use of single-qubit measurements.  The difficult part is to create a universal resource state on which the measurements are made. We propose to use continuous-variable (CV) entanglement in the optical frequency comb of a single optical parametric oscillator with a multimode pump to produce a very large CV graph state with a special 4-regular graph.  This scheme is interesting because of its potential for scalability, although issues of error correction and fault tolerance are yet to be fully addressed.

 Other possible physical configurations that are achievable with this scheme are related to the existence of certain bipartite edge-weighted graphs with circulant support having orthogonal adjacency matrices.

If the above description fails to move you, don't worry, there will be pretty pictures.  Joint work with N. Menicucci and O. Pfister, and with S. Severini.


Charlotte Gils, Zurich

Non-abelian topological phases and unconventional criticality in a model of interacting anyons

Non-abelian anyons and topologically ordered systems  are of particular interest in the context of topological quantum computation.  However, not much is known about physical systems, or even microscopic models, that exhibit  topological phases with non-abelian quasiparticle excitations. In this work, we  investigate a microscopic model whose degrees of freedom form  a class of non-abelian anyons, so-called Fibonacci anyons.  We find that  wide parts of the phase diagram are covered by non-abelian topological phases, and reveal the  role of  topology in determining the essential properties of  these phases. Furthermore, we observe  a phase transition between two distinct topological phases, as well as a second extended critical phase. We find that these critical phases are described by  conformal field theories.

Jim Geelen, University of Waterloo, ON 

On Vertex Minors


A vertex-minor of a graph G is any graph that can be obtained from G by a sequence local complementations and vertex deletions. The purpose of this talk is to explore the possibility of extending the graph minors project of Robertson and Seymour to vertex minors. There are some aspects of vertex minors that make them easier than graph minors. The talk will be based more on conjecture than fact, but I will present one new result based on joint work with Sang-il Oum. 

Joseph Geraci, USC, Los Angeles, USA and University of Toronto 

Some relationships between Quantum Computation and classical statistical physics

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.

Chris Godsil, Waterloo, ON

Complex Lines


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.

Aram Harrow, University of Bristol, UK

Pseudo-random quantum states and operations


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.

Richard Jozsa, Universtity of Bristol, UK

Matchgates and the classical simulation of associated quantum circuits


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.

Elham Kashefi, Grenoble, FR

Lost in Translation


We consider the question of forward and backward translation between measurement-based quantum computing, called patterns, and quantum circuit computation. It is known that the class of patterns with a particular properties, having flow, is in one-to-one correspondence with quantum circuits. However we show that a more general class of patterns, those having generalised flow, will sometime translate to imaginary circuits, quantum circuits with time-like curves. Extending this approach, we first present the semantics of quantum circuits with time-like curves in terms of post-selection quantum computing and then characterise the class of curves with unitary or completely-positive semantic. Finally we present the re-write rules for opening the loops to transform an imaginary circuit to a normal circuit and discuss the connection between time-like curves and depth complexity.

Achim Kempf, Waterloo, ON 

A unifying view of graph theory in quantum field theory


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)

Andrew Landahl, UNM

Universal quantum walks on graphs


We construct a family of time-independent nearest-neighbor Hamiltonians coupling eight-state systems on a 1D ring that enables universal quantum computation. Hamiltonians in this family can achieve universality either by driving a continuous-time quantum walk or by terminating an adiabatic algorithm. In either case, the universality property can be understood as arising from an efficient simulation of a programmable quantum circuit. Using gadget perturbation theory, one can demonstrate the same kind of universality for related Hamiltonian families acting on qubits in 2D. Our results demonstrate that simulating 1D chains of spin-7/2 particles is BQP-hard, and indeed BQP-complete because the outputs of decision problems can be encoded in the outputs of such simulations.

Debbie Leung, Waterloo

Quantum network coding, entanglement, and graphs.

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.

Akimasa Miyake, Innsbruck, IQOQI

Ground-code measurement-based quantum computer

I will talk about a scheme of the ground-code measurement-based quantum computer, which enjoys two major advantages. (i) Every logical qubit is encoded in the gapped degenerate ground subspace of a spin-1 chain with nearest-neighbor two-body interactions, so that it equips built-in robustness against noise.

(ii) Computation is processed by single-spin measurements along multiple chains dynamically coupled on demand, so as to keep teleporting only logical information into a gap-protected ground state of the rest chains after the interactions with spins to be measured are adiabatically turned off.

Our scheme is a conceptual advance, since measurements generally create excitations in the system so that two desired properties, keeping the information in the ground state and processing the information by measurements, are not seemingly compatible.

I may shortly describe implementations using trapped atoms or polar molecules in an optical lattice, where the gap is expected to be as large as 0.2 KHz or 4.8 KHz respectively. This is a joint work with G.K. Brennen. 

Caterina-Eloisa Mora, IQC

Universal resources for approximate and stochastic measurement-based quantum computation

We investigate which families of quantum states can be used as resources for approximate and/or stochastic universal measurement-based quantum computation, in the sense that single-qubit operations and classical communication are sufficient to prepare (with some fixed precision and/or probability) any quantum state from the initial resource. We find entanglement-based criteria for non-universality in the approximate and/or stochastic case. By applying them, we are able to discard some families of states as not universal also in this weaker sense. Finally, we show that any family $\Sigma$ of states that is "close" to an (approximate and/or stochastic) universal family $\Gamma$ is approximate and stochastic universal, and we prove that if $\Gamma$ was efficiently universal then also $\Sigma$ is.

Jiannis Pachos, University of Leeds

Emergence of non-abelian statistics from an abelian model

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. We propose a string framing and ancillary qubits to implement the non-trivial chirality of this model.


Simon Perdix, Grenoble, FR

Flows for determinism and parallelism in one-way quantum computation.

In this talk, I will present how the determinism in the one-way model, which is based on non deterministic quantum measurements, can be captured by the existence of a generalized flow in the graph that underlies the computation. Moreover, the depth of the one-way quantum computation is upper-bounded by the depth of the generalized flow. Finding a flow of minimal depth is then a key issue in order to decrease the depth of the one-way quantum computation. I will show that generalized flow of minimal depth can be found efficiently (i.e. in a polynomial time on a classical computer).

This talk is based on work with Dan Browne, Elham Kashefi and Mehdi Mhalla.

Michel Planat, FEMTO-ST, France,

On group theory for quantum gates and quantum coherence


Finite group extensions offer a natural language to quantum computing. In a nutshell, one roughly describes the action of a quantum computer as consisting of two finite groups of gates: error gates from the general Pauli group P and stabilizing gates within an extension group C. In this communication one explores the nice adequacy between group theoretical concepts such as commutators, normal subgroups, group of automorphisms, short exact sequences, wreath products etc. and the coherent quantum computational primitives. The structure of the single-qubit and two-qubit Clifford groups is analyzed in detail. As a byproduct, one discovers thatM20, the smallest perfect group for which the commutator subgroup departs from the set of commutators, underlies quantum coherence of the two-qubit system. One recovers similar results by looking at the automorphisms of a complete set of mutually unbiased bases.

Joint work with P. Jorrand

Pradeep Sarvepalli, Texas, US

Two Approaches to Sparse Graph Quantum Codes

Constructing good quantum LDPC codes remains an important problem in quantum coding theory. We contribute to the ongoing discussion on this topic by proposing two approaches to constructing quantum LDPC codes. In the first, we rely on an algebraic method that uses a redundant description of the parity check matrix to overcome the problem of 4-cycles in the Tanner graph that degrade the performance of iterative decoding. In the second we use the fact that subsystem coding can simplify the decoding process. We show that if there exist classical LDPC codes with large error exponents, then we can construct degenerate subsystem LDPC codes with the stabilizer generators having low weight.

Pasquale Sodano, Perugia

Exotic Phases and Entanglement Properties of Condensed Matter Systems Living on Graphs.

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.


Yaoyun Shi,  University of Michigan, Ann Arbor, USA

Graph expansions and simulating one-way quantum computation

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. Those properties imply that a one-way quantum computation on the graph state |G> can be simulated by a randomized algorithm in time exp(O(tw(G))). Previously, it was known that such a computation can be simulated in time exp(O(tw(G) Delta(G))) [Markov and Shi, to appear in SICOMP], which is substantially more expensive than our bound when Delta(G) is large. 

Joint work with Igor Markov, based on arXiv:0707.3622.

Rolando Somma, PI 

Quantum Simulations of Classical Annealing Processes  


Quantum computers provide new resources to solve combinatorial optimization problems (COPs). Using techniques borrowed from quantum information theory, I will present a quantum algorithm that simulates classical annealing processes, where the (quantum) annealing rate greatly outperforms other classical methods like Markov chain Monte-Carlo based algorithms. Our quantum algorithm provides quadratic speedups to find both, the solution to particular instances of COPs, and the preparation of (quantum) Gibbs' states.

Maarten van den Nest, University of Innsbruck, AT

Quantum information, graphs, and statistical mechanics

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

Yong-Shi Wu, Utah

Yang-Baxter Equations, Extra-special Two-groups and Topological-like Features in Quantum Information Theory

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. 

Additional sponsorship provided by:

Institute for Quantum Computing