# Quantum Information Theory Seminar

## Previous

#### Raul Santos Sanhueza. 4 March 2020.

Title
Building new phases of matter from the bottom up.
Abstract
In this talk, I will discuss a method to build and search for new fermionic phases of matter by coupling simple building blocks. Starting from an anisotropic lattice, the role of electron hopping, Coulomb interactions and symmetries will be assessed in general. I will show the strengths of the method by constructing a precursor of a topological state and discuss the challenges to implement it.

#### Angelo Lucia. 13 February 2020.

Title
Tensor network representations and entanglement geometry
Abstract
Tensor networks (TN) have become one of the most successful tool to study, numerically and analytically, many-body quantum states. Part of the reason for their success lies in the fact that TN are able to succinctly describe complex entanglement structures in terms of local operations acting on a graph of maximally entangled states. The dimension of these entangled states, known as the bond dimension, is usually the dominant parameter in the computational cost of contracting such networks. Since this representation is not unique, can we optimise it to reduce the bond dimension? And what advantages can we obtain by replacing the maximally mixed states by other multi-partite entangled states, such as GHZ states?

In this talk, I will show how the theory of multi-partite entanglement and some tools from algebraic geometry can be used to answer these questions. In particular, I will show how in some cases it is possible to reduce the bond dimension by replacing a fixed TN state with a superposition of a moderate number of TN states with strictly smaller bond dimension (whose contractions can be computed in parallel independently from each other). With this technique, we can construct a new representation of the Resonating Valence Bond (RVB) state, as well as showing that networks of k-levels GHZ states describe the same states as TN with bond dimension roughly equal to k (up to a small correction).

Based on arXiv:1809.08185. Joint work with Matthias Christandl, Péter Vrana and Albert H. Werner.

#### Kfir Dolev. 27 November 2019.

Title
Constraining the doability of relativistic quantum tasks
Abstract
Relativistic quantum tasks are useful for describing the propagation and processing of information in spacetime. We show that the doability of a task is dependent on only a small fraction of the causal details of the spacetime on which it is defined. Our results generalize earlier no go theorems on position based quantum cryptography and serve as a consistency check for holography.

#### Markus Frembs (Imperial College London). 15 August 2019.

Title
Contextuality as a Resource for Measurement-Based Quantum Computation
Abstract
Contextuality has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource: if local measurements on a multi-qubit state can be used to evaluate nonlinear boolean functions with only linear control processing, then this computation constitutes a proof of contextuality—the possible local measurement outcomes cannot all be pre-assigned. In this talk I will give some background to this connection between contextuality and computational complexity and prove a generalisation to the case when the local measured systems are qudits. I will also discuss some important differences between the qubit and qudit case from a resource-theoretic perspective.

#### Emilio Onorati (UCL). 4 July 2019.

Title
Mixing properties of distribution on the unitary group

#### Aram Harrow (MIT). 13 June 2019.

Title
Random quantum circuits in different geometries
Abstract
Random unitary dynamics are a toy model for chaotic quantum dynamics and also have applications to quantum information theory and computing. A basic question about them is whether their first few moments approximately match those of the Haar measure; if so, we call them approximate unitary designs. It is natural to conjecture that the time needed for quantum dynamics to yield an approximate design is given by the time for a signal to propagate from one side of the system to the other. I will describe the proof of this claim in one or more dimensions in Euclidean geometry and will give examples where this claim fails in more general geometries, including the Schwarzschild metric. I will briefly discuss two applications: (1) the proposal by Google and other groups to use random quantum circuits for “quantum supremacy,” meaning a quantum circuit performing a task that is hard for a classical computer to simulate; and (2) the question of how quickly information is scrambled in black holes.

This is based on the following three papers.
arXiv:1208.0692 (with Fernando Brandao and Michal Horodeck)
arXiv:1809.06957 (with Saeed Mehraban)
arXiv:1906.02219 (with Linghang Kong, Zi-Wen Liu, Saeed Mehraban, and Peter Shor)

#### Deniz Stiegemann (Leibniz Universität Hannover). 23 May 2019.

