⚛️ quantum physics

Approximating fixed size quantum correlations in polynomial time

This paper demonstrates that $\varepsilon$ -additive approximations of the optimal value for fixed-size two-player free games with fixed-dimensional entanglement can be computed in polynomial time using novel Bose-symmetric quantum de Finetti theorems, representation-theoretic symmetry reductions, and a measurement-based rounding scheme.

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

Published 2026-08-06

📖 8 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where two friends, Alice and Bob, are separated by vast distances and cannot talk to each other, yet they must coordinate their answers to a stranger's questions to win a prize. In the classical world, their best strategy is to agree on a plan beforehand, like a secret code. But in the quantum world, they can share a special "spooky" connection called entanglement, which allows them to coordinate in ways that seem impossible for normal objects. This setup is known as a "non-local game," and it's the playground for testing the very limits of reality. The big question scientists have been asking is: just how good can Alice and Bob get if they use these quantum tricks? For some games, we know the answer, but for many, calculating the absolute best winning chance is so incredibly hard that it might be impossible for any computer to solve in a reasonable amount of time. It's like trying to find the single best path through a maze that has more turns than there are atoms in the universe.

This is where a team of researchers steps in with a new, clever approach. They aren't trying to solve the impossible maze all at once; instead, they are building a series of "approximation ladders" that get closer and closer to the top. Their main discovery is that for games where the players have a fixed, limited amount of quantum power (a specific size of their entangled connection), they can calculate a very good estimate of the winning chance in a time that grows reasonably with how precise they want to be. They achieved this by inventing a new mathematical tool that treats the players' shared quantum state like a symphony of identical notes, allowing them to ignore the messy, repetitive parts of the calculation. This turns a problem that used to take an exponential amount of time (like waiting for the universe to end) into one that takes a polynomial amount of time (like counting to a large number). They didn't just find the answer; they also built a way to turn their mathematical estimate back into a real, working strategy that Alice and Bob could actually use, proving that their shortcut leads to a genuine solution.

The Quantum Game Show

Imagine a game show hosted by a referee who sends two players, Alice and Bob, into separate rooms. The referee picks a question for Alice and a different one for Bob, chosen at random. They can't talk to each other once the questions are asked, but they can whisper a plan before the doors close. Their goal? To give answers that match a secret rule. If they win, they get a point.

In the "classical" version of this game, Alice and Bob are limited to standard strategies, like flipping a coin or following a pre-written script. But in the "quantum" version, they are allowed to share a mysterious, linked resource called entanglement. Think of entanglement like a pair of magic dice. No matter how far apart they are, if Alice rolls a 6, Bob's die instantly shows a 6, even though neither of them decided what the result would be until they looked. This "spooky" connection allows them to coordinate their answers in ways that classical physics says shouldn't be possible, often letting them win the game more often than they could with just a script.

The big puzzle for scientists is: What is the absolute maximum probability they can win? For some simple games, we know the answer. But for more complex ones, finding this perfect number is a nightmare for computers. The problem is that the number of possible strategies grows so fast that even the fastest supercomputers would take longer than the age of the universe to check them all. It's like trying to find the single best move in a game of chess where the board keeps doubling in size every time you make a move.

The New Shortcut: Symmetry and "Bose" Magic

The researchers in this paper, Julius Zeiss and his team, didn't try to brute-force the problem. Instead, they realized that for games where the players have a fixed size of quantum help (meaning the "magic dice" have a specific, limited number of sides), there is a hidden pattern they could exploit.

They treated the problem like a massive, messy library. Usually, searching for a specific book in a library with billions of unorganized books takes forever. But what if you realized that 99% of the books were just copies of the same few titles, just with different covers? You wouldn't need to read every single copy; you could just read one representative of each type.

The team used a mathematical concept called Bose-symmetry. In the quantum world, particles can be "indistinguishable," meaning swapping two of them doesn't change the state of the system. The researchers realized that the best strategies for these games often have this same "indistinguishable" property. By focusing only on these symmetric strategies, they could shrink the problem down from a library of billions of books to a small, manageable shelf.

They developed a new method, which they call a Bose-symmetric hierarchy. Think of this as a series of increasingly accurate guesses.

The First Guess: They start with a rough approximation that is easy to calculate but might be a bit too high (an "outer bound").
The Refinement: They add more layers of symmetry constraints, making the guess tighter and closer to the true answer.
The Result: They proved that to get an answer that is off by only a tiny amount (let's call it $\epsilon$ ), they only need to go up a certain number of rungs on this ladder. Crucially, the time it takes to climb this ladder grows polynomially with $1/\epsilon$ .

What does "polynomial" mean here? It means if you want to be twice as precise, the computer doesn't need to work twice as hard; it might need to work four times as hard, or maybe eight times, but it doesn't need to work a million times harder. This is a massive improvement over previous methods, which grew exponentially (doubling the precision would require doubling the time, then doubling it again, and again, until the time became infinite).

From Math to Reality: The Rounding Trick

Finding a number is one thing; finding a real strategy to win the game is another. The researchers didn't stop at just calculating the winning probability. They also invented a "rounding scheme."

Imagine they calculated that the best possible score is 99.9%. But how do you actually play to get that score? Their method takes the mathematical solution from their simplified, symmetric world and "rounds" it back into a real, playable strategy. They do this by simulating a measurement process: they take the abstract, perfect solution and extract a specific set of instructions (measurements) that Alice and Bob can actually perform.

This is like having a perfect map of a treasure island drawn in a dream language. The researchers not only figured out where the treasure is (the winning probability) but also translated the map into a set of clear, step-by-step directions that a real explorer could follow. They showed that this translated strategy is guaranteed to be very close to the optimal one, providing a "feasible" way to win the game.

Why This Matters

This work is a big deal because it solves a long-standing problem in quantum information theory. For a long time, scientists knew that for games with fixed-size quantum resources, the answer should be computable, but they couldn't find a way to do it efficiently. Previous methods were stuck in "exponential time," making them useless for anything but the tiniest games.

By proving that these problems can be solved in polynomial time, the authors have opened the door to efficiently analyzing a wide class of quantum games. This isn't just about winning game shows; it helps us understand the fundamental boundaries between the classical and quantum worlds. It tells us exactly how much "quantum advantage" is possible in specific scenarios and gives us the tools to find the strategies that achieve it.

The paper also hints that these techniques could be useful for other tough problems in quantum physics, like checking if a quantum computer is working correctly (error correction) or figuring out if two quantum states are truly different. But for now, the main victory is clear: they turned an impossible calculation into a manageable one, using the power of symmetry to cut through the noise.

In short, the team showed that while the quantum world is complex and confusing, it has a hidden order. By listening to that order, we can predict the future of quantum games with surprising speed and accuracy.

Technical Summary: Approximating Fixed Size Quantum Correlations in Polynomial Time

Problem Statement
The paper addresses the computational complexity of approximating the optimal winning probability, $w_Q^{(T)}(V, \pi)$ , of two-player free non-local games where the players share quantum resources of a fixed local dimension $|T|$ . While determining the exact value of general quantum games is undecidable (RE-complete), and previous approximation methods for fixed-dimension games yielded only quasi-polynomial or exponential time guarantees with respect to the inverse error $\epsilon^{-1}$ , this work seeks to establish whether such approximations can be achieved in time polynomial in $1/\epsilon$ .

The core difficulty lies in the fact that optimizing over the set of separable states (which characterizes the game value via a reformulation involving quantum steering) is generally not semidefinite-representable due to bilinear constraints. Previous approaches, such as the Doherty–Parrilo–Spedalieri (DPS) hierarchy, provide converging outer approximations but suffer from exponential scaling in the hierarchy level $n$ required to achieve error $\epsilon$ , particularly when linear constraints (arising from the game structure) are present.

Methodology
The authors develop a framework that synthesizes quantum information theory (specifically quantum steering and de Finetti theorems) with representation theory (Schur-Weyl duality and symmetric subspace methods). The approach proceeds in three main stages:

Reformulation as Constrained Separability: The non-local game is reformulated as a constrained bipartite separability problem (cSEP). Using techniques from quantum steering, the optimization over strategies is mapped to a linear optimization over bipartite separable states subject to specific linear constraints (fixed-point and marginal constraints).
Bose-Symmetric Hierarchy: To approximate the constrained separability set, the authors introduce a novel hierarchy of outer bounds based on Bose-symmetric states. Unlike standard symmetric states (which are invariant under permutations but may have support outside the symmetric subspace), Bose-symmetric states are strictly supported on the symmetric subspace $\vee^n(\mathcal{H})$ . The authors prove a new constrained Bose-symmetric de Finetti representation theorem, which certifies that any state satisfying the constraints and Bose-symmetry is close (in trace distance) to a convex mixture of product states satisfying the same constraints. This provides a converging sequence of upper bounds.
Symmetry Reduction and Efficient Construction: A critical contribution is the demonstration that the semidefinite programs (SDPs) arising from this hierarchy can be constructed and solved in polynomial time.
- Bose-Symmetric Reduction: The authors show that the algebra of Bose-symmetric operators forms a single full matrix $*$ -algebra of polynomial dimension. By constructing an explicit unital $*$ -isomorphism to this algebra using a "type basis" (derived from semistandard Young tableaux of a single-row shape), they reduce the SDP size from exponential to polynomial in $n$ . Crucially, they prove that the transformation to this symmetry-adapted basis can be computed directly in polynomial time without ever constructing the exponentially large original matrices.
- Alternative Exchange-Symmetry Reduction: As a secondary method, they apply standard symmetry reduction techniques (decomposing the full tensor space into isotypic components indexed by partitions) to the exchange-symmetric hierarchy. While this involves multiple matrix blocks rather than a single one, it also yields a polynomial-time algorithm, particularly advantageous when local dimensions are large.

Key Contributions

Polynomial-Time Approximation: The primary result is an algorithm that approximates the value of fixed-size free non-local games with fixed-dimensional entanglement assistance up to an additive error $\epsilon$ in time $\text{poly}(1/\epsilon)$ . This contrasts with previous results that were exponential in $1/\epsilon$ .
Constrained Bose-Symmetric de Finetti Theorem: The paper derives a new de Finetti theorem tailored for constrained separability problems. This theorem extends previous work by accommodating linear constraints (such as those imposed by the game's rule function and no-signaling conditions) within the Bose-symmetric framework.
Measurement-Based Rounding (Inner Bounds): The authors introduce a rounding scheme that converts the outer SDP solutions into feasible inner strategies (specifically, shared entangled states with conditional measurements). This scheme provides rigorous lower bounds and converges to the optimal value, enabling a finite-level certificate of optimality (an $\epsilon$ -gap between upper and lower bounds).
Efficient SDP Construction: The work provides the first detailed complexity analysis showing that the transformation of symmetric SDPs into their symmetry-adapted forms can be performed in polynomial time, even in the presence of additional linear constraints.

Results

Complexity Bounds: For a game with $|A|$ answers, $|Q|$ questions, and quantum dimension $|T|$ , the authors construct an SDP with $\text{poly}(1/\epsilon)$ real degrees of freedom. Specifically, the number of variables scales as $O(\epsilon^{-4} \cdot \text{poly}(|A|, |Q|, |T|))$ .
Convergence Rates: The convergence of the Bose-symmetric hierarchy is certified by the new de Finetti theorem, with the error scaling as $O(|B|/\sqrt{n})$ , where $n$ is the hierarchy level. This allows setting $n = \text{poly}(1/\epsilon)$ to achieve the desired accuracy.
Inner/Outer Bounds: The combination of the Bose-symmetric outer hierarchy and the measurement-based rounding procedure yields a pair of converging sequences (upper and lower bounds) that bracket the true game value, providing a computable certificate of optimality.

Significance and Claims
The paper claims to resolve outstanding problems regarding the approximation of quantum correlations in fixed-size settings, as articulated in prior literature (e.g., [Jee+21], [Ber+21]). By leveraging Bose-symmetry and representation-theoretic reductions, the authors demonstrate that the computational cost of approximating these games is not inherently exponential in the inverse error, but rather polynomial.

The authors position their techniques as having independent interest for broader classes of constrained separability problems in quantum information theory, such as approximate quantum error correction. They explicitly state that while they developed these methods for game-theoretic instances, the underlying constrained Bose-symmetric hierarchy offers a potential alternative to standard symmetry reduction approaches in other domains. The work does not propose new experimental setups but rather provides a rigorous theoretical and algorithmic foundation for efficiently computing quantum game values.

The Quantum Game Show

The New Shortcut: Symmetry and "Bose" Magic

From Math to Reality: The Rounding Trick

Why This Matters

Technical Summary: Approximating Fixed Size Quantum Correlations in Polynomial Time

More like this