Tag - Quantum computation

There has been considerable interest in two person cooperative games and their classical and quantum-assisted values. Such a game is synchronous if the set of inputs is the same for both players and the rules include the rule that whenever both players receive the same question they must give the same response. A conditional probability density p(a,b|x,y) is called synchronous if whenever the inputs are equal the probability of giving different outputs is 0. The synchronous values of games are given by restricting allowed strategies to those that produce synchronous densities. In this talk we study synchronous values of various games and show why for some games this is more natural than the ordinary value.

Think of a communication scenario where one party, Alice, prepares D-dimensional states that another party, Bob, probes. In such a prepare-and-measure scenario, we prove that any set of pure states {ψ_i}_i=1^M and any set of extreme POVMs {Q_j}_j=1^N can be jointly and robustly self-tested. That is: there exists a linear function f, acting on the vector P of measurement probabilities, such that f(P) is close to its maximum value iff the underlying quantum states and measurements generating P are close in trace (resp., operator) norm to the reference states and POVMs, modulo a unitary or an anti-unitary transformation. The proof requires a generalization of Wigner’s theorem, a fundamental result in particle physics that characterizes the structure of physical symmetries. The robustness analysis combines ideas from quantum state discrimination and exactly soluble models.

We wish to understand when a tensor s can be transformed into a tensor t by application of linear maps to its tensor legs (we then say s restricts to t). In the language of restrictions, the rank of a tensor t is given by the minimal size of a diagonal tensor restricting to t. The study of rank and restrictions are motivated by algebraic complexity theory, where the rank corresponds to the computational complexity of a bilinear map (e.g. matrix multiplication) which then is viewed as a tensor with three legs.

Interestingly, some important open problems can be formulated in terms of asymptotic properties of restriction, among them the exponent of matrix multiplication. Following the seminal work of Volker Strassen, we will therefore study whether for large n the (n+o(n))th tensor power of s can be restricted to the n'th tensor power of t. The information-theoretic flavor of the problem is apparent and was heavily used by Strassen in conjunction with the discovery of algebraic structures (his spectral theorem).

Identifying k-leg-tensors with states of quantum systems of k particles allows us to bring tools and ideas from quantum information theory to the table, among them entanglement polytopes and quantum entropy. I will use these to construct a family of functionals - the quantum functionals - that can serve as obstructions to asymptotic restrictions. The functionals are the first of their kind applicable to all tensors, thereby solving a problem by Strassen from 1986.

The theory of non-local games, rooted in Bell’s seminal work on non-locality, is at the forefront of entanglement theory and has revealed profound connections with non-commutative analysis. Examples of quantum non-local games have been studied, wherein quantum states and/or measurements are used in place of classical questions and/or answers, but a general theory has only recently begun to emerge. This developing theory and its potential applications increase the necessity to avail of a systematic way of comparing essential attributes of distinct quantum games, in particular, their values, i.e., maximum success probabilities. In this work, we give operator space tensor norm expressions for the local, quantum, and quantum commuting values for general quantum non-local games.

In this talk we will introduce quantum XOR games as a non-commutative version of classical XOR games. We will explain some examples, which show that these games exhibit properties of entanglement that cannot be observed in the classical case. We will also explain the connection between quantum XOR games and the problem of distinguishability of quantum states, which motivates the study of these games when the players are allowed to interchange classical communication as part of their strategies.