N/A

Lunch served at 12:00

Given an unknown discrete distribution, classical algorithms for estimating its Shannon and Renyi entropies have been intensively developed and tight bounds of queries to the distribution have been established. However, the quantum query complexity of entropy estimation is still open in general. We give quantum algorithms that give quadratic speed-up for Shannon entropy estimation compared to its classical lower bound and also speed-up for \alpha-Renyi entropy estimation when 1/2<\alpha<2.

Shannon's entropy power inequality gives a lower bound on the entropy power of the sum of two independent random variables in terms of the individual entropy powers. This statement and some of its consequences are information-theoretic counterparts of certain geometric inequalities. In this talk, I will give an overview of analogous statements for bosonic quantum systems. The first concerns a certain convolution operation between two quantum states: here two independent bosonic modes combine at a beamsplitter.

When we encode information into physical systems that are small enough to be governed by the laws of quantum mechanics, a large part of our intuition about how information behaves goes out the window -- for example, information can no longer be copied perfectly. This has far-reaching implications in several areas of computer science, including cryptography, where it changes the rules of the game for both honest participants and potential attackers. In this talk, I will present an overview of quantum cryptography and how my own work fits in the picture.

Quantum algorithms appear to outperform classical algorithms on various tasks. They generally come in two flavors: those like Shor's factoring algorithm, which appears to give an exponential speedup over classical computation but only for a structured problem (and not for NP-complete problems), and those like Grover's algorithm, which gives only a polynomial (quadratic) speedup but works even for unstructured problems.
 

I'll talk about two questions related to quantum speedups over classical computation. First, if we had a universal quantum computer, which computational problems should we solve on it? I'll argue that the task of simulating physical systems is one of the best choices for this and discuss the state of the art for quantum algorithms solving this problem.

Lunch served at 12:00
 

In a typical post-quantum scenario, the adversary has a quantum computer at their disposal, but only gets classical access to the cryptographic scheme. Recent research has shown that, if adversaries also get quantum access (e.g., the ability to encrypt or authenticate in superposition) then they can easily break many constructions currently believed to be “quantum-secure.”

Lunch served at 12:00
 

I will discuss classical algorithms for computing low-energy states of quantum impurity models.  Such models describe a bath of free fermions coupled to a small interacting subsystem called an impurity. Hamiltonians of this form were famously studied by Anderson, Kondo, Wilson and others in 1960s. Impurity models also play the central role in modern material simulation algorithms based on the DMFT method. Quite recently it was suggested that DMFT simulation algorithms may benefit from quantum computers.