I am a Post-doctoral research assistant in the Quantum Group at the Oxford Department of Computer Science. I recently submitted my DPhil (aka PhD) thesis as a student in the same group, and await my viva (aka thesis defence).
I completed a bachelors of computer science and applied mathematics at the University of Tulsa in 2007. For my masters, I completed the MFoCS program at the Oxford Mathematical Institute in 2008.
Research
My primary research areas are category theory, quantum information, graphical calculi, and graph rewriting. To this end, my research falls under three threads: Graphical Languages and Higher Categories, the Graphical Structure of Entanglement, and Graph Rewriting and Automation.
Graphical Languages and Higher Categories
Contractions of tensors in multilinear algebra admit a crisp, diagrammatic notation, using “boxes and wires”. This notation dates at least back to the 1970s, with Penrose’s seminal paper “Applications of Negative-Dimensional Tensors”1. Here, tensors are represented as boxes, with lower indices depicted as inputs and upper indices as outputs. An edge is then drawn to represent tensor composition (i.e. summing a lower index with an upper index):
Special cases include tensor networks used for efficient representations of many-body entanglement, spin chains and networks, and even Feynman diagrams.
But “box-and-wire” diagrams aren’t just for physics and multilinear algebra. In fact, they make sense whenever there is a notion a “map”, a procedure for composing maps (i.e. vertical composition), and a procedure for putting two maps “side-by-side” (horizontal composition). That is, this notation makes sense in any monoidal category. This was worked out in detail by Joyal and Street2 for (planar) monoidal categories, symmetric monoidal categories, and traced symmetric monoidal categories. Similar results exist for lots of flavours of monoidal categories, most of which were gathered up by Selinger3. This work forms the categorical foundation for most of the work coming out of the Quantum Group.
Of course, monoidal categories are just a degenerate example of 2-categories (i.e. those with only a single 0-cell). As such, the language of monoidal categories can generalise in at least one way to higher categories. While the cases of diagrams in 2-categories, and (symmetric/braided/traced/autonomous) monoidal categories are well-understood, very little is known about graphical languages for enriched categories, (generic) closed monoidal categories, and n-categories for n ≥ 3. My interest lies in understanding these better, possibly with the help of automated tools for rewriting on graphs and graph-like objects like simplicial complexes.
1 Roger Penrose. Applications of negative dimensional tensors, Combinatorial Mathematics and its Applications. ed. D. Welsh, Academic Press, New York, 1971, pp. 221-244.
2 André Joyal and Ross Street. The geometry of tensor calculus I, Advances in Math. 88 (MR92d:18011), 1991, pp. 55-112.
3 Peter Selinger. A Survey of Graphical Languages, New Structures in Physics. ed. B. Coecke, Springer, 2011, pp. 275-337. Also available online.
Graphical Structure of Entanglement
One of the most important features of quantum mechanics is the ability for spatially-separated quantum systems to exhibit correlations that can’t be explained by classical physics. This phenomenon is called entanglement. While the behaviour and nature of entangled states involving two systems (or bipartite entanglement) is well understood, entangled states become exponentially more complex are more parties become involved. Obtaining a complete conceptual understanding of general multipartite entangled states is one of the biggest open problems in quantum physics.
We approach this problem by looking at many-body systems not as a single, monolithic state, but as a composition of smaller states. We do this by invoking map-state duality (aka the Choi-Jamiolkowski isomorphism) to think of states as generalised processes, and moreover as algebraic operations. In algebra, binary operations (maps from 2 to 1) are ubiquitous. Thinking of an (N+M)-qubit state as a map from N qubits to M qubits, it becomes clear that (2+1)-qubit states are worthy of special attention.
Dür, Vidal, and Cirac4 showed in 2000 that, up to stochastic local operations, there are only two kinds genuine, tripartite qubit states, GHZ and W.
|GHZ⟩ := |000⟩ + |111⟩ |W⟩ := |100⟩ + |010⟩ + |001⟩
This justifies the use of these states and algebraic primitives in the construction of arbitrary multipartite states. In our paper, we have characterised these states using only their graphical, algebraic properties, and shown that graphs consisting only of the induced GHZ/W-algebras and single-qubit states are universal for quantum state preparation. We can also see many aspects of a compound state’s behaviour by using a graphical calculus (the GHZ/W-calculus) that dictates how its components interact. Our work now focuses on answering these questions:
- How can we best axiomatise the GHZ/W-calculus? Does this axiomatisation have nice computational properties?
- What is the relationship between a graphical state representation and its representation as a tensor network? Can our approach aid in efficient (classical) manipulation of certain classes of highly entangled states?
- How can this algebraic characterisation help us understand the qualitative properties of complex states?
4 W. Dür and G. Vidal and J. I. Cirac. Three qubits can be entangled in two inequivalent ways. Phys. Rev. A, 2000. 62 (062314).
Graph Rewriting and Automation
Graphical languages already provide a powerful tool for reasoning about categorical algebra. However, large and long computations quickly become unwieldy. Just as term algebras from universal algebra can be turned into term rewrite systems, graphical algebras can be turned into graph rewrite systems. Whereas a graphical theory consists of a set of equations or identities, a graph rewrite system consists of a set of directed graph rewrite rules. Naïvely, this simply amounts to directing each of the equations in an equational theory, but this simple change takes an abstract set of identities to a system capable of computation.
In order to automate graph rewriting, we must represent graphs as concrete pieces of data, rather than simply as morphisms in a monoidal category. As such we are concerned not just with digraphs in the usual sense, but what we call open-graphs, where edges may not be connected to a vertex at one or both ends, and can even be connected to themselves. In Open Graphs and Monoidal Theories, Lucas Dixon and I defined the category of open-graphs and described how double-pushout graph rewriting, as defined in e.g. Ehrig et al5, can be applied to open-graphs. We also demonstrate how the category of open-graphs can be used to construct free symmetric and traced monoidal categories containing algebraic structures (as described by a graph rewrite system). Thus we complete the correspondence between algebraic structures in monoidal categories and graph rewrite systems.
On the practical side, we have been working on a tool called Quantomatic, which performs automated and semi-automated graph rewriting on open-graphs. Most of our future work on rewriting consists of:
- improving the flexibility of Quantomatic to implement a wide range of theories and rewrite systems,
- implementing powerful techniques from term and graph rewriting (e.g. Knuth-Bendix completion, conjecture synthesis), and
- integrating Quantomatic with computer algebra systems to explore how (prototype) graphical theories behave with respect to the representations of graphs as linear maps.
5 Ehrig, H., Ehrig, K., Prange, U., and Taentzer, G. Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. EATCS Series. Springer, 2006.
