# Workshop Programme

## for period 27 - 28 November 2013

### Heilbronn Quantum Algorithms meeting

27 - 28 November 2013

Timetable

Wednesday 27 November | ||||

10:00-11:00 | Registration & Morning Coffee | |||

11:00-11:05 | Welcome from John Toland (INI Director) | |||

11:05-11:10 | Welcome from Robert Allison (Heilbronn Institute) | |||

11:15-12:15 | Eisert, J (Freie Universität Berlin) |
|||

Boson sampling in the light of sampling complexity: A review | Sem 1 | |||

Boson sampling is a classically computationally hard problem that can - in principle - be efficiently solved with quantum linear optical networks. Recently this has lead to an experimental race to implement such devices. This talk will provide a review on the state of affairs concerning the possibility of certifying boson sampling devices. We discuss in detail several settings: 1. The use of symmetric and non-symmetric algorithms for distinguishing the boson sampling distribution from a particular other distribution. 2. Classical simulation of boson sampling in the presence of errors. 3. The impossibility of an efficient classical certification. We present some new results on estimating first and second moments of photon number distributions. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

13:30-14:30 | Ta-Shma, A (Tel Aviv University) |
|||

Inverting well-conditioned matrices in Quantum Logspace | Sem 1 | |||

We show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. To the best of our knowledge the best classical algorithm for the problem requires Omega(log^2n) space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with additive accuracy, and how to approximate the SVD decomposition of a matrix whose singular values are well separated. The technique builds on ideas from several previous works, including simulating a Hamiltonian in small quantum space, treating a Hermitian matrix as a Hamiltonian and running the quantum phase estimation procedure on it (building on Harrow, Hassidim, and Lloyd) and making small space probabilistic (and quantum) computation consistent through the use of offline randomness and the shift and truncate method of Saks and Zhou. |
||||

14:30-15:00 | Afternoon Tea | |||

15:00-16:00 | Vidick, T (Massachusetts Institute of Technology) |
|||

A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians | Sem 1 | |||

Co-authors: Zeph Landau (UC Berkeley), Umesh Vazirani (UC Berkeley) Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved. Joint work with Zeph Landau and Umesh Vazirani. |
||||

16:00-17:00 | Montanaro, A (University of Bristol) |
|||

Complexity classification of local Hamiltonian problems | Sem 1 | |||

Co-author: Toby Cubitt (University of Cambridge) The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this talk I will discuss work which characterises the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems. |
||||

17:00-18:00 | Welcome Wine Reception | |||

19:00-22:00 | Conference Dinner at Cambridge Union Society hosted by Cambridge Dining Company |

Thursday 28 November | ||||

10:00-11:00 | McClean, J (Harvard University) |
|||

A variational eigenvalue solver on a quantum processor | Sem 1 | |||

Co-authors: Alberto Peruzzo (University of Sydney), Peter Shadbolt (University of Bristol), Man-Hong Yung (Tsinghua University), Xiao-Qi Zhou (University of Bristol), Peter Love (Haverford College), Alan Aspuru-Guzik (Harvard University), Jeremy O'Brien (University of Bristol) Quantum computers promise to efficiently solve important problems that are intractable on a conventional computer. For quantum systems, where the dimension of the problem space grows exponentially, finding the eigenvalues of certain operators is one such intractable problem and remains a fundamental challenge. The quantum phase estimation algorithm can efficiently find the eigenvalue of a given eigenvector but requires fully coherent evolution. We present an alternative approach that greatly reduces the requirements for coherent evolution and we combine this method with a new approach to state preparation based on ans\"atze and classical optimization. We have implemented the algorithm by combining a small-scale photonic quantum processor with a conventional computer. We experimentally demonstrate the feasibility of this approach with an example from quantum chemistry: calculating the ground state molecular energy for He-H+, to within chemical accuracy. The proposed appro ach, by drastically reducing the coherence time requirements, enhances the potential of the quantum resources available today and in the near future. |
||||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Ronnow, T (ETH Zürich) |
|||

Probing Quantum Speedup in D-Wave Two | Sem 1 | |||

Co-authors: Sergio Boixo (Google Inc.), Sergei V. Isakov (Google Inc.), Zhihui Wang (ISI, University of California), Joshua Job (ISI, University of California), Daniel Lidar (ISI, University of California), John Martinis (Department of Physics, University of California), Matthias Troyer (ETH Zurich) We are at a point where the first quantum devices are becoming available both in laboratories and commercially. While universal quantum computing still its infancy, analogue devices, such cold atoms experiments and quantum annealers, constitute the first step towards using quantum hardware for solving computational problems. In this talk, we show that D-Wave devices closely follows the statistics of simulated quantum annealing, whereas it is clearly different from semi-classical spin dynamics and classical thermal annealing. The theoretical study by Santoro [Science, Santoro et al., 295 (5564), 2427], where it was shown that quantum annealing outperforms classical thermal annealing, suggests that the D-Wave machines could have advantages over to classical hardware. We discuss how one probe for such advantages correctly, and we present preliminary results on the computational capabilities of the D-Wave devices. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

13:30-14:30 | Severini, S (University College London) |
|||

Graph Isomorphism: Quantum Ideas | Sem 1 | |||

14:30-15:00 | Afternoon Tea | |||

15:00-16:00 | Cubitt, T (University of Cambridge) |
|||

A constructive algorithm for the commutative Quantum Lovász Local Lemma | Sem 1 | |||

Co-authors: Martin Schwarz (University of Vienna), Frank Verstraete (University of Vienna) The recently proven Quantum Lovász Local Lemma generalises the well-known Lovász Local Lemma. It states that, if a collection of subspace constraints are "weakly dependent", there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the quantum kQSAT satisfiability problem are necessarily satisfiable, or that many-body systems with "not too many" interactions are never frustrated. However, the QLLL only asserts existence; it says nothing about how to find the quantum state that satisfies the constraints. Inspired by Moser's breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the sought quantum state. As well as proving a constructive commutative QLLL, this provides a non-trivial poly-time example of a new type of "dissipative quantum algorithm". |