Close

Date: July 1st, 2020

Speaker: Subhasree Patro

Title: Conditional quantum time lower bound of n^1.5 for the 0-edge-wt-triangle finding problem

Abstract:

The 0-edge-wt-triangle finding problem is defined as follows: Given a graph of n nodes with weighted edges, is there a triangle whose sum of the weights of the edges adds upto zero? It is shown that the 0-edge-wt-triangle finding problem requires n^3 time classically unless 3SUM conjecture, i.e. there is no subquadratic classical algorithm for 3SUM, is false. We extend this result in the quantum setting by showing that 0-edge-wt-triangle finding problem requires n^1.5 time quantumly unless 3SUM has a sublinear quantum time algorithm. The discussion will cover the following: The definition of 3SUM problem, the classical reduction, how the classical reduction cannot be directly ported quantumly, and therefore the use of some quantum techniques to make the reduction work in the quantum setting.

Close

Date: November 25th, 2020

Speaker: Jana Sotáková

Title: Isogenies: the what and the how

Abstract:

I will introduce isogenies (of elliptic curves) - a promising operation that has been used for post-quantum cryptography. The main focus will be on the isogenies used in the CSIDH key exchange scheme and we will discuss how to compute these isogenies in constant time and why would we want this in the first place.

Close

Date: November 11th, 2020

Speaker: Marten Folkertsma

Title: From LOCC to Continuous LOCC: A study of Continuous Classical-Quantum interactions

Abstract:

During my presentation I'll show our study of a subset of quantum channels known as local operations and classical communication (LOCC), which are central to the theory of entanglement. LOCC channels have a natural discrete structure – they can be understood as two parties taking turns to manipulate their local quantum states while exchanging classical messages. We suggest a new form of LOCC –timeless, continuous LOCC (TCLOCC). We first define a timeless LOCC (TLOCC) channel and then use it in combination with the Lindblad formalism to create a timeless continuous version of LOCC. Our formalism uses quantum-classical channels (qc-channels) together with qc-states to implement TCLOCC channels. We use our formalism to derive a very natural continuous version of a protocol by Fortescue and Lo for distilling entanglement between two parties from a three-party W state.

Close

Date: November 4th, 2020

Speaker: Chris Cade

Title: Tick goes the clock

Abstract:

An introduction to the Kitaev-Feynman clock construction and the complexity of finding groundstates of physical systems.

Close

Date: October 21st, 2020

Speaker: Freek Witteveen

Title: An introduction to Lieb-Robinson bounds

Abstract:

Lieb-Robinson bounds show that under time evolution by a geometrically local Hamiltonian the support of local operators grows (approximately) linearly in time. In other words, in a quantum mechanical system local perturbations have a region of influence that grows only with a certain velocity. In the last fifteen years there has been renewed interest, as the LR bounds have found interesting new applications. In this talk I will explain what LR bounds are and how they come about, and then explain two applications: simulation of time evolution on a quantum computer, and the fact that gapped Hamiltonians have ground states with exponentially decaying correlation functions.

Close

Date: July 1st, 2020

Speaker: Alex Grilo

Title: Proof of ignorance

Abstract:

The notion of "proof of knowledge" has been proposed in cryptography back in the 80s by Goldwasser, Micali and Rackoff, and later refined by Bellare and Goldreich. In a proof of knowledge, our goal is to convince other parties of the knowledge of some secret without revealing it explicitly and this definition has been very useful in some constructions in cryptography such as digital signatures schemes. In this talk, I will present "proof of ignorance", a rather recent concept proposed recently by Deshpande and Kalai. Here, our goal is to convince other parties that we don't know a specific secret. In the talk, I will present the definition of proofs of ignorance and discuss some of their constructions and applications.

Close

Date: June 24th, 2020

Speaker: Laurens Ligthart

Title: Entropy inequalities for Gaussian quantum states

Abstract:

