Overview of QuSoft junior meetings
Date:  Speaker:  Title:  
July 1st, 2020  Subhasree Patro  Conditional quantum time lower bound of n^1.5 for the 0edgewttriangle finding problem  Abstract 
November 25th, 2020  Jana Sotáková  Isogenies: the what and the how  Abstract 
November 11th, 2020  Marten Folkertsma  From LOCC to Continuous LOCC: A study of Continuous ClassicalQuantum interactions  Abstract 
November 4th, 2020  Chris Cade  Tick goes the clock  Abstract 
October 21st, 2020  Freek Witteveen  An introduction to LiebRobinson bounds  Abstract 
July 1st, 2020  Alex Grilo  Proof of ignorance  Abstract 
June 24th, 2020  Laurens Ligthart  Entropy inequalities for Gaussian quantum states  Abstract 
June 17th, 2020  Chris Cade  Exponential quantumclassical separations in graph propertytesting  Abstract 
May 20th, 2020  Jan Czaikowski  The compressed oracle technique  Abstract 
May 6th, 2020  Jonas Helsen  Stability of group representations, a primer.  Abstract 
April 22nd, 2020  Joris Kattemölle  Bethe ansatz  Abstract 
April 8th, 2020  Chris Majenz  Simultaneous searchtodecision reduction in the quantum random oracle model  Abstract 
February 26th, 2020  Harold Nieuwboer  Norm minimization and scaling algorithms  Abstract 
February 20th, 2020  Florian Speelman  Quantum position verification with experimental constraints  Abstract 
January 29th, 2020  Farrokh Labib  Szemeredi's theorem  Abstract 
January 15th, 2020  Alvaro Piedrafita  Sequential methods for state discrimination  Abstract 
December 18th, 2019  Ido Niesen  Quantum Monte Carlo  Abstract 
November 11th, 2019  Joran van Apeldoorn  Quantum algorithms  Abstract 
November 6th, 2019  Yinan Li  A brief introduction to the noncommutative graph theory  Abstract 
October 23rd, 2019  Freek Witteveen  Quantum information in quantum gravity  Abstract 
October 9th, 2019  Arjan Cornelissen  Introduction to span programs  Abstract 
September 24th, 2019  Subhasree Patro  Hardness of computing parity and its relation to recovering the message  Abstract 
June 19th, 2019  Alvaro Piedrafita  Additivity of quantum channels and the search for the dimensionindependent holy grail.  Abstract 
May 22nd, 2019  Bas Dirkse  Statistics for entanglement witness experiments  Abstract 
May 8th, 2019  Yfke Dulek  Introduction to quantum multiparty computation  Abstract 
April 3rd, 2019  Arjan Cornelissen  Triangle Finding problem  Abstract 
March 27th, 2019  Subhasree Patro  Conditional quantum lower bound for the EditDistance problem  A work in progress  Abstract 
February 27th, 2019  Chris Majenz  proof systems, proofs of knowledge and the Fiat Shamir transformation  Abstract 
February 13th, 2019  Mathys Rennela  Quantum algorithms from Jacobi polynomials  Abstract 
January 30th, 2019  Tom Bannink  Nonlocal games  Abstract 
December 10th, 2018  Alex Grilo  Quantum PCP conjecture  Abstract 
November 28th, 2018  Farrokh Labib  Constructing transitive quantum channels using Cayley graphs  Abstract 
November 14th, 2018  András Gilyén  Quantuminspired lowrank stochastic regression with logarithmic dependence on the dimension  Abstract 
October 31st, 2018  Sander Gribling  The return of the SDP: A (new) characterization of quantum query complexity  Abstract 
October 17th, 2018  Jan Czaikowski  Sequential measurement of a single state and almost "on state" commuting projectors  Abstract 
Date: July 1st, 2020
Speaker: Subhasree Patro
Title: Conditional quantum time lower bound of n^1.5 for the 0edgewttriangle finding problem
Abstract:
The 0edgewttriangle 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 0edgewttriangle 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 0edgewttriangle 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.
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 postquantum 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.
Date: November 11th, 2020
Speaker: Marten Folkertsma
Title: From LOCC to Continuous LOCC: A study of Continuous ClassicalQuantum 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 quantumclassical channels (qcchannels) together with qcstates 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 threeparty W state.
Date: November 4th, 2020
Speaker: Chris Cade
Title: Tick goes the clock
Abstract:
An introduction to the KitaevFeynman clock construction and the complexity of finding groundstates of physical systems.
Date: October 21st, 2020
Speaker: Freek Witteveen
Title: An introduction to LiebRobinson bounds
Abstract:
LiebRobinson 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.
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.
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.
Date: June 17th, 2020
Speaker: Chris Cade
Title: Exponential quantumclassical separations in graph propertytesting
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 wellknown 'gluedtrees' 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 ‘farfrom’ having that property. I'll discuss some ongoing 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 ;)
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 frameworkmaking 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.
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 quasirepresentations has been popping up a lot in various parts of quantum information (device characterization, nonlocal games, robust selftesting), 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 quasirepresentation, 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 HilbertSchmidt norm, which is more relevant in quantum info, and also features a much richer theory of quasification.
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 socalled Bethe ansatz, it is possible to analytically solve for the ground state energy of a class of nontrivial 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.
Date: April 8th, 2020
Speaker: Chris Majenz
Title: Simultaneous searchtodecision 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 quantumaccessible oracles, the searchtodecision reduction still works by measuring (this is the socalled O2H lemma), but with lower success probability, preventing the union bound argument for simultaneous success in the twoplayer 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.
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 polynomialtime 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.
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.
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 Higherorder Fourier analysis.
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.
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.
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.
Date: November 6th, 2019
Speaker: Yinan Li
Title: A brief introduction to the noncommutative graph theory
Abstract:
Shannon in 1956 observed the connection between zeroerror information theory and graph theory. In 2013, Duan, Severini and Winter extend this connection to the quantum setting, where the zeroerror (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.
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.
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 stconnectivity in an undirected graph.
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/quantph/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.
Date: June 19th, 2019
Speaker: Alvaro Piedrafita
Title: Additivity of quantum channels and the search for the dimensionindependent holy grail.
Abstract:
Channel additivity has been an open line of research for more than fifteen years, with connections to quantum information theory, nonlocal 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.
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 singleshot 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 singleshot 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 3node NVcentre experiment.
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 workinprogress talk about the quantum variant of this problem, where I will present the current stateoftheart 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.
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.
Date: March 27th, 2019
Speaker: Subhasree Patro
Title: Conditional quantum lower bound for the EditDistance problem  A work in progress
Abstract:
I will be discussing the EditDistance 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.
Date: February 27th, 2019
Speaker: Chris Majenz
Title: proof systems, proofs of knowledge and the Fiat Shamir transformation
Abstract:
N/A
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 operatortheoretic 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.
Date: January 30th, 2019
Speaker: Tom Bannink
Title: Nonlocal games
Abstract:
This talk will be about nonlocal games. In particular I will discuss a connection between communication complexity and nonlocal games, and discuss an open problem. I will then discuss one of our results [ https://arxiv.org/abs/1811.11068 ] and discuss the proof.
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 QMAcompleteness of LH and then presenting the variants of the Quantum PCP conjecture.
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.
Date: November 14th, 2018
Speaker: András Gilyén
Title: Quantuminspired lowrank stochastic regression with logarithmic dependence on the dimension
Abstract:
We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for lowrank matrices. Inspired by recent work of Tang, assuming lengthsquare sampling access to input data, we implement the pseudoinverse of a lowrank matrix and sample from the solution to the problem Ax=b using fast sampling techniques. We implement the pseudoinverse 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 lowrank quantum algorithms can be effectively "dequantised" into classical lengthsquare sampling algorithms.
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 errorprobability 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).
Date: October 17th, 2018
Speaker: Jan Czaikowski
Title: Sequential measurement of a single state and almost "on state" commuting projectors
Abstract:
N/A
aencjuniorlist   


About aencjuniorlist  
To see the collection of prior postings to the list, visit the aencjuniorlist Archives. (The current archive is only available to the list members.) 

Using aencjuniorlist  
To post a message to all the list members, send email to
aencjuniorlist@cwi.nl.
You can subscribe to the list, or change your existing subscription, in the sections below. 

Subscribing to aencjuniorlist  
Subscribe to aencjuniorlist by filling out the following form. You will be sent email requesting confirmation, to prevent others from gratuitously subscribing you. This is a private list, which means that the list of members is not available to nonmembers.


aencjuniorlist Subscribers  

version 2.1.29 