Date: Tuesday 31 March – Thursday 2 April 2009

Location: Institute for Mathematical Sciences, Imperial College, London

### EC Network Qubit Applications

#### Scope

Quantum computing represents the prodigiously fertile union of quantum physics with the theory of computation and especially issues of computational complexity. It is known that quantum processes can offer solutions to some information processing tasks that are exponentially more efficient than any known classical methods. Perhaps the most celebrated example is Shor’s 1994 quantum algorithm for integer factorisation.

In recent years there has been a surge of activity in our understanding of quantum computational power and its prospective applicability and limitations. A variety of problems in diverse areas of mathematics, has been identified (so-called BQP-complete problems) that have efficient quantum algorithms and also embody the full power of efficient quantum computation. In quantum many body physics (including study of quantum circuits, of local hamiltonians, and of further formalisms such as measurement based computing) some problems have been shown, surprisingly, to admit efficient classical solution while others (e.g. certain ground state properties of local hamiltonians) are likely to be computationally intractible, having been shown to be so-called QMA-complete.

Quantum entanglement is often regarded as an essential ingredient in these considerations and there has been considerable development in understanding its scaling behaviour in many body systems.

This conference is devoted to recent theoretical developments in these areas and related issues. Invited speakers will be requested to include overview material (in addition to recent research) with the aim of making the essential ideas of these important developments accessible to a broader audience of QIP researchers.

### Organising Committee

**Richard Jozsa**, University of Bristol (Chair)

**Martin Plenio**, Imperial College

**Anthony Sudbery**, University of York

**Vlatko Vedral**, University of Leeds

### Invited Speakers

**Marcus Cramer**, Imperial College

**Area laws for the entanglement entropy
**

**Abstract:**Physical interactions in quantum many-body systems are typically local: Individual constituents interact mainly with their few nearest neighbors. This locality of interactions is inherited by a decay of correlation functions, but also reflected by scaling laws of the en-tanglement entropy of ground states. This entropy of the reduced state of a subregion often merely grows like the boundary area of the subregion, and not like its volume, in sharp contrast to an ex tensive behavior. Such “area laws” for the entanglement entropy and related quantities have received considerable attention in recent years. They emerge in several seemingly unrelated fields, in the context of black hole physics, quantum information science, and quantum many-body physics.

In this talk we review the current status of area laws in these fields. Center stage is taken by rigorous results on lattice models in one and higher spatial dimensions. A significant proportion of the talk is devoted to the connection between the entanglement content of states and the possibility of their efficient numerical simulation.

The talk is based on the recent review “Area laws for the entanglement entropy – a review”, J. Eisert, M. Cramer, M.B. Plenio, arXiv:0808.3773, to be published in Reviews of Modern Physics.

**Daniel Gottesman**, Perimeter Institute, Canada

**Computationally hard problems in spin systems
**

**Abstract:**Consider the problem of finding the ground state energy of a Hamiltonian describing a spin system with local interactions. It turns out that this is an extremely difficult problem, so hard that we believe it cannot be efficiently solved on a quantum computer (i.e., it is not in BQP), nor can a potential answer be checked efficiently on a classical computer (it is not in NP). This problem is in fact complete for a complexity class known as QMA, which is the most natural quantum analogue of NP. I will define QMA and describe the major results and techniques relating to QMA-completeness of local Hamiltonians.

**Miguel Angel Martin-Delgado**, Departamento de Fisica TeoricaI, Universidad Complutense, Madrid

**Topology Induced Anomalous Defect Production by Crossing a Quantum Critical Point
**

**Abstract:**We study the influence of topology on the quench dynamics of a system driven across a quantum critical point. We show how the appearance of certain edge states, which fully characterise the topology of the system, dramatically modifies the process of defect production during the crossing of the critical point. Interestingly enough, the density of defects is no longer described by the Kibble-Zurek scaling, but determined instead by the non-universal topological features of the system. Edge states are shown to be robust against defect production, which highlights their topological nature. arXiv:0811.3843 (Phys. Rev. Lett. to be published).

