QuICS seminar

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.

We prove a general relation between adaptive and nonadaptive strategies in the quantum setting, i.e., between strategies where the adversary can or cannot adaptively base its action on some auxiliary quantum side information. Our relation holds in a very general setting, and is applicable as long as we can control the bit-size of the side information, or, more generally, its "information content".

We prove that constant-depth quantum circuits are more powerful than their classical counterparts. We describe an explicit (i.e., non-oracular) computational problem which can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates. In contrast, we prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the problem with high probability must have depth logarithmic in the input size. This is joint work with Sergey Bravyi and Robert Koenig (arXiv:1704.00690).