Tag - Quantum computation

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.