**Tobias Osborne**, Royal Holloway, London

**The computational complexity of simulating quantum spin systems
**

**Abstract:**In this talk I’ll review the foundational results concerning the computational complexity of simulating quantum spin systems. In particular, I’ll describe what is known about simulating the ground-state properties of 1D spin systems and the dynamical properties of low-dimensional quantum spin spin systems, as well as partial results concerning disordered quantum spin systems. I’ll also describe how the efficiency of popular numerical methods such as the density matrix renormalization group is intertwined with how information propagates through quantum spin systems.

**Pawel Wocjan**, University of Central Florida

**The Power and Limitations of Quantum Computing – a Characterization in terms of PromiseBQP-complete Problems
**

**Abstract:**In this talk, I will give an extensive introduction to the known characterizations of BQP in terms of PromiseBQP-complete problems such as evaluating quadratically signed weight enumerators and the Jones polynomial. PromiseBQP-complete problems are in a precise complexity-theoretic sense the hardest problems that can be solved efficiently on a quantum computer. I will especially focus on the “non-quantum” characterization of the power and limitations of quantum computing in terms of the following simple matrix problem.

Let A be a real symmetric matrix of size N such that the number of non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an efficiently computable function. The problem is to estimate an arbitrary diagonal entry (A^m)_{jj} of the matrix A^m up to an error of epsilon b^m, where b is an a priori given upper bound on the norm of A and m and epsilon are polylogarithmic and inverse polylogarithmic in N, respectively.

### Programme

**Tuesday, 31st March**

08.50 – 09.00 | Opening remarks |

09.00 – 10.00 | Computationally hard problems in spin systemsDaniel Gottesman (Perimeter Institute, Canada) |

10.00 – 10.30 | The computational difficulty of finding MPS ground statesNorbert Schuch (Max-Planck-Institut fur Quantenoptik),Ignacio Cirac (Max-Planck-Institut fur Quantenoptik) and Frank Verstraete (Universitat Wien) |

10.30 – 11.00 | Coffee break |

11.00 – 11.30 | The complexity of poly-gapped local Hamiltonians: ExtendingFernando G.S.L. Brandao (IMS, Imperial College London),Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings Dorit Aharonov (The Hebrew University, Israel), Michael Ben-Or (The Hebrew University, Israel) and Or Sattath (The Hebrew University, Israel) |

11.30 – 12.00 | Interacting electrons, Density Functional Theory, and QuantumNorbert Schuch (Max-Planck-Institut fur Quantenoptik) andMerlin Arthur Frank Verstraete (Fakultat fur Physik, Universitat Wien) |

12.00 – 03.00 | Lunch break |

03.00 – 04.00 | The computational complexity of simulating quantum spin systemsTobias Osborne (Royal Holloway, London) |

04.00 – 04.30 | Simulating time evolution of one dimensional infinite systems withMari-Carmen Banuls and J. Ignacio Cirac (Max-Planck-Institut fur Quantenoptik)Matrix Product States |

04.30 – 05.00 | Coffee break |

05.00 – 05.20 | Bypassing state initialisation in perfect state transfer protocols onC. Di Franco, M. Paternostro and M. S. Kim (Queen’s University Belfast)spin-chains |

05.20 – 05.40 | Simulating the BCS Hamiltonian on a qubus quantum computerKatherine Brown (University of Leeds and Hewlett-Packard Laboratories),Viv Kendon (University of Leeds) and Bill Munro (Hewlett-Packard Laboratories) |

05.40 – 06.00 | Local temperature in quantum thermal statesAlessandro Ferraro (ICFO-Institut de Ciencies Fotoniques, Barcelona) |

**Wednesday, 1st April**

09.00 – 10.00 | Area laws for the entanglement entropyMarcus Cramer (Imperial College) |

10.00 – 10.30 | Quantum algorithm for the Laughlin wave functionA. Riera, J. I. Latorre and V. Pico(Dept. d’Estructura i Constituents de la Materia, Universitat de Barcelona) |

