Talks

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.

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)

The Hamiltonian of traditionally adopted detector models features out of diagonal elements between the vacuum and the one particle states of the field to be detected. We argue that reasonably good detectors, when written in terms of fundamental fields, have a more trivial response on the vacuum. In particular, the model configuration ``detector in its ground state + vacuum of the field\' generally corresponds to a stable bound state of the underlying theory (e.g. the hydrogen atom in a suitable QED with electrons and protons) and therefore should be also an eigenstate of the model Hamiltonian. As a concrete example, we study a consistent ``fundamental\' toy field theory where a stable particle can capture a light quantum and form a quasi-stable state. To such stable particle correspond eigenstates of the full theory, as is shown explicitly by using a dressed particle formalism at first order in perturbation theory. We then write the corresponding Hamiltonian for a model detector (at rest) where the stable particle and the quasi-stable configurations correspond to the two internal levels, ``ground\' and ``excited\', of the detector. The accelerated version of this Hamiltonian is inevitably model dependent emph{i.e.} it will generally depend on how the stable particle/detector is forced along the accelerated trajectory. However, in its most basic version, the accelerated detector doesn\'t see Unruh radiation.

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. 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.

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.

One of the main strengths of the ERG is that it admits nonperturbative approximation schemes which preserve renormalizability. I will introduce a particularly powerful scheme, the derivative expansion.

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).

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.

Consider the quantum predictions for EPR-type measurements on two systems with Hilbert space of dimension at least 3 in any maximally entangled state. I show that the only possible hidden variables model of these probabilities that satisfies both Shimony\'s and Jarrett\'s condition of parameter independence (or `locality\') and Jones and Clifton\'s condition of conditional parameter independence (or `constrained locality\') is trivial, i.e. given by the quantum probabilities themselves. I shall attempt to discuss also the meaning of the conditions and of this result.

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.