Quantum Information and Graph Theory: Emerging Connections - 2008

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

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.

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.

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.

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)

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.

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

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.

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.

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

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.