In Quantum Information Theory the von Neumann entropy is an important quantity that tells us about the amount of information that is stored in a quantum system. When multiple quantum systems are involved, there are several inequalities that restrict the possible values that the entropies can take. In particular, strong subadditivity (SSA) is of interest in this talk. During the presentation, I will start by discussing the inequalities that govern the von Neumann entropy. After this, we will see that some additional inequalities can be found for specific quantum states, namely for Gaussian states. These states are the thermal and ground states of quadratic Hamiltonians. I will show the proof of *generalised SSA* inequalities for these Gaussian states. I will also briefly motivate why it is useful to investigate Gaussian states specifically by linking the proof to applications in quantum computing and quantum optics.

Close

Date: June 17th, 2020

Speaker: Chris Cade

Title: Exponential quantum-classical separations in graph property-testing

Abstract:

Recently the possibility of obtaining exponential quantum speedups for graph problems was mostly ruled out: recent work has shown that they contain too much symmetry and insufficient structure to allow a quantum algorithm to always outperform a classical one. However, these results hold only for the so- called 'adjacency matrix' input model, and in the alternative 'adjacency array' model it might still be possible to obtain exponential speedups, as recently demonstrated by a particular promise problem based on the well-known 'glued-trees' problem. It is still open whether speedups can also be obtained without such a strong promise on the input. In particular, a question that has remained open for almost a decade is whether there exists an exponential separation in the natural setting of graph property testing, in which the task is to decide if a given graph has some property, or is ‘far-from’ having that property. I'll discuss some on-going joint work with Ashley Montanaro on finding such a separation, and mention an obstacle that we encountered and have so far been unable to overcome. Maybe someone in the audience will spot a solution ;)

Close

Date: May 20th, 2020

Speaker: Jan Czaikowski

Title: The compressed oracle technique

Abstract:

The framework we will be interested in is quantum algorithms with quantum access to a random oracle. By 'quantum access' we mean that the algorithm can query a superposition of inputs and get in return a superposition of outputs of a random function. The compressed oracle technique is a way to lazy sample a random function in a way compatible with this framework---making the oracle efficient. We will discuss in detail an application of this technique. There are some other use cases, which we will mention as well. Finally I will describe an open problem that has been troubling me for a while. As a reference you can take look at our preprint https://arxiv.org/abs/1904.11477.

Close

Date: May 6th, 2020

Speaker: Jonas Helsen

Title: Stability of group representations, a primer.

Abstract:

In this talk I will consider the question of "stability under quasification" of group representations, i.e. what happens when you slightly "perturb" the definition of representations of a group. This idea of stability of quasi-representations has been popping up a lot in various parts of quantum information (device characterization, non-local games, robust self-testing), and I figured it would be fun to give some feeling for what this is all about. I'll go through a nice proof that group representations are in many cases "stable" under perturbations (with respect to the operator norm), which means that given a quasi-representation, there is always a proper representation to be found "nearby" (following an argument by Kazhdan). I'll also give an example of a group where this isn't the case at all. If there is time I'd also like to talk about stability with respect to other norms, such as the normalized Hilbert-Schmidt norm, which is more relevant in quantum info, and also features a much richer theory of quasification.

Close

Date: April 22nd, 2020

Speaker: Joris Kattemölle

Title: Bethe ansatz

Abstract:

One of the most important future applications of quantum computers is finding ground state energies of Hamiltonians. (That is, finding the lowest eigenvalue of sparse Hermitian matrices). Using the so-called Bethe ansatz, it is possible to analytically solve for the ground state energy of a class of non-trivial Hamiltonians. A good understanding of this technique may aid in the design of quantum algorithms that find ground state energies outside of this class. To this end, I will take a specific Hamiltonian (the Heisenberg spin chain), and show how its ground state and ground state energy are found within the Bethe ansatz. I won’t assume a background in physics.

Close

Date: April 8th, 2020

Speaker: Chris Majenz

Title: Simultaneous search-to-decision reduction in the quantum random oracle model

Abstract:

If a classical algorithm can distinguish two oracles that only differ at one particular input, we can use it to find that input with probability equal to the inverse of the number of queries this algorithm makes. The reduction is almost trivial, just output a random query the algorithm makes to its oracle. If, in a distributed scenario, two algorithms succeed at distinguishing, with probability significantly larger than 3/4 each, this reduction allows them to simultaneously find the distinguishing input with good probability by a union bound. For quantum-accessible oracles, the search-to-decision reduction still works by measuring (this is the so-called O2H lemma), but with lower success probability, preventing the union bound argument for simultaneous success in the two-player setting. After describing the above problem, I will present a nice technique from this paper by Broadbent and Lord that shows that simultaneous search success can be proven in a slightly modified setting.

