Quantum "cheat codes": Playing nonlocal graph coloring games on trapped-ion quantum computers

In the world of classical computing, some rules are absolute. If a map requires four colors to ensure no two adjacent regions share the same shade, a classical computer simply cannot do it with three. However, in the quantum realm, "cheating" in gamified versions of such tasks is not only possible; it rules out that nature can be described by local hidden-variable theories - deterministic models that Einstein, Podolsky, and Rosen suggested in a (failed) attempt to restore determinism and local realism to quantum mechanics, aiming to prove it was just an incomplete description of reality. 

The paper "Nonlocal games as cross-platform quantum benchmarks: Exceeding unconditional classical bounds on trapped-ion processors" (arXiv:2603.18323), by QLab researchers Anton Than, Norbert Linke, and their collaborators, showcases how quantum entanglement enables solutions of mathematical puzzles that are classically impossible and how nonlocal games allow for a holistic benchmarking of different quantum computing devices.

The Setup: What is a Nonlocal Game?

At its core, a nonlocal game is a coordination challenge. Imagine two players, Alice and Bob, who are separated in different rooms and forbidden from communicating. A referee sends each of them a question. To win, Alice and Bob must provide answers that satisfy a specific set of conditions (the game rules).

• Classical Strategy: Alice and Bob can agree on a plan before they are separated - a "local hidden variable" strategy. Such a strategy is formalized as a probability distribution for answers a and b by Alice and Bob, for questions x and y given to them by the referee. However, without real-time communication, their ability to coordinate their answers is strictly limited by classical probability.
• Quantum Strategy: For a quantum strategy, Alice and Bob share an entangled state. By performing local measurements on their respective qubits, they can achieve correlations that mimic communication, even though no information is actually traveling between them. Alice and Bob now give answers based on the results of local question-dependent quantum measurements.

Bell Inequalities: The Hidden Link

This experimental framework is deeply tied to Bell inequalities. In the 1960s, John Bell proved that there are limits to how correlated classical systems can be. Nonlocal games turn these abstract mathematical limits into a game score:

• Quantum resources may allow Alice and Bob to win more often than any classical strategy would admit, effectively demonstrating the violation of a Bell inequality.
• This violation proves that the system is using quantum entanglement rather than pre-arranged classical notes.

The Challenge: The Graph Coloring Game

Anton Than, Norbert Linke, and the team focused on a specific type of nonlocal graph coloring game. In this game, the referee sends Alice and Bob vertices from a specific graph. To win, they must follow two rules:

1. Consistency: If they are both asked about the same vertex, they must give the same color.
2. Adjacency: If they are asked about two vertices connected by an edge, they must give different colors.

For certain "hard" graphs, if you are only allowed a small number of colors, it is mathematically impossible for classical players to win 100% of the time. For example, a consistent (classical) colorings of a checker board requires two colors and a coloring of the US map requires four colors. For a specific, 14-vertex graph with classical chromatic number 5, the researchers demonstrated that by using an entangled state across a trapped-ion quantum processor, they could satisfy the coloring game rules using only 4 colors - essentially coloring the "uncolorable."

Why Trapped Ions?

The experiment was conducted on trapped-ion systems of the Duke Quanutm Center and IonQ, platforms known for their high gate fidelities and all-to-all connectivity. Unlike other quantum architectures where qubits can only talk to their immediate neighbors, ions in a trap can be directly entangled with any other ion in the chain. This flexibility is crucial for nonlocal games, which often require complex, multi-qubit entangling operations to reach the maximum quantum "win rate."

Significance of the Work

"This isn't just about winning a mathematical game," says Dr. Norbert Linke, Director of QLab. "These experiments verify the 'quantumness' of our hardware in a way that is independent of the device's internal workings. If the win rate exceeds the classical bound, we have definitive proof of high-quality entanglement, and it allows us to assess the performance of different quantum computing devices in a holistic way."