Title
Thompson Field Theory
Abstract
We introduce Thompson field theory, a class of toy models of conformal field theory in which Thompson’s group T takes the role of a discrete analogue of the chiral conformal group. T and the related group F are discrete transformations of dyadic partitions of the circle and the unit interval, respectively. When vectors or tensors are associated with partitions, one can construct a direct limit Hilbert space, here called the semicontinuous limit, and F and T have unitary representations on this space. We give an abstract description of these representations following the work of Jones. We also show that T can be thought of as acting on the boundary of an equal-time Poincaré disk in AdS3. This defines a representation of T on the Hilbert space that contains all tree-like holographic states, as introduced by Pastawski, Yoshida, Harlow, and Preskill. It also establishes a bulk-boundary correspondence through Imbert’s isomorphism between T and Penner’s Ptolemy group. We further propose definitions of field operators and correlation functions for the discrete theory. Finally, we sketch new developments like particle creation and annihilation, as well as black holes and possible connections with topological quantum field theory.

#### Andrew Childs (University of Maryland). 11 April 2019.

Title
Quantum algorithms and lower bounds for convex optimization
Abstract
While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n-dimensional convex body using $\tilde O(n)$ queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires $\tilde\Omega(\sqrt{n})$ evaluation queries and $\Omega(\sqrt{n})$ membership queries.

#### Johannes Bausch (Cambridge). 14 March 2019.

Title:
Chasing Quantum Codes: how to Outsmart a Brute-Force Approach
Abstract:
In the iid noise model, error correction crucially depends on the existence of good codes. In this context, “good” relates to an as-large-as-possible coherent information under the action of various noisy channels, such as depolarizing, dephrasure, or BB84. Each of these channels has a noise parameter p, which allows us to ask which codes are optimal for a particular choice of p. Existing upper bounds on the quantum capacity of the above channels are not known to be tight, and in certain noise regimes there is a large gap between upper and lower bounds on the quantum capacity.

Our goal is to find optimal codes under a family of states called “graph states”. Such states often feature large symmetries, which together with a Pauli channel’s properties (e.g. covariance) can be exploited to vastly reduce the numerical complexity of exhaustive search. We present
a few prelimiary results.

This is a work-in-progress project jointly with Felix Leditzky (University of Colorado Boulder/JILA).

#### Cambyze Rouzé (TU München). 7 March 2019.

Title:
Functional inequalities and strong converses in quantum information theory
Abstract:
Quantum channel capacities, defined as the asymptotic optimal rates of classical, quantum or private information that can be reliably sent per channel use, are generally characterized by expressions involving entropic quantities. Contrary to their classical analogue, these expressions usually involve a quantity optimized over an unbounded number of uses of the channel. This prevents the existence of a general algorithm to compute them, even in the simplest case of the depolarizing channel. Hence, estimating these expressions remains one of the key challenges of quantum information theory. A bound on a capacity is said to satisfy a strong converse property if the error made by trying to reach a rate above it converges to one in the limit of a large number $n$ of uses of the channel at hand.

An important class of channels is that of quantum Markov semigroups (QMS). These models are most relevant to capture the time-dependent, memoryless interaction between a system and its environment. In this talk, we will discuss the interplay between QMS theory and the strong converse properties of various quantum information theoretical tasks. First, we will derive time-dependent strong converse bounds for the capacities of a large class of quantum Markov semigroups. These bounds are expressed in terms of the mixing time of an associated classical Markov process. In the second half of the talk, we will show a new promising technique to derive finite $n$ strong converse bounds, mainly focusing on the framework of binary hypothesis testing. Here, the technique relies on a functional inequality satisfied by the generalized quantum depolarizing semigroup, namely the tensorization of its reverse hypercontractivity.

This talk is based on an article (arXiv:1804.10100) that is joint work with Salman Beigi and Nilanjana Datta, as well as on a paper in preparation with Ivan Bardet, Marius Junge, Nicholas Laracuente and Daniel Stilck França.

#### Joel Klassen (TU Delft). 1 March 2019.

Title:
When is a Hamiltonian Stoquastic?
Abstract:
Finding the lowest energy of a Hamiltonian is a hard problem in general, however for many physical systems quantum Monte Carlo methods can often be effectively applied to determine the lowest energy of a Hamiltonian, and it is commonly understood that the absence of a sign problem is a requisite condition for the success of these methods. The notion of stoquastic Hamiltonians was introduced with the aim of categorising those Hamiltonians which do not suffer from the sign problem. Indeed, the study of stoquastic Hamiltonians in the context of computational complexity theory has lent support to the notion that stoquastic Hamiltonians are somehow “simpler” than generic Hamiltonians. Importantly, the property of being stoquastic makes itself manifest only in a particular local basis choice. In this work we explore how hard it is, from a computational complexity perspective, to find such a choice of basis.