Close

Date: February 26th, 2020

Speaker: Harold Nieuwboer

Title: Norm minimization and scaling algorithms

Abstract:

Given a complex reductive Lie group, a holomorphic representation endowed with a suitable inner product, and a vector in the representation, one might attempt to find a vector of approximately minimal norm inside the orbit. We will look at some trivial and some less trivial examples of this problem, for which special cases are known to have polynomial-time algorithms. We relate this problem to a generalization of matrix/tensor scaling problems via the theory of moment maps, and discuss some more general computational problems phrased in terms of moment polytopes. One specialization of these problems is the (approximate) membership problem for quantum entanglement polytopes. If time permits, we discuss some of the key ingredients for developing algorithms in the general setting.

Close

Date: February 20th, 2020

Speaker: Florian Speelman

Title: Quantum position verification with experimental constraints

Abstract:

The goal of quantum position verification (QPV) is to certify that someone is present at a certain location. This is a task which is impossible to do classically, when an adversary controls a coalition of attackers that work together, even with standard computational assumptions. The question of whether this task is possible using quantum information (combined with assumptions on the resources available to attackers) is not entirely settled, but there are many interesting partial results that show promise. Many protocols for QPV require honest parties to manipulate very small quantum states, and have rigorous security proofs against attackers that share no (or a small amount of) entanglement. For some protocols, for instance those combining quantum and classical information, it is heuristically plausible that they stay secure even against attackers that share large entangled states, while the honest parties only have to measure single qubits. What stops us from implementing such a protocol in practice? Since these protocols require quantum information to travel at the speed of light, sending qubits as photons is the most natural solution. Unfortunately photons often get lost in transmission, and, when using fiber, the photons travel significantly slower than the speed of light in vacuum. Naive solutions to these two problems make most proposed protocols completely insecure. I will survey some of the partial solutions to these problems that I and others have developed, and highlight the open questions (i.e., room for new protocols) that still exist.

Close

Date: January 29th, 2020

Speaker: Farrokh Labib

Title: Szemeredi's theorem

Abstract:

In this meeting, I will discuss a centerpiece result in additive combinatorics: Szemeredi's theorem. The finitary version says the following: let \delta>0 and k a natural number. There exists an N=N(\delta,k) such that if A is a subset of {1,2,...,N} of density \delta, then A will necessarily contain an arithmetic progression of length k. I will give a proof of the case k=3, which is due to Roth (1953). It's a beautiful proof using Fourier analysis and a "density increment" strategy. I will also say something about the case k>3 and why "linear" Fourier analysis does not work. If time permits, I will also say something about constructing XOR games using these ideas for which bounds on classical and quantum bias can be given using tools from Higher-order Fourier analysis.

Close

Date: January 15th, 2020

Speaker: Alvaro Piedrafita

Title: Sequential methods for state discrimination

Abstract:

Imagine that one is given a state preparation machine and promised that it produces one of two possible states. In the standard Bayesian approach to hypothesis testing one normally assumes that an arbitrary but fixed number of copies of the state are given. With such resources, one devises a protocol consisting of measurements, either local or global, fixed or adaptive, and a strategy for analyzing the results that will lead to an average error e(N). Inverting this relation one can easily find an upper bound for the number of copies N(e) that are needed to guarantee, using the bayesian strategy, that the average error does not exceed a value e. Alternatively, if all we want is to minimize the number of copies N(e) necessary for a certain error, we can let go of the requirement that this number is fixed and devise a sequential protocol. These sequential protocols turn out to be better than the bayesian ones at minimizing N(e), dramatically so if the states are pure.

Close

Date: December 18th, 2019

Speaker: Ido Niesen

Title: Quantum Monte Carlo

Abstract:

