Heilbronn Quantum Algorithms meeting
Wednesday 27th November 2013 to Thursday 28th November 2013
10:00 to 11:00  Registration & Morning Coffee  
11:00 to 11:05  Welcome from John Toland (INI Director)  INI 1  
11:05 to 11:10  Welcome from Robert Allison (Heilbronn Institute)  INI 1  
11:15 to 12:15 
Boson sampling in the light of sampling complexity: A review
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 nonsymmetric 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.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 14:30 
Inverting wellconditioned matrices in Quantum Logspace
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. 
INI 1  
14:30 to 15:00  Afternoon Tea  
15:00 to 16:00 
T Vidick (Massachusetts Institute of Technology) A polynomialtime algorithm for the ground state of 1D gapped local Hamiltonians
Coauthors: 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 polynomialtime algorithm for finding ground states of gapped onedimensional Hamiltonians: it outputs an (inversepolynomial) 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. 
INI 1  
16:00 to 17:00 
Complexity classification of local Hamiltonian problems
Coauthor: Toby Cubitt (University of Cambridge)
The calculation of groundstate energies of physical systems can be formalised as the klocal 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 condensedmatter physics. In this talk I will discuss work which characterises the complexity of this problem for all 2local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NPcomplete; polynomialtime equivalent to the Ising model with transverse magnetic fields; or QMAcomplete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1local terms; for example, we prove for the first time QMAcompleteness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2local interactions: for any constant k, all klocal qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomialtime equivalent to the Ising model with transverse magnetic fields; or QMAcomplete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems. 
INI 1  
17:00 to 18:00  Welcome Wine Reception  
19:00 to 22:00  Conference Dinner at Cambridge Union Society hosted by Cambridge Dining Company 
10:00 to 11:00 
A variational eigenvalue solver on a quantum processor
Coauthors: Alberto Peruzzo (University of Sydney), Peter Shadbolt (University of Bristol), ManHong Yung (Tsinghua University), XiaoQi Zhou (University of Bristol), Peter Love (Haverford College), Alan AspuruGuzik (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 smallscale 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 HeH+, 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. 
INI 1  
11:00 to 11:30  Morning Coffee  
11:30 to 12:30 
Probing Quantum Speedup in DWave Two
Coauthors: 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 DWave devices closely follows the statistics of simulated quantum annealing, whereas it is clearly different from semiclassical 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 DWave 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 DWave devices. 
INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 14:30  Graph Isomorphism: Quantum Ideas  INI 1  
14:30 to 15:00  Afternoon Tea  
15:00 to 16:00 
A constructive algorithm for the commutative Quantum Lovász Local Lemma
Coauthors: Martin Schwarz (University of Vienna), Frank Verstraete (University of Vienna)
The recently proven Quantum Lovász Local Lemma generalises the wellknown 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 manybody 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 nontrivial polytime example of a new type of "dissipative quantum algorithm". 
INI 1 