#### Sathyawageeswar Subramanian (Cambridge). 28 February 2019.

Title:
Applications of the LCU technique of implementing a linear combination of unitaries on a quantum computer
Abstract:
The recent LCU method for implementing a linear combination of unitary operators has evolved into an important algorithmic primitive for quantum algorithms. The method was first developed in the context of Hamiltonian simulation (in various works of Berry, Childs, Kothari and collaborators), but has since then been used in many other applications, including an improved quantum linear systems algorithm. In this talk, I will first introduce the method itself, and then illustrate an analysis using Chebyshev polynomial approximations to show how to implement any function of a Hermitian matrix specified by an oracle, given a Taylor series for the function. I will also illustrate an application to quantum chemistry, to implement a hybrid quantum-classical algorithm for the variational coupled cluster method, which will require fixed point oblivious amplitude amplification, another recent algorithmic primitive.

#### Mithuna Yoganathan (Cambridge). 14 February 2019.

Title:
Quantum advantage of Clifford Magic circuits
Abstract:
This talk is about the computational power of a class of circuits called Clifford Magic (CM). CM is a restricted class of circuits and therefore is unlikely to be universal. In fact the main motivation for studying CM is that these circuits closely resemble a class known to be classically simulatable. Despite this, we showed that CM itself can’t be classically simulated (under plausible conjectures), and therefore performs a truly quantum computation.

To prove this result we needed to show a generalisation of the Gottesman-Knill theorem. This result may be of independent interest because it gives an algorithm for compressing the number of qubits in a quantum computation. It does this by taking any quantum computation and identifying some parts that are easy to do classically, leaving behind a smaller computation to be performed quantumly.

#### Stephen Piddock (Bristol). 13 December 2018.

Title:
Oracle complexity classes and local measurements on physical Hamiltonians
Abstract:
This talk will focus on the problem of predicting the outcome of a local measurement of a low energy state of a local Hamiltonian. This problem was introduced by Ambainis as APX-SIM and was shown to be complete for the class P^QMA[log], which you can think of as being slightly harder than QMA, the quantum analogue of NP. The proof involves a very complicated Hamiltonian construction: one of our main contributions is to show how to generalise these results to more physically realistic Hamiltonians such as the qubit Heisenberg interaction on a square lattice, using the simulation techniques of [Cubitt, Montanaro, P]. Along the way, we simplify the original proofs of Ambainis dramatically, allowing us to prove analogous results for classical and stoquastic Hamiltonians, giving a full classification of the problem for 2-local Hamiltonians, and we are able to prove some new complexity class equalities.
Based on joint work with Sevag Gharibian and Justin Yirka.

#### Tamara Köhler (UCL). 29 November 2018.

Title:
Complete Toy Models of Holographic Duality
Abstract:
Tensor networks have previously been used to construct holographic quantum error correcting codes (HQECC), which are toy models of the AdS/CFT correspondence. HQECC have been able to exhibit many of the interesting features of the duality, such as complementary recovery and redundant encoding. However, in previous HQECC the boundary Hamiltonian which results from mapping a local bulk Hamiltonian to the boundary is a non-local Hamiltonian, with global terms that act over the entire boundary. In this work, we combine HQECC with recently developed Hamiltonian simulation theory to construct a bulk-boundary mapping in which local bulk Hamiltonians map to local boundary Hamiltonians. This allows us to construct a toy model of a complete holographic duality between models, not just states and observables. This mapping of local Hamiltonians extends the toy models to encompass the relationship between bulk and boundary energy scales, and in particular the mapping between bulk and boundary time dynamics. We discuss what insight this gives into toy models of black hole formation.

#### Mario Berta (Imperial). 22 November 2018.

Title:
Semidefinite programming hierarchies for quantum error correction

Abstract:
We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[M(X⊗Y)], maximized with respect to joint semidefinite constraints on (X,Y). Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans. Inf. Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo’s asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brandão & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from O(dk/2) to poly(d,k), where d denotes local dimension and k the number of copies.

#### Nadish de Silva (UCL). 2 October 2018.