The subject of the talk is quantum Monte Carlo (QMC), which is one of the main methods used to study quantum mechanical systems on classical computers. I will begin with an explanation of what Monte Carlo is, and why you want to use it. Then I will show how to implement Monte Carlo to study quantum spin systems. Finally, I will discuss limitations of QMC.

Close

Date: November 11th, 2019

Speaker: Joran van Apeldoorn

Title: Quantum algorithms

Abstract:

N/A. Note by Arjan: the talk was about a novel way of explaining the phase estimation algorithm. Rather than introducing the QFT as some magical black box which seems to work well in the derivation of the phase estimation algorithm, a more instructive approach is taken in which it becomes intuitively apparent why such a circuit leads to the desired behavior.

Close

Date: November 6th, 2019

Speaker: Yinan Li

Title: A brief introduction to the noncommutative graph theory

Abstract:

Shannon in 1956 observed the connection between zero-error information theory and graph theory. In 2013, Duan, Severini and Winter extend this connection to the quantum setting, where the zero-error (classical) information is transmitted through quantum channels, and the corresponding graphs are replaced by "noncommutative" graphs. I will review the classical connection by Shannon and introduce the "noncommutative" counterparts, including the independence number, the Shannon capacity, the Lovász theta function and the Haemers bound of noncommutative graphs.

Close

Date: October 23rd, 2019

Speaker: Freek Witteveen

Title: Quantum information in quantum gravity

Abstract:

Over the last decade there has been a strong interest in quantum information from the quantum gravity community, following the realisation that 'holography' raises various questions about the role of information in quantum gravity. I will try to explain some concepts and ideas from quantum gravity with minimal technical detail, and then explain how various concepts from quantum information theory and computation are relevant in this context.

Close

Date: October 9th, 2019

Speaker: Arjan Cornelissen

Title: Introduction to span programs

Abstract:

Span programs provide a framework via which quantum algorithms for oracle problems can be developed. Following the notation in "Approximate span programs" (https://arxiv.org/abs/1507.00432), we will talk about what a span program is and how it can be used to construct quantum algorithms. We will end with the example of determining st-connectivity in an undirected graph.

Close

Date: September 24th, 2019

Speaker: Subhasree Patro

Title: Hardness of computing parity and its relation to recovering the message

Abstract:

The presentation will start with discussing the results of a classic paper Quantum Entanglement and the Communication Complexity of the Inner Product Function (https://arxiv.org/pdf/quant-ph/9708019.pdf). Following that will be a brief introduction to the problem that the people of the "Peanut butter room" and Florian are solving together.

Close

Date: June 19th, 2019

Speaker: Alvaro Piedrafita

Title: Additivity of quantum channels and the search for the dimension-independent holy grail.

Abstract:

Channel additivity has been an open line of research for more than fifteen years, with connections to quantum information theory, non-local games and Computer science. Although many things about the additivity of two channels are now known, much less is known about the additivity of an arbitrary tensor product of channels. I will review the question and the current state of affairs and talk about our conjecture on a reduced version of the additivity question. And hopefully, I will have time to tell you about the two approaches that might work and their challenges.

Close

Date: May 22nd, 2019

Speaker: Bas Dirkse

Title: Statistics for entanglement witness experiments

Abstract:

An entanglement witness is an observable used to experimentally certify the entanglement of quantum states. The entanglement is certified if the expectation value of the observable with respect to the quantum state violates some threshold. In practical experiments however, the expectation value is not directly accessible and must be estimated from a finite amount of measurement data. Typical experiments report the estimated expectation value and the observed standard deviation of the witness, based on N single-shot measurements. This is statistically problematic. Furthermore, measurement devices are typically not characterized, leading to possible false positive conclusions. We derived a rigorous method for analysing the data of finite single-shot entanglement witness experiments with minimal assumptions. This method is based on the statistical framework of hypothesis testing. During this talk, I will discuss the following topics: 1) What are entanglement witnesses? 2) What is the problem with current statistics and how can we solve this? 3) Main results: How to construct an experiment and analyse its data? 4) Application and motivation: Witnessing genuine multipartite entanglement in a 3-node NV-centre experiment.

Close

Date: May 8th, 2019

Speaker: Yfke Dulek

