QuICS seminar

I will present a study of continuum limits of Matrix Product States (MPS). We show that an MPS has a continuum limit if and only if its transfer matrix is an infinitely divisible channel. To prove this result, we first need to define the irreducible form of an MPS, which is a generalization of the canonical form. This result also implies that the continuum limit of an MPS can generally not be described by a continuous MPS -- I will mention a possible generalization of the latter class.

Our first result concerns an old question in quantum information theory: how much quantum communication is required to approximately convert one pure bipartite entangled state into another? We give a simple and efficiently computable bound in terms of the earth mover or Wasserstein distance. We show that the communication cost of converting between two pure states is bounded (up to a constant factor) by the Absolute Earth Mover distance between the distributions given by the negative logarithm of the Schmidt coefficients of each state.

Port-based teleportation (PBT) is a variant of the well-known task of quantum teleportation where the receiver Bob, instead of having to apply a non-trivial correction unitary, merely has to pick up the right quantum system at a “port” specified by the classical message he received from Alice. While much more resource-demanding than standard teleportation, PBT has applications to instantaneous non-local computation and can be used to attack position-based quantum cryptography.

The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian and the quantum circuit that encodes its description. In the quest to better approximate time-evolution, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits for generalized measurement.

We introduce a three-player nonlocal game, such that the optimal winning probability of 1 can only be achieved in the limit of strategies using arbitrarily high dimensional entangled states.  This game is explicit, and has very few classical questions and answers.  Our game is based on the coherent state exchange game introduced in arXiv:0804.4118, which in turns is based on embezzlement of entanglement due to van Dam and Hayden.  We discuss the main ideas behind each of these ingredients, and how they can be put together to obtain a quantitative tradeoff in the winni

The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps. Approximate degree has wide-ranging applications in theoretical computer science. As one example, the approximate degree of a function is a lower bound on its quantum query complexity. Despite its importance, the approximate degree of many basic functions has resisted characterization. 

In this talk, I will describe recent advances in proving both upper and lower bounds on the approximate degree of specific functions. 

We show that there are two distinct aspects of a general quantum circuit that can make it hard to efficiently simulate with a classical computer. The first aspect, which has been well-studied, is that it can be hard to efficiently estimate the probability associated with a particular measurement outcome. However, we show that this aspect alone does not determine whether a quantum circuit can be efficiently simulated.

The prospect of interactive quantum communication leads to stunning advantages over its classical counterpart: some specifically crafted problems have provable exponential quantum advantage. However, the underlying protocols assume perfect quantum communication as well as local processing. What about more restricted models of quantum computation and communication which are closer to what is achievable in the near future? Can we still obtain substantial quantum advantages with such?
 

Joint work with: Joran van Apeldoorn, Sander Gribling and Ronald de Wolf

We develop an efficient and fast quantum computational scheme to determine the equilibrium Green's functions at finite temperature without requiring any adiabatic state preparation steps. The approach works for generic models that obey the eigenstate thermalization hypothesis and one can show the short-time behavior of the Green's functions is produced exactly by this method. We also describe cooling schemes that could be invoked to reach lower temperatures than what can be reached by simple interaction-strength ramping.