The photon's mobility makes optical quantum systems ideally suited for delegated quantum computations. Here I will briefly review various photonic experiments covering secure quantum cloud computing and the verification of quantum computers via interacting proofs. I will also show results of resource-efficient random walk computations that rely on passive optical networks. Finally I will show that such passive networks raise significant challenges for any interaction and thus the verification of the performance.

We will survey the power of interactive proof systems with multiple entangled provers and a classical verifier.

Three topics will be discussed in more detail. These include the NP-hardness of exactly determining the game value of a nonlocal game, the breakthrough of Ito and Vidick on multi-prover interactive proofs for NEXP sound against entangled provers, and some recent observations on the binary constraint system games.

The theme of this talk will be how shared entanglement between provers can break certain interactive proofs and what we can do to suppress and to make use of this effect.

The goal of secure program obfuscation is to make a program "unintelligible" while preserving its functionality. For decades, program obfuscation for general programs has remained an art, with all public general-purpose obfuscation methods known to be broken.

In this talk, we will describe new developments that for the first time provide a mathematical approach to the problem of general-purpose program obfuscation, where extracting secrets from the obfuscated program requires solving mathematical problems that we believe to be intractable. We will also discuss the implications of these developments.

Nonlocal games allow us to control and test the behavior of untrusted quantum devices. Recently Yaoyun Shi and I provided the first proof of a protocol for robust exponential randomness expansion with untrusted devices. In this talk I will discuss the techniques that enabled our proof, including the use of nonlocal games to simulate partially trusted measurements.

The Martians built an amazingly fast computer and they run it to answer the great question of life, the universe and everything. They claim that the answer is 42. Will they be able to convince us that this is the right answer, assuming that we do not have sufficient computational power to run the computation ourselves, and that we do not trust Martians?

The problem of verifiable computation delegation is a central problem in cryptography. We show a curious connection between that problem and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in relation to multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light.

We prove that the class of languages that have polynomial-time multi-prover interactive proofs that are sound against no-signaling strategies, is exactly EXP. We use this to give a 1-round delegation protocol for every language in EXP.

Joint work with Yael Tauman Kalai and Ron Rothblum.

Monogamy relations and de Finetti theorems have broad application, including to quantum key distribution, Hamiltonian complexity, analyzing non-local games and even classical optimization algorithms. One limitation of most work in this space is that the number of systems needs to grow like a power of the dimension of each system. Brandao, Christandl and Yard achieved a major breakthrough by making use of information theory to reduce the number of systems needed to scale only like the logarithm of the local dimension. I will describe a further improvement of their theorem which has a simpler proof and generalizes to multipartite states and non-signaling distributions. Next I'll describe several applications to non-local games, quantum complexity theory, and other topics. Finally, I'll explain how conjectured improvements of these results could resolve several major open problems in classical and quantum complexity theory.

Direct products arise in many complexity settings, often for the purpose of hardness amplification.

One particular setting is that of two-prover games, whose direct product is called parallel repetition.

I will begin with an introductory survey of direct products and parallel repetition in the classical setting, and then move to talk about extensions to the quantum setting. Namely, where the game is classical but the provers share an entangled quantum state.

I will describe a recent result (joint with David Steurer and Thomas Vidick) that gives an upper bound to the entangled value of the n-fold repeated game that decreases exponentially with n. This result holds for a broad class of games called "projection games."

The proof extends a recent "analytical / linear algebraic" proof for classical parallel repetition of projection games. An interesting new ingredient is a quantum analog to Holenstein's correlated sampling lemma, generalizing recent results on universal embezzlement to an approximate scenario: Two isolated parties, given classical descriptions of bipartite states x,y respectively such that x \approx y , are able to locally generate a joint entangled state z \approx x \approx y using an initial entangled state that is independent of their inputs.

In this talk, we will present the current state of the art in the implementations of two-party quantum cryptographic protocols such as key distribution and coin flipping. We will discuss the challenges that appear in the effort to satisfy assumptions present in theoretical security proofs using practical systems, and the solutions that have been adopted in the last years. These have allowed implementations offering strong security guarantees and have opened the way to new theoretical investigations motivated by the need to accommodate for experimental imperfections.