Title:
A seminar on Bravyi-Gosset-König’s “Quantum advantage with shallow circuits”
Abstract:
Rigorously separating classical and quantum computational power is an important problem in quantum computer science. Known results tend to rely on the use of oracles or unproven complexity-theoretic assumptions. In contrast, BGK prove an unconditional separation between the power of constant-depth classical and quantum circuits to solve a 2D variant of the Bernstein-Vazirani problem. Their proof relies on establishing the difficulty of classically simulating the nonlocal correlations arising from entangled states and indicates further scope for exploiting insights of quantum foundations towards rigorously establishing quantum advantage. We will walk through the technical details of their proof in a friendly and interactive way. (The preprint is available at: https://arxiv.org/abs/1704.00690.)

#### Daniel Gottesman (Perimeter Institute). 20 September 2018.

Title:
Stabilizer codes for prime power qudits.

#### Hongxiang Chen (UCL). 31 August 2018.

Title:
Continuous-variable Quantum Neural Networks
Abstract:
In this talk we will introduce basic elements for continuous-variable quantum computation, and how the quantum neural networks in continuous-variable computation could naturally connected with classical neural networks. We will base our discussion on the paper Continuous-variable quantum neural networks (https://arxiv.org/abs/1806.06871).

#### Sevag Gharibian (Universität Paderborn). 26 July 2018.

Title:
On efficiently solvable cases of Quantum k-SAT
Abstract:
The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k>=3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. In this talk, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “matching” or “dimer covering”; this is an NP problem whose decision variant is trivial, but whose search complexity remains open.

Our results fall into three directions, all of which relate to the “matching” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “matching”.

#### James Watson (UCL). 10 July 2018.

Title:
The Computational Complexity of the Ground State Energy Density Problem
Abstract:
The field of Hamiltonian Complexity is concerned with the Local Hamiltonian problem, which asks for the ground state energy of a Hamiltonian to some precision. Physically the problem tells can tell us about the existence of Hamiltonians which have metastable states. The Local Hamiltonian problem has been shown to be QMA_{EXP}-complete for a 1D, translationally invariant, nearest neighbour Hamiltonian (Gottesman & Irani), and a complete classification has been realised for 2-qubit Hamiltonians (Cubitt & Montanaro).

We extend the field of Hamiltonian Complexity to the thermodynamic limit by introducing the `Ground State Energy Density Problem’ (GSED Problem). This asks whether the nth digit of the ground state energy density of an infinite lattice is 0 or 1 (thus in effect asking for the ground state energy density to some specified precision). We show that for a translationally invariant, nearest neighbour Hamiltonian on a 2D infinite lattice, the GSED problem is QMA_{EXP}-complete.

#### Danial Dervovic (UCL). 3 July 2018.

Title:
Szegedy Quantum Walks Demystified
Abstract:
In 2004, Szegedy formulated a new quantisation scheme for random walks on graphs. This scheme has since become one of the leading formulations of quantum walks in the literature, due to its favourable spectral properties and algorithmic applications.
This seminar talk will provide a short introduction to the Szegedy walk and its applications.

#### Ramis Movassagh (IBM). 15 June 2018.

Title:
Supercritical Entanglement in Exactly Solvable Models: Counter-Examples to the Area Law for Quantum Matter
Abstract:
In recent years, there has been a surge of activities in proposing exactly solvable quantum spin chains with the surprisingly high amount of ground state entanglement entropies–beyond what one expects from critical systems described by conformal field theories (i.e., super-logarithmic violations of the area law). We will introduce entanglement and discuss these models. We prove that the ground state entanglement entropy is \sqrt(n) and in some cases even extensive (i.e., ~n). These models have rich connections with combinatorics, random walks, and universality of Brownian excursions. Lastly, we develop techniques that enable proving the gap of these models. As a consequence, the gap scaling rules out the possibility of these models having a relativistic conformal field theory description.

#### Thomas Frerix (TU Münich). 2 March 2018.

Title:
Proximal Backpropagation
Abstract:
I will introduce proximal backpropagation (ProxProp) as a neural network training algorithm that takes implicit instead of explicit gradient steps. This algorithm is motivated by the step size limitation of explicit gradient descent, which poses an impediment for optimization. The starting point for the analysis is a general point of view on the backpropagation algorithm as sequential gradient steps on a quadratic penalty functional. I will then give some intuition about proximal optimization and show how such implicit gradient steps don’t suffer from the above mentioned step size restriction. Altogether, this motivates taking proximal instead of gradient steps for neural network training. I will state the main convergence result, as this conveys an interesting intuition of how the algorithm acts layerwise on the model. Finally, I will conclude with some practical remarks concerning an efficient implementation of ProxProp with modern deep learning frameworks and I will show numerical results.

#### Harmony Zhan (University of Waterloo). 22 February 2018.

Title:
Mixing in Discrete-Time Quantum Walks
Abstract:
Discrete-time quantum walks are building blocks for quantum algorithms. There are some parameters of a quantum walk that affect the performance of a quantum algorithm, such as the (time-averaged) limiting distribution and the mixing time. In this talk, I will discuss properties of the average mixing matrix, and bounds on mixing times for certain graphs.

#### Nina Kamcev (ETH Zürich). 20 October 2017.

Title:
Zero forcing in random and pseudorandom graphs
Abstract:
A subset S of initially infected vertices of a graph G is called forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a tool in quantum information theory.

The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our bounds on the forcing number of pseudorandom graphs and related problems. The results are joint work with Thomas Kalinowski and Benny Sudakov.

#### Martino Lupini (Caltech). 19 September 2017.

Title:
Borel quantum chromatic numbers
Abstract:
I will present the ongoing study of the Borel quantum chromatic number of (not necessarily finite) graphs whose set of vertices is endowed with a standard Borel structure. This is defined, similarly as for finite graphs, in terms of quantum strategies for the graph-coloring game, where the strategy is demanded to depend in a Borel fashion from the given vertex. This is joint work with Luke Juusola.

#### Michael Bremner (UT Sydney). 8 August 2017.

Title:
Beyond classical computing via low-depth quantum circuit sampling
Abstract:
Over the last few years there has been significant attention devoted to devising experimental demonstrations of quantum computational supremacy: namely a quantum computer solving a computational task that goes beyond what a classical machine could achieve. This is, in part, driven by the hope that a clear demonstration of post-classical computation can be performed with a device that is intermediate between the small quantum circuits that can currently be built and a full-scale quantum computer. The theoretical challenge that this poses is twofold: firstly we must identify the physically least expensive quantum computations that are classically unachievable; and we must also determine if this advantage can be maintained in the presence of physical noise. In this talk I will review the IQP and Boson Sampling approaches to quantum computational supremacy, how they can be generalized to other intermediate quantum computing models, and to what extent the experimental resource requirements of these problems can be reduced.

See:
– M. J. Bremner, A. Montanaro, and D. J. Shepherd “Achieving quantum supremacy with sparse and noisy commuting quantum computations”, Quantum 1, 8 (2017). arXiv:1610.01808
– M. J. Bremner, A. Montanaro, and D. J. Shepherd “Average-case complexity versus approximate simulation of commuting quantum computations”, Phys. Rev. Lett. 117, 080501 (2016). arXiv:1504.07999
– S. Boixo, et al, “Characterizing quantum supremacy in near-term devices”, arXiv:1608.00263
– A. Lund, M. J. Bremner, T. C. Ralph “Quantum sampling problems, BosonSampling and quantum supremacy” npj Quantum Information 3, Article number: 15 (2017). arXiv:1702.03061

#### Antonios Varvitsiotis (NTU and CQT, Singapore). 12 July 2017.

Title:
Quantum correlations: Conic formulations, dimension bounds, and matrix factorizations
Abstract:
In this talk we focus on the sets of two-party correlations generated from a Bell scenario involving two spatially separated systems with respect to various physical models. In recent worked we showed that the sets of quantum and classical correlations can be expressed as projections of affine sections of the completely positive semidefinite (cpsd) cone and the completely positive cone, respectively. This correspondence allows to set up a dictionary between properties of quantum correlations and features the cpsd cone and additionally, between dimensionality questions concerning quantum correlations and algebraic properties of a new notion of matrix rank. My goal in this talk is to give a brief summary of the most important results obtained in both directions.

#### Giuseppe Carleo (ETH Zürich). 15 June 2017.

Title:
Machine Learning Many-Body Quantum Physics.
Abstract:
Machine-learning-based approaches are being increasingly adopted in a wide variety of domains, and very recently their effectiveness has been demonstrated
also for many-body physics [1-4]. In this seminar I will present recent applications to quantum physics.

First, I will discuss how a systematic machine learning of the many-body wave-function can be realized. This goal has been achieved in [1], introducing a variational representation of quantum states based on artificial neural networks. In conjunction with Monte Carlo schemes, this representation can be used to study both ground-state and unitary dynamics, with controlled accuracy. Moreover, I will show how a similar representation can be used to perform efficient Quantum State Tomography on highly-entangled states [5], previously inaccessible to state-of-the art tomographic approaches.

I will then briefly discuss, recent developments in quantum information theory, concerning the high representational power of neural-network quantum states.

[1] Carleo, and Troyer — Science 355, 602 (2017).
[2] Carrasquilla, and Melko — Nat. Physics doi:10.1038/nphys4035 (2017)
[3] Wang — Phys. Rev. B 94, 195105 (2016)
[4] van Nieuwenburg, Liu, and Huber — Nat. Physics doi:10.1038/nphys4037 (2017)
[5] Torlai, Mazzola, Carrasquilla, Troyer, Melko, and Carleo — arXiv:1703.05334 (2017)

#### Ansis Rosmanis (CQT Singapore). 7 June 2017.

Title:
Fidelity of quantum strategies with applications to quantum cryptography.
Abstract:
We introduce a definition of the fidelity function for multi-round quantum strategies, which we call the strategy fidelity, which is a generalization of the fidelity function for quantum states. We provide many interesting properties of the strategy fidelity including a Fuchs-van de Graaf relationship with the strategy norm. We also provide a very general monotinicity result for both the strategy fidelity and strategy norm under the actions of strategy-to-strategy linear maps. We illustrate an operational interpretation of the strategy fidelity in the spirit of Uhlmann’s Theorem and discuss its application to the security analysis of quantum protocols for interactive cryptographic tasks such as bit-commitment and oblivious string transfer. Our analysis is very general in the sense that the actions of the protocol need not be fully specified, which is in stark contrast to most other security proofs. Lastly, we provide a semidefinite programming formulation of the strategy fidelity. This is joint work with Gus Gutoski and Jamie Sikora.

#### Leonard Wossnig (ETH Zürich). 28 April 2017.

Title:
A quantum linear system algorithm for dense matrices
Abstract:
Solving linear systems of equations is a frequently encountered problem in machine learning and optimisation, with applications ranging from Gaussian process regression to the training of neural networks. In the seminal work of Harrow, Hassidim and Lloyd [Physical Review Letters, 103 (15), 150502], a quantum algorithm for linear systems with an exponential increase in efficiency over classical algorithms has been presented. Their algorithm achieves an exponential speedup over classical algorithms when the linear system is sparse and well conditioned.

In this work, we present a quantum algorithm that achieves a quadratic speedup over the HHL algorithm even if the linear system is dense. Therefore we extend the range of linear systems that are efficiently solvable using quantum computation to a larger class of problems.
Our algorithm builds upon a quantum singular value estimation (QSVE) procedure which was introduced by Kerenidis and Prakash [I. Kerenidis and A. Prakash (2016), arXiv:1603.08675]. It extends their results by providing a trick to convert an arbitrary QSVE procedure into a linear system solver. We further prove the correctness of our scheme and the indicated lower bound on the runtime.

#### Elizabeth Crosson (CalTech). 11 April 2017

Title:
Ground state isoperimetric inequalities and the energy spectrum of local Hamiltonians
Abstract:
By generalizing a standard framework from the analysis of Markov chains to arbitrary (non-stoquastic) Hamiltonians we are naturally led to see that the spectral gap can always be upper bounded by a geometric quantity that depends only on the ground state probability distribution and the range of the terms in the Hamiltonian, but not on any other details of the interaction couplings. This means that for a given probability distribution the inequality can constrain the spectral gap (and other low-lying eigenvalues) of any local Hamiltonian with this distribution as its ground state probability distribution in some basis. These constraints reveal that some probability distributions will take exponential time to be precisely reached by a purely adiabatic evolution, while also showing the necessity of removing bottlenecks in the ground state geometry to improve the performance within the adiabatic paradigm.

#### Māris Ozols (Cambridge). 29 March 2017

Title:
How to permute quantum systems continuously
Abstract:
Can you write down a Hamiltonian that exchanges two quantum systems continuously? How about three? I will explain how this can be done using basic group theory and representation theory together with Fourier transform. The same tools apply more generally and let you make *any* finite group continuous by embedding it in a certain subgroup of the unitary group! My talk is based on arXiv:1508.00860.