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 systems Daniel Gottesman (Perimeter Institute, Canada) |
| 10.00 – 10.30 | The computational difficulty of finding MPS ground states Norbert 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: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings Fernando G.S.L. Brandao (IMS, Imperial College London), 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 Quantum Merlin Arthur Norbert Schuch (Max-Planck-Institut fur Quantenoptik) and Frank Verstraete (Fakultat fur Physik, Universitat Wien) |
| 12.00 – 03.00 | Lunch break |
| 03.00 – 04.00 | The computational complexity of simulating quantum spin systems Tobias Osborne (Royal Holloway, London) |
| 04.00 – 04.30 | Simulating time evolution of one dimensional infinite systems with Matrix Product States Mari-Carmen Banuls and J. Ignacio Cirac (Max-Planck-Institut fur Quantenoptik) |
| 04.30 – 05.00 | Coffee break |
| 05.00 – 05.20 | Bypassing state initialisation in perfect state transfer protocols on spin-chains C. Di Franco, M. Paternostro and M. S. Kim (Queen’s University Belfast) |
| 05.20 – 05.40 | Simulating the BCS Hamiltonian on a qubus quantum computer Katherine 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 states Alessandro Ferraro (ICFO-Institut de Ciencies Fotoniques, Barcelona) |
Wednesday, 1st April
| 09.00 – 10.00 | Area laws for the entanglement entropy Marcus Cramer (Imperial College) |
| 10.00 – 10.30 | Quantum algorithm for the Laughlin wave function A. 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 computations Stefano Pironio, Artur Garcia, Miguel Navascues and Antonio Acin (ICFO-Institut de Ciencies Fotoniques Barcelona) |
| 11.30 – 12.00 | Upper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers S. Virmani (University of Hertfordshire and Imperial College London) and M. Plenio (IMS, Imperial College London) |
| 12.00 – 03.00 | Lunch break |
| 03.00 – 04.00 | Topology Induced Anomalous Defect Production by Crossing a Quantum Critical Point Miguel Angel Martin-Delgado (Departamento de Fisica TeoricaI, 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 Picture Michael J. Hartmann (Physik Department, Technische Universitaet 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 computing Michel Planat (Institut FEMTO-ST, CNRS) |
| 05.20 – 05.40 | Quantum computing beyond entanglement Animesh Datta (IMS, Imperial College London) |
| 05.40 – 06.00 | A dissipative scheme to approach the boundary of two-qubit entangled mixed states S. Campbell and M. Paternostro (Queen’s University Belfast) |
| 07.30 – 09.30 | Conference dinner |
Thursday, 2nd April
| 09.00 – 10.00 | The Power and Limitations of Quantum Computing – a Characterization in terms of Promise BQP-complete problems Pawel Wocjan (University of Central Florida) |
| 10.00 – 10.30 | Instantaneous Quantum Computation Michael J. Bremner (University of Bristol) and Dan 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 swapping Nicolas 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 quantum computation in a quantum many-body system David Jennings (University of Sydney) |
| 03.00 – 03.20 | A Quiver Gauge Theory and Toric Variety route to Entanglement Entropy Peter Crompton (Lancaster University) |
| 03.20 – 03.50 | Coffee break |
| 03.50 – 04.20 | Holonomic quantum computation on subsystems Ognyan Oreshkov (Grup de F´isica Te`orica, Universitat Aut`onoma de Barcelona) |
| 04.20 – 04.40 | Quantum Secure Multi-party computation Klearchos 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.