Title: Introduction to quantum multiparty computation

Abstract:

In multiparty computation, some number of parties try to jointly perform a computation, to which they each hold part of the input. Of course, they don't really trust each other, so they want to make sure that nobody is trying to sabotage the computation, or to learn secret information about the other players' inputs. Wednesday's talk will be a work-in-progress talk about the quantum variant of this problem, where I will present the current state-of-the-art of *two*-party quantum computation, touch upon the difficulties of extending that result to more than two parties, and hint at how to overcome those difficulties.

Close

Date: April 3rd, 2019

Speaker: Arjan Cornelissen

Title: Triangle Finding problem

Abstract:

First, we will briefly look at the different approaches that have been taken to construct algorithms that solve the problem. Then, we will zoom in on one particular aspect of the problem, namely a result by Boladis and Iraids relating it to the Graph Collision problem. Finally, we will have a look at one possible strategy to prove a new lower bound on the Triangle Finding problem.

Close

Date: March 27th, 2019

Speaker: Subhasree Patro

Title: Conditional quantum lower bound for the Edit-Distance problem - A work in progress

Abstract:

I will be discussing the Edit-Distance problem and how the conditional classical lower bound is obtained. Having done that I will discuss how we use this classical reduction in a quantum setting to get a conditional quantum lower bound for the same Edit distance problem.

Close

Date: February 27th, 2019

Speaker: Chris Majenz

Title: proof systems, proofs of knowledge and the Fiat Shamir transformation

Abstract:

N/A

Close

Date: February 13th, 2019

Speaker: Mathys Rennela

Title: Quantum algorithms from Jacobi polynomials

Abstract:

This talk will be about the study of Jacobi polynomials and in particular Chebyshev polynomials, from an operator-theoretic perspective, in light of the characterisation of quantum query algorithms as completely bounded forms (see https://ir.cwi.nl/pub/28509). I will show that Chebyshev polynomials correspond to completely bounded forms. To provide some context to this study, I will also discuss the use of Chebyshev polynomials in the approximation of symmetric Boolean functions.

Close

Date: January 30th, 2019

Speaker: Tom Bannink

Title: Non-local games

Abstract:

This talk will be about non-local games. In particular I will discuss a connection between communication complexity and non-local games, and discuss an open problem. I will then discuss one of our results [ https://arxiv.org/abs/1811.11068 ] and discuss the proof.

Close

Date: December 10th, 2018

Speaker: Alex Grilo

Title: Quantum PCP conjecture

Abstract:

I will start by presenting/reminding the definition of QMA/Local Hamiltonian problem, sketching the QMA-completeness of LH and then presenting the variants of the Quantum PCP conjecture.

Close

Date: November 28th, 2018

Speaker: Farrokh Labib

Title: Constructing transitive quantum channels using Cayley graphs

Abstract:

I will explain how to construct transitive quantum channels (I will recall what transitive means) using representation theory of finite groups (and the Cayley graph of that group together with a generating set). This construction is due to Harrow.

Close

Date: November 14th, 2018

Speaker: András Gilyén

Title: Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension

Abstract:

We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices. Inspired by recent work of Tang, assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix and sample from the solution to the problem Ax=b using fast sampling techniques. We implement the pseudo-inverse by finding an approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, the approach can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem, our result suggests that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.

Close

Date: October 31st, 2018

Speaker: Sander Gribling

Title: The return of the SDP: A (new) characterization of quantum query complexity

Abstract:

Recently Srinivasan, Jop, and Carlos Palazuelos gave a new characterization of the quantum query complexity of a Boolean function: it is equal to the completely bounded degree of that function. (This characterization even holds when the error-probability is set to zero!) In this talk I will sketch their result (including definitions) and show how their result provides a new semidefinite programming (SDP) characterization of quantum query complexity. I will then discuss some corollaries. No prior knowledge of SDPs is required. I will assume that everyone knows about the existence of the polynomial method and the general adversary method (see for example Section 9 of Ronald's lecture notes).

Close

Date: October 17th, 2018

Speaker: Jan Czaikowski

Title: Sequential measurement of a single state and almost "on state" commuting projectors

Abstract:

N/A