GPU-accelerated semidefinite programming for causal games

This paper presents a GPU-accelerated semidefinite programming solver that enables the exploration of higher local dimensions in causal games, revealing that increasing the dimension beyond $d=5$ does not significantly improve the winning probability, thereby suggesting that current strategies are insufficient to close the gap with known upper bounds.

The Gist

The Big Picture: A Game Without a Timeline

Imagine two people, Alice and Bob, playing a guessing game. They are in separate rooms and cannot talk to each other.

• The Rules: Alice gets a secret number (0 or 1), and Bob gets a secret number (0 or 1). They must each guess the other person's number.
• The Goal: They win if Alice guesses Bob's number AND Bob guesses Alice's number.

In our normal, everyday world, time flows in one direction. Either Alice acts first, or Bob acts first, or they act at the same time. In this "fixed time" world, the best they can do is win 50% of the time. It's like flipping a coin; you can't do better than random guessing if you don't know the other person's input.

However, quantum physics allows for something weird: indefinite causal order. Imagine a scenario where it's not clear who went first. It's as if the "arrow of time" is in a superposition, pointing both ways at once. This is the realm of "process matrices."

The Mystery: Is There a Hidden Limit?

Scientists have found a quantum strategy (using a "process matrix") that lets Alice and Bob win this game about 62.2% of the time. This beats the 50% limit of normal time, proving that the "arrow of time" can indeed be fuzzy.

But there is a gap:

• Current Best Score: ~62.2% (achieved with a specific quantum setup).
• Theoretical Maximum: ~75.9% (a mathematical ceiling calculated by other researchers).

The big question was: Is the gap between 62.2% and 75.9% because we just haven't found a better strategy yet, or is there a hard wall preventing us from getting higher?

To find out, the researchers tried to build "bigger" quantum setups. In their game, the "size" of the setup is called the local dimension ($d$). Think of $d$ as the number of different "colors" or "types" of quantum cards they can use.

• Previous work used a deck of 5 colors ($d=5$).
• This paper asked: "What if we use a deck of 6, 7, or 8 colors? Will the score jump up?"

The Problem: The Math is Too Heavy

To test these bigger decks, they had to solve massive math puzzles called Semidefinite Programs (SDPs).

• The Analogy: Imagine trying to find the highest point on a mountain range that is constantly shifting shape. To do this, you have to check millions of spots.
• The Bottleneck: Every time the computer checks a spot, it has to perform a very heavy calculation (projecting a matrix onto a "positive-semidefinite cone"). It's like trying to sort a massive pile of sand into a perfect pyramid. Doing this on a standard computer (CPU) is incredibly slow. If they tried to check dimensions up to $d=8$ with standard tools, it would take forever.

The Solution: A GPU Supercharger

The authors built a custom tool to speed this up.

• The Tool: They took an existing math solver (called SCS) and modified it.
• The Upgrade: They moved the heavy "sand-sorting" calculation from the slow CPU to a GPU (Graphics Processing Unit). GPUs are like having a thousand tiny workers instead of one big worker.
• The Trick: They used a "mixed-precision" strategy. In the beginning, when they are just exploring, they used "rough" math (single precision) which is very fast. As they got close to the answer, they switched to "precise" math (double precision) to make sure the result was accurate.
• The Result: This made the calculation 6 times faster.

The Findings: The Mountain is Flat

Using their super-fast solver, they tested decks of size $d=2$ all the way up to $d=8$.

1. The Score Went Up (Slowly): As they increased the deck size, the winning probability did go up, but only by a tiny, tiny amount.
   • At $d=5$, the score was ~0.6218.
   • At $d=8$, the score was ~0.6219.
2. The Gap Remains: Even with the bigger decks, they barely improved the score. They are still stuck far below the theoretical ceiling of 75.9%.

The Conclusion

The paper concludes that simply making the quantum system "bigger" (increasing the dimension) is not enough to bridge the gap between the current best score and the theoretical limit.

What does this mean?
It suggests one of two things:

1. We need a completely new type of strategy (a qualitatively different approach) to get closer to the limit.
2. The theoretical limit (75.9%) might be wrong or too loose, and the real limit is actually much lower, closer to what we are already seeing.

The authors did not find a way to break the 62.2% barrier significantly, but they did prove that their new, faster computer code works, opening the door for others to try even bigger numbers in the future.

