IMA Conference on Quantum Computing and Complexity of Quantum Simulation


Date: Tuesday 31 March – Thursday 2 April 2009
Location: Institute for Mathematical Sciences, Imperial College, London

EC Network Qubit Applications


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.


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

Leave a Reply

Your email address will not be published. Required fields are marked *