Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2507.12302

Approximating fixed size quantum correlations in polynomial time

Julius A. Zeiss, Gereon Koßmann, Omar Fawzi, Mario Berta

Published Jul 16, 2025• 0 citations
arXivHTMLPDF

Abstract

We show that $\varepsilon$-additive approximations of the optimal value of fixed-size two-player free games with fixed-dimensional entanglement assistance can be computed in time $\mathrm{poly}(1/\varepsilon)$. This stands in contrast to previous analytic approaches, which focused on scaling with the number of questions and answers, but yielded only strict $\mathrm{exp}(1/\varepsilon)$ 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 $\mathrm{poly}(1/\varepsilon)$, thereby enabling efficient $\varepsilon$-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.

DOI
10.48550/arxiv.2507.12302

Related papers

Quasi-Polynomial Time Algorithms for Free Quantum Games in Bounded Dimension

Hyejung H. Jee, Carlo Sparaciari, Omar Fawzi +1 more

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.

arXiv:2005.08883•Leibniz international proceedings in informatics•May 18, 2020•4 citations

Fixed points in de Finetti hierarchies

Gereon Kossmann, Julius A. Zeiss

De Finetti theorems convert permutation symmetry into approximate mixtures of product states and thereby justify a wide range of reductions in classical and quantum statistics. In this work we study de Finetti hierarchies in which the feasible states are additionally constrained to be fixed points of quantum channels, a condition that subsumes invariance under arbitrary compact symmetry groups. Combining the mean-ergodic theorem with the structure theory of conditional expectations, we prove a tight bound on the entanglement-assisted classical capacity of the dual of a conditional expectation, block-wise distortion bounds for informationally complete measurements adapted to fixed point algebras, and an exact type-based refinement of the chain rule for permutation-invariant states. From these tools we derive several de Finetti theorems: a double-sided extension theorem with $O\left(\sqrt{\log n}/n\right)$ convergence, an interpolation theorem whose dimension dependence is governed solely by the block structure of the fixed point algebras and which recovers the dimension-independent classical behavior for maximal tori, and a Bose-symmetric variant. Exploiting Schur-Weyl duality and Gelfand-Tsetlin bases, we further show that the rounding scheme producing certifiably good separable inner approximations for (constrained) separability problems can be implemented in time polynomial in $1/ε$ for fixed local dimensions, complementing the known efficient outer hierarchies. Applications to bilinear optimization under symmetries and to approximate quantum error correction are discussed.

quant-pharXiv:2607.23689•Jul 28, 2026•0 citations

Quantum de finetti theorems under local measurements with applications

Fernando G. S. L. Brandão, Aram W. Harrow

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.

arXiv:1210.6367•ACM Symposium on Theory of Computing (STOC)•May 28, 2013•69 citations

Quantum Bilinear Optimization

Mario Berta, Omar Fawzi, Volkher B. Scholz

We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.

arXiv:1506.08810•SIAM Journal on Optimization•Jan 1, 2016•31 citations

Efficient Approximation of Quantum Channel Fidelity Exploiting Symmetry

Yeow Meng Chee, Hoang Ta, Van Khu Vu

Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of $ε$ in $\mathrm{poly}(1/ε, \text{input dimension})$ time.

arXiv:2308.15884•Aug 30, 2023•0 citations

Unique Games with Entangled Provers Are Easy

Julia Kempe, Oded Regev, Ben Toner

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are “unique” constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program (SDP). Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel “quantum rounding technique,” showing how to take a solution to an SDP and transform it into a strategy for entangled provers. Using our approximation by an SDP, we also show a parallel repetition theorem for unique entangled games.

SIAM Journal on Computing•Jan 1, 2010•73 citations
We show that ε\varepsilonε-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/ε)\mathrm{poly}(1/\varepsilon)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/ε)\mathrm{exp}(1/\varepsilon)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/ε)\mathrm{poly}(1/\varepsilon)poly(1/ε), thereby enabling efficient ε\varepsilonε-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.
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.
De Finetti theorems convert permutation symmetry into approximate mixtures of product states and thereby justify a wide range of reductions in classical and quantum statistics. In this work we study de Finetti hierarchies in which the feasible states are additionally constrained to be fixed points of quantum channels, a condition that subsumes invariance under arbitrary compact symmetry groups. Combining the mean-ergodic theorem with the structure theory of conditional expectations, we prove a tight bound on the entanglement-assisted classical capacity of the dual of a conditional expectation, block-wise distortion bounds for informationally complete measurements adapted to fixed point algebras, and an exact type-based refinement of the chain rule for permutation-invariant states. From these tools we derive several de Finetti theorems: a double-sided extension theorem with O(log⁡n/n)O\left(\sqrt{\log n}/n\right)O(logn​/n) convergence, an interpolation theorem whose dimension dependence is governed solely by the block structure of the fixed point algebras and which recovers the dimension-independent classical behavior for maximal tori, and a Bose-symmetric variant. Exploiting Schur-Weyl duality and Gelfand-Tsetlin bases, we further show that the rounding scheme producing certifiably good separable inner approximations for (constrained) separability problems can be implemented in time polynomial in 1/ε1/ε1/ε for fixed local dimensions, complementing the known efficient outer hierarchies. Applications to bilinear optimization under symmetries and to approximate quantum error correction are discussed.
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 nnn 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.
We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.
Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of εεε in poly(1/ε,input dimension)\mathrm{poly}(1/ε, \text{input dimension})poly(1/ε,input dimension) time.
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are “unique” constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program (SDP). Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel “quantum rounding technique,” showing how to take a solution to an SDP and transform it into a strategy for entangled provers. Using our approximation by an SDP, we also show a parallel repetition theorem for unique entangled games.