Monday, February 24th, 2014

11:30 am12:00 pm

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.

2:00 pm3:00 pm

Some local Hamiltonians have a "history" state as its ground state. It is a superposition over snapshots of a quantum computation. The terms in this superposition need to be locally connected (or checkable). First, we will review how this can be done with clock constructions – domain-wall (unary), pulse (tuned to a single excitation), and geometric (data moving on a lattice). Second, we will discuss the various ways of preferring proper clock states – in frustration-free ways, or using frustrated gadgets. Finally, we will look at composite clocks (q-3-SAT) as well as new ideas beyond unary clocks, asking whether they could possibly lead to better eigenvalue/promise gaps.

3:30 pm4:15 pm

An interesting current open problem in quantum complexity theory is the quantum PCP conjecture. In analogy with the PCP theorem, the conjecture states that it is QMA-hard to tell whether a quantum constraint satisfaction problem (aka a local quantum Hamiltonian) is satisfiable or far from satisfiable, with a constant fraction of the constraints being violated in any assignment.

In this talk I will discuss limitations for quantum PCPs due to one of the most distinguishing features of quantum entanglement: its monogamous character. The monogamy of entanglement is the principle that the more entangled a system is with another one, the less entangled it can be with anything else. I will show how a quantitative understanding of entanglement monogamy leads both to limitations on the parameters that a potential quantum analogue of the PCP theorem might have, and to potential approaches to proving such an analogue (for instance by attempting to quantize the main steps of Dinur’s proof of the PCP theorem).

The talk will be mostly based on joint work with Aram Harrow (arXiv:1310.0017).

Tuesday, February 25th, 2014

9:00 am10:00 am

he Sliding Scale Conjecture in PCP states that NP has multi-prover protocols with a constant number of provers and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers.

The Sliding Scale Conjecture is one of the oldest open problems in classical multi-prover protocols, and it implies hardness of approximation up to polynomial factors for problems like Max-CSP (with polynomial-sized alphabet), Directed-Sparsest-Cut and Directed-Multi-Cut.

In this work we prove:

  1. The Sliding Scale Conjecture follows from a construction of a low degree test whose soundness error is exponentially small in the randomness of the verifier.
  2. A parallel repetition theorem for low degree testing that decreases the error probability of a low degree test exponentially.
  3. Applying the parallel repetition theorem on an existing low degree test, we get the low degree test with the smallest error known to date.

The missing piece for proving the Sliding Scale Conjecture is a derandomization of the parallel repetition theorem. This seems plausible given the algebraic structure of the low degree testing problem, which was utilized for derandomization in the past.

10:30 am11:30 am

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.

1:45 pm2:45 pm

When (re)analysing the security of classical cryptographic protocols in a quantum setting, one finds that many classical proof techniques break down. Proofs of knowledge are a typical example of this: Their proofs usually involve rewinding, which is challenging in the quantum setting due to the no-cloning theorem. We present known solutions for proving the quantum security of proofs of knowledge, with a particular focus on what is not solved.

3:15 pm4:15 pm
Speaker: Amit Sahai, UCLA

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.

4:30 pm5:00 pm

We consider the usual problem of circuit obfuscation: given some classical circuit C, can we prepare an obfuscated version which allows a user to simulate black-box access to C without learning anything else? Classically this problem is known to be impossible, even for relatively weak formulations. But it may still be possible to produce a quantum state which obfuscates C, even in the very strong sense that any measurement of that state can be simulated (up to computational indistinguishability) using black-box access to C.

I will describe a protocol for quantum obfuscation of classical circuits, whose security is open. Time permitting I will discuss some of the technical issues that come up in the analysis.

Wednesday, February 26th, 2014

9:45 am10:30 am

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.

11:30 am12:15 pm

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.

2:00 pm3:00 pm

The understanding of the low energy physics of 2D strongly correlated quantum systems is one of the main challenges in condensed matter physics. One of the reasons which makes such systems so rich (and difficult) is the presence of topological entanglement. In this talk, I will give an introduction to the field, pointing out some of the key ideas and main open problems.

3:30 pm4:30 pm

We discuss some basic concepts from operator algebra and Banach space theory which are useful for classical and quantum games.
Starting from Tsirelson's interpretation of Grothendieck's inequality, we try illustrate the connection between certain tensor norms and how they relate to games and strategies, and Bell inequalitites.

Thursday, February 27th, 2014

10:00 am10:45 am

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.

11:15 am12:00 pm

The powerful correlations known as quantum entanglement are responsible for many of the most interesting effects in quantum information and complexity theory, but remarkable as the correlations are, they are very tightly constrained. Most importantly, entanglement is monogamous: more entanglement between Alice and Bob means less between Alice and Eve. I will give an overview of some of the more useful mathematical manifestations of this law, from inequalities for entanglement measures, to the non-existence of symmetric extensions.

Laws of nature, unlike the laws of nations, cannot be broken. They can, however, be evaded. While entanglement cannot be created without some type of quantum mechanical interaction, it can sometimes be stolen in such a way that no one would ever notice. The phenomenon, known as "embezzlement" is alternately vexing and helpful, but aspiring quantum complexity theorists should be aware of it either way!

2:00 pm3:00 pm

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.

3:30 pm4:00 pm

In a two player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value of a game G is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The n-fold parallel repetition Gn of G consists of n instances of G where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win Gn if they win each instance of G.

We show that the entangled value of Gn decreases exponentially in n if the original game has entangled value strictly less than 1. We also extend this result to any distribution, but with worst parameters. To prove this parallel repetition, we introduce the concept of Superposed Information Cost for entangled games which is inspired from the information cost used in communication complexity.

4:00 pm4:30 pm

We show a parallel repetition theorem for the entangled value of any two-player one-round game where the questions to Alice and Bob are drawn from a product distribution. Our proof is information theoretic and is broadly on similar lines as the proof of Raz and Holenstein for classical games. The additional quantum arguments we use, to deal with entangled games, are inspired by the work of Jain, Radhakrishnan, and Sen.

Friday, February 28th, 2014

9:00 am10:00 am

We provide a proof of existence of quantum weak coin flipping protocol with arbitrarily small bias. This proof is based on the work of Mochon, while some parts of it are simplified. Moreover, we provide an analysis of the number of qubits and rounds needed in the protocol as a function of the bias. This is joint work with D. Aharonov, A. Chailloux, M. Ganz and L. Magnin.

10:30 am11:00 am

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.

11:15 am11:45 am

We examine a cryptographic primitive known as (quantum) coin-flipping where two parties generate a random bit over a (quantum) communication channel. Using semidefinite programming, we formulate optimal cheating strategies and use duality theory to construct their point games. Using linear programming, we formulate optimal cheating strategies for the classical protocol counterpart. We also investigate their point games, discuss how they are connected to the quantum point games, and show that they are useful in the security analysis.

This is joint work with Ashwin Nayak and Levent Tunçel.

2:00 pm2:45 pm

BosonSampling, which Alex Arkhipov and I proposed several years ago, is a rudimentary, non-universal form of linear-optical quantum computing that nevertheless seems to be intractable to simulate using a classical computer. Unfortunately, verifying that a claimed BosonSampling device is working might itself be an intractable computational problem, and BosonSampling has come in for some criticism on that ground. In this talk, after introducing BosonSampling, I will explain recent polynomial-time classical protocols that distinguish a BosonSampling device from several important "null hypotheses." I will also discuss the possibility of an interactive protocol to verify post-classical computational power in a BosonSampling device.