10.30 – 11.00 | Coffee break |

11.00 – 11.30 | Non-commutative polynomial optimization for many-body computationsStefano Pironio, Artur Garcia, Miguel Navascues andAntonio Acin (ICFO-Institut de Ciencies Fotoniques Barcelona) |

11.30 – 12.00 | Upper bounds on fault tolerance thresholds of noisy Clifford-basedS. Virmani (University of Hertfordshire and Imperial College London) andquantum computers M. Plenio (IMS, Imperial College London) |

12.00 – 03.00 | Lunch break |

03.00 – 04.00 | Topology Induced Anomalous Defect Production by Crossing aMiguel Angel Martin-Delgado (Departamento de Fisica TeoricaI,Quantum Critical Point Universidad Complutense Madrid), A. Bermudez (Departamento de Fisica TeoricaI, Universidad Complutense Madrid), D. Patane (MATIS-INFM, Universita di Catania) and L. Amico (MATIS-INFM, Universita di Catania) |

04.00 – 04.30 | Matrix Renormalization Group in the Heisenberg PictureMichael J. Hartmann (Physik Department, TechnischeUniversitaet Muenchen), Javier Prior (IMS, Imperial College London), Stephen R. Clark (Clarendon Laboratory, University of Oxford) and Martin B. Plenio (IMS, Imperial College London) |

04.30 – 05.00 | Coffee break |

05.00 – 05.20 | Clifford group dipoles in quantum computingMichel Planat (Institut FEMTO-ST, CNRS) |

05.20 – 05.40 | Quantum computing beyond entanglementAnimesh Datta (IMS, Imperial College London) |

05.40 – 06.00 | A dissipative scheme to approach the boundary of two-qubitS. Campbell and M. Paternostro (Queen’s University Belfast)entangled mixed states |

07.30 – 09.30 | Conference dinner |

**Thursday, 2nd April**

09.00 – 10.00 | The Power and Limitations of Quantum Computing – a CharacterizationPawel Wocjan (University of Central Florida)in terms of Promise BQP-complete problems |

10.00 – 10.30 | Instantaneous Quantum ComputationMichael J. Bremner (University of Bristol) andDan Shepherd (University of Bristol and GCHQ) |

10.30 – 11.00 | Coffee break |

11.00 – 11.30 | Parallelising computations by exploiting entanglement?Dan Browne (UCL),Janet Anders (UCL), Earl Campbell (UCL), Matty Hoban (UCL), Klearchos Loukopoulos (Oxford) and Simon Perdrix (Oxford and Universite Paris Diderot) |

11.30 – 12.00 | Are random pure states useful for quantum computation?Michael J. Bremner (University of Bristol),Caterina Mora (IQC, Unversity of Waterloo) and Andreas Winter (University of Bristol and NUS Singapore) |

12.00 – 02.00 | Lunch break |

02.00 – 02.30 | Emergence of quantum correlation from non-locality swappingNicolas Brunner (University of Bristol),Paul Skrzypczyk (University of Bristol), Sandu Popescu (University of Bristol and Hewlett-Packard Laboratories) |

02.30 – 03.00 | Transitions in universality for measurement-based quantumDavid Jennings (University of Sydney)computation in a quantum many-body system |

03.00 – 03.20 | A Quiver Gauge Theory and Toric Variety route to Entanglement EntropyPeter Crompton (Lancaster University) |

03.20 – 03.50 | Coffee break |

03.50 – 04.20 | Holonomic quantum computation on subsystemsOgnyan Oreshkov (Grup de F´isica Te`orica, Universitat Aut`onomade Barcelona) |

04.20 – 04.40 | Quantum Secure Multi-party computationKlearchos Loukopoulos and Dan Browne (UCL) |

### Conference Fees

Non Member: | £185.00 |

IMA Member: | £150.00 |

Student: | £80.00 |

The conference dinner will take place at 170 Queen’s Gate on 1st April 2009 at a cost of £45.

*Published*