A Game You Cannot Win Unless You Have a Quantum Computer

Google Quantum AI demonstrates quantum contextuality on a superconducting processor, proving a game solvable only by quantum mechanics. Using the Willow chip, researchers achieved a 98.3% win rate versus the classical 88.9% limit, validating contextuality as a resource for scalable quantum advantage.

Audio reading is not available in this browser
A Game You Cannot Win Unless You Have a Quantum Computer

Tags

Quick summary

Google Quantum AI demonstrates quantum contextuality on a superconducting processor, proving a game solvable only by quantum mechanics. Using the Willow chip, researchers achieved a 98.3% win rate versus the classical 88.9% limit, validating contextuality as a resource for scalable quantum advantage.

A Game You Cannot Win Unless You Have a Quantum Computer

For decades, the strange rules of quantum mechanics have been described in terms of philosophical paradoxes. Einstein famously questioned whether physical properties exist when they are not being measured. Now, Google Research has transformed that abstract debate into a concrete, playable game. By leveraging a property known as quantum contextuality, researchers have demonstrated a scenario where classical logic fails completely, but a quantum computer succeeds.

The experiment, detailed in a blog post by Google Research, turns one of quantum mechanics' strangest features into something measurable and benchmarkable. The team utilized a superconducting processor to prove that certain tasks are fundamentally impossible for classical systems but achievable with quantum hardware.

The Magic Square Game

The foundation of this demonstration is a puzzle often referred to as the "magic square game." Imagine a 3x3 grid where every cell must be filled with either +1 or -1. The grid must adhere to two strict rules: every row must multiply to +1, and every column must multiply to -1.

At first glance, this seems like a simple arithmetic challenge. However, it is mathematically impossible to construct such a grid. For a row to multiply to +1, it must contain an even number of -1s. For a column to multiply to -1, it must contain an odd number. If you sum the requirements for all three rows, the total number of -1s in the grid must be even. If you sum the requirements for all three columns, the total must be odd. A number cannot be both even and odd simultaneously; the grid represents a logical contradiction.

Google researchers turned this paradox into a game involving two players, Alice and Bob. In each round, Alice is given a row index, and Bob is given a column index. They must fill their respective row and column without communicating. They win the round if the number they place in the intersecting cell is the same.

Any strategy based on a pre-written table is doomed to fail. Since no such table exists, the best classical strategy can win at most 8 out of 9 rounds (approximately 88.89%). This limitation holds true regardless of how clever the pre-arranged plan is.

Quantum Contextuality as a Resource

The game changes entirely when Alice and Bob use a quantum computer. Instead of looking up values in a hidden table, they share entangled Bell pairs. They measure these qubits based on their assigned row or column to generate their answers.

The reason for this success is a property called quantum contextuality. In classical physics, one might assume that measurement outcomes are predetermined, existing independently of how they are measured. Quantum contextuality challenges this. It asserts that the answer to a measurement can depend on the context—specifically, which other compatible measurements are performed alongside it.

In the game, Alice and Bob do not have fixed values waiting to be observed. Their answers come into being only when measured within their specific context. Through shared entanglement and a prearranged measurement plan, their answers for the shared cell align perfectly. In principle, this allows them to win every single round, a feat impossible for any classical system.

Google Quantum AI researchers, Shashwat Kumar and Rodrigo Cortiñas, demonstrated this on their Willow quantum processor. In their experiment, Alice and Bob each held two qubits, sharing two entangled Bell pairs. They ran the game 100,000 times for each of the nine possible versions.

The results were statistically significant. The best conceivable classical strategy wins at most 88.89% of the time. The quantum qubits, however, won 98.30% of the rounds (0.9830 ± 0.0001). They lost roughly one in sixty times. This gap confirms that the qubits coordinated better than any pre-written table allows, proving that contextuality is a real, usable resource.

Measuring the Machine: A New Ruler

Beyond winning games, measuring contextuality provides a unique way to benchmark quantum hardware. Researchers used a Bell–Kochen–Specker inequality to quantify the level of contextuality in the machine. This inequality bundles correlations into a single number, denoted as χ.

In any universe where measurement outcomes are predetermined, χ must be less than or equal to 4. Quantum mechanics, however, permits values up to 6. This test is state-independent, meaning it measures a property of the machine itself rather than a specific input state.

Google's team ran 540 measurements in a row, repeated 1,000 times, using an extra helper qubit to capture results without disturbing the main qubits. Their results placed χ comfortably past the classical bound of 4 and only 7% away from the quantum limit of 6. This number serves as an objective score: the distance between what the machine achieves and what nature permits.

This is particularly relevant for real-world applications like molecular simulations. Unlike classical benchmarks that might become easier to clear as hardware improves, this quantum ceiling remains fixed. As processors get better, this benchmark discriminates more precisely, catching subtle coherent errors that random-circuit tests might miss.

Scaling Up: The GHZ Parity Game

A critical question remains: does contextuality survive at scale? Quantum effects are fragile, and adding qubits introduces noise that could wash out these advantages. To test this, the team played the GHZ parity game.

In this multiplayer variant, N players share one entangled GHZ state. Each player receives a one-bit question and answers with one bit without communicating. They win if the parity of all answers matches a rule set by the questions. While random guessing wins 50% of the time, the best classical plan only reaches 75% for three players, shrinking toward 50% as more players are added. A shared GHZ state, however, wins every time.

Google researchers played with up to 71 players, one per qubit. Despite hardware noise causing the win rate to drop below 100% as qubits were added, the lead over the classical bound remained significant. They also verified genuine entanglement across 45 qubits, exceeding the full size of many earlier GHZ experiments.

Hidden Linear Functions and Constant Depth

The implications of contextuality extend beyond games to fundamental computational problems. In 2018, a landmark theorem proved that finding a hidden linear function can be solved by a constant-depth quantum circuit, whereas no classical circuit of constant depth can solve it. This quantum advantage traces directly back to contextuality.

Constant depth means the circuit does not get deeper as the problem grows; information travels only a short distance. Classical circuits are limited by this locality, while quantum circuits with pre-laid entanglement are not.

Google ran this algorithm at scale on real hardware, solving hidden linear function instances on grids of up to 105 qubits. Using the shallow-circuit recipe prescribed by theory, they achieved success probabilities above one-half. As the system size grew to the maximum processor size, noise degraded the probability of success from roughly 1 to 0.6. Despite this degradation, the performance stayed above the conjectured classical bound.

Conclusion

The work by Google Quantum AI demonstrates that contextuality is not just a theoretical curiosity but a tangible resource that powers quantum advantage. By turning the "magic square game" into a benchmark, the team has shown that quantum computers can outperform classical systems in tasks that are logically impossible for classical logic.

These experiments also reveal a new way to measure quantum hardware. By setting a ceiling defined by the laws of physics, contextuality provides a ruler that never moves, allowing scientists to track progress with unprecedented precision. As the team continues to scale these systems, the gap between classical and quantum capabilities promises to widen, driven by the very strangeness of the quantum world.

Source: https://research.google/blog/a-game-you-cannot-win-unless-you-have-a-quantum-computer

Sources