Technical Summary

Technical Summary: GPU-accelerated semidefinite programming for causal games

Problem Statement
The paper addresses the challenge of characterizing quantum correlations in scenarios lacking a fixed causal order, described by the process matrix formalism. A central open problem is determining the maximal violation of causal inequalities, specifically within the "Guess-Your-Neighbour's-Input" (GYNI) game. In this game, two parties attempt to guess each other's inputs. While correlations compatible with any definite or probabilistically mixed causal order are bounded by a winning probability of $1/2$, the best known process-matrix strategy achieves approximately $0.6218$ using local systems of dimension $d=5$. Conversely, the strongest known dimension-independent upper bound (a Tsirelson-type bound) is approximately $0.7592$. It remains unclear whether the gap between $0.6218$ and $0.7592$ reflects a fundamental limitation of process matrices or merely the constraints of current numerical optimization methods, which have historically been restricted to small local dimensions due to the rapid growth of the semidefinite program (SDP) variable size ($d^4$).

Methodology
To investigate whether increasing the local dimension beyond $d=5$ can narrow this gap, the authors employ a "see-saw" optimization scheme. This iterative algorithm alternates between optimizing local quantum instruments for a fixed process matrix and optimizing the process matrix for fixed instruments. Each step involves solving a large-scale SDP.

The core technical contribution lies in the development of a custom, GPU-accelerated implementation of the SCS (Splitting Conic Solver) algorithm, tailored to the structure of the process matrix formalism:

1. Sparse Parametrization: The authors utilize an orthonormal traceless basis (generalized Gell-Mann basis) adapted to the linear constraints of the process matrix subspace. This allows for a sparse representation where normalization and process constraints are incorporated directly into the variables, avoiding redundant affine constraints.
2. GPU Offloading: In standard SCS implementations (up to version 3.2.11), the computationally dominant step—the projection onto the positive-semidefinite (PSD) cone via eigendecomposition—is performed on the CPU. The authors offload this specific operation to a GPU using JAX.
3. Mixed-Precision Strategy: To maximize speed while maintaining accuracy, the implementation performs initial optimization iterations in single precision and switches to double precision only near convergence.
4. Complex Hermitian Handling: Unlike other GPU solvers that require embedding complex Hermitian constraints into real symmetric representations (doubling matrix dimensions), this implementation works directly with complex Hermitian variables, avoiding the associated computational overhead.

Key Results
Using the GPU-accelerated solver, the authors explored local dimensions up to $d=8$ on the MareNostrum5 supercomputer. The results, summarized in Table I of the paper, show:

• The winning probability increases with dimension, reaching $0.6219$ at $d=6$ and $d=7$.
• At $d=8$, the value is $0.62189$, which is marginally lower than at $d=6$ and $d=7$. The authors attribute this to the increased difficulty of exhaustively searching the optimization landscape at higher dimensions within the allocated computational time, rather than a true decrease in the optimal value.
• The improvement beyond $d=5$ is extremely marginal. The growth rate of the winning probability slows significantly, failing to approach the $0.7592$ upper bound.

Significance and Claims
The paper concludes that increasing the local dimension alone is likely insufficient to approach the known Tsirelson-type upper bound for the GYNI game. The authors suggest two possibilities:

1. Qualitatively different strategies (beyond simple dimension scaling) are required to approach the bound.
2. The current upper bound of $0.7592$ may not be tight.

The work demonstrates that GPU acceleration can significantly improve the scalability of process-matrix optimization (yielding up to a six-fold speedup), enabling the exploration of higher dimensions that were previously intractable. However, the modest gains observed suggest that the bottleneck may be theoretical rather than purely computational.

Future Directions Proposed
The authors identify several avenues for future work based on their findings:

• Improved Upper Bounds: Developing stronger relaxations for the set of process-matrix correlations, potentially using semidefinite block-moment matrix relaxations, to determine if the current bound is tight.
• Approximate Projections: Investigating approximate PSD cone projections (e.g., via matrix polynomials) to further reduce computational costs and enable optimization in even larger dimensions.
• Symmetry Exploitation: Utilizing the symmetries of the GYNI game to reduce the number of optimization variables or decompose PSD constraints.
• Extension to Multipartite Scenarios: Applying these GPU-accelerated techniques to multipartite settings and higher-order quantum operations, where the dimensionality of the problem grows exponentially.