In a recent landmark result [Ji et al., arXiv:2001.04383 (2020)], it was shown that approximating the value of a two-player game is undecidable when the players are allowed to share quantum states of unbounded dimension. In this paper, we study the computational complexity of two-player games when the dimension of the quantum systems is bounded by T. More specifically, we give a semidefinite program of size exp(𝒪(T^{12}(log²(AT)+log(Q)log(AT))/ε²)) to compute additive ε-approximations on the value of two-player free games with T× T-dimensional quantum entanglement, where A and Q denote the number of answers and questions of the game, respectively. For fixed dimension T, this scales polynomially in Q and quasi-polynomially in A, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in Q and A. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints that we derive via quantum entropy inequalities.
In a recent landmark result [Ji et al., arXiv:2001.04383 (2020)], it was shown that approximating the value of a two-player game is undecidable when the players are allowed to share quantum states of unbounded dimension. In this paper, we study the computational complexity of two-player games when the dimension of the quantum systems is bounded by T. More specifically, we give a semidefinite program of size exp(𝒪(T^{12}(log²(AT)+log(Q)log(AT))/ε²)) to compute additive ε-approximations on the value of two-player free games with T× T-dimensional quantum entanglement, where A and Q denote the number of answers and questions of the game, respectively. For fixed dimension T, this scales polynomially in Q and quasi-polynomially in A, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in Q and A. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints that we derive via quantum entropy inequalities.
We show that ε-additive approximations of the optimal value of fixed-size two-player free games with fixed-dimensional entanglement assistance can be computed in time poly(1/ε). This stands in contrast to previous analytic approaches, which focused on scaling with the number of questions and answers, but yielded only strict exp(1/ε) guarantees. Our main result is based on novel Bose-symmetric quantum de Finetti theorems tailored for constrained quantum separability problems. These results give rise to semidefinite programming (SDP) outer hierarchies for approximating the entangled value of such games. By employing representation-theoretic symmetry reduction techniques, we demonstrate that these SDPs can be formulated and solved with computational complexity poly(1/ε), thereby enabling efficient ε-additive approximations. In addition, we introduce a measurement-based rounding scheme that translates the resulting outer bounds into certifiably good inner sequences of entangled strategies. These strategies can, for instance, serve as warm starts for see-saw optimization methods. We believe that our techniques are of independent interest for broader classes of constrained separability problems in quantum information theory.
Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - ε) qubits would imply a exp (n1 - 2ε polylog(n))-time algorithm for 3-SAT. We show that the maximum winning probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log|Q| + log2|A|/ε2) ), with |Q| and |A| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a O(k-1/2) advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables n by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.
The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC’14). In the quantum world, there are two complexity classes that can be considered quantum analogues of classical free games: (1) AM*, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. (1) We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker (2010) and also shows, conditional on ETH, that the algorithm of Brandão, Christandl and Yard (STOC’11) for optimizing over separable states is tight up to logarithmic factors. (2) We show that AM* with nprovers = 2, question length O(1), and answer-length log(n) is equal to RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. (In contrast, Aaronson, Impagliazzo and Moshkovitz show that classical free games are much weaker than general classical games.) We show this using a question “hyper-compression” theorem that iteratively applies the introspection technique of Ji et al. (2020). Our result is a significant improvement over the headline result of Ji et al., whose MIP* protocol for the halting problem has (n)-sized questions and answers. (3) By the same techniques, we obtain a zero-gap AM* protocol for a Π2 complete language with constant-size questions and almost logarithmically (O(logn · log* n)) large answers, improving on the headline result of Mousavi, Nezhadi and Yuen (STOC’22). (4) Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires Ω(logn) bits of communication. It follows that our results in item 3 are optimal up to an O(log* n) factor, and that the gapless compression theorems of Mousavi, Nezhadi and Yuen are asymptotically optimal. We conjecture that these bounds can be saturated in the gapped case as well.
We present a quasipolynomial-time algorithm for solving the weak membership problem for the convex set of separable, i.e. non-entangled, bipartite density matrices. The algorithm decides whether a density matrix is separable or whether it is eps-away from the set of the separable states in time exp(O(eps^-2 log |A| log |B|)), where |A| and |B| are the local dimensions, and the distance is measured with either the Euclidean norm, or with the so-called LOCC norm. The latter is an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by quantum local operations and classical communication (LOCC) between the parties. We also obtain improved algorithms for optimizing over the set of separable states and for computing the ground-state energy of mean-field Hamiltonians. The techniques we develop are also applied to quantum Merlin-Arthur games, where we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC protocols, or when the verification procedure is formed by a measurement of small Euclidean norm. This answers a question posed by Aaronson et al (Theory of Computing 5, 1, 2009) and provides two new characterizations of the complexity class QMA, a quantum analog of NP. Our algorithm uses semidefinite programming to search for a symmetric extension, as first proposed by Doherty, Parrilo and Spedialieri (Phys. Rev. A, 69, 022308, 2004). The bound on the runtime follows from an improved de Finetti-type bound quantifying the monogamy of quantum entanglement, proved in (arXiv:1010.1750). This result, in turn, follows from a new lower bound on the quantum conditional mutual information and the entanglement measure squashed entanglement.
We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qubit answers can be implemented exactly by players who share an entangled state of no more than 5n qubits--a bound which is optimal to within a factor of 5/2. Previously, no upper bound at all was known on the amount of entanglement required even to approximate such a strategy. It follows that the problem of computing the value of these games is in NP, whereas previously this problem was not known to be computable.
Entangled games are a quantum analog of constraint satisfaction problems and have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by a quantum strategy. We study the complexity of computing the (commuting-operator) entangled value omega^* of entangled XOR games with any number of players. Based on a duality theory for systems of operator equations, we introduce necessary and sufficient criteria for an XOR game to have omega^* = 1, and use these criteria to derive the following results: 1) An algorithm for symmetric games that decides in polynomial time whether omega^* = 1 or omega^* < 1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 2) A family of games with three players and with omega^* < 1, where it takes doubly exponential time for the ncSoS algorithm to witness this. By contrast, our algorithm runs in polynomial time. 3) Existence of an unsatisfiable phase for random (non-symmetric) XOR games. We show that there exists a constant C_k^{unsat} depending only on the number k of players, such that a random k-XOR game over an alphabet of size n has omega^* < 1 with high probability when the number of clauses is above C_k^{unsat} n. 4) A lower bound of Omega(n log(n)/log log(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the (3n)^{th} level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.