QuICS seminar

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.”

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.

11:00 am

This talk will address several aspects of tunneling when attempting quantum adiabatic optimization (QAO). First, I derive how the width and height of potential barriers affect the minimal spectral gap of the QAO algorithm. This derivation uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone. Next, 

In high energy and gravitational physics, the S-matrix is the starting point for studying any fundamental physics in asymptotically flat spacetimes. In the context of information theory, the S-matrix can be viewed simply as one of many possible unitary time evolution operators. I'll give some simple examples highlighting the overlap of these views; in particular, I will discuss the interplay of entanglement with relativistic scattering.

The grand canonical ensemble lies at the core of statistical mechanics. A small system thermalizes to this state while exchanging heat and particles with a bath. A quantum system may exchange quantities, or “charges,” represented by operators that fail to commute. Whether such a system thermalizes, and what form the thermal state has, concerns truly quantum thermodynamics.
 

The celebrated Lovasz Local Lemma (LLL) guarantees that locally sparse systems always have solutions, which one can also algorithmically find by the Moser-Tardos RESAMPLE algorithm. Among the major questions that remain open is  that  how far *beyond* Lovasz's condition can we expect that RESAMPLE still performs in polynomial (linear) expected running time? Stating the question correctly is a challenge already. For a solvable and fixed instance RESAMPLE always comes up with a solution, but the catch is that the number of steps may be very large.

Zero-knowledge (ZK) proof systems are fundamental in modern cryptography. Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks.

Commitment schemes are a fundamental primitive in cryptography. Their security (more precisely the computational binding property) is closely tied to the notion of collision-resistance of hash functions. Classical definitions of binding and collision-resistance turn out too be weaker than expected when used in the quantum setting. We present strengthened notions (collapse-binding commitments and collapsing hash functions), explain why they are "better", and show how they be realized under standard assumptions.

Positive energy theorems play a fundamental role in general relativity. Recently, we found a new class of positive energy theorems using information inequalities such as the positivity and monotonicity of the relative entropy.

This and related applications of information theory are providing us new insights into gravitational theory.