Tag - Quantum computing

We consider a game-theoretical scenario involving two parties, say Alice and Bob. At each round, Alice chooses a quantum state from a given ensemble, known to both parties, and sends it to Bob. Bob is allowed to perform any quantum operation on the state and to query Alice multiple times, one state at a time, until he correctly guesses the state. The game is repeated many times, and Bob’s aim is to minimize the average number of queries needed. This problem, known as quantum guesswork, can be reframed as an instance of quantum hypothesis testing, and has therefore long been conjectured not to admit analytical solutions except for the cases in which the hypothesis testing problem is soluble, that is, for binary and symmetric ensembles. Here, we disprove such a belief by deriving conditions under which the guesswork problem can be recast as a combinatorial problem, that is, an optimization over a finite set, and therefore can be solved analytically by exhaustive search. We further show that such conditions are verified by any qubit ensemble, thus conclusively settling the problem in dimension two, and we show that in that case the guesswork is equivalent to an NP-hard combinatorial problem known as quadratic assignment problem (QAP). Leveraging on known results on the QAP, we introduce the (infinite) class of so-called benevolent qubit ensembles, that includes symmetric, informationally complete (SIC) and mutually unbiased basis (MUBs) ensembles, and we explicitly solve the corresponding QAP for such a class. For non-benevolent ensembles, we show that in the presence of symmetries the size of the exhaustive search can be reduced by a quadratic factor.

We discuss recent results in quantum data compressoin and optimal rate-distortion trade-off for mixed state ensembles, and present related open problems in analysis and optimization.

I'll report on some recent joint work with Sam Harris, Ivan Todorov, and Lyudmyla Turowska, where we introduce an analogue of bisynchronous correlations in the context of quantum input-quantum output non-local games. One of the main motivations for this work was to find a non-local game interpretation of the quantum automorphisms and isomorphisms of quantum graphs that have appeared recently in the literature. I'll explain how these considerations are related to tracial representations of quantum automorphism groups of matrix algebras, and in the case of ordinary graphs, lead us to consider a more general notion of quantum symmetry for graphs.

It's a natural question to ask when an element of *-algebra is positive on all *-representations. In the theory of nonlocal games, we'd like to be able to answer this question for *-polynomials in a product of free *-algebras, and similar algebras. Unfortunately it turns out that this problem is undecidable. I'll give an overview of this result, which is joint work with Arthur Mehta and Yuming Zhao, and look at other decision problems in operator